Cracking Codes with Python An Introduction to Building and Breaking Ciphers (Al Sweigart) (Z-Library)

Page 1

C R A C K I N G C O D E S W I T H P Y T H O N A N I N T R O D U C T I O N T O B U I L D I N G A N D B R E A K I N G C I P H E R S A L S W E I G A R T S E C R E T C I P H E R S B Y H A C K I N G L E A R N P Y T H O N Learn how to program in Python while making and breaking ciphers—algorithms used to create and send secret messages! After a crash course in Python programming basics, you’ll learn to make, test, and hack programs that encrypt text with classical ciphers like the transposition cipher and Vigenère cipher. You’ll begin with simple programs for the reverse and Caesar ciphers and then work your way up to public key cryptography, the type of encryption used to secure today’s online transactions, including digital signatures, email, and Bitcoin. Each program includes the full code and a line-by-line explanation of how things work. By the end of the book, you’ll have learned how to code in Python and you’ll have the clever programs to prove it! You’ll also learn how to: • Combine loops, variables, and flow control statements into real working programs • Use dictionary files to instantly detect whether decrypted messages are valid English or gibberish • Create test programs to make sure that your code encrypts and decrypts correctly • Code (and hack!) a working example of the affine cipher, which uses modular arithmetic to encrypt a message • Break ciphers with techniques such as brute-force and frequency analysis There’s no better way to learn to code than to play with real programs. Cracking Codes with Python makes the learning fun! A B O U T T H E A U T H O R Al Sweigart is a professional software developer who teaches programming to kids and adults. He is the author of Automate the Boring Stuff with Python, Invent Your Own Computer Games with Python, and Scratch Programming Playground, also from No Starch Press. His programming tutorials can be found at inventwithpython.com. www.nostarch.com TH E F I N EST I N G E E K E NTE RTA I N M E NT ™ “ I L I E F LAT .” Th is book uses a durab le b ind ing that won’t snap shut. FSC FPO SHELVE IN: PROGRAM M ING LANGUAGES/PYTHON $29.95 ($39.95 CDN) COVERS PYTHON 3 C R A C K IN G C O D E S W IT H P Y T H O N C R A C K IN G C O D E S W IT H P Y T H O N S W E IG A R T

Page 2

CraCking Codes with Python

Page 3

(This page has no text content)

Page 4

C r a C k i n g C o d e s w i t h P y t h o n a n i n t r o d u c t i o n t o B u i l d i n g a n d B r e a k i n g C i p h e r s by Al Sweigart San Francisco

Page 5

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; info@nostarch.com 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.

Page 6

Dedicated to Aaron Swartz, 1986–2013 “Aaron was part of an army of citizens that believes democracy only works when the citizenry are informed, when we know about our rights—and our obligations. An army that believes we must make justice and knowledge available to all—not just the well born or those that have grabbed the reins of power—so 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

Page 7

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 (Chapters 22–24) 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).

Page 8

B r i e f C o n t e n t s Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xix Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxi Chapter 1: Making Paper Cryptography Tools . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 Chapter 2: Programming in the Interactive Shell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 Chapter 3: Strings and Writing Programs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 Chapter 4: The Reverse Cipher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 Chapter 5: The Caesar Cipher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 Chapter 6: Hacking the Caesar Cipher with Brute-Force . . . . . . . . . . . . . . . . . . . . . . . . . . 69 Chapter 7: Encrypting with the Transposition Cipher . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 Chapter 8: Decrypting with the Transposition Cipher . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 Chapter 9: Programming a Program to Test Your Program . . . . . . . . . . . . . . . . . . . . . . . 113 Chapter 10: Encrypting and Decrypting Files . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 Chapter 11: Detecting English Programmatically . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141 Chapter 12: Hacking the Transposition Cipher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161 Chapter 13: A Modular Arithmetic Module for the Affine Cipher . . . . . . . . . . . . . . . . . . . 171 Chapter 14: Programming the Affine Cipher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185 Chapter 15: Hacking the Affine Cipher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197 Chapter 16: Programming the Simple Substitution Cipher . . . . . . . . . . . . . . . . . . . . . . . . 207 Chapter 17: Hacking the Simple Substitution Cipher . . . . . . . . . . . . . . . . . . . . . . . . . . . 221 Chapter 18: Programming the Vigenère Cipher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247 Chapter 19: Frequency Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 259 Chapter 20: Hacking the Vigenère Cipher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 279

