1 History and Basic Cryptographic Concepts ................ 1
1.1 Terminology ......................................... 1
1.2 Classical Ciphers .................................. 13
1.3 Classification of Attacks .......................... 25
2 Protocols, Discrete Log, and Diffie-Hellman ............ 33
2.1 Cryptographic Protocols ............................ 33
2.2 The Discrete Log Problem ........................... 39
2.3 Exponentiation Ciphers and Diffie-Hellman .......... 47
3 Public-Key Cryptography ................................ 53
3.1 One-Way Functions .................................. 53
3.2 Public-Key Cryptosystems and RSA ................... 60
3.3 ElGamal Cryptosystems .............................. 67
3.4 Symmetric vs. Asymmetric Cryptosystems ............. 73
3.5 Secret History of Public-Key Cryptography .......... 77
4 Probabilistic Primality Tests .......................... 79
4.1 Introduction ....................................... 79
4.2 Pseudoprimes and Carmichael Numbers ................ 81
4.3 Solovay-Strassen Test .............................. 84
4.4 Miller-Selfridge-Rabin Test ........................ 87
5 Factoring .............................................. 93
5.1 Universal Exponent Method .......................... 93
5.2 Pollard's p - 1 Method ............................. 96
5.3 Lenstra's Elliptic Curve Method .................... 99
5.4 Multipolynomial Quadratic Sieve ................... 104
5.5 The Number Field Sieve ............................ 108
6 Security of RSA ....................................... 111
6.1 Implementation Attacks ............................ 111
6.2 Exponent Attacks .................................. 115
6.3 Strong Moduli ..................................... 120
6.4 Generation of Random Primes ....................... 124
7 Authentication ........................................ 127
7.1 Identification, Impersonation, and Signatures ..... 127
7.2 Digital Signature Schemes ......................... 135
7.3 Digital Cash and Electronic Commerce .............. 143
8 Key Management ........................................ 153
8.1 Secret Sharing .................................... 153
8.2 Key Establishment ................................. 160
8.3 Public-Key Infrastructure (PKI) ................... 173
9 Applications and the Future ........................... 179
9.1 Secrecy and Authentication ........................ 179
9.2 Other Threats to System Security .................. 185
9.3 Wireless Security ................................. 190
9.4 Smart Cards and Biometrics ........................ 198
Appendix A: Letter Frequency Analysis ................. 203
Appendix B: Elementary Complexity Theory .............. 205
Appendix C: Fundamental Facts ......................... 212
Solutions to Odd-Numbered Exercises ................... 224
Bibliography .......................................... 249
List of Symbols ....................................... 267
Index ................................................. 268
|
