Preface |
|
v | |
|
Part 1 Mathematical Background |
|
|
1 | (116) |
|
Chapter 1 Modular Arithmetic, Groups, Finite Fields and Probability |
|
|
3 | (24) |
|
|
3 | (5) |
|
|
8 | (3) |
|
|
11 | (10) |
|
|
21 | (3) |
|
|
24 | (3) |
|
Chapter 2 Primality Testing and Factoring |
|
|
27 | (24) |
|
|
27 | (5) |
|
2.2 The Factoring and Factoring-Related Problems |
|
|
32 | (6) |
|
2.3 Basic Factoring Algorithms |
|
|
38 | (4) |
|
2.4 Modern Factoring Algorithms |
|
|
42 | (2) |
|
|
44 | (7) |
|
Chapter 3 Discrete Logarithms |
|
|
51 | (16) |
|
3.1 The DLP, DHP and DDH Problems |
|
|
51 | (3) |
|
|
54 | (3) |
|
3.3 Baby-Step/Giant-Step Method |
|
|
57 | (2) |
|
|
59 | (5) |
|
3.5 Sub-exponential Methods for Finite Fields |
|
|
64 | (3) |
|
Chapter 4 Elliptic Curves |
|
|
67 | (12) |
|
|
67 | (2) |
|
|
69 | (3) |
|
4.3 Elliptic Curves over Finite Fields |
|
|
72 | (2) |
|
4.4 Projective Coordinates |
|
|
74 | (1) |
|
|
75 | (2) |
|
4.6 Choosing an Elliptic Curve |
|
|
77 | (2) |
|
|
79 | (16) |
|
5.1 Lattices and Lattice Reduction |
|
|
79 | (6) |
|
5.2 "Hard" Lattice Problems |
|
|
85 | (4) |
|
|
89 | (1) |
|
5.4 Coppersmith's Theorem |
|
|
90 | (5) |
|
Chapter 6 Implementation Issues |
|
|
95 | (22) |
|
|
95 | (1) |
|
6.2 Exponentiation Algorithms |
|
|
95 | (4) |
|
6.3 Special Exponentiation Methods |
|
|
99 | (2) |
|
6.4 Multi-precision Arithmetic |
|
|
101 | (6) |
|
6.5 Finite Field Arithmetic |
|
|
107 | (10) |
|
Part 2 Historical Ciphers |
|
|
117 | (78) |
|
Chapter 7 Historical Ciphers |
|
|
119 | (14) |
|
|
119 | (1) |
|
|
120 | (3) |
|
|
123 | (3) |
|
|
126 | (5) |
|
|
131 | (2) |
|
Chapter 8 The Enigma Machine |
|
|
133 | (30) |
|
|
133 | (3) |
|
8.2 An Equation for the Enigma |
|
|
136 | (1) |
|
8.3 Determining the Plugboard Given the Rotor Settings |
|
|
137 | (3) |
|
8.4 Double Encryption of Message Keys |
|
|
140 | (1) |
|
8.5 Determining the Internal Rotor Wirings |
|
|
141 | (6) |
|
8.6 Determining the Day Settings |
|
|
147 | (1) |
|
8.7 The Germans Make It Harder |
|
|
148 | (2) |
|
8.8 Known Plaintext Attack and the Bombes |
|
|
150 | (8) |
|
8.9 Ciphertext Only Attack |
|
|
158 | (5) |
|
Chapter 9 Information-Theoretic Security |
|
|
163 | (16) |
|
|
163 | (1) |
|
9.2 Probability and Ciphers |
|
|
164 | (5) |
|
|
169 | (4) |
|
9.4 Spurious Keys and Unicity Distance |
|
|
173 | (6) |
|
Chapter 10 Historical Stream Ciphers |
|
|
179 | (16) |
|
10.1 Introduction to Symmetric Ciphers |
|
|
179 | (2) |
|
10.2 Stream Cipher Basics |
|
|
181 | (1) |
|
|
182 | (6) |
|
10.4 Breaking the Lorenz Cipher's Wheels |
|
|
188 | (4) |
|
10.5 Breaking a Lorenz Cipher Message |
|
|
192 | (3) |
|
Part 3 Modern Cryptography Basics |
|
|
195 | (206) |
|
Chapter 11 Defining Security |
|
|
197 | (28) |
|
|
197 | (1) |
|
11.2 Pseudo-random Functions and Permutations |
|
|
197 | (4) |
|
11.3 One-Way Functions and Trapdoor One-Way Functions |
|
|
201 | (1) |
|
11.4 Public Key Cryptography |
|
|
202 | (1) |
|
11.5 Security of Encryption |
|
|
203 | (6) |
|
11.6 Other Notions of Security |
|
|
209 | (6) |
|
11.7 Authentication: Security of Signatures and MACs |
|
|
215 | (4) |
|
|
219 | (2) |
|
11.9 Computational Models: The Random Oracle Model |
|
|
221 | (4) |
|
Chapter 12 Modern Stream Ciphers |
|
|
225 | (16) |
|
12.1 Stream Ciphers from Pseudo-random Functions |
|
|
225 | (2) |
|
12.2 Linear Feedback Shift Registers |
|
|
227 | (6) |
|
|
233 | (5) |
|
|
238 | (3) |
|
Chapter 13 Block Ciphers and Modes of Operation |
|
|
241 | (30) |
|
13.1 Introduction to Block Ciphers |
|
|
241 | (3) |
|
13.2 Feistel Ciphers and DES |
|
|
244 | (6) |
|
|
250 | (4) |
|
|
254 | (12) |
|
13.5 Obtaining Chosen Ciphertext Security |
|
|
266 | (5) |
|
Chapter 14 Hash Functions, Message Authentication Codes and Key Derivation Functions |
|
|
271 | (24) |
|
14.1 Collision Resistance |
|
|
271 | (4) |
|
|
275 | (1) |
|
14.3 The Merkle--Damgard Construction |
|
|
276 | (2) |
|
|
278 | (4) |
|
|
282 | (2) |
|
14.6 Merkle--Damgard-Based Key Derivation Function |
|
|
284 | (1) |
|
14.7 MACs and KDFs Based on Block Ciphers |
|
|
285 | (3) |
|
14.8 The Sponge Construction and SHA-3 |
|
|
288 | (7) |
|
Chapter 15 The "Naive" RSA Algorithm |
|
|
295 | (18) |
|
15.1 "Naive" RSA Encryption |
|
|
295 | (4) |
|
15.2 "Naive" RSA Signatures |
|
|
299 | (2) |
|
|
301 | (4) |
|
15.4 Some Lattice-Based Attacks on RSA |
|
|
305 | (4) |
|
15.5 Partial Key Exposure Attacks on RSA |
|
|
309 | (1) |
|
|
310 | (3) |
|
Chapter 16 Public Key Encryption and Signature Algorithms |
|
|
313 | (36) |
|
16.1 Passively Secure Public Key Encryption Schemes |
|
|
313 | (6) |
|
16.2 Random Oracle Model, OAEP and the Fujisaki--Okamoto Transform |
|
|
319 | (5) |
|
|
324 | (5) |
|
|
329 | (4) |
|
16.5 Secure Digital Signatures |
|
|
333 | (9) |
|
16.6 Schemes Avoiding Random Oracles |
|
|
342 | (7) |
|
Chapter 17 Cryptography Based on Really Hard Problems |
|
|
349 | (20) |
|
17.1 Cryptography and Complexity Theory |
|
|
349 | (4) |
|
17.2 Knapsack-Based Cryptosystems |
|
|
353 | (3) |
|
17.3 Worst-Case to Average-Case Reductions |
|
|
356 | (4) |
|
17.4 Learning With Errors (LWE) |
|
|
360 | (9) |
|
Chapter 18 Certificates, Key Transport and Key Agreement |
|
|
369 | (32) |
|
|
369 | (2) |
|
18.2 Certificates and Certificate Authorities |
|
|
371 | (4) |
|
18.3 Fresh Ephemeral Symmetric Keys from Static Symmetric Keys |
|
|
375 | (7) |
|
18.4 Fresh Ephemeral Symmetric Keys from Static Public Keys |
|
|
382 | (6) |
|
18.5 The Symbolic Method of Protocol Analysis |
|
|
388 | (4) |
|
18.6 The Game-Based Method of Protocol Analysis |
|
|
392 | (9) |
|
Part 4 Advanced Protocols |
|
|
401 | (50) |
|
Chapter 19 Secret Sharing Schemes |
|
|
403 | (14) |
|
|
403 | (2) |
|
19.2 General Secret Sharing |
|
|
405 | (2) |
|
|
407 | (5) |
|
19.4 Shamir Secret Sharing |
|
|
412 | (2) |
|
19.5 Application: Shared RSA Signature Generation |
|
|
414 | (3) |
|
Chapter 20 Commitments and Oblivious Transfer |
|
|
417 | (8) |
|
|
417 | (1) |
|
|
417 | (4) |
|
|
421 | (4) |
|
Chapter 21 Zero-Knowledge Proofs |
|
|
425 | (14) |
|
21.1 Showing a Graph Isomorphism in Zero-Knowledge |
|
|
425 | (3) |
|
21.2 Zero-Knowledge and NP |
|
|
428 | (1) |
|
|
429 | (7) |
|
21.4 An Electronic Voting System |
|
|
436 | (3) |
|
Chapter 22 Secure Multi-party Computation |
|
|
439 | (12) |
|
|
439 | (2) |
|
|
441 | (4) |
|
22.3 The Multi-party Case: Honest-but-Curious Adversaries |
|
|
445 | (3) |
|
22.4 The Multi-party Case: Malicious Adversaries |
|
|
448 | (3) |
|
|
451 | (24) |
|
Basic Mathematical Terminology |
|
|
453 | (22) |
|
|
453 | (1) |
|
|
453 | (2) |
|
|
455 | (1) |
|
|
456 | (3) |
|
|
459 | (2) |
|
|
461 | (7) |
|
|
468 | (1) |
|
|
469 | (1) |
|
|
470 | (5) |
Index |
|
475 | |