A Course in Cryptography

Cover......Page 1
Title page......Page 4
Contents......Page 8
Preface......Page 14
0.1. Installation......Page 20
0.3. Browser Notebooks......Page 21
0.4. Computations with SageMath......Page 22
1.1. Sets, Relations and Functions......Page 26
1.2. Combinatorics......Page 33
1.3. Computational Complexity......Page 35
1.4. Discrete Probability......Page 38
1.5. Random Numbers......Page 42
1.6. Summary......Page 46
Exercises......Page 47
Chapter 2. Encryption Schemes and Definitions of Security......Page 50
2.1. Encryption Schemes......Page 51
2.2. Perfect Secrecy......Page 54
2.3. Computational Security......Page 55
2.4. Indistinguishable Encryptions......Page 56
2.5. Eavesdropping Attacks......Page 58
2.6. Chosen Plaintext Attacks......Page 60
2.7. Chosen Ciphertext Attacks......Page 62
2.8. Pseudorandom Generators......Page 64
2.9. Pseudorandom Functions......Page 67
2.10. Block Ciphers and Operation Modes......Page 71
Exercises......Page 77
3.1. Integers......Page 80
3.2. Congruences......Page 84
3.3. Modular Exponentiation......Page 86
Exercises......Page 88
4.1. Groups......Page 92
4.2. Rings and Fields......Page 100
4.3. Finite Fields......Page 101
4.4. Linear and Affine Maps......Page 111
Exercises......Page 116
5.1. Constructions of Block Ciphers......Page 120
5.2. Advanced Encryption Standard......Page 123
Exercises......Page 130
6.1. Definition of Stream Ciphers......Page 134
6.2. Linear Feedback Shift Registers......Page 138
6.3. RC4......Page 147
6.4. Salsa20 and ChaCha20......Page 149
Exercises......Page 154
7.1. Definitions and Security Requirements......Page 156
7.2. Applications of Hash Functions......Page 158
7.3. Merkle-Damgård Construction......Page 159
7.4. SHA-1......Page 161
7.5. SHA-2......Page 164
7.6. SHA-3......Page 165
Exercises......Page 168
8.1. Definitions and Security Requirements......Page 170
8.2. CBC MAC......Page 173
8.3. HMAC......Page 175
8.4. Authenticated Encryption......Page 176
Exercises......Page 180
9.1. Public-Key Cryptosystems......Page 182
9.2. Plain RSA......Page 185
9.3. RSA Security......Page 187
9.4. Generation of Primes......Page 189
9.5. Efficiency of RSA......Page 192
9.6. Padded RSA......Page 194
9.7. Factoring......Page 196
Exercises......Page 201
Chapter 10. Key Establishment......Page 204
10.2. Key Exchange Protocols......Page 205
10.3. Diffie-Hellman Key Exchange......Page 207
10.4. Diffie-Hellman using Subgroups of zz _{��}*......Page 209
10.5. Discrete Logarithm......Page 211
10.6. Key Encapsulation......Page 213
10.7. Hybrid Encryption......Page 216
Exercises......Page 219
11.1. Definitions and Security Requirements......Page 222
11.2. Plain RSA Signature......Page 224
11.3. Probabilistic Signature Scheme......Page 225
Exercises......Page 229
12.1. Weierstrass Equations and Elliptic Curves......Page 232
12.2. Elliptic Curve Diffie-Hellman......Page 241
12.3. Efficiency and Security of Elliptic Curve Cryptography......Page 242
12.4. Elliptic Curve Factoring Method......Page 243
Exercises......Page 246
Chapter 13. Quantum Computing......Page 248
13.1. Quantum Bits......Page 249
13.2. Multiple Qubit Systems......Page 253
13.3. Quantum Algorithms......Page 254
13.4. Quantum Fourier Transform......Page 260
13.5. Shor’s Factoring Algorithm......Page 261
13.6. Quantum Key Distribution......Page 267
Exercises......Page 270
Chapter 14. Lattice-based Cryptography......Page 272
14.1. Lattices......Page 273
14.2. Lattice Algorithms......Page 279
14.3. GGH Cryptosystem......Page 288
14.4. NTRU......Page 290
14.5. Learning with Errors......Page 295
Exercises......Page 301
Chapter 15. Code-based Cryptography......Page 304
15.1. Linear Codes......Page 305
15.2. Bounds on Codes......Page 309
15.3. Goppa Codes......Page 314
15.4. McEliece Cryptosystem......Page 322
15.5. Summary......Page 328
Exercises......Page 329
Bibliography......Page 332
Index......Page 338
Back cover......Page 344