Page 9

viii Brief Contents Chapter 21: The One-Time Pad Cipher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315 Chapter 22: Finding and Generating Prime Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . 321 Chapter 23: Generating Keys for the Public Key Cipher . . . . . . . . . . . . . . . . . . . . . . . . . 335 Chapter 24: Programming the Public Key Cipher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 349 Appendix: Debugging Python Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 375 Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 381

Page 10

C o n t e n t s i n d e t a i l aCknowledgments xix introduCtion xxi Who Should Read This Book? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxii What’s in This Book? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .xxiii How to Use This Book . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .xxiv Typing Source Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .xxiv Checking for Typos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxv Coding Conventions in This Book . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxv Online Resources . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxv Downloading and Installing Python . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxv Windows Instructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .xxvi macOS Instructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .xxvi Ubuntu Instructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .xxvi Downloading pyperclip .py . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .xxvi Starting IDLE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxvii Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxviii 1 making PaPer CryPtograPhy tools 1 What Is Cryptography? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Codes vs . Ciphers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 The Caesar Cipher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 The Cipher Wheel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Encrypting with the Cipher Wheel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 Decrypting with the Cipher Wheel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 Encrypting and Decrypting with Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 Why Double Encryption Doesn’t Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 Practice Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2 Programming in the interaCtive shell 11 Some Simple Math Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 Integers and Floating-Point Values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 Order of Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 Evaluating Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 Storing Values with Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 Overwriting Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 Variable Names . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 Practice Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

Page 11

x Contents in Detail 3 strings and writing Programs 21 Working with Text Using String Values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 String Concatenation with the + Operator . . . . . . . . . . . . . . . . . . . . . . . . . . 23 String Replication with the * Operator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 Getting Characters from Strings Using Indexes . . . . . . . . . . . . . . . . . . . . . . . 24 Printing Values with the print() Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 Printing Escape Characters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 Quotes and Double Quotes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 Writing Programs in IDLE’s File Editor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 Source Code for the “Hello, World!” Program . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 Checking Your Source Code with the Online Diff Tool . . . . . . . . . . . . . . . . . . . . . . . . 31 Using IDLE to Access Your Program Later . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 Saving Your Program . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 Running Your Program . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 Opening the Programs You’ve Saved . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 How the “Hello, World!” Program Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 Comments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 Printing Directions to the User . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 Taking a User’s Input . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 Ending the Program . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 Practice Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 4 the reverse CiPher 39 Source Code for the Reverse Cipher Program . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 Sample Run of the Reverse Cipher Program . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 Setting Up Comments and Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 Finding the Length of a String . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 Introducing the while Loop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 The Boolean Data Type . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 Comparison Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 Blocks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 The while Loop Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 “Growing” a String . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 Improving the Program with an input() Prompt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 Practice Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 5 the Caesar CiPher 53 Source Code for the Caesar Cipher Program . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 Sample Run of the Caesar Cipher Program . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 Importing Modules and Setting Up Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 Constants and Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 The for Loop Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 An Example for Loop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 A while Loop Equivalent of a for Loop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

Page 12

