Cryptography

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