Introduction to cryptography with open-source software

Once the privilege of a secret few, cryptography is now taught at universities around the world. Introduction to Cryptography with Open-Source Software illustrates algorithms and cryptosystems using examples and the open-source computer algebra system of Sage. The author, a noted educator in the field, provides a highly practical learning experience by progressing at a gentle pace, keeping mathematics at a manageable level, and including numerous end-of-chapter exercises.

Focusing on the cryptosystems themselves rather than the means of breaking them, the book first explores when and how the methods of modern cryptography can be used and misused. It then presents number theory and the algorithms and methods that make up the basis of cryptography today. After a brief review of "classical" cryptography, the book introduces information theory and examines the public-key cryptosystems of RSA and Rabin's cryptosystem. Other public-key systems studied include the El Gamal cryptosystem, systems based on knapsack problems, and algorithms for creating digital signature schemes.

The second half of the text moves on to consider bit-oriented secret-key, or symmetric, systems suitable for encrypting large amounts of data. The author describes block ciphers (including the Data Encryption Standard), cryptographic hash functions, finite fields, the Advanced Encryption Standard, cryptosystems based on elliptical curves, random number generation, and stream ciphers. The book concludes with a look at examples and applications of modern cryptographic systems, such as multi-party computation, zero-knowledge proofs, oblivious transfer, and voting protocols.

Author Notes

Alasdair McAndrew is a senior lecturer in the School of Engineering and Science at Victoria University in Melbourne, Australia.

