Cryptological Mathematics

This book wants to be read by bright young people of every age. Beautiful mathematics just slides by because the story is told well and because it is useful in constructing and cracking ciphers. What a wonderful book! The book is about codes (not the error correcting kind, but rather the secret kind). It is both about making and breaking codes. Beth and Stephanie wish to exchange messages keeping them secret from Molly. For some reason, Molly has no trouble intercepting these messages, but she is faced with the problem of cracking Beth's and Stephanie's codes. Because Molly is very clever, Beth and Stephanie must resort to ever more sophisticated schemes for their messages. Lewand not only encodes and decodes, he also tells us a little about some of the giants of the ciphering world, at least on the U.S. side of the ocean.

In the first chapter, the mathematics of the integers and modular arithmetic are developed in order to introduce monoalphabetic coding methods. Induction, the division algorithm, unique factorization, greatest common divisors, the integers modulo n under addition and multiplication, and inversion modulo n are all introduced in an engaging setting that points toward simple linear, multiplicative, and affine monoalphabetic ciphers.

The style is always interesting. For example, a footnote describes the solid square printed at the end of a proof by saying, "This strange looking symbol ([square block]) that you'll notice scattered throughout this book indicates that we've finished proving the theorem. Just so you know." Small interjections capture our attention and focus us exactly when our minds may have been wandering. For example, "Keep in mind that the division algorithm is really nothing new to you," attaching a semi-abstract notion to very concrete ideas we already understand.

For each kind of code the procedures for encoding and decoding messages are covered. Even more interesting are Molly's methods for analyzing the codes. Frequency analysis is covered for letters, digraphs, and trigraphs. Beth and Stephanie have encoded a message that Molly successfully decodes. Clearly these codes are vulnerable to frequency analysis, leading naturally to a desire for more sophisticated ciphers. The first chapter ends with a description of Herbert O. Yardley and his "Black Chamber."

The second chapter takes up polyalphabetic substitution ciphers. Factorials, permutations, combinations, and probability are the mathematical foundations for the second chapter. The barest essentials are covered in an interesting way. "I know what you are thinking. (Or at least I know what you should be thinking!)"

The Vigenère Square enciphering method is introduced showing both how to encode and decode a message. However, matters become interesting when Molly must decipher the message. The Kasiski Test is introduced to find candidates for the length of a keyword. The Friedman Test is introduced to help distinguish between monoalphabetic and polyalphabetic ciphers. Molly uses the Index of Coincidence to guess that a message might be encoded in a polyalphabetic cipher. She then uses the Kasiski Test to find candidates for the length of a keyword. Then by cleverly arranging the message in an array, she is able to discover the keyword, supposing of course that she knew the polyalphabetic encoding method was by the Vigenère Square. Incidentally, throughout the text Stephanie, Beth, and Molly are represented by cartoon talking heads that sometimes make pithy comments.

The second chapter ends with a biographical sketch of William F. Friedman. "Okay, what if you go through these steps and the message still doesn't make sense? That is why this book has more than two chapters."

The third chapter deserts alphabetic coding schemes for more general polygraphic techniques. Now some linear algebra is needed. So Lewand introduces us to matrices, addition, multiplication, and inverses. Because the book builds, he has not forgotten either modular arithmetic or probability. He expresses linear equations in terms of matrices and uses 2x2 matrices to transform figures in the plane. "Matrices can give you surprising, revealing, and even fun results!"

We are now treated to Hill's system for encoding messages using a 2x2 matrix scheme. If Molly assumes Hill's system was used then she can look for digraphs and trigraphs in the encoded message. With some good guesswork, Molly is able to crack the message by solving some linear equations. The deciphering now is much more mathematically complex so the process follows Molly to a complex set of possible solutions, one of which is obviously correct. The methodology is analyzed to describe a possible cryptanalysis that will attack all the encoding schemes covered thus far in the text.

The third chapter ends with the exploits of Agnes M. Driscoll (Miss Aggie) "Mrs. Driscoll was considered a character by some, a mystery by others, and a genius to the few who had known her at the height of her career."

The final chapter is devoted to the RSA public key encryption algorithm. The mathematics here is number theory. Euler's Theorem is needed and a complete, intelligible proof is given. Half way through Beth says, "Hey, Steph! That's a lot of lemmas. Can't we take a break?" To which Stephanie replies, "Don't be such a wimp!" Later, when Molly sees her tools, she says, "Lemma 4.7 rocks!" Of course, Fermat's Little Theorem is a corollary of Euler's Theorem.

The RSA scheme along with both encoding and decoding algorithms is discussed with examples carefully and engagingly used to illustrate. Mathematica and Maple are introduced to carry out the rather intimidating calculations. By looking at the time required to factor big numbers, Lewand estimates cracking times for various RSA codes. Using Mathematica and Maple he carefully encodes and decodes two messages in a nicely arranged tabular form that makes the steps very clear.

With a public key, anyone can encode a bogus message and send it. Thus, it is important that messages be signed. Lewand describes how to do this with the RSA scheme. We've finally stumped Molly, not because she is unable to decipher messages, but because she is not going to do it in her lifetime.

Finally, the book describes the Massey-Omura variant of RSA encoding. This scheme requires that both the encoding and decoding keys be kept private. A short message is encoded and decoded using this scheme. And then we are treated to the story of Frank Rowlett who worked on secret codes for the U.S.

The level of this text is about in the middle of the New Mathematical Library. It is readable by bright high school students, but also thoroughly enjoyable to old algebraists like me. For those who want to roll up their sleeves and do some work, there are plenty of interesting exercises with answers for the even ones: puzzles, even until the end.

 Thomas R. Berger (trberger@colby.edu) is Carter Professor of Mathematics and Computer Science at Colby College.