Cryptography

Description

This text introduces cryptography, from its earliest roots to cryptosystems used today for secure online communication. Beginning with classical ciphers and their cryptanalysis, this book proceeds to focus on modern public key cryptosystems such as Diffie-Hellman, ElGamal, RSA, and elliptic curve cryptography with an analysis of vulnerabilities of these systems and underlying mathematical issues such as factorization algorithms. Specialized topics such as zero knowledge proofs, cryptographic voting, coding theory, and new research are covered in the final section of this book. Aimed at undergraduate students, this book contains a large selection of problems, ranging from straightforward to difficult, and can be used as a textbook for classes as well as self-study. Requiring only a solid grounding in basic mathematics, this book will also appeal to advanced high school students and amateur mathematicians interested in this fascinating and topical subject. Contents......Page 6 Introduction......Page 11 1.1 The Setup of Cryptography......Page 13 1.2 A Note on Sage......Page 14 1.3 Problems......Page 15 2.2 Cracking the Cæsar Cipher......Page 16 2.3 Some Terminology......Page 17 2.4 Problems......Page 18 3.1 What is a Substitution Cipher?......Page 20 3.2 A Cheap Attack Against the Substitution Cipher......Page 21 3.3 Frequency Analysis......Page 23 3.4 Problems......Page 30 4.1 Prime Numbers and Factorization......Page 35 4.2 Modular Arithmetic......Page 39 4.3 The GCD and the Euclidean Algorithm......Page 42 4.4 The Chinese Remainder Theorem......Page 44 4.5 Multiplication Modulo m and the Totient Function......Page 46 4.6 Problems......Page 47 5.1 The Vigenère Cipher......Page 50 5.2 Algebraic Description of the Vigenère Cipher......Page 51 5.3 Cracking the Vigenère Cipher: The Kasiski Examination......Page 52 5.4 Distinguishing Substitution and Vigenère Ciphers......Page 57 5.5 Friedman's Coincidence Index......Page 58 5.6 Problems......Page 61 6.1 Matrices......Page 64 6.2 Encrypting with Matrices......Page 67 6.3 Attacking the Hill Cipher......Page 69 6.4 Problems......Page 71 7.1 The Autokey Cipher......Page 72 7.2 Transposition Ciphers......Page 74 7.3 One-Time Pads......Page 77 7.4 Introduction to Modern Cryptosystems......Page 78 7.5 Problems......Page 80 8.1 Big O Notation......Page 83 8.2 Logarithms......Page 84 8.3 Running Times of Algorithms......Page 85 8.4 Problems......Page 90 9.1 Some Group Theory......Page 92 9.2 Fields......Page 93 9.3 Problems......Page 94 10.1 Fermat's Little Theorem......Page 95 10.3 Primitive Roots and the Structure of mathbbFptimes......Page 96 10.4 Numbers in Other Bases......Page 98 10.5 Fast Computation of Powers in mathbbZ/mmathbbZ......Page 99 10.6 Multiplicative Functions......Page 100 10.7 Problems......Page 103 11.1 The Diffie–Hellman Key Exchange......Page 105 11.2 The Discrete Logarithm Problem......Page 106 11.3 ElGamal Encryption......Page 107 11.5 Shanks's Baby-Step Giant-Step Algorithm......Page 109 11.6 Pohlig–Hellman......Page 111 11.7 The Index Calculus......Page 113 11.8 Problems......Page 117 12.1 RSA......Page 119 12.2 Attacking Naïve RSA......Page 120 12.4 Blocking......Page 122 12.6 Digital Signatures......Page 124 12.7 Attacks on RSA......Page 127 12.8 Security......Page 128 12.9 Problems......Page 130 13.1 Introduction to Clever Factorization Algorithms and Primality Tests......Page 133 13.3 Pollard ρ Algorithm......Page 134 13.4 Smooth Numbers......Page 136 13.5 The Quadratic Sieve......Page 137 13.6 The Miller–Rabin Primality Test......Page 141 13.7 The Agrawal–Kayal–Saxena Primality Test......Page 143 13.8 Problems......Page 145 14.1 Rational Points on a Circle......Page 147 14.2 Elliptic Curves......Page 149 14.3 Elliptic Curves Over Finite Fields......Page 152 14.5 A Smattering of Group Theory......Page 154 14.7 Elliptic Curve Diffie–Hellman......Page 156 14.8 Why Elliptic Curves?......Page 159 14.9 Problems......Page 160 15.1 Pollard's p-1 Factorization......Page 162 15.2 Elliptic Curves Over mathbbZ/nmathbbZ......Page 165 15.3 Lenstra's Elliptic Curve Factorization......Page 166 15.4 Elliptic Curves Over mathbbQ......Page 169 15.5 Elliptic Curves and Diophantine Equations......Page 170 15.6 Elliptic Curves Over mathbbZ......Page 173 15.7 Problems......Page 174 16.1 Introduction to Zero-Knowledge Proofs......Page 177 16.2 What is a Zero-Knowledge Proof?......Page 178 16.3 Ali Baba's Cave......Page 180 16.4 Three-Colorability......Page 181 16.5 Sudoku......Page 184 16.6 Quadratic Residuosity......Page 186 16.7 Discrete Logarithms......Page 187 16.8 Time Machines and Prover Tricks......Page 189 16.9 Commitment Schemes......Page 190 16.10 Problems......Page 191 17.1 Secret Sharing......Page 194 17.2 Shamir's Secret-Sharing Scheme......Page 195 17.3 Blakley's Secret-Sharing Scheme......Page 196 17.4 Visual Cryptography......Page 197 17.5 Cryptographic Voting......Page 199 17.6 An Outline of a Cryptographic Voting Protocol......Page 200 17.7 Key Generation......Page 201 17.9 Encrypting and Verifying the Votes......Page 202 17.10 The Decryption Mix-Net......Page 204 17.11 Problems......Page 206 18.1 Quantum Versus Classical Computers......Page 209 18.2 Modifying Quantum States......Page 211 18.3 A Quantum Cryptographic Protocol......Page 212 18.4 Quantum Computers Defeat Classical Cryptography......Page 214 18.5 The Quantum Fourier Transform......Page 216 18.6 Continued Fractions......Page 217 18.7 Back to Shor's Algorithm......Page 219 18.8 Problems......Page 221 19.1 Introduction to Probability......Page 222 19.2 Markov Chains......Page 224 19.3 Stationarity......Page 227 19.4 Letters and Markov Chains......Page 228 19.5 Problems......Page 230 20.1 Introduction to Coding Theory......Page 232 20.2 Linear Codes......Page 234 20.3 Lexicographic Codes......Page 235 20.4 Prisoners and Their Hats......Page 239 20.5 Nim......Page 242 20.6 Hamming Codes......Page 243 20.7 Back to the Hats......Page 244 20.8 Linearity......Page 245 20.10 The Ternary Golay Code......Page 247 20.11 The Binary Golay Code......Page 249 20.13 Problems......Page 250 BookmarkTitle:......Page 252 Index......Page 257