Preface	p. xv
1 Introduction to cryptography	p. 1
1.1 Hiding information: Confidentiality	p. 1
1.2 Some basic definitions	p. 3
1.3 Attacks on a cryptosystem	p. 5
1.4 Some cryptographic problems	p. 7
1.5 Cryptographic protocols	p. 8
1.6 Some simple ciphers	p. 12
1.7 Cryptography and computer security	p. 18
1.8 Glossary	p. 19
Exercises	p. 20
2 Basic number theory	p. 23
2.1 Introduction	p. 23
2.2 Some basic definitions	p. 23
2.3 Some number theoretic calculations	p. 27
2.4 Primality testing44
2.5 Glossary	p. 47
Exercises	p. 48
3 Classical cryptosystems	p. 55
3.1 Introduction	p. 55
3.2 The Caesar cipher	p. 56
3.3 Translation ciphers	p. 57
3.4 Transposition ciphers	p. 58
3.5 The Vigenere cipher	p. 61
3.6 The one-time pad	p. 65
3.7 Permutation ciphers	p. 65
3.8 Matrix ciphers	p. 66
3.9 Glossary	p. 71
Exercises	p. 71
4 Introduction to information theory	p. 79
4.1 Entropy and uncertainty	p. 79
4.2 Perfect secrecy	p. 82
4.3 Estimating the entropy of English	p. 84
4.4 Unicity distance	p. 88
4.5 Glossary	p. 89
Exercises	p. 89
5 Public-key cryptosystems based on factoring	p. 93
5.1 Introduction	p. 93
5.2 The RSA cryptosystem	p. 93
5.3 Attacks against RSA	p. 99
5.4 RSA in Sage	p. 101
5.5 Rabin's cryptosystem	p. 104
5.6 Rabin's cryptosystem in Sage	p. 109
5.7 Some notes on security	p. 111
5.8 Factoring	p. 112
5.9 Glossary	p. 115
Exercises	p. 115
6 Public-key cryptosystems based on logarithms and knap-sacks	p. 119
6.1 El Gamal's cryptosystem	p. 119
6.2 El Gamal in Sage	p. 122
6.3 Computing discrete logarithms	p. 125
6.4 Diffie-Hellman key exchange	p. 127
6.5 Knapsack cryptosystems	p. 128
6.6 Breaking the knapsack	p. 137
6.7 Glossary	p. 139
Exercises	p. 140
7 Digital signatures	p. 145
7.1 Introduction	p. 145
7.2 RSA signature scheme	p. 147
7.3 Rabin digital signatures	p. 150
7.4 The Ei Gamal digital signature scheme	p. 152
7.5 The Digital Signature Standard	p. 157
7.6 Glossary	p. 161
Exercises	p. 162
8 Block ciphers and the data encryption standard	p. 167
8.1 Block ciphers	p. 167
8.2 Some definitions	p. 169
8.3 Substitution/permutation ciphers	p. 171
8.4 Modes of encryption	p. 173
8.5 Exploring modes of encryption	p. 178
8.6 The Data Encryption Standard	p. 182
8.7 Feistel ciphers	p. 182
8.8 Simplified DES: sDES	p. 183
8.9 The DES algorithm	p. 190
8.10 Security of S-boxes	p. 196
8.11 Security of DES	p. 204
8.12 Using DES	p. 205
8.13 Experimenting with DES	p. 206
8.14 Lightweight ciphers	p. 207
8.15 Glossary	p. 211
Exercises	p. 212
9 Finite fields	p. 215
9.1 Groups and rings	p. 215
9.2 Introduction to fields	p. 219
9.3 Fundamental algebra of finite fields	p. 222
9.4 Polynomials mod 2	p. 224
9.5 A field of order 8	p. 226
9.6 Other fields GF(2n)	p. 229
9.7 Multiplication and inversion	p. 230
9.8 Multiplication without power tables	p. 234
9.9 Glossary	p. 238
Exercises	p. 238
10 The Advanced Encryption Standard	p. 245
10.1 Introduction and some history	p. 245
10.2 Basic structure	p. 246
10.3 The layers in detail	p. 248
10.4 Decryption	p. 252
10.5 Experimenting with AES	p. 256
10.6 A simplified Rijndael	p. 258
10.7 Security of the AES	p. 264
10.8 Glossary	p. 265
Exercises	p. 265
11 Hash functions	p. 267
11.1 Uses of hash functions	p. 268
11.2 Security of hash functions	p. 270
11.3 Constructing a hash function	p. 271
11.4 Provably secure hash functions	p. 281
11.5 New hash functions	p. 285
11.6 Message authentication codes	p. 287
11.7 Using a MAC	p. 288
11.8 Glossary	p. 289
Exercises	p. 289
12 Elliptic curves and cryptosystems	p. 295
12.1 Basic definitions	p. 295
12.2 The group on an elliptic curve	p. 300
12.3 Background and history	p. 307
12.4 Multiplication	p. 308
12.5 Elliptic curve cryptosystems	p. 309
12.6 Elliptic curve signature schemes	p. 316
12.7 Elliptic curves over binary fields	p. 317
12.8 Pairing-based cryptography	p. 318
12.9 Exploring pairings in Sage	p. 323
12.10 Glossary	p. 326
Exercises	p. 327
13 Random numbers and stream ciphers	p. 333
13.1 Introduction	p. 333
13.2 Pseudo-random number generators	p. 334
13.3 Some cryptographically strong generators	p. 338
13.4 The shrinking generator	p. 341
13.5 Isaac and Fortuna	p. 344
13.6 Stream ciphers	p. 346
13.7 RC4	p. 348
13.8 The Blum-Goldwasser cryptosystem	p. 351
13.9 Glossary	p. 355
Exercises	p. 356
14 Advanced applications and protocols	p. 361
14.1 Secure multi-party computation	p. 361
14.2 Zero knowledge proofs	p. 366
14.3 Oblivious transfer	p. 371
14.4 Digital cash	p. 374
14.5 Voting protocols	p. 382
14.6 Glossary	p. 388
Exercises	p. 389
Appendix A Introduction to Sage	p. 395
A.l Obtaining and installing Sage	p. 395
A.2 Starting with Sage	p. 396
A.3 Basic usage	p. 396
A.4 Tab completion and help	p. 402
A.5 Basic programming	p. 404
A.6 A programming example	p. 407
Exercises	p. 408
Appendix B Advanced computational number theory	p. 411
B.1 The quadratic sieve	p. 411
B.2 The Aks primality test	p. 415
B.3 Methods of computing discrete logarithms	p. 417
Exercises	p. 423
Bibliography	p. 425
Index	p. 435

Available:*

On Order

Summary

Summary

Author Notes

Table of Contents