You are here

The Mathematics of Secrets: Cryptography from Caesar Ciphers to Digital Encryption

Joshua Holden
Princeton University Press
Publication Date: 
Number of Pages: 
[Reviewed by
Mark Hunacek
, on

Cryptography is a great course to teach at the undergraduate level because it combines beautiful mathematics with a subject matter that most people seem to find inherently interesting. The allure of cryptography has led to a proliferation of books on the subject, ranging from fairly mathematics-oriented texts that are intended for an upper-level audience of mathematics majors (e.g., Introduction to Mathematical Cryptography by Hoffstein, Pipher and Silverman) to books that are comprehensible to a general reader (e.g., Cyptology: Classical and Modern with Maplets by Klima and Sigmon) and which focus on history and interesting stories. The book under review is, on this scale, somewhere in the middle; it is intended to be comprehensible to non-majors, but it does address some fairly sophisticated mathematics.

The author describes the prerequisites for the book as “high school algebra and a willingness to think really hard about it. There’s no trigonometry here, no calculus, no differential equations.” I think this is generally true, with some mild caveats. First, calculus actually does appear briefly in the book, in a section on elliptic curves, but the appearance is quick and can easily be skipped. Second, the quoted statement, notwithstanding the “think really hard about it” qualification, may underestimate the extent to which some real mathematics is discussed here. Based on my experiences teaching general-education audiences at Iowa State University, for example, I think that many of these students will have more difficulty with the mathematics than the quoted statement might suggest.

This isn’t the fault of the author, who has taken pains to make the material as clear as possible while remaining honest about it. The fact is, the author wants to discuss some real mathematics, and a great many non-majors who don’t have an affinity for mathematics might find the material heavy going. People whose idea of a mathematical challenge is using the quadratic formula might be taken aback by concepts such as Fermat’s Little Theorem or elliptic curves, no matter how substantial the expository skills of the author.

The book begins with the simplest kind of ciphers, based on substitution, in chapter 1 and then generalizes this to polyalphabetic substitution ciphers in chapter 2. Subsequent chapters discuss transposition ciphers, stream ciphers, ciphers based on exponentiation, and various public-key ciphers (RSA, ElGamal, and elliptic curve ciphers). Of course, these are broad categories, and within each one, the author discusses a number of different ciphers, giving both interesting historical discussions and mathematical analysis. A final chapter is entitled “The Future of Cryptography” and discusses, among other issues, quantum computing and quantum cryptography.

The mathematics necessary to understand these ideas is developed as necessary. This includes basic divisibility theory (including the Euclidean algorithm), modular arithmetic (including Fermat’s little theorem, the Euler phi function, and discrete logarithms), permutations, basic probability and statistics, and some elementary theory of elliptic curves.

There is also a lot of interesting stuff at the end of the book, including about 40 pages of detailed notes for each chapter, an annotated list of books suggested for further reading, and, in addition, an extensive bibliography. I thought the “Suggestions for Further Reading” was quite informative, and wish that more authors engaged in the practice of discussing, rather than just listing, other things for students to read.

One thing, however, that this book lacks is exercises. There are none at all, which could pose a serious drawback to anybody thinking of using this as a text for a course.

To summarize and conclude: the author covers a lot of interesting topics, and he does so with considerable clarity and enthusiasm. Notwithstanding this, however, this book may well be too demanding for use as a text for a “general mathematics” course (such as one offered to give non-majors a chance to fulfill a graduation requirement without taking calculus). It might work more satisfactorily, though, as a text for an honors seminar or other course for higher-ability students.

Mark Hunacek ( teaches mathematics at Iowa State University.

Preface xi
Acknowledgments xiii
Introduction to Ciphers and Substitution 1
1.1 Alice and Bob and Carl and Julius: Terminology and Caesar Cipher 1
1.2 The Key to the Matter: Generalizing the Caesar Cipher 4
1.3 Multiplicative Ciphers 6
1.4 Affine Ciphers 15
1.5 Attack at Dawn: Cryptanalysis of Sample Substitution Ciphers 18
1.6 Just to Get Up That Hill: Polygraphic Substitution Ciphers 20
1.7 Known-Plaintext Attacks 25
1.8 Looking Forward 26
Polyalphabetic Substitution Ciphers 29
2.1 Homophonic Ciphers 29
2.2 Coincidence or Conspiracy? 31
2.3 Alberti Ciphers 36
2.4 It's Hip to Be Square: Tabula Recta or Vigenère Square Ciphers 39
2.5 How Many Is Many? Determining the Number of Alphabets 43
2.6 Superman Is Staying for Dinner: Superimposition and Reduction 52
2.7 Products of Polyalphabetic Ciphers 55
2.8 Pinwheel Machines and Rotor Machines 58
2.9 Looking Forward 73
Transposition Ciphers 75
3.1 This Is Sparta! The Scytale 75
3.2 Rails and Routes: Geometric Transposition Ciphers 78
3.3 Permutations and Permutation Ciphers 81
3.4 Permutation Products 86
3.5 Keyed Columnar Transposition Ciphers 91
Sidebar 3.1 Functional Nihilism 94
3.6 Determining the Width of the Rectangle 97
3.7 Anagramming 101
Sidebar 3.2 But When You Talk about Disruption 104
3.8 Looking Forward 106
Ciphers and Computers 109
4.1 Bringing Home the Bacon: Polyliteral Ciphers and Binary Numerals 109
4.2 Fractionating Ciphers 115
4.3 How to Design a Digital Cipher: SP-Networks and Feistel Networks 119
Sidebar 4.1 Digitizing Plaintext 125
4.4 The Data Encryption Standard 130
4.5 The Advanced Encryption Standard 135
4.6 Looking Forward 143
Stream Ciphers 145
5.1 Running-Key Ciphers 145
Sidebar 5.1 We Have All Been Here Before 150
5.2 One-Time Pads 153
5.3 Baby You Can Drive My Car: Autokey Ciphers 157
5.4 Linear Feedback Shift Registers 167
5.5 Adding Nonlinearity to LFSRs 174
5.6 Looking Forward 178
Ciphers Involving Exponentiation 182
6.1 Encrypting Using Exponentiation 182
6.2 Fermat's Little Theorem 183
6.3 Decrypting Using Exponentiation 186
6.4 The Discrete Logarithm Problem 188
6.5 Composite Moduli 190
6.6 The Euler Phi Function 192
6.7 Decryption with Composite Moduli 195
Sidebar 6.1 Fee-fi-fo-fum 197
6.8 Looking Forward 199
Public-Key Ciphers 201
7.1 Right out in Public: The Idea of Public-Key Ciphers 201
7.2 Diffie-Hellman Key Agreement 207
7.3 Asymmetric-Key Cryptography 213
7.4 RSA 216
7.5 Priming the Pump: Primality Testing 222
7.6 Why is RSA a (Good) Public-Key System? 226
7.7 Cryptanalysis of RSA 229
7.8 Looking Forward 233
Appendix A The Secret History of Public-Key Cryptography 235
Other Public-Key Systems 241
8.1 The Three-Pass Protocol 241
8.2 ElGamal 247
8.3 Elliptic Curve Cryptography 251
8.4 Digital Signatures 265
8.5 Looking Forward 271
The Future of Cryptography 276
9.1 Quantum Computing 276
9.2 Postquantum Cryptography 281
9.3 Quantum Cryptography 292
9.4 Looking Forward 301
List of Symbols 303
Notes 305
Suggestions for Further Reading 345
Bibliography 349
Index 367