Al Sweigart - Cracking Codes with Python

An Introduction to Building and Breaking Ciphers

by Al Sweigart

San Francisco

CRACKING CODES WITH PYTHON. Copyright 2018 by Al Sweigart.

Some rights reserved. This work is licensed under the Creative Commons Attribution-NonCommercial-ShareAlike 3.0 United States License. To view a copy of this license, visit http://creativecommons.org/licenses/by-nc-sa/3.0/us/ or send a letter to Creative Commons, PO Box 1866, Mountain View, CA 94042, USA.

ISBN-10: 1-59327-822-5
ISBN-13: 978-1-59327-822-9

Publisher: William Pollock
Production Editor: Riley Hoffman
Cover Illustration: Josh Ellingson
Interior Design: Octopod Studios
Developmental Editors: Jan Cash and Annie Choi
Technical Reviewers: Ari Lacenski and Jean-Philippe Aumasson
Copyeditor: Anne Marie Walker
Compositors: Riley Hoffman and Meg Sneeringer
Proofreader: Paula L. Fleming

For information on distribution, translations, or bulk sales,
please contact No Starch Press, Inc. directly:

No Starch Press, Inc.
245 8th Street, San Francisco, CA 94103
phone: 1.415.863.9900;
www.nostarch.com

Library of Congress Cataloging-in-Publication Data

Names: Sweigart, Al, author.
Title: Cracking codes with Python : an introduction to building and breaking
ciphers / Al Sweigart.
Description: San Francisco : No Starch Press,Inc., [2018]
Identifiers: LCCN 2017035704 (print) | LCCN 2017047589 (ebook) | ISBN
9781593278694 (epub) | ISBN 1593278691 (epub) | ISBN 9781593278229 (pbk.)
| ISBN 1593278225 (pbk.)
Subjects: LCSH: Data encryption (Computer science) | Python (Computer program
language) | Computer security. | Hacking.
Classification: LCC QA76.9.A25 (ebook) | LCC QA76.9.A25 S9317 2018 (print) |
DDC 005.8/7--dc23
LC record available at https://lccn.loc.gov/2017035704

No Starch Press and the No Starch Press logo are registered trademarks of No Starch Press, Inc. Other product and company names mentioned herein may be the trademarks of their respective owners. Rather than use a trademark symbol with every occurrence of a trademarked name, we are using the names only in an editorial fashion and to the benefit of the trademark owner, with no intention of infringement of the trademark.

The information in this book is distributed on an As Is basis, without warranty. While every precaution has been taken in the preparation of this work, neither the author nor No Starch Press, Inc. shall have any liability to any person or entity with respect to any loss or damage caused or alleged to be caused directly or indirectly by the information contained in it.

Dedicated to Aaron Swartz, 19862013

Aaron was part of an army of citizens that believes democracy only works when the citizenry are informed, when we know about our rightsand our obligations. An army that believes we must make justice and knowledge available to allnot just the well born or those that have grabbed the reins of powerso that we may govern ourselves more wisely. When I see our army, I see Aaron Swartz and my heart is broken. We have truly lost one of our better angels.
Carl Malamud

About the Author

Al Sweigart is a software developer and tech book author living in San Francisco. Python is his favorite programming language, and he is the developer of several open source modules for it. His other books are freely available under a Creative Commons license on his website https://inventwithpython.com/. His cat weighs 12 pounds.

About the Technical Reviewers

Ari Lacenski creates mobile apps and Python software. She lives in Seattle.

Jean-Philippe Aumasson () is Principal Research Engineer at Kudelski Security, Switzerland. He speaks regularly at information security conferences such as Black Hat, DEF CON, Troopers, and Infiltrate. He is the author of Serious Cryptography (No Starch Press, 2017).

BRIEF CONTENTS

CONTENTS IN DETAIL

1
MAKING PAPER CRYPTOGRAPHY TOOLS

2
PROGRAMMING IN THE INTERACTIVE SHELL

3
STRINGS AND WRITING PROGRAMS

4
THE REVERSE CIPHER

5
THE CAESAR CIPHER

6
HACKING THE CAESAR CIPHER WITH BRUTE-FORCE

7
ENCRYPTING WITH THE TRANSPOSITION CIPHER

8
DECRYPTING WITH THE TRANSPOSITION CIPHER

9
PROGRAMMING A PROGRAM TO TEST YOUR PROGRAM

10
ENCRYPTING AND DECRYPTING FILES

11
DETECTING ENGLISH PROGRAMMATICALLY

12
HACKING THE TRANSPOSITION CIPHER

13
A MODULAR ARITHMETIC MODULE FOR THE AFFINE CIPHER

14
PROGRAMMING THE AFFINE CIPHER

15
HACKING THE AFFINE CIPHER

16
PROGRAMMING THE SIMPLE SUBSTITUTION CIPHER

17
HACKING THE SIMPLE SUBSTITUTION CIPHER

18
PROGRAMMING THE VIGENRE CIPHER

19
FREQUENCY ANALYSIS

20
HACKING THE VIGENRE CIPHER

21
THE ONE-TIME PAD CIPHER

22
FINDING AND GENERATING PRIME NUMBERS

23
GENERATING KEYS FOR THE PUBLIC KEY CIPHER

24
PROGRAMMING THE PUBLIC KEY CIPHER

APPENDIX
DEBUGGING PYTHON CODE

ACKNOWLEDGMENTS

This book would not have been possible without the exceptional work of the No Starch Press team. Thanks to my publisher, Bill Pollock; thanks to my editors, Riley Hoffman, Jan Cash, Annie Choi, Anne Marie Walker, and Laurel Chun, for their incredible help throughout the process; thanks to my technical editor, Ari Lacenski, for her help in this edition and back when it was just a stack of printouts I showed her at Shotwells; thanks to JP Aumasson for lending his expertise in the public key chapters; and thanks to Josh Ellingson for a great cover.

INTRODUCTION

I couldnt help but overhear, probably because I was eavesdropping.
Anonymous

If you could travel back to the early 1990s with this book, the contents of that implement part of the RSA cipher would be illegal to export out of the United States. Because messages encrypted with RSA are impossible to hack, the export of encryption software like RSA was deemed a matter of national security and required State Department approval. In fact, strong cryptography was regulated at the same level as tanks, missiles, and flamethrowers.

In 1990, Daniel J. Bernstein, a student at the University of California, Berkeley, wanted to publish an academic paper that featured source code of his Snuffle encryption system. The US government informed him that he would need to become a licensed arms dealer before he could post his source code on the internet. The government also told him that it would deny him an export license if he applied for one because his technology was too secure.