Table of contents for Introduction to modern cryptography : principles and protocols / Jonathan Katz and Yehuda Lindell.

Bibliographic record and links to related information available from the Library of Congress catalog.

Note: Contents data are machine generated based on pre-publication provided by the publisher. Contents may have variations from the printed book or be incomplete or contain other coding.

```
Contents
Preface iii
I Introduction and Classical Cryptography 1
1 Introduction 3
1.1 Cryptography and Modern Cryptography . . . . . . . . . . . 3
1.2 The Setting of Private-Key Encryption . . . . . . . . . . . . 4
1.3 Historical Ciphers and Their Cryptanalysis . . . . . . . . . . 9
1.4 The Basic Principles of Modern Cryptography . . . . . . . . 18
1.4.1 Principle 1 { Formulation of Exact De
nitions . . . . 18
1.4.2 Principle 2 { Reliance on Precise Assumptions . . . . 24
1.4.3 Principle 3 { Rigorous Proofs of Security . . . . . . . 26
References and Additional Reading . . . . . . . . . . . . . . . . . 27
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2 Perfectly-Secret Encryption 29
2.1 De
nitions and Basic Properties . . . . . . . . . . . . . . . . 29
2.2 The One-Time Pad (Vernam's Cipher) . . . . . . . . . . . . 34
2.3 Limitations of Perfect Secrecy . . . . . . . . . . . . . . . . . 37
2.4 * Shannon's Theorem . . . . . . . . . . . . . . . . . . . . . . 38
2.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
References and Additional Reading . . . . . . . . . . . . . . . . . 41
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
II Private-Key (Symmetric) Cryptography 45
3 Private-Key Encryption and Pseudorandomness 47
3.1 A Computational Approach to Cryptography . . . . . . . . . 47
3.1.1 The Basic Idea of Computational Security . . . . . . . 48
3.1.2 Ecient Algorithms and Negligible Success Probability 54
3.1.3 Proofs by Reduction . . . . . . . . . . . . . . . . . . . 58
3.2 A De
nition of Computationally-Secure Encryption . . . . . 60
3.2.1 A De
nition of Security for Encryption . . . . . . . . 61
3.2.2 * Properties of the De
nition . . . . . . . . . . . . . . 64
3.3 Pseudorandomness . . . . . . . . . . . . . . . . . . . . . . . . 69
3.4 Constructing Secure Encryption Schemes . . . . . . . . . . . 72
3.4.1 A Secure Fixed-Length Encryption Scheme . . . . . . 72
3.4.2 Handling Variable-Length Messages . . . . . . . . . . 76
3.4.3 Stream Ciphers and Multiple Encryptions . . . . . . . 77
3.5 Security Against Chosen-Plaintext Attacks (CPA) . . . . . . 82
3.6 Constructing CPA-Secure Encryption Schemes . . . . . . . . 86
3.6.1 Pseudorandom Functions . . . . . . . . . . . . . . . . 86
3.6.2 CPA-Secure Encryption from Pseudorandom Functions 89
3.6.3 Pseudorandom Permutations and Block Ciphers . . . 94
3.6.4 Modes of Operation . . . . . . . . . . . . . . . . . . . 96
3.7 Security Against Chosen-Ciphertext Attacks (CCA) . . . . . 103
References and Additional Reading . . . . . . . . . . . . . . . . . 105
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
4 Message Authentication Codes and Collision-Resistant Hash
Functions 111
4.1 Secure Communication and Message Integrity . . . . . . . . 111
4.2 Encryption vs. Message Authentication . . . . . . . . . . . . 112
4.3 Message Authentication Codes { De
nitions . . . . . . . . . 113
4.4 Constructing Secure Message Authentication Codes . . . . . 118
4.5 CBC-MAC . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
4.6 Collision-Resistant Hash Functions . . . . . . . . . . . . . . . 127
4.6.1 De
ning Collision Resistance . . . . . . . . . . . . . . 128
4.6.2 Weaker Notions of Security for Hash Functions . . . . 130
4.6.3 A Generic \Birthday" Attack . . . . . . . . . . . . . . 130
4.6.4 The Merkle-Damgard Transform . . . . . . . . . . . . 133
4.6.5 Collision-Resistant Hash Functions in Practice . . . . 135
4.7 * NMAC and HMAC . . . . . . . . . . . . . . . . . . . . . . 137
4.7.1 Nested MAC (NMAC) . . . . . . . . . . . . . . . . . . 138
4.7.2 HMAC . . . . . . . . . . . . . . . . . . . . . . . . . . 141
4.8 * Constructing CCA-Secure Encryption Schemes . . . . . . . 143
4.9 * Obtaining Privacy and Message Authentication . . . . . . 148
References and Additional Reading . . . . . . . . . . . . . . . . . 154
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
5 Pseudorandom Permutations in Practice: Block Ciphers 159
5.1 Substitution-Permutation Networks . . . . . . . . . . . . . . 162
5.2 Feistel Networks . . . . . . . . . . . . . . . . . . . . . . . . . 170
5.3 DES { The Data Encryption Standard . . . . . . . . . . . . 173
5.3.1 The Design of DES . . . . . . . . . . . . . . . . . . . . 173
5.3.2 Attacks on Reduced-Round Variants of DES . . . . . 176
5.3.3 The Security of DES . . . . . . . . . . . . . . . . . . . 179
5.4 Increasing the Key Size of a Block Cipher . . . . . . . . . . . 181
5.5 AES { The Advanced Encryption Standard . . . . . . . . . . 184
5.6 Dierential and Linear Cryptanalysis { A Brief Look . . . . 187
Additional Reading and References . . . . . . . . . . . . . . . . . 188
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
6 * Theoretical Constructions of Pseudorandom Objects 193
6.1 One-Way Functions . . . . . . . . . . . . . . . . . . . . . . . 194
6.1.1 De
nitions . . . . . . . . . . . . . . . . . . . . . . . . 194
6.1.2 Candidate One-Way Functions . . . . . . . . . . . . . 197
6.1.3 Hard-Core Predicates . . . . . . . . . . . . . . . . . . 198
6.2 Overview: From One-Way Functions to Pseudorandomness . 200
6.3 A Hard-Core Predicate for Any One-Way Function . . . . . 202
6.3.1 A Simple Case . . . . . . . . . . . . . . . . . . . . . . 202
6.3.2 A More Involved Case . . . . . . . . . . . . . . . . . . 204
6.3.3 The Full Proof . . . . . . . . . . . . . . . . . . . . . . 207
6.4 Constructing Pseudorandom Generators . . . . . . . . . . . . 213
6.4.1 Pseudorandom Generators with Minimal Expansion . 213
6.4.2 Increasing the Expansion Factor . . . . . . . . . . . . 214
6.5 Constructing Pseudorandom Functions . . . . . . . . . . . . 220
6.6 Constructing (Strong) Pseudorandom Permutations . . . . . 224
6.7 Necessary Assumptions for Private-Key Cryptography . . . . 226
6.8 A Digression { Computational Indistinguishability . . . . . . 232
6.8.1 Pseudorandomness and Pseudorandom Generators . . 233
6.8.2 Multiple Samples . . . . . . . . . . . . . . . . . . . . . 234
References and Additional Reading . . . . . . . . . . . . . . . . . 237
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237
III Public-Key (Asymmetric) Cryptography 241
7 Number Theory and Cryptographic Hardness Assumptions 243
7.1 Preliminaries and Basic Group Theory . . . . . . . . . . . . 245
7.1.1 Primes and Divisibility . . . . . . . . . . . . . . . . . . 246
7.1.2 Modular Arithmetic . . . . . . . . . . . . . . . . . . . 248
7.1.3 Groups . . . . . . . . . . . . . . . . . . . . . . . . . . 250
7.1.4 The Group ZN . . . . . . . . . . . . . . . . . . . . . . 254
7.1.5 * Isomorphisms and the Chinese Remainder Theorem 256
7.2 Primes, Factoring, and RSA . . . . . . . . . . . . . . . . . . 261
7.2.1 Generating Random Primes . . . . . . . . . . . . . . . 262
7.2.2 * Primality Testing . . . . . . . . . . . . . . . . . . . . 265
7.2.3 The Factoring Assumption . . . . . . . . . . . . . . . 271
7.2.4 The RSA Assumption . . . . . . . . . . . . . . . . . . 271
7.3 Assumptions in Cyclic Groups . . . . . . . . . . . . . . . . . 273
7.3.1 Cyclic Groups and Generators . . . . . . . . . . . . . 274
7.3.2 The Discrete Logarithm and Die-Hellman Assumptions
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 277
7.3.3 Working in (Subgroups of) Zp . . . . . . . . . . . . . . 281
7.3.4 * Elliptic Curve Groups . . . . . . . . . . . . . . . . . 282
7.4 Cryptographic Applications of Number-Theoretic Assumptions 286
7.4.1 One-Way Functions and Permutations . . . . . . . . . 286
7.4.2 Constructing Collision-Resistant Hash Functions . . . 289
References and Additional Reading . . . . . . . . . . . . . . . . . 292
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293
8 * Factoring and Computing Discrete Logarithms 297
8.1 Algorithms for Factoring . . . . . . . . . . . . . . . . . . . . 297
8.1.1 Pollard's p ?? 1 Method . . . . . . . . . . . . . . . . . . 298
8.1.2 Pollard's Rho Method . . . . . . . . . . . . . . . . . . 300
8.1.3 The Quadratic Sieve Algorithm . . . . . . . . . . . . . 302
8.2 Algorithms for Computing Discrete Logarithms . . . . . . . 305
8.2.1 The Baby-Step/Giant-Step Algorithm . . . . . . . . . 307
8.2.2 The Pohlig-Hellman Algorithm . . . . . . . . . . . . . 308
8.2.3 The Discrete Logarithm Problem in ZN . . . . . . . . 310
8.2.4 The Index Calculus Method . . . . . . . . . . . . . . . 311
References and Additional Reading . . . . . . . . . . . . . . . . . 313
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313
9 Private-Key Management and the Public-Key Revolution 315
9.1 Limitations of Private-Key Cryptography . . . . . . . . . . . 315
9.1.1 The Key-Management Problem . . . . . . . . . . . . . 315
9.1.2 A Partial Solution { Key Distribution Centers . . . . 317
9.2 The Public-Key Revolution . . . . . . . . . . . . . . . . . . . 320
9.3 Die-Hellman Key Exchange . . . . . . . . . . . . . . . . . . 323
References and Additional Reading . . . . . . . . . . . . . . . . . 329
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 330
10 Public-Key Encryption 331
10.1 Public-Key Encryption { An Overview . . . . . . . . . . . . 331
10.2 De
nitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 334
10.2.1 Security against Chosen-Plaintext Attacks . . . . . . . 335
10.2.2 Multiple Encryptions . . . . . . . . . . . . . . . . . . . 338
10.3 Hybrid Encryption . . . . . . . . . . . . . . . . . . . . . . . . 344
10.4 RSA Encryption . . . . . . . . . . . . . . . . . . . . . . . . . 353
10.4.1 \Textbook RSA" and its Insecurity . . . . . . . . . . . 353
10.4.2 Attacks on RSA . . . . . . . . . . . . . . . . . . . . . 356
10.4.3 Padded RSA . . . . . . . . . . . . . . . . . . . . . . . 359
10.5 The El Gamal Encryption Scheme . . . . . . . . . . . . . . . 361
10.6 Security Against Chosen-Ciphertext Attacks . . . . . . . . . 366
10.7 * Trapdoor Permutations . . . . . . . . . . . . . . . . . . . . 370
10.7.1 De
nition . . . . . . . . . . . . . . . . . . . . . . . . . 371
10.7.2 Public-Key Encryption from Trapdoor Permutations . 372
References and Additional Reading . . . . . . . . . . . . . . . . . 375
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 376
11 * Additional Public-Key Encryption Schemes 381
11.1 The Goldwasser-Micali Encryption Scheme . . . . . . . . . . 382
11.1.1 Quadratic Residues Modulo a Prime . . . . . . . . . . 382
11.1.2 Quadratic Residues Modulo a Composite . . . . . . . 385
11.1.3 The Quadratic Residuosity Assumption . . . . . . . . 389
11.1.4 The Goldwasser-Micali Encryption Scheme . . . . . . 390
11.2 The Rabin Encryption Scheme . . . . . . . . . . . . . . . . . 393
11.2.1 Computing Modular Square Roots . . . . . . . . . . . 394
11.2.2 A Trapdoor Permutation Based on Factoring . . . . . 398
11.2.3 The Rabin Encryption Scheme . . . . . . . . . . . . . 402
11.3 The Paillier Encryption Scheme . . . . . . . . . . . . . . . . 404
11.3.1 The Structure of ZN2 . . . . . . . . . . . . . . . . . . 405
11.3.2 The Paillier Encryption Scheme . . . . . . . . . . . . . 407
11.3.3 Homomorphic Encryption . . . . . . . . . . . . . . . . 412
References and Additional Reading . . . . . . . . . . . . . . . . . 413
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 414
12 Digital Signature Schemes 417
12.1 Digital Signatures { An Overview . . . . . . . . . . . . . . . 417
12.2 De
nitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 419
12.3 RSA Signatures . . . . . . . . . . . . . . . . . . . . . . . . . 422
12.3.1 \Textbook RSA" and its Insecurity . . . . . . . . . . . 422
12.3.2 Hashed RSA . . . . . . . . . . . . . . . . . . . . . . . 424
12.4 The \Hash-and-Sign" Paradigm . . . . . . . . . . . . . . . . 425
12.5 Lamport's One-Time Signature Scheme . . . . . . . . . . . . 428
12.6 * Signatures from Collision-Resistant Hashing . . . . . . . . 432
12.6.1 \Chain-Based" Signatures . . . . . . . . . . . . . . . . 432
12.6.2 \Tree-Based" Signatures . . . . . . . . . . . . . . . . . 436
12.7 The Digital Signature Standard . . . . . . . . . . . . . . . . 441
12.8 Certi
cates and Public-Key Infrastructures . . . . . . . . . . 442
References and Additional Reading . . . . . . . . . . . . . . . . . 449
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 450
13 Public-Key Cryptosystems in the Random Oracle Model 453
13.1 The Random Oracle Methodology . . . . . . . . . . . . . . . 454
13.1.1 The Random Oracle Model in Detail . . . . . . . . . . 455
13.1.2 Is the Random Oracle Methodology Sound? . . . . . . 461
13.2 Public-Key Encryption in the Random Oracle Model . . . . 464
13.2.1 Security Against Chosen-Plaintext Attacks . . . . . . 464
13.2.2 Security Against Chosen-Ciphertext Attacks . . . . . 468
13.2.3 OAEP . . . . . . . . . . . . . . . . . . . . . . . . . . . 473
13.3 RSA Signatures in the Random Oracle Model . . . . . . . . 475
References and Additional Reading . . . . . . . . . . . . . . . . . 479
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 480
Common Notation 483
References 487
A Mathematical Background 497
A.1 Identities and Inequalities . . . . . . . . . . . . . . . . . . . . 497
A.2 Asymptotic Notation . . . . . . . . . . . . . . . . . . . . . . 497
A.3 Basic Probability . . . . . . . . . . . . . . . . . . . . . . . . 498
A.4 The \Birthday" Problem . . . . . . . . . . . . . . . . . . . . 500
B Supplementary Algorithmic Number Theory 503
B.1 Integer Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . 505
B.1.1 Basic Operations . . . . . . . . . . . . . . . . . . . . . 505
B.1.2 The Euclidean and Extended Euclidean Algorithms . 506
B.2 Modular Arithmetic . . . . . . . . . . . . . . . . . . . . . . . 508
B.2.1 Basic Operations . . . . . . . . . . . . . . . . . . . . . 508
B.2.2 Computing Modular Inverses . . . . . . . . . . . . . . 508
B.2.3 Modular Exponentiation . . . . . . . . . . . . . . . . . 509
B.2.4 Choosing a Random Group Element . . . . . . . . . . 511
B.3 * Finding a Generator of a Cyclic Group . . . . . . . . . . . 516
B.3.1 Group-Theoretic Background . . . . . . . . . . . . . . 516
B.3.2 Ecient Algorithms . . . . . . . . . . . . . . . . . . . 517
References and Additional Reading . . . . . . . . . . . . . . . . . 519
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 519
```

Library of Congress Subject Headings for this publication:

Computer security.
Cryptography.