Introduction to Modern Cryptography

Cover......Page 1
Half Title......Page 2
Series Page......Page 3
Title Page......Page 4
Copyright Page......Page 5
Dedication......Page 6
Table of Contents......Page 8
Preface......Page 16
I: Introduction and Classical Cryptography......Page 22
1.1 Cryptography and Modern Cryptography......Page 24
1.2 The Setting of Private-Key Encryption......Page 25
1.3 Historical Ciphers and Their Cryptanalysis......Page 29
1.4 Principles of Modern Cryptography......Page 37
1.4.1 Principle 1 { Formal Denitions......Page 38
1.4.2 Principle 2 { Precise Assumptions......Page 41
1.4.4 Provable Security and Real-World Security......Page 43
Exercises......Page 44
2: Perfectly Secret Encryption......Page 46
2.1 Defnitions......Page 47
2.2 The One-Time Pad......Page 54
2.3 Limitations of Perfect Secrecy......Page 56
2.4 *Shannon\'s Theorem......Page 57
Exercises......Page 59
II: Private-Key (Symmetric) Cryptography......Page 64
3.1 Computational Security......Page 66
3.1.1 The Concrete Approach......Page 67
3.1.2 The Asymptotic Approach......Page 68
3.2 Defining Computationally Secure Encryption......Page 74
3.2.1 The Basic Definition of Security (EAV-Security)......Page 75
3.2.2 *Semantic Security......Page 79
3.3.1 Pseudorandom Generators......Page 83
3.3.2 Proofs by Reduction......Page 87
3.3.3 EAV-Security from a Pseudorandom Generator......Page 88
3.4.1 Security for Multiple Encryptions......Page 93
3.4.2 Chosen-Plaintext Attacks and CPA-Security......Page 95
3.4.3 CPA-Security for Multiple Encryptions......Page 97
3.5 Constructing a CPA-Secure Encryption Scheme......Page 98
3.5.1 Pseudorandom Functions and Permutations......Page 99
3.5.2 CPA-Security from a Pseudorandom Function......Page 103
3.6 Modes of Operation and Encryption in Practice......Page 107
3.6.1 Stream Ciphers......Page 108
3.6.2 Stream-Cipher Modes of Operation......Page 110
3.6.3 Block Ciphers and Block-Cipher Modes of Operation......Page 111
3.6.4 *Nonce-Based Encryption......Page 119
Exercises......Page 122
4.1.1 Secrecy vs. Integrity......Page 128
4.1.2 Encryption vs. Message Authentication......Page 129
4.2 Message Authentication Codes (MACs) - Definitions......Page 131
4.3.1 A Fixed-Length MAC......Page 137
4.3.2 Domain Extension for MACs......Page 139
4.4.1 The Basic Construction......Page 143
4.4.2 *Proof of Security......Page 146
4.5.1 MACs from Difference-Universal Functions......Page 151
4.5.2 Instantiations......Page 154
4.6 *Information-Theoretic MACs......Page 156
4.6.1 One-Time MACs from Strongly Universal Functions......Page 157
4.6.2 One-Time MACs from Difference-Universal Functions......Page 160
4.6.3 Limitations on Information-Theoretic MACs......Page 162
Exercises......Page 163
5.1 Chosen-Ciphertext Attacks and CCA-Security......Page 168
5.1.1 Padding-Oracle Attacks......Page 169
5.1.2 Defining CCA-Security......Page 172
5.2.1 Defining Authenticated Encryption......Page 174
5.2.2 CCA Security vs. Authenticated Encryption......Page 176
5.3.1 Generic Constructions......Page 177
5.3.2 Standardized Schemes......Page 184
5.4 Secure Communication Sessions......Page 185
Exercises......Page 187
6.1 Definitions......Page 190
6.1.1 Collision Resistance......Page 191
6.2 Domain Extension: The Merkle-Damgård Transform......Page 193
6.3.1 Hash-and-MAC......Page 195
6.3.2 HMAC......Page 198
6.4 Generic Attacks on Hash Functions......Page 200
6.4.1 Birthday Attacks for Finding Collisions......Page 201
6.4.2 Small-Space Birthday Attacks......Page 202
6.4.3 *Time/Space Tradeoffs for Inverting Hash Functions......Page 205
6.5 The Random-Oracle Model......Page 210
6.5.1 The Random-Oracle Model in Detail......Page 211
6.5.2 Is the Random-Oracle Methodology Sound?......Page 215
6.6.1 Fingerprinting and Deduplication......Page 218
6.6.2 Merkle Trees......Page 219
6.6.3 Password Hashing......Page 221
6.6.4 Key Derivation......Page 222
6.6.5 Commitment Schemes......Page 223
References and Additional Reading......Page 225
Exercises......Page 226
7: Practical Constructions of Symmetric-Key Primitives......Page 230
7.1 Stream Ciphers......Page 231
7.1.1 Linear-Feedback Shift Registers......Page 232
7.1.2 Adding Nonlinearity......Page 234
7.1.3 Trivium......Page 235
7.1.4 RC4......Page 236
7.1.5 ChaCha20......Page 239
7.2 Block Ciphers......Page 240
7.2.1 Substitution-Permutation Networks......Page 242
7.2.2 Feistel Networks......Page 249
7.2.3 DES - The Data Encryption Standard......Page 251
7.2.4 3DES: Increasing the Key Length of a Block Cipher......Page 258
7.2.5 AES - The Advanced Encryption Standard......Page 261
7.2.6 *Differential and Linear Cryptanalysis......Page 263
7.3.1 Compression Functions from Block Ciphers......Page 269
7.3.2 MD5, SHA-1, and SHA-2......Page 272
7.3.3 The Sponge Construction and SHA-3 (Keccak)......Page 273
References and Additional Reading......Page 277
Exercises......Page 278
8: *Theoretical Constructions of Symmetric-Key Primitives......Page 284
8.1.1 Definitions......Page 285
8.1.2 Candidate One-Way Functions......Page 288
8.1.3 Hard-Core Predicates......Page 289
8.2 From One-Way Functions to Pseudorandomness......Page 290
8.3 Hard-Core Predicates from One-Way Functions......Page 292
8.3.2 A More Involved Case......Page 293
8.3.3 The Full Proof......Page 297
8.4.1 Pseudorandom Generators with Minimal Expansion......Page 300
8.4.2 Increasing the Expansion Factor......Page 302
8.5 Constructing Pseudorandom Functions......Page 307
8.6 Constructing (Strong) Pseudorandom Permutations......Page 312
8.7 Assumptions for Private-Key Cryptography......Page 316
8.8 Computational Indistinguishability......Page 319
References and Additional Reading......Page 321
Exercises......Page 322
III: Public-Key (Asymmetric) Cryptography......Page 326
9: Number Theory and Cryptographic Hardness Assumptions......Page 328
9.1 Preliminaries and Basic Group Theory......Page 329
9.1.1 Primes and Divisibility......Page 330
9.1.2 Modular Arithmetic......Page 332
9.1.3 Groups......Page 334
9.1.4 The Group ℤ*N......Page 338
9.1.5 *Isomorphisms and the Chinese Remainder Theorem......Page 340
9.2 Primes, Factoring, and RSA......Page 345
9.2.1 Generating Random Primes......Page 346
9.2.2 *Primality Testing......Page 348
9.2.4 The RSA Assumption......Page 354
9.2.5 *Relating the Factoring and RSA Assumptions......Page 357
9.3.1 Cyclic Groups and Generators......Page 359
9.3.2 The Discrete-Logarithm/Diffie-Hellman Assumptions......Page 362
9.3.3 Working in (Subgroups of) ℤ*p......Page 365
9.3.4 Elliptic Curves......Page 368
9.4 *Cryptographic Applications......Page 377
9.4.1 One-Way Functions and Permutations......Page 378
9.4.2 Collision-Resistant Hash Functions......Page 380
References and Additional Reading......Page 382
Exercises......Page 383
10: *Algorithms for Factoring and Computing Discrete Logarithms......Page 388
10.1 Algorithms for Factoring......Page 389
10.1.1 Pollard\'s p - 1 Algorithm......Page 390
10.1.2 Pollard\'s Rho Algorithm......Page 391
10.1.3 The Quadratic Sieve Algorithm......Page 392
10.2 Generic Algorithms for Computing Discrete Logarithms......Page 395
10.2.1 The Pohlig-Hellman Algorithm......Page 397
10.2.2 The Baby-Step/Giant-Step Algorithm......Page 399
10.2.3 Discrete Logarithms from Collisions......Page 400
10.3 Index Calculus: Computing Discrete Logarithms in ℤ*p......Page 401
10.4 Recommended Key Lengths......Page 403
References and Additional Reading......Page 404
Exercises......Page 405
11.1 Key Distribution and Key Management......Page 408
11.2 A Partial Solution: Key-Distribution Centers......Page 410
11.3 Key Exchange and the Diffie-Hellman Protocol......Page 412
11.4 The Public-Key Revolution......Page 419
References and Additional Reading......Page 421
Exercises......Page 422
12.1 Public-Key Encryption - An Overview......Page 424
12.2 Definitions......Page 427
12.2.1 Security against Chosen-Plaintext Attacks......Page 428
12.2.2 Multiple Encryptions......Page 430
12.2.3 Security against Chosen-Ciphertext Attacks......Page 435
12.3 Hybrid Encryption and the KEM/DEM Paradigm......Page 438
12.3.1 CPA-Security......Page 442
12.3.2 CCA-Security......Page 447
12.4 CDH/DDH-Based Encryption......Page 448
12.4.1 El Gamal Encryption......Page 449
12.4.2 DDH-Based Key Encapsulation......Page 453
12.4.3 *A CDH-Based KEM in the Random-Oracle Model......Page 455
12.4.4 *Chosen-Ciphertext Security and DHIES/ECIES......Page 457
12.5.1 Plain RSA Encryption......Page 459
12.5.2 Padded RSA and PKCS #1 v1.5......Page 464
12.5.3 *CPA-Secure Encryption without Random Oracles......Page 466
12.5.4 OAEP and PKCS #1 v2......Page 470
12.5.5 *A CCA-Secure KEM in the Random-Oracle Model......Page 474
12.5.6 RSA Implementation Issues and Pitfalls......Page 478
References and Additional Reading......Page 481
Exercises......Page 482
13.1 Digital Signatures - An Overview......Page 486
13.2 Definitions......Page 488
13.3 The Hash-and-Sign Paradigm......Page 490
13.4.1 Plain RSA Signatures......Page 491
13.4.2 RSA-FDH and PKCS #1 Standards......Page 493
13.5.1 Identification Schemes and Signatures......Page 498
13.5.2 The Schnorr Identification/Signature Schemes......Page 503
13.5.3 DSA and ECDSA......Page 506
13.6 Certificates and Public-Key Infrastructures......Page 508
13.7 Putting It All Together - TLS......Page 514
13.8 *Signcryption......Page 516
Exercises......Page 518
14: *Post-Quantum Cryptography......Page 522
14.1.1 Grover\'s Algorithm and Symmetric-Key Lengths......Page 523
14.1.2 Collision-Finding Algorithms and Hash Functions......Page 524
14.2 Shor\'s Algorithm and its Impact on Cryptography......Page 525
14.3 Post-Quantum Public-Key Encryption......Page 527
14.4 Post-Quantum Signatures......Page 532
14.4.1 Lamport\'s Signature Scheme......Page 533
14.4.2 Chain-Based Signatures......Page 536
14.4.3 Tree-Based Signatures......Page 540
References and Additional Reading......Page 545
Exercises......Page 546
15.1 Public-Key Encryption from Trapdoor Permutations......Page 548
15.1.1 Trapdoor Permutations......Page 549
15.1.2 Public-Key Encryption from Trapdoor Permutations......Page 550
15.2 The Paillier Encryption Scheme......Page 552
15.2.1 The Structure of ℤ*N2......Page 553
15.2.2 The Paillier Encryption Scheme......Page 555
15.2.3 Homomorphic Encryption......Page 560
15.3.1 Secret Sharing......Page 562
15.3.2 Verifiable Secret Sharing......Page 564
15.3.3 Threshold Encryption and Electronic Voting......Page 566
15.4.1 Quadratic Residues Modulo a Prime......Page 568
15.4.2 Quadratic Residues Modulo a Composite......Page 571
15.4.3 The Quadratic Residuosity Assumption......Page 575
15.4.4 The Goldwasser-Micali Encryption Scheme......Page 576
15.5.1 Computing Modular Square Roots......Page 579
15.5.2 A Trapdoor Permutation Based on Factoring......Page 584
15.5.3 The Rabin Encryption Scheme......Page 588
References and Additional Reading......Page 589
Exercises......Page 590
Index of Common Notation......Page 594
A.2 Asymptotic Notation......Page 598
A.3 Basic Probability......Page 599
A.4 The \"Birthday\" Problem......Page 604
A.5 *Finite Fields......Page 607
Appendix B: Basic Algorithmic Number Theory......Page 610
B.1.1 Basic Operations......Page 612
B.1.2 The Euclidean and Extended Euclidean Algorithms......Page 613
B.2 Modular Arithmetic......Page 614
B.2.2 Computing Modular Inverses......Page 615
B.2.3 Modular Exponentiation......Page 616
B.2.4 *Montgomery Multiplication......Page 618
B.2.5 Choosing a Uniform Group Element......Page 620
B.3.1 Group-Theoretic Background......Page 622
B.3.2 Efficient Algorithms......Page 624
Exercises......Page 625
References......Page 626
Index......Page 642