Algebra for Cryptologists

The title of this book is a little misleading. The phrase “algebra for cryptologists” suggests that this is a book on abstract algebra, covering those topics in algebra that are useful for an understanding of cryptography. While this book does in fact cover these topics, it also does quite a bit more.

First, the text also covers number theory and also introduces information theory and coding theory. This material is of course algebraic in nature, but does go beyond what one typically expects to see in a book (particularly one at the undergraduate level) that is advertised as a text in algebra. Second, the book not only discusses these topics but actually shows how they are used in the study of cryptography. In the process, therefore, a considerable amount of cryptography is discussed, although there are some omissions in coverage at the very elementary level that will be discussed later.

The book starts with an introductory chapter covering the basics of sets, functions and equivalence relations, and also introducing the subject of cryptography. This is followed by a chapter on number theory that discusses divisibility and congruence modulo \(n\). The approach taken here emphasizes algebra; the existence of a greatest common divisor, for example, is proved by first defining an ideal in the set of integers, and showing that any such ideal is principal. (No complaints here — I’ve always felt that this is the right way to do this.)

The next chapter introduces the basic constructs of abstract algebra — groups, rings and fields. No prior exposure to these ideas is assumed by the author, and these items are defined from scratch. Continuing the author’s approach of emphasizing algebra in number theory, Fermat’s little theorem is deduced as a consequence of Lagrange’s theorem. The material discussed in these chapters is then put to work in a chapter on public key cryptography: RSA, Diffie-Hellman, ElGamal, etc.

This is followed by two chapters on field theory, the first constituting an introduction and the second focusing on finite fields. Background material on polynomials over fields is developed as needed, and the second of these two chapters ends with a very brief introduction to elliptic curves over finite fields. This is followed by another chapter on applications to cryptography, this one discussing stream ciphers, and then a chapter on Boolean functions (i.e., functions mapping into the two-element set \(\{0,1\}\)). This chapter also includes an introduction to the Discrete Fourier Transform.

The last two primary chapters of the book return to cryptographic applications. First, there is a chapter on block cryptography, and then one which states, proves, and gives cryptographic applications of, the law of quadratic reciprocity. I say “primary” because there is then a fairly short chapter (“Where Do We Go from Here?”) that offers an annotated bibliography and a quick expository survey of more advanced topics.

As noted earlier, the author does not assume prior knowledge of algebra, number theory or probability (although the latter topic is summarized in an Appendix). The principal prerequisites for the book are some background in linear algebra and the inevitable “mathematical maturity” (defined here by the author to mean “you don’t run away screaming in fright when you encounter a \(\sum\) sign”). Although the prerequisites are relatively light, however, the exposition is not slow, so some prior background in algebra, though not essential, would probably be useful.

The book is generally clear and accessible, and there are an adequate number of exercises that are appropriate to the level of the text. The author does have a tendency to overuse footnotes (page 72, for example, has five of them) but, in his defense, some of them are amusing and he also recognizes the large number of them; he tells the reader to blame the typesetting language, “which makes inserting them far too easy”.

There are also, as I noted earlier, some omissions in the coverage of the cryptographic topics discussed here. Because the book emphasizes the mathematics that gets used in cryptography, “our descriptions blithely ignore implementation issues, including their security, and all matters concerned with the complexity of any algorithms that we deal with”. This didn’t bother me at all, but other omissions struck me as more troublesome, at least from the perspective of somebody thinking of using this as a text for a course in cryptography. The book omits, for example, some of the easiest and most basic examples of ciphers, such as simple substitution ones. Admittedly, nobody makes serious use of these easily-broken ciphers today, but they still serve to illustrate some ideas and provide a nice application of integer congruence. I also thought the book could have done a better job with historical discussions; I think most students find the history of cryptography to be one of its more interesting features, and that topic seemed definitely slighted here.

Conclusion: this is a nicely written book containing some interesting mathematics. My only real reservation is that there might be some difficulty matching this text with a typical mathematics department’s course offerings. As noted in the paragraph above, the omissions in the text may render it unsuitable as a text for an introductory cryptography course. However, if a college offers an “applied algebra” course (either as a substitute for, or sequel to, a standard abstract algebra course) or perhaps a “topics in algebra” course (as, say, a second semester algebra offering, where the instructor has some discretion in the selection of topic), this book might definitely have some appeal as a prospective text.

Mark Hunacek (mhunacek@iastate.edu) teaches mathematics at Iowa State University.