The Mathematics of Encryption An Elementary Introduction

The Mathematics of Encryption An Elementary Introduction Margaret Cozzens Steven J. Miller opying and reprinting. Individual readers of this publication, and nonprofit libraries acting for them, are permitted to make fair use of the material, such as to copy a chapter for use in teaching or research. Permission is granted to quote b rief passages from this publication in reviews, provided the customary acknowledgment of the source is given. Republication, systematic copying, or multiple reproduction of any material in this publication is permitted only under license from the American Mathematical Society. Requests for such permission should be addressed to the Acquisitions Department, American Mathematical Society, 201 Charles Street, Providence, Rhode Island 02904-2294 USA. Requests can also be made by e-mail to reprint-permission@ams.org. c 2013 by the American Mathematical Society. All rights reserved. The American Mathematical Society retains all rights except those granted to the United States Government. Printed in the United States of America. ∞ The paper used in this book is acid-free and falls within the guidelines established to ensure permanence and durability. Visit the AMS home page at http://www.ams.org/ 10 9 8 7 6 5 4 3 2 1 18 17 16 15 14 13 Margaret Cozzens dedicates to Tyler and Brad. Steven Miller dedicates to Cameron and Kayla Miller, for their patience as the book was written and for hours of fun exploring the Caesar cipher. This book is also dedicated to the men and women who have advanced freedom’s cause through the centuries by devoting and sometimes giving up their lives to breaking codes and protecting these successes. Contents Preface xi Acknowledgments xvii Chapter 1. Historical Introduction 1 1.1. Ancient Times 2 1.2. Cryptography During the Two World Wars 8 1.3. Postwar Cryptography, Computers, and Security 12 1.4. Summary 14 1.5. Problems 15 Chapter 2. Classical Cryptology: Methods 19 2.1. Ancient Cryptography 20 2.2. Substitution Alphabet Ciphers 22 2.3. The Caesar Cipher 24 2.4. Modular Arithmetic 26 2.5. Number Theory Notation 28 2.6. The Affine Cipher 30 2.7. The Vigen`ere Cipher 33 2.8. The Permutation Cipher 36 2.9. The Hill Cipher 39 2.10. Summary 42 2.11. Problems 42 Chapter 3. Enigma and Ultra 51 3.1. Setting the Stage 51 3.2. Some Counting 54 3.3. Enigma’s Security 60 3.4. Cracking the Enigma 67 3.5. Codes in World War II 70 3.6. Summary 72 3.7. Appendix: Proofs by Induction 73 vii viii CONTENTS 3.8. Problems 75 Chapter 4. Classical Cryptography: Attacks I 81 4.1. Breaking the Caesar Cipher 81 4.2. Function Preliminaries 84 4.3. Modular Arithmetic and the Affine Cipher 86 4.4. Breaking the Affine Cipher 91 4.5. The Substitution Alphabet Cipher 94 4.6. Frequency Analysis and the Vigen`ere Cipher 99 4.7. The Kasiski Test 102 4.8. Summary 106 4.9. Problems 107 Chapter 5. Classical Cryptography: Attacks II 113 5.1. Breaking the Permutation Cipher 114 5.2. Breaking the Hill Cipher 115 5.3. Running Key Ciphers 120 5.4. One-Time Pads 122 5.5. Summary 127 5.6. Problems 128 Chapter 6. Modern Symmetric Encryption 133 6.1. Binary Numbers and Message Streams 133 6.2. Linear Feedback Shift Registers 138 6.3. Known-Plaintext Attack on LFSR Stream Ciphers 142 6.4. LFSRsum 145 6.5. BabyCSS 150 6.6. Breaking BabyCSS 152 6.7. BabyBlock 158 6.8. Security of BabyBlock 161 6.9. Meet-in-the-Middle Attacks 162 6.10. Summary 164 6.11. Problems 164 Chapter 7. Introduction to Public-Channel Cryptography 171 7.1. The Perfect Code Cryptography System 173 7.2. KidRSA 180 7.3. The Euclidean Algorithm 182 7.4. Binary Expansion and Fast Modular Exponentiation 188 7.5. Prime Numbers 192 7.6. Fermat’s little Theorem 198 7.7. Summary 203 7.8. Problems 203 Chapter 8. Public-Channel Cryptography 213 8.1. RSA 214 8.2. RSA and Symmetric Encryption 218 CONTENTS ix 8.3. Digital Signatures 219 8.4. Hash Functions 221 8.5. Diffie–Hellman Key Exchange8.6. Why RSA Works 228 8.7. Summary 230 8.8. Problems 231 Chapter 9. Error Detecting and Correcting Codes 239 9.1. Introduction 240 9.2. Error Detection and Correction Riddles 241 9.3. Definitions and Setup 247 9.4. Examples of Error Detecting Codes 249 9.5. Error Correcting Codes 252 9.6. More on the Hamming (7, 4) Code 255 9.7. From Parity to UPC Symbols 257 9.8. Summary and Further Topics 259 9.9. Problems 261 Chapter 10. Modern Cryptography 269 10.1. Steganography—Messages You Don’t Know Exist 269 10.2. Steganography in the Computer Age 273 10.3. Quantum Cryptography 278 10.4. Cryptography and Terrorists at Home and Abroad 282 10.5. Summary 285 10.6. Problems 285 Chapter 11. Primality Testing and Factorization 289 11.1. Introduction 289 11.2. Brute Force Factoring 291 11.3. Fermat’s Factoring Method 295 11.4. Monte Carlo Algorithms and FT Primality Test 299 11.5. Miller–Rabin Test 302 11.6. Agrawal–Kayal–Saxena Primality Test 305 11.7. Problems 310 Chapter 12. Solutions to Selected Problems 317 12.1. Chapter 1: Historical Introduction 317 12.2. Chapter 2: Classical Cryptography: Methods 317 12.3. Chapter 3: Enigma and Ultra 318 12.4. Chapter 4: Classical Cryptography: Attacks I 319 12.5. Chapter 5: Classical Cryptography: Attacks II 320 12.6. Chapter 6: Modern Symmetric Encryption 320 12.7. Chapter 7: Introduction to Public-Channel Cryptography 320 12.8. Chapter 8: Public-Channel Cryptography 321 12.9. Chapter 9: Error Detecting and Correcting Codes 321 12.10. Chapter 10: Modern Cryptography 322 x CONTENTS 12.11. Chapter 11: Primality Testing and Factorization 322 Bibliography 325 Index 3 rief passages from this publication in reviews, provided the customary acknowledgment of the source is given. Republication, systematic copying, or multiple reproduction of any material in this publication is permitted only under license from the American Mathematical Society. Requests for such permission should be addressed to the Acquisitions Department, American Mathematical Society, 201 Charles Street, Providence, Rhode Island 02904-2294 USA. Requests can also be made by e-mail to reprint-permission@ams.org. c 2013 by the American Mathematical Society. All rights reserved. The American Mathematical Society retains all rights except those granted to the United States Government. Printed in the United States of America. ∞ The paper used in this book is acid-free and falls within the guidelines established to ensure permanence and durability. Visit the AMS home page at http://www.ams.org/ 10 9 8 7 6 5 4 3 2 1 18 17 16 15 14 13 Margaret Cozzens dedicates to Tyler and Brad. Steven Miller dedicates to Cameron and Kayla Miller, for their patience as the book was written and for hours of fun exploring the Caesar cipher. This book is also dedicated to the men and women who have advanced freedom’s cause through the centuries by devoting and sometimes giving up their lives to breaking codes and protecting these successes. Contents Preface xi Acknowledgments xvii Chapter 1. Historical Introduction 1 1.1. Ancient Times 2 1.2. Cryptography During the Two World Wars 8 1.3. Postwar Cryptography, Computers, and Security 12 1.4. Summary 14 1.5. Problems 15 Chapter 2. Classical Cryptology: Methods 19 2.1. Ancient Cryptography 20 2.2. Substitution Alphabet Ciphers 22 2.3. The Caesar Cipher 24 2.4. Modular Arithmetic 26 2.5. Number Theory Notation 28 2.6. The Affine Cipher 30 2.7. The Vigen`ere Cipher 33 2.8. The Permutation Cipher 36 2.9. The Hill Cipher 39 2.10. Summary 42 2.11. Problems 42 Chapter 3. Enigma and Ultra 51 3.1. Setting the Stage 51 3.2. Some Counting 54 3.3. Enigma’s Security 60 3.4. Cracking the Enigma 67 3.5. Codes in World War II 70 3.6. Summary 72 3.7. Appendix: Proofs by Induction 73 vii viii CONTENTS 3.8. Problems 75 Chapter 4. Classical Cryptography: Attacks I 81 4.1. Breaking the Caesar Cipher 81 4.2. Function Preliminaries 84 4.3. Modular Arithmetic and the Affine Cipher 86 4.4. Breaking the Affine Cipher 91 4.5. The Substitution Alphabet Cipher 94 4.6. Frequency Analysis and the Vigen`ere Cipher 99 4.7. The Kasiski Test 102 4.8. Summary 106 4.9. Problems 107 Chapter 5. Classical Cryptography: Attacks II 113 5.1. Breaking the Permutation Cipher 114 5.2. Breaking the Hill Cipher 115 5.3. Running Key Ciphers 120 5.4. One-Time Pads 122 5.5. Summary 127 5.6. Problems 128 Chapter 6. Modern Symmetric Encryption 133 6.1. Binary Numbers and Message Streams 133 6.2. Linear Feedback Shift Registers 138 6.3. Known-Plaintext Attack on LFSR Stream Ciphers 142 6.4. LFSRsum 145 6.5. BabyCSS 150 6.6. Breaking BabyCSS 152 6.7. BabyBlock 158 6.8. Security of BabyBlock 161 6.9. Meet-in-the-Middle Attacks 162 6.10. Summary 164 6.11. Problems 164 Chapter 7. Introduction to Public-Channel Cryptography 171 7.1. The Perfect Code Cryptography System 173 7.2. KidRSA 180 7.3. The Euclidean Algorithm 182 7.4. Binary Expansion and Fast Modular Exponentiation 188 7.5. Prime Numbers 192 7.6. Fermat’s little Theorem 198 7.7. Summary 203 7.8. Problems 203 Chapter 8. Public-Channel Cryptography 213 8.1. RSA 214 8.2. RSA and Symmetric Encryption 218 CONTENTS ix 8.3. Digital Signatures 219 8.4. Hash Functions 221 8.5. Diffie–Hellman Key Exchange8.6. Why RSA Works 228 8.7. Summary 230 8.8. Problems 231 Chapter 9. Error Detecting and Correcting Codes 239 9.1. Introduction 240 9.2. Error Detection and Correction Riddles 241 9.3. Definitions and Setup 247 9.4. Examples of Error Detecting Codes 249 9.5. Error Correcting Codes 252 9.6. More on the Hamming (7, 4) Code 255 9.7. From Parity to UPC Symbols 257 9.8. Summary and Further Topics 259 9.9. Problems 261 Chapter 10. Modern Cryptography 269 10.1. Steganography—Messages You Don’t Know Exist 269 10.2. Steganography in the Computer Age 273 10.3. Quantum Cryptography 278 10.4. Cryptography and Terrorists at Home and Abroad 282 10.5. Summary 285 10.6. Problems 285 Chapter 11. Primality Testing and Factorization 289 11.1. Introduction 289 11.2. Brute Force Factoring 291 11.3. Fermat’s Factoring Method 295 11.4. Monte Carlo Algorithms and FT Primality Test 299 11.5. Miller–Rabin Test 302 11.6. Agrawal–Kayal–Saxena Primality Test 305 11.7. Problems 310 Chapter 12. Solutions to Selected Problems 317 12.1. Chapter 1: Historical Introduction 317 12.2. Chapter 2: Classical Cryptography: Methods 317 12.3. Chapter 3: Enigma and Ultra 318 12.4. Chapter 4: Classical Cryptography: Attacks I 319 12.5. Chapter 5: Classical Cryptography: Attacks II 320 12.6. Chapter 6: Modern Symmetric Encryption 320 12.7. Chapter 7: Introduction to Public-Channel Cryptography 320 12.8. Chapter 8: Public-Channel Cryptography 321 12.9. Chapter 9: Error Detecting and Correcting Codes 321 12.10. Chapter 10: Modern Cryptography 322 x CONTENTS 12.11. Chapter 11: Primality Testing and Factorization 322 Bibliography 325 Index 3