Contents in Detail xi The if Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 An Example if Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 The else Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 The elif Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 The in and not in Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 The find() String Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 Encrypting and Decrypting Symbols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 Handling Wraparound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 Handling Symbols Outside of the Symbol Set . . . . . . . . . . . . . . . . . . . . . . . . 65 Displaying and Copying the Translated String . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 Encrypting Other Symbols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 Practice Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 6 haCking the Caesar CiPher with Brute-ForCe 69 Source Code for the Caesar Cipher Hacker Program . . . . . . . . . . . . . . . . . . . . . . . . . 70 Sample Run of the Caesar Cipher Hacker Program . . . . . . . . . . . . . . . . . . . . . . . . . . 71 Setting Up Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 Looping with the range() Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 Decrypting the Message . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 Using String Formatting to Display the Key and Decrypted Messages . . . . . . . . . . . . . . 75 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 Practice Question . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 7 enCryPting with the transPosition CiPher 77 How the Transposition Cipher Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 Encrypting a Message by Hand . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 Creating the Encryption Program . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 Source Code for the Transposition Cipher Encryption Program . . . . . . . . . . . . . . . . . . . 81 Sample Run of the Transposition Cipher Encryption Program . . . . . . . . . . . . . . . . . . . . 82 Creating Your Own Functions with def Statements . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 Defining a Function that Takes Arguments with Parameters . . . . . . . . . . . . . . . 83 Changes to Parameters Exist Only Inside the Function . . . . . . . . . . . . . . . . . . 84 Defining the main() Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 Passing the Key and Message As Arguments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 The List Data Type . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 Reassigning the Items in Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 Lists of Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 Using len() and the in Operator with Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 List Concatenation and Replication with the + and * Operators . . . . . . . . . . . 89 The Transposition Encryption Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 Augmented Assignment Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 Moving currentIndex Through the Message . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 The join() String Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 Return Values and return Statements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 A return Statement Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 Returning the Encrypted Ciphertext . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 The __name__ Variable . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 Practice Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97

Page 13

xii Contents in Detail 8 deCryPting with the transPosition CiPher 99 How to Decrypt with the Transposition Cipher on Paper . . . . . . . . . . . . . . . . . . . . . . 100 Source Code for the Transposition Cipher Decryption Program . . . . . . . . . . . . . . . . . 101 Sample Run of the Transposition Cipher Decryption Program . . . . . . . . . . . . . . . . . . . 102 Importing Modules and Setting Up the main() Function . . . . . . . . . . . . . . . . . . . . . . . 102 Decrypting the Message with the Key . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 The round(), math .ceil(), and math .floor() Functions . . . . . . . . . . . . . . . . . . . 103 The decryptMessage() Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 Boolean Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 Adjusting the column and row Variables . . . . . . . . . . . . . . . . . . . . . . . . . . 109 Calling the main() Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 Practice Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 9 Programming a Program to test your Program 113 Source Code for the Transposition Cipher Tester Program . . . . . . . . . . . . . . . . . . . . . 114 Sample Run of the Transposition Cipher Tester Program . . . . . . . . . . . . . . . . . . . . . . 115 Importing the Modules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 Creating Pseudorandom Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 Creating a Random String . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 Duplicating a String a Random Number of Times . . . . . . . . . . . . . . . . . . . . 118 List Variables Use References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 Passing References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 Using copy .deepcopy() to Duplicate a List . . . . . . . . . . . . . . . . . . . . . . . . . 122 The random .shuffle() Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 Randomly Scrambling a String . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 Testing Each Message . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 Checking Whether the Cipher Worked and Ending the Program . . . . . . . . . . . . . . . . 124 Calling the main() Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 Testing the Test Program . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 Practice Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126 10 enCryPting and deCryPting Files 127 Plain Text Files . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128 Source Code for the Transposition File Cipher Program . . . . . . . . . . . . . . . . . . . . . . 128 Sample Run of the Transposition File Cipher Program . . . . . . . . . . . . . . . . . . . . . . . . 130 Working with Files . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 Opening Files . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 Writing to and Closing Files . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 Reading from a File . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132 Setting Up the main() Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132 Checking Whether a File Exists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 The os .path .exists() Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 Checking Whether the Input File Exists with the os .path .exists() Function . . . . 134 Using String Methods to Make User Input More Flexible . . . . . . . . . . . . . . . . . . . . . . 134 The upper(), lower(), and title() String Methods . . . . . . . . . . . . . . . . . . . . . . 134 The startswith() and endswith() String Methods . . . . . . . . . . . . . . . . . . . . . . 135 Using These String Methods in the Program . . . . . . . . . . . . . . . . . . . . . . . . 135

