Cryptography

Description

Contents......Page 3 Intro......Page 8 1.1 Setup of Cryptography......Page 10 1.2 Note on Sage......Page 11 1.3 Problems......Page 12 2.2 Cracking the Cæsar Cipher......Page 13 2.3 Some Terminology......Page 14 2.4 Problems......Page 15 3.1 What is Substitution Cipher......Page 17 3.2 Cheap Attack against Substitution Cipher......Page 18 3.3 Frequency Analysis......Page 20 3.4 Problems......Page 27 4.1 Prime Numbers & Factorization......Page 32 4.2 Modular Arithmetic......Page 36 4.3 GCD & Euclidean Algorithm......Page 39 4.4 Chinese Remainder Theorem......Page 41 4.5 Multiplication Modulo m & Totient Function......Page 43 4.6 Problems......Page 44 5.1 Vigenère Cipher......Page 47 5.2 Algebraic Description of Vigenère Cipher......Page 48 5.3 Cracking the Vigenère Cipher - Kasiski Examination......Page 49 5.4 Distinguishing Substitution & Vigenère Ciphers......Page 54 5.5 Friedman Coincidence Index......Page 55 5.6 Problems......Page 58 6.1 Matrices......Page 61 6.2 Encrypting with Matrices......Page 64 6.3 Attacking the Hill Cipher......Page 66 6.4 Problems......Page 68 7.1 Autokey Cipher......Page 69 7.2 Transposition Ciphers......Page 71 7.3 One-Time Pads......Page 74 7.4 Intro to Modern Cryptosystems......Page 75 7.5 Problems......Page 77 8.1 Big O Notation......Page 80 8.2 Logarithms......Page 81 8.3 Running Times of Algorithms......Page 82 8.4 Problems......Page 87 9.1 Some Group Theory......Page 89 9.2 Fields......Page 90 9.3 Problems......Page 91 10.1 Fermat Little Theorem......Page 92 10.3 Primitive Roots & Structure of Fp......Page 93 10.4 Numbers in other Bases......Page 95 10.5 Fast Computation of Powers in Z/mZ......Page 96 10.6 Multiplicative Functions......Page 97 10.7 Problems......Page 100 11.1 Diffie–Hellman Key Exchange......Page 102 11.2 Discrete Logarithm Problem......Page 103 11.3 ElGamal Encryption......Page 104 11.5 Shanks Baby-Step Giant-Step Algorithm......Page 106 11.6 Pohlig–Hellman......Page 108 11.7 Index Calculus......Page 110 11.8 Problems......Page 114 12.1 RSA......Page 116 12.2 Attacking Naïve RSA......Page 117 12.4 Blocking......Page 119 12.6 Digital Signatures......Page 121 12.7 Attacks on RSA......Page 124 12.8 Security......Page 125 12.9 Problems......Page 127 13.1 Intro to Clever Factorization Algorithms & Primality Tests......Page 130 13.3 Pollard ρ Algorithm......Page 131 13.4 Smooth Numbers......Page 133 13.5 Quadratic Sieve......Page 134 13.6 Miller–Rabin Primality Test......Page 138 13.7 Agrawal–Kayal–Saxena Primality Test......Page 140 13.8 Problems......Page 142 14.1 Rational Points on Circle......Page 144 14.2 Elliptic Curves......Page 146 14.3 Elliptic Curves over Finite Fields......Page 149 14.5 A Smattering of Group Theory......Page 151 14.7 Elliptic Curve Diffie–Hellman......Page 153 14.8 Why Elliptic Curves......Page 156 14.9 Problems......Page 157 15.1 Pollard p-1 Factorization......Page 159 15.2 Elliptic Curves over Z/nZ......Page 162 15.3 Lenstra's Elliptic Curve Factorization......Page 163 15.4 Elliptic Curves over Q......Page 166 15.5 Elliptic Curves & Diophantine Equations......Page 167 15.6 Elliptic Curves over Z......Page 170 15.7 Problems......Page 171 16.1 Intro to Zero-Knowledge Proofs......Page 174 16.2 What is Zero-Knowledge Proof......Page 175 16.3 Ali Baba Cave......Page 177 16.4 3-Colorability......Page 178 16.5 Sudoku......Page 181 16.6 Quadratic Residuosity......Page 183 16.7 Discrete Logarithms......Page 184 16.8 Time Machines & Prover Tricks......Page 186 16.9 Commitment Schemes......Page 187 16.10 Problems......Page 188 17.1 Secret Sharing......Page 191 17.2 Shamir Secret-Sharing Scheme......Page 192 17.3 Blakley Secret-Sharing Scheme......Page 193 17.4 Visual Cryptography......Page 194 17.5 Cryptographic Voting......Page 196 17.6 Cryptographic Voting Protocol......Page 197 17.7 Key Generation......Page 198 17.9 Encrypting & Verifying the Votes......Page 199 17.10 Decryption Mix-Net......Page 201 17.11 Problems......Page 203 18.1 Quantum vs Classical Computers......Page 206 18.2 Modifying Quantum States......Page 208 18.3 Quantum Cryptographic Protocol......Page 209 18.4 Quantum Computers defeat Classical Cryptography......Page 211 18.5 Quantum Fourier Transform......Page 213 18.6 Continued Fractions......Page 214 18.7 Back to Shor Algorithm......Page 216 18.8 Problems......Page 218 19.1 Introduction to Probability......Page 219 19.2 Markov Chains......Page 221 19.3 Stationarity......Page 224 19.4 Letters and Markov Chains......Page 225 19.5 Problems......Page 227 20.1 Intro to Coding Theory......Page 229 20.2 Linear Codes......Page 231 20.3 Lexicographic Codes......Page 232 20.4 Prisoners & their Hats......Page 236 20.5 Nim......Page 239 20.6 Hamming Codes......Page 240 20.7 Back to the Hats......Page 241 20.8 Linearity......Page 242 20.10 The Ternary Golay Code......Page 244 20.11 The Binary Golay Code......Page 246 20.13 Problems......Page 247 Refs......Page 249 Index......Page 254