Preface |
|
xv | |
1 Introduction to Cryptography |
|
1 | (14) |
|
1.1 Cryptosystems and Basic Cryptographic Tools |
|
|
1 | (3) |
|
1.1.1 Secret-key Cryptosystems |
|
|
1 | (1) |
|
1.1.2 Public-key Cryptosystems |
|
|
2 | (1) |
|
1.1.3 Block and Stream Ciphers |
|
|
3 | (1) |
|
1.1.4 Hybrid Cryptography |
|
|
3 | (1) |
|
|
4 | (5) |
|
1.2.1 Message Authentication Codes |
|
|
6 | (1) |
|
|
6 | (1) |
|
|
7 | (1) |
|
|
8 | (1) |
|
|
8 | (1) |
|
1.3 Cryptographic Protocols |
|
|
9 | (1) |
|
|
10 | (3) |
|
|
13 | (2) |
2 Classical Cryptography |
|
15 | (46) |
|
2.1 Introduction: Some Simple Cryptosystems |
|
|
15 | (23) |
|
|
17 | (3) |
|
2.1.2 The Substitution Cipher |
|
|
20 | (2) |
|
|
22 | (4) |
|
2.1.4 The Vigenere Cipher |
|
|
26 | (1) |
|
|
27 | (5) |
|
2.1.6 The Permutation Cipher |
|
|
32 | (2) |
|
|
34 | (4) |
|
|
38 | (13) |
|
2.2.1 Cryptanalysis of the Affine Cipher |
|
|
40 | (2) |
|
2.2.2 Cryptanalysis of the Substitution Cipher |
|
|
42 | (3) |
|
2.2.3 Cryptanalysis of the Vigenere Cipher |
|
|
45 | (3) |
|
2.2.4 Cryptanalysis of the Hill Cipher |
|
|
48 | (1) |
|
2.2.5 Cryptanalysis of the LFSR Stream Cipher |
|
|
49 | (2) |
|
|
51 | (1) |
|
|
51 | (10) |
3 Shannon's Theory, Perfect Secrecy, and the One-Time Pad |
|
61 | (22) |
|
|
61 | (1) |
|
3.2 Elementary Probability Theory |
|
|
62 | (2) |
|
|
64 | (6) |
|
|
70 | (5) |
|
3.4.1 Properties of Entropy |
|
|
72 | (3) |
|
3.5 Spurious Keys and Unicity Distance |
|
|
75 | (4) |
|
|
79 | (1) |
|
|
80 | (3) |
4 Block Ciphers and Stream Ciphers |
|
83 | (54) |
|
|
83 | (1) |
|
4.2 Substitution-Permutation Networks |
|
|
84 | (5) |
|
|
89 | (9) |
|
4.3.1 The Piling-up Lemma |
|
|
89 | (2) |
|
4.3.2 Linear Approximations of S-boxes |
|
|
91 | (3) |
|
4.3.3 A Linear Attack on an SPN |
|
|
94 | (4) |
|
4.4 Differential Cryptanalysis |
|
|
98 | (7) |
|
4.5 The Data Encryption Standard |
|
|
105 | (4) |
|
|
105 | (2) |
|
|
107 | (2) |
|
4.6 The Advanced Encryption Standard |
|
|
109 | (7) |
|
|
110 | (5) |
|
|
115 | (1) |
|
|
116 | (6) |
|
4.7.1 Padding Oracle Attack on CBC Mode |
|
|
120 | (2) |
|
|
122 | (9) |
|
4.8.1 Correlation Attack on a Combination Generator |
|
|
123 | (4) |
|
4.8.2 Algebraic Attack on a Filter Generator |
|
|
127 | (3) |
|
|
130 | (1) |
|
|
131 | (1) |
|
|
131 | (6) |
5 Hash Functions and Message Authentication |
|
137 | (48) |
|
5.1 Hash Functions and Data Integrity |
|
|
137 | (2) |
|
5.2 Security of Hash Functions |
|
|
139 | (9) |
|
5.2.1 The Random Oracle Model |
|
|
140 | (2) |
|
5.2.2 Algorithms in the Random Oracle Model |
|
|
142 | (4) |
|
5.2.3 Comparison of Security Criteria |
|
|
146 | (2) |
|
5.3 Iterated Hash Functions |
|
|
148 | (9) |
|
5.3.1 The Merkle-Damgard Construction |
|
|
151 | (5) |
|
5.3.2 Some Examples of Iterated Hash Functions |
|
|
156 | (1) |
|
5.4 The Sponge Construction |
|
|
157 | (4) |
|
|
160 | (1) |
|
5.5 Message Authentication Codes |
|
|
161 | (9) |
|
5.5.1 Nested MACs and HMAC |
|
|
163 | (3) |
|
|
166 | (1) |
|
5.5.3 Authenticated Encryption |
|
|
167 | (3) |
|
5.6 Unconditionally Secure MACs |
|
|
170 | (7) |
|
5.6.1 Strongly Universal Hash Families |
|
|
173 | (2) |
|
5.6.2 Optimality of Deception Probabilities |
|
|
175 | (2) |
|
|
177 | (1) |
|
|
178 | (7) |
6 The RSA Cryptosystem and Factoring Integers |
|
185 | (70) |
|
6.1 Introduction to Public-key Cryptography |
|
|
185 | (3) |
|
|
188 | (8) |
|
6.2.1 The Euclidean Algorithm |
|
|
188 | (3) |
|
6.2.2 The Chinese Remainder Theorem |
|
|
191 | (3) |
|
|
194 | (2) |
|
|
196 | (4) |
|
|
198 | (2) |
|
|
200 | (10) |
|
6.4.1 Legendre and Jacobi Symbols |
|
|
202 | (3) |
|
6.4.2 The Solovay-Strassen Algorithm |
|
|
205 | (3) |
|
6.4.3 The Miller-Rabin Algorithm |
|
|
208 | (2) |
|
6.5 Square Roots Modulo n |
|
|
210 | (1) |
|
|
211 | (12) |
|
6.6.1 The Pollard p-1 Algorithm |
|
|
212 | (1) |
|
6.6.2 The Pollard Rho Algorithm |
|
|
213 | (3) |
|
6.6.3 Dixon's Random Squares Algorithm |
|
|
216 | (5) |
|
6.6.4 Factoring Algorithms in Practice |
|
|
221 | (2) |
|
|
223 | (9) |
|
|
223 | (1) |
|
6.7.2 The Decryption Exponent |
|
|
223 | (5) |
|
6.7.3 Wiener's Low Decryption Exponent Attack |
|
|
228 | (4) |
|
6.8 The Rabin Cryptosystem |
|
|
232 | (4) |
|
6.8.1 Security of the Rabin Cryptosystem |
|
|
234 | (2) |
|
6.9 Semantic Security of RSA |
|
|
236 | (9) |
|
6.9.1 Partial Information Concerning Plaintext Bits |
|
|
237 | (2) |
|
6.9.2 Obtaining Semantic Security |
|
|
239 | (6) |
|
6.10 Notes and References |
|
|
245 | (1) |
|
|
246 | (9) |
7 Public-Key Cryptography and Discrete Logarithms |
|
255 | (54) |
|
|
255 | (3) |
|
7.1.1 The ElGamal Cryptosystem |
|
|
256 | (2) |
|
7.2 Algorithms for the Discrete Logarithm Problem |
|
|
258 | (10) |
|
|
258 | (2) |
|
7.2.2 The Pollard Rho Discrete Logarithm Algorithm |
|
|
260 | (3) |
|
7.2.3 The Pohlig-Hellman Algorithm |
|
|
263 | (3) |
|
7.2.4 The Index Calculus Method |
|
|
266 | (2) |
|
7.3 Lower Bounds on the Complexity of Generic Algorithms |
|
|
268 | (4) |
|
|
272 | (6) |
|
7.4.1 Joux's Index Calculus |
|
|
276 | (2) |
|
|
278 | (16) |
|
7.5.1 Elliptic Curves over the Reals |
|
|
278 | (3) |
|
7.5.2 Elliptic Curves Modulo a Prime |
|
|
281 | (3) |
|
7.5.3 Elliptic Curves over Finite Fields |
|
|
284 | (1) |
|
7.5.4 Properties of Elliptic Curves |
|
|
285 | (1) |
|
7.5.5 Pairings on Elliptic Curves |
|
|
286 | (4) |
|
7.5.6 ElGamal Cryptosystems on Elliptic Curves |
|
|
290 | (2) |
|
7.5.7 Computing Point Multiples on Elliptic Curves |
|
|
292 | (2) |
|
7.6 Discrete Logarithm Algorithms in Practice |
|
|
294 | (2) |
|
7.7 Security of ElGamal Systems |
|
|
296 | (5) |
|
7.7.1 Bit Security of Discrete Logarithms |
|
|
296 | (3) |
|
7.7.2 Semantic Security of ElGamal Systems |
|
|
299 | (1) |
|
7.7.3 The Diffie-Hellman Problems |
|
|
300 | (1) |
|
|
301 | (1) |
|
|
302 | (7) |
8 Signature Schemes |
|
309 | (32) |
|
|
309 | (3) |
|
8.1.1 RSA Signature Scheme |
|
|
310 | (2) |
|
8.2 Security Requirements for Signature Schemes |
|
|
312 | (2) |
|
8.2.1 Signatures and Hash Functions |
|
|
313 | (1) |
|
8.3 The ElGamal Signature Scheme |
|
|
314 | (6) |
|
8.3.1 Security of the ElGamal Signature Scheme |
|
|
317 | (3) |
|
8.4 Variants of the ElGamal Signature Scheme |
|
|
320 | (6) |
|
8.4.1 The Schnorr Signature Scheme |
|
|
320 | (2) |
|
8.4.2 The Digital Signature Algorithm |
|
|
322 | (3) |
|
8.4.3 The Elliptic Curve DSA |
|
|
325 | (1) |
|
|
326 | (4) |
|
|
330 | (1) |
|
8.7 Signing and Encrypting |
|
|
331 | (2) |
|
|
333 | (1) |
|
|
334 | (7) |
9 Post-Quantum Cryptography |
|
341 | (38) |
|
|
341 | (3) |
|
9.2 Lattice-based Cryptography |
|
|
344 | (9) |
|
|
344 | (4) |
|
9.2.2 Lattices and the Security of NTRU |
|
|
348 | (3) |
|
9.2.3 Learning With Errors |
|
|
351 | (2) |
|
9.3 Code-based Cryptography and the McEliece Cryptosystem |
|
|
353 | (5) |
|
9.4 Multivariate Cryptography |
|
|
358 | (9) |
|
9.4.1 Hidden Field Equations |
|
|
359 | (5) |
|
9.4.2 The Oil and Vinegar Signature Scheme |
|
|
364 | (3) |
|
9.5 Hash-based Signature Schemes |
|
|
367 | (9) |
|
9.5.1 Lamport Signature Scheme |
|
|
368 | (11) |
|
9.5.2 Winternitz Signature Scheme |
|
|
379 | |
|
9.5.3 Merkle Signature Scheme |
|
|
373 | (3) |
|
|
376 | (1) |
|
|
376 | (3) |
10 Identification Schemes and Entity Authentication |
|
379 | (36) |
|
|
379 | (5) |
|
|
381 | (2) |
|
10.1.2 Secure Identification Schemes |
|
|
383 | (1) |
|
10.2 Challenge-and-Response in the Secret-key Setting |
|
|
384 | (10) |
|
10.2.1 Attack Model and Adversarial Goals |
|
|
389 | (2) |
|
10.2.2 Mutual Authentication |
|
|
391 | (3) |
|
10.3 Challenge-and-Response in the Public-key Setting |
|
|
394 | (3) |
|
10.3.1 Public-key Identification Schemes |
|
|
394 | (3) |
|
10.4 The Schnorr Identification Scheme |
|
|
397 | (9) |
|
10.4.1 Security of the Schnorr Identification Scheme |
|
|
400 | (6) |
|
10.5 The Feige-Fiat-Shamir Identification Scheme |
|
|
406 | (5) |
|
10.6 Notes and References |
|
|
411 | (1) |
|
|
412 | (3) |
11 Key Distribution |
|
415 | (46) |
|
|
415 | (4) |
|
11.1.1 Attack Models and Adversarial Goals |
|
|
418 | (1) |
|
|
419 | (13) |
|
11.2.1 Diffie-Hellman Key Predistribution |
|
|
419 | (2) |
|
|
421 | (7) |
|
11.2.3 Key Predistribution in Sensor Networks |
|
|
428 | (4) |
|
11.3 Session Key Distribution Schemes |
|
|
432 | (9) |
|
11.3.1 The Needham-Schroeder Scheme |
|
|
432 | (1) |
|
11.3.2 The Denning-Sacco Attack on the NS Scheme |
|
|
433 | (2) |
|
|
435 | (3) |
|
11.3.4 The Bellare-Rogaway Scheme |
|
|
438 | (3) |
|
11.4 Re-keying and the Logical Key Hierarchy |
|
|
441 | (3) |
|
|
444 | (10) |
|
|
445 | (3) |
|
11.5.2 A Simplified (t, t)-threshold Scheme |
|
|
448 | (2) |
|
11.5.3 Visual Threshold Schemes |
|
|
450 | (4) |
|
11.6 Notes and References |
|
|
454 | (1) |
|
|
454 | (7) |
12 Key Agreement Schemes |
|
461 | (30) |
|
|
461 | (2) |
|
12.1.1 Transport Layer Security (TLS) |
|
|
461 | (2) |
|
12.2 Diffie-Hellman Key Agreement |
|
|
463 | (8) |
|
12.2.1 The Station-to-station Key Agreement Scheme |
|
|
465 | (1) |
|
|
466 | (3) |
|
12.2.3 Known Session Key Attacks |
|
|
469 | (2) |
|
12.3 Key Derivation Functions |
|
|
471 | (1) |
|
12.4 MTI Key Agreement Schemes |
|
|
472 | (6) |
|
12.4.1 Known Session Key Attacks on MTI/A0 |
|
|
476 | (2) |
|
12.5 Deniable Key Agreement Schemes |
|
|
478 | (3) |
|
|
481 | (3) |
|
12.7 Conference Key Agreement Schemes |
|
|
484 | (4) |
|
12.8 Notes and References |
|
|
488 | (1) |
|
|
488 | (3) |
13 Miscellaneous Topics |
|
491 | (36) |
|
13.1 Identity-based Cryptography |
|
|
491 | (12) |
|
13.1.1 The Cocks Identity-based Cryptosystem |
|
|
492 | (6) |
|
13.1.2 Boneh-Franklin Identity-based Cryptosystem |
|
|
498 | (5) |
|
13.2 The Paillier Cryptosystem |
|
|
503 | (3) |
|
13.3 Copyright Protection |
|
|
506 | (12) |
|
|
507 | (2) |
|
13.3.2 Identifiable Parent Property |
|
|
509 | (2) |
|
|
511 | (3) |
|
13.3.4 Tracing Illegally Redistributed Keys |
|
|
514 | (4) |
|
13.4 Bitcoin and Blockchain Technology |
|
|
518 | (4) |
|
13.5 Notes and References |
|
|
522 | (1) |
|
|
523 | (4) |
A Number Theory and Algebraic Concepts for Cryptography |
|
527 | (16) |
|
|
527 | (1) |
|
|
528 | (8) |
|
A.2.1 Orders of Group Elements |
|
|
530 | (1) |
|
A.2.2 Cyclic Groups and Primitive Elements |
|
|
531 | (1) |
|
A.2.3 Subgroups and Cosets |
|
|
532 | (1) |
|
A.2.4 Group Isomorphisms and Homomorphisms |
|
|
533 | (1) |
|
|
534 | (1) |
|
A.2.6 Euclidean Algorithm |
|
|
535 | (1) |
|
|
536 | (1) |
|
|
536 | (4) |
|
A.3.1 The Chinese Remainder Theorem |
|
|
538 | (1) |
|
A.3.2 Ideals and Quotient Rings |
|
|
539 | (1) |
|
|
540 | (3) |
B Pseudorandom Bit Generation for Cryptography |
|
543 | (8) |
|
|
543 | (5) |
|
B.2 Security of Pseudorandom Bit Generators |
|
|
548 | (2) |
|
|
550 | (1) |
Bibliography |
|
551 | (16) |
Index |
|
567 | |