Page 14

Contents in Detail xiii Reading the Input File . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136 Measuring the Time It Took to Encrypt or Decrypt . . . . . . . . . . . . . . . . . . . . . . . . . . . 136 The time Module and time .time() Function . . . . . . . . . . . . . . . . . . . . . . . . . . 136 Using the time .time() Function in the Program . . . . . . . . . . . . . . . . . . . . . . . 137 Writing the Output File . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 Calling the main() Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 Practice Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139 11 deteCting english ProgrammatiCally 141 How Can a Computer Understand English? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142 Source Code for the Detect English Module . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 Sample Run of the Detect English Module . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 Instructions and Setting Up Constants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 The Dictionary Data Type . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146 The Difference Between Dictionaries and Lists . . . . . . . . . . . . . . . . . . . . . . . 147 Adding or Changing Items in a Dictionary . . . . . . . . . . . . . . . . . . . . . . . . . 147 Using the len() Function with Dictionaries . . . . . . . . . . . . . . . . . . . . . . . . . . 148 Using the in Operator with Dictionaries . . . . . . . . . . . . . . . . . . . . . . . . . . . 148 Finding Items Is Faster with Dictionaries than with Lists . . . . . . . . . . . . . . . . . 149 Using for Loops with Dictionaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149 Implementing the Dictionary File . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150 The split() Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150 Splitting the Dictionary File into Individual Words . . . . . . . . . . . . . . . . . . . . 151 Returning the Dictionary Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151 Counting the Number of English Words in message . . . . . . . . . . . . . . . . . . . . . . . . . 152 Divide-by-Zero Errors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152 Counting the English Word Matches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153 The float(), int(), and str() Functions and Integer Division . . . . . . . . . . . . . . . . 154 Finding the Ratio of English Words in the Message . . . . . . . . . . . . . . . . . . . 154 Removing Non-Letter Characters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155 The append() List Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155 Creating a String of Letters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156 Detecting English Words . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156 Using Default Arguments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157 Calculating Percentages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 Practice Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160 12 haCking the transPosition CiPher 161 Source Code of the Transposition Cipher Hacker Program . . . . . . . . . . . . . . . . . . . . 162 Sample Run of the Transposition Cipher Hacker Program . . . . . . . . . . . . . . . . . . . . . 163 Importing the Modules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164 Multiline Strings with Triple Quotes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164 Displaying the Results of Hacking the Message . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165 Getting the Hacked Message . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166 The strip() String Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167 Applying the strip() String Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168 Failing to Hack the Message . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168

Page 15

