CONTENTS
1 Classical Cryptography ... 1
   1.1 Introduction: Some Simple Cryptosystems ... 1
      1.1.1 The Shift Cipher ... 3
      1.1.2 The Substitution Cipher ... 7
      1.1.3 The Affine Cipher ... 8
      1.1.4 The Vigenere Cipher ... 12
      1.1.5 The Hill Cipher ... 14
      1.1.6 The Permutation Cipher ... 18
      1.1.7 Stream Ciphers ... 20
   1.2 Cryptanalysis ... 25
      1.2.1 Cryptanalysis of the Affine Cipher ... 26
      1.2.2 Cryptanalysis of the Substitution Cipher ... 28
      1.2.3 Cryptanalysis of the Vigenere Cipher ... 31
      1.2.4 A Known Plaintext Attack on the Hill Cipher ... 37
      1.2.5 Cryptanalysis of the LFSR-based Stream Cipher ... 37
   1.3 Notes ... 39
   Exercises ... 40
2 Shannon's Theory ... 44
   2.1 Perfect Secrecy ... 44
   2.2 Entropy ... 51
   2.2.1 Huffman Encodings and Entropy ... 53
   2.3 Properties of Entropy ... 56
   2.4 Spurious Keys and Unicity Distance ... 59
   2.5 Product Cryptosystems ... 64
   2.6 Notes ... 67
   Exercises ... 67
3 The Data Encryption Standard ... 70
   3.1 Introduction ... 70
   3.2 Description of DES ... 70
      3.2.1 An Example of DES Encryption ... 79
   3.3 The DES Controversy ... 82
   3.4 DES in Practice ... 83
   3.4.1 DES Modes of Operation ... 83
   3.5 A Time-memory Trade-off ... 86
   3.6 Differential Cryptanalysis ... 89
      3.6.1 An Attack on a 3-round DES ... 93
      3.6.2 An Attack on a 6-round DES ... 98
      3.6.3 Other examples of Differential Cryptsnalysis ... 104
   3.7 Notes and References ... 110
   Exercises ... 110
4 The RSA System and Factoring ... 114
   4.1 Introduction to Public-key Cryptography ... 114
   4.2 More Number Theory ... 116
      4.2.1 The Euclidean Algorithm ... 116
      4.2.2 The Chinese Remainder Theorem ... 119
      4.2.3 Other Useful Facts ... 122
   4.3 The RSA Cryptosystem ... 124
   4.4 Implementing RSA ... 125
   4.5 Probabilistic Primality Testing ... 129
   4.6 Attacks On RSA ... 138
      4.6.1 The Decryption Exponent ... 139
      4.6.2 Partial Information Concerning Plaintext Bits ... 144
   4.7 The Rabin Cryptosystem ... 145
   4.8 Factoring Algorithms ... 150
      4.8.1 The p-1 Method ... 151
      4.8.2 Dixon's Algorithm and the Quadratic Sieve ... 153
      4.8.3 Factoring Algorithm in Practice ... 155
   4.9 Notes and References ... 156
   Exercises ... 157
5 Other Public-key Cryptosystems ... 162
   5.1 The ElGamal Cryptosystem and Discrete Logs ... 162
      5.1.1 Algorithm for the Descrete Log Problem ... 164
      5.1.2 Bit Security of Discrete Logs ... 173
   5.2 Finite Field and Elliptic Curve Systems ... 177
      5.2.1 Galois Fields ... 180
      5.2.2 Elliptic Curves ... 184
   5.3 The Merkle-Hellman Knapsack System ... 191
   5.4 The McEliece System ... 194
   5.5 Notes and References ... 199
   Exercises ... 200
6 Signature Schemes ... 203
   6.1 Introduction ... 203
   6.2 the ElGamal Signature Scheme ... 206
   6.3 The Digital Signature Standard ... 210
   6.4 One-Time Signatures ... 214
   6.5 Undeniable Signatures ... 218
   6.6 Fail-stop Signatures ... 225
   6.7 Notes and References ... 230
   Exercises ... 231
7 Hash Functions ... 233
   7.1 Signatures and Hash Functions ... 233
   7.2 Collision-free Hash Functions ... 234
   7.3 The Birthday Attack ... 237
   7.4 A Discrete Log Hash Function ... 239
   7.5 Extending Hash Functions ... 242
   7.6 Hash Functions From Cryptosystems ... 247
   7.7 The MD4 Hash Function ... 248
   7.8 Timestamping ... 254
   7.9 Notes and References ... 256
   Exercises ... 256
8 Key Distribution and Key Agreement ... 259
   8.1 Introduction ... 259
   8.2 Key Predistribution ... 261
      8.2.1 Blom's Scheme ... 261
      8.2.2 Diffie-Hellman Key Predistribution ... 264
   8.3 Kerboros ... 268
   8.4 Diffie-Hellman Key Exchange ... 271
      8.4.1 The Station-to-station Protocol ... 272
      8.4.2 MTI Key Agreement Protocols ... 274
      8.4.3 Key Agreement Using Self-certifying Keys ... 277
   8.5 Notes and References ... 281
   Exercises ... 281
9 Identification Schemes ... 283
   9.1 Introduction ... 283
   9.2 The Schnorr Identification Scheme ... 285
   9.3 The Okamoto Identification Scheme ... 291
   9.4 The Guillou-Quisquater Identification Scheme ... 296
      9.4.1 Identitv-based Identification Schemes ... 300
   9.5 Converting Identification to Signature Schemes ... 302
   9.6 Notes and References ... 302
   Exercises ... 303
10 Authentication Codes ... 305
   10.1 Introduction ... 305
   10.2 Computing Deception Probabilities ... 307
   10.3 Combinatorial Bounds ... 312
      10.3.1 Orthogonal Arrays ... 315
      10.3.2 Constructions and Bounds for OAs ... 316
      10.3.3 Characterizations of Authentication Codes ... 320
   10.4 Entropy Bounds ... 322
   10.5 Notes and References ... 324
   Exercises ... 325
11 Secret Sharing Schemes ... 327
   11.1 Introduction: The Shamir Threshold Scheme ... 327
   11.2 Access Structures and General Secret Sharing ... 333
   11.3 The Monotone Circuit Construction ... 334
   11.4 Formal Definitions ... 339
   11.5 Information Rate ... 343
   11.6 The Brichell Vector Space Construction ... 345
   11.7 An Upper Bound on the Information Rate ... 350
   11.8 The Decomposition Construction ... 355
   11.9 Notes and References ... 359
   Exercises ... 359
12 Pseudo-random Number Generation ... 361
   12.1 Introduction and Examples ... 361
   12.2 Indistinguishable Probability Distrubutions ... 365
      12.2.1 Next Bit Predictors ... 367
   12.3 The Blum-Blum-Shub Generator ... 372
      12.3.1 Security of the BBS Generator ... 375
   12.4 Probabilistic Encryption ... 380
   12.5 Notes and References ... 384
   Exercises ... 385
13 Zero-knowledge Proofs ... 387
   13.1 Interactive Proof Systems ... 387
   13.2 Perfect Zero-knowledge Proofs ... 390
   13.3 Bit Commitments ... 400
   13.4 Computational Zero-knowledge Proofs ... 402
   13.5 Zero-knowledge Arguments ... 407
   13.6 Notes and References ... 409
   Exercises ... 410
Further Reading ... 412
Bibliography ... 413
Index ... 428