xiv Contents in Detail Calling the main() Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169 Practice Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169 13 a modular arithmetiC module For the aFFine CiPher 171 Modular Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172 The Modulo Operator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173 Finding Factors to Calculate the Greatest Common Divisor . . . . . . . . . . . . . . . . . . . . 173 Multiple Assignment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175 Euclid’s Algorithm for Finding the GCD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176 Understanding How the Multiplicative and Affine Ciphers Work . . . . . . . . . . . . . . . . 177 Choosing Valid Multiplicative Keys . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178 Encrypting with the Affine Cipher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179 Decrypting with the Affine Cipher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179 Finding Modular Inverses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181 The Integer Division Operator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181 Source Code for the Cryptomath Module . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183 Practice Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183 14 Programming the aFFine CiPher 185 Source Code for the Affine Cipher Program . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186 Sample Run of the Affine Cipher Program . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188 Setting Up Modules, Constants, and the main() Function . . . . . . . . . . . . . . . . . . . . . . 188 Calculating and Validating the Keys . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189 The Tuple Data Type . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190 Checking for Weak Keys . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190 How Many Keys Can the Affine Cipher Have? . . . . . . . . . . . . . . . . . . . . . . 191 Writing the Encryption Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193 Writing the Decryption Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194 Generating Random Keys . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195 Calling the main() Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196 Practice Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196 15 haCking the aFFine CiPher 197 Source Code for the Affine Cipher Hacker Program . . . . . . . . . . . . . . . . . . . . . . . . . 198 Sample Run of the Affine Cipher Hacker Program . . . . . . . . . . . . . . . . . . . . . . . . . . 199 Setting Up Modules, Constants, and the main() Function . . . . . . . . . . . . . . . . . . . . . . 200 The Affine Cipher Hacking Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201 The Exponent Operator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201 Calculating the Total Number of Possible Keys . . . . . . . . . . . . . . . . . . . . . . 201 The continue Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202 Using continue to Skip Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203 Calling the main() Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205 Practice Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205

Page 16

Contents in Detail xv 16 Programming the simPle suBstitution CiPher 207 How the Simple Substitution Cipher Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208 Source Code for the Simple Substitution Cipher Program . . . . . . . . . . . . . . . . . . . . . 209 Sample Run of the Simple Substitution Cipher Program . . . . . . . . . . . . . . . . . . . . . . . 210 Setting Up Modules, Constants, and the main() Function . . . . . . . . . . . . . . . . . . . . . . 211 The sort() List Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212 Wrapper Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213 The translateMessage() Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215 The isupper() and islower() String Methods . . . . . . . . . . . . . . . . . . . . . . . . . 216 Preserving Cases with isupper() . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217 Generating a Random Key . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218 Calling the main() Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219 Practice Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219 17 haCking the simPle suBstitution CiPher 221 Using Word Patterns to Decrypt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222 Finding Word Patterns . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222 Finding Potential Decryption Letters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223 Overview of the Hacking Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225 The Word Pattern Modules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225 Source Code for the Simple Substitution Hacking Program . . . . . . . . . . . . . . . . . . . . 226 Sample Run of the Simple Substitution Hacking Program . . . . . . . . . . . . . . . . . . . . . . 229 Setting Up Modules and Constants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230 Finding Characters with Regular Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230 Setting Up the main() Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231 Displaying Hacking Results to the User . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232 Creating a Cipherletter Mapping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232 Creating a Blank Mapping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232 Adding Letters to a Mapping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233 Intersecting Two Mappings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234 How the Letter-Mapping Helper Functions Work . . . . . . . . . . . . . . . . . . . . . 235 Identifying Solved Letters in Mappings . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238 Testing the removeSolvedLetterFromMapping() Function . . . . . . . . . . . . . . . . 240 The hackSimpleSub() Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241 The replace() String Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243 Decrypting the Message . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243 Decrypting in the Interactive Shell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244 Calling the main() Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246 Practice Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246 18 Programming the vigenère CiPher 247 Using Multiple Letter Keys in the Vigenère Cipher . . . . . . . . . . . . . . . . . . . . . . . . . . . 248 Longer Vigenère Keys Are More Secure . . . . . . . . . . . . . . . . . . . . . . . . . . . 249 Choosing a Key That Prevents Dictionary Attacks . . . . . . . . . . . . . . . . . . . . 250 Source Code for the Vigenère Cipher Program . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251 Sample Run of the Vigenère Cipher Program . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252

Page 17

xvi Contents in Detail Setting Up Modules, Constants, and the main() Function . . . . . . . . . . . . . . . . . . . . . . 252 Building Strings with the List-Append-Join Process . . . . . . . . . . . . . . . . . . . . . . . . . . . 253 Encrypting and Decrypting the Message . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255 Calling the main() Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257 Practice Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 258 19 FrequenCy analysis 259 Analyzing the Frequency of Letters in Text . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 260 Matching Letter Frequencies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262 Calculating the Frequency Match Score for the Simple Substitution Cipher . . . 262 Calculating the Frequency Match Score for the Transposition Cipher . . . . . . . 263 Using Frequency Analysis on the Vigenère Cipher . . . . . . . . . . . . . . . . . . . . 264 Source Code for Matching Letter Frequencies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265 Storing the Letters in ETAOIN Order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 266 Counting the Letters in a Message . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 267 Getting the First Member of a Tuple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 268 Ordering the Letters in the Message by Frequency . . . . . . . . . . . . . . . . . . . . . . . . . . 268 Counting the Letters with getLetterCount() . . . . . . . . . . . . . . . . . . . . . . . . . . 269 Creating a Dictionary of Frequency Counts and Letter Lists . . . . . . . . . . . . . . 269 Sorting the Letter Lists in Reverse ETAOIN Order . . . . . . . . . . . . . . . . . . . . . 270 Sorting the Dictionary Lists by Frequency . . . . . . . . . . . . . . . . . . . . . . . . . . 274 Creating a List of the Sorted Letters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 276 Calculating the Frequency Match Score of the Message . . . . . . . . . . . . . . . . . . . . . . 276 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277 Practice Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 278 20 haCking the vigenère CiPher 279 Using a Dictionary Attack to Brute-Force the Vigenère Cipher . . . . . . . . . . . . . . . . . . 280 Source Code for the Vigenère Dictionary Hacker Program . . . . . . . . . . . . . . . . . . . . 280 Sample Run of the Vigenère Dictionary Hacker Program . . . . . . . . . . . . . . . . . . . . . . 281 About the Vigenère Dictionary Hacker Program . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281 Using Kasiski Examination to Find the Key’s Length . . . . . . . . . . . . . . . . . . . . . . . . . 282 Finding Repeated Sequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282 Getting Factors of Spacings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283 Getting Every Nth Letters from a String . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284 Using Frequency Analysis to Break Each Subkey . . . . . . . . . . . . . . . . . . . . . 285 Brute-Forcing Through the Possible Keys . . . . . . . . . . . . . . . . . . . . . . . . . . . 287 Source Code for the Vigenère Hacking Program . . . . . . . . . . . . . . . . . . . . . . . . . . . 287 Sample Run of the Vigenère Hacking Program . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293 Importing Modules and Setting Up the main() Function . . . . . . . . . . . . . . . . . . . . . . . 294 Finding Repeated Sequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294 Calculating the Factors of the Spacings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297 Removing Duplicates with the set() Function . . . . . . . . . . . . . . . . . . . . . . . . 298 Removing Duplicate Factors and Sorting the List . . . . . . . . . . . . . . . . . . . . . 298 Finding the Most Common Factors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 298 Finding the Most Likely Key Lengths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 300 The extend() List Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 301 Extending the repeatedSeqSpacings Dictionary . . . . . . . . . . . . . . . . . . . . . 301 Getting the Factors from factorsByCount . . . . . . . . . . . . . . . . . . . . . . . . . . . 302

Page 18

Contents in Detail xvii Getting Letters Encrypted with the Same Subkey . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302 Attempting Decryption with a Likely Key Length . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303 The end Keyword Argument for print() . . . . . . . . . . . . . . . . . . . . . . . . . . . . 306 Running the Program in Silent Mode or Printing Information to the User . . . . . 306 Finding Possible Combinations of Subkeys . . . . . . . . . . . . . . . . . . . . . . . . . 306 Printing the Decrypted Text with the Correct Casing . . . . . . . . . . . . . . . . . . . 310 Returning the Hacked Message . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 311 Breaking Out of the Loop When a Potential Key Is Found . . . . . . . . . . . . . . . 311 Brute-Forcing All Other Key Lengths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 312 Calling the main() Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313 Modifying the Constants of the Hacking Program . . . . . . . . . . . . . . . . . . . . . . . . . . . 313 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314 Practice Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314 21 the one-time Pad CiPher 315 The Unbreakable One-Time Pad Cipher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 316 Making Key Length Equal Message Length . . . . . . . . . . . . . . . . . . . . . . . . . 316 Making the Key Truly Random . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 318 Avoiding the Two-Time Pad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319 Why the Two-Time Pad Is the Vigenère Cipher . . . . . . . . . . . . . . . . . . . . . . 319 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 320 Practice Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 320 22 Finding and generating Prime numBers 321 What Is a Prime Number? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 322 Source Code for the Prime Numbers Module . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324 Sample Run of the Prime Numbers Module . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 326 How the Trial Division Algorithm Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 326 Implementing the Trial Division Algorithm Test . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 328 The Sieve of Eratosthenes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 328 Generating Prime Numbers with the Sieve of Eratosthenes . . . . . . . . . . . . . . . . . . . . 330 The Rabin-Miller Primality Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 331 Finding Large Prime Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332 Generating Large Prime Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 334 Practice Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 334 23 generating keys For the PuBliC key CiPher 335 Public Key Cryptography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 336 The Problem with Authentication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 337 Digital Signatures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 338 Beware the MITM Attack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 339 Steps for Generating Public and Private Keys . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 340 Source Code for the Public Key Generation Program . . . . . . . . . . . . . . . . . . . . . . . . 340 Sample Run of the Public Key Generation Program . . . . . . . . . . . . . . . . . . . . . . . . . . 342 Creating the main() Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343

Page 19

xviii Contents in Detail Generating Keys with the generateKey() Function . . . . . . . . . . . . . . . . . . . . . . . . . . . 343 Calculating an e Value . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 344 Calculating a d Value . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 344 Returning the Keys . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 345 Creating Key Files with the makeKeyFiles() Function . . . . . . . . . . . . . . . . . . . . . . . . . 345 Calling the main() Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 347 Hybrid Cryptosystems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 347 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 348 Practice Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 348 24 Programming the PuBliC key CiPher 349 How the Public Key Cipher Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 350 Creating Blocks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 350 Converting a String into a Block . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 350 The Mathematics of Public Key Cipher Encryption and Decryption . . . . . . . . . 353 Converting a Block to a String . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354 Why We Can’t Hack the Public Key Cipher . . . . . . . . . . . . . . . . . . . . . . . . 355 Source Code for the Public Key Cipher Program . . . . . . . . . . . . . . . . . . . . . . . . . . . 357 Sample Run of the Public Key Cipher Program . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 360 Setting Up the Program . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 362 How the Program Determines Whether to Encrypt or Decrypt . . . . . . . . . . . . . . . . . . . 362 Converting Strings to Blocks with getBlocksFromText() . . . . . . . . . . . . . . . . . . . . . . . . 363 The min() and max() Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 364 Storing Blocks in blockInt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 364 Using getTextFromBlocks() to Decrypt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 366 Using the insert() List Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 367 Merging the Message List into One String . . . . . . . . . . . . . . . . . . . . . . . . . 367 Writing the encryptMessage() Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 367 Writing the decryptMessage() Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 368 Reading in the Public and Private Keys from Their Key Files . . . . . . . . . . . . . . . . . . . . 369 Writing the Encryption to a File . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 369 Decrypting from a File . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 371 Calling the main() Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 373 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 373 aPPendix deBugging Python Code 375 How the Debugger Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 375 Debugging the Reverse Cipher Program . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 377 Setting Breakpoints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 379 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 380 index 381

Page 20

a C k n o w l e d g m e n t s 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 Shotwell’s; thanks to JP Aumasson for lending his expertise in the public key chapters; and thanks to Josh Ellingson for a great cover.