It seems that every time that your MAA Reviews editor send out the list of books in search of a reviewer there is a new book about cryptography on the list (and I almost always jump at the chance to review it!). In fact, as of this writing there are more than 50 books in the cryptography section of MAA Reviews. These books vary widely in level, content, and quality: there are books for middle school students, and highly technical monographs. There are books about the past and books about the future. There are books that could double as computer science books and books that rely heavily on physics. It is also worth mentioning that there are many many books about the field that for one reason or another are not in the MAA Reviews database. So anytime one picks up a new book in the area, one should ask oneself not only whether it is a good book but also whether it is better than the other books in the sub-sub-niche that it is trying to fill.
This was the case for me when I was asked to review Mathematics of Public Key Cryptography by Steven Galbraith. Galbraith is a professor at the University of Aukland, and is one of the more prominent researchers in the field of elliptic curve cryptography with more than 50 publications in the area. He also maintains the very interesting blog ellipticnews discussing the latest developments in the field. So it is somewhat natural that he would throw his hat in the ring and write a graduate level textbook on public key cryptography. Public key cryptography is a relatively recent field, dating back thirty or forty years (depending on what you count as its birthday), but in that time has grown as both a field of mathematics of its own intrinsic interest and also of incredible importance to electronic commerce and our other computer systems.
People familiar with the field could accurately guess what most of the table of contents looks like without cracking the spine. In a brief introduction, Galbraith sketches the main themes and questions in public key cryptography, including a description of what he calls “Textbook RSA” as well as descriptions of the typical types of attacks one would like to prevent. He then recommends jumping ahead 400 pages to Part V of the book, entitled “Cryptography Related To Discrete Logarithms.” The chapters in this section introduce The Diffie-Hellman Problem as well as its applications to key exchange problems, Elgamal encryption, and digital signatures. Galbraith sets up the Diffie-Hellman problem as taking place in an arbitrary algebraic group but suggests that a reader new to these ideas think about them as being set in the multiplicative group of a finite field Fp at first. Only when the reader is comfortable with these ideas would Galbraith suggest going back to the first three parts of the book, which give more detail and more background.
In particular, the first chapter of the book is essentially a crash course in algorithmic number theory, with topics such as Euclid’s algorithm, the Chinese remainder theorem, and arithmetic of finite fields. The second chapter discusses the basics of hash functions and their role in cryptography. The next seven chapters give background on algebraic groups, including quite a bit of the algebraic geometry of curves, divisor class groups, rational maps, elliptic curves, and hyperelliptic curves. This is material that can be found in any number of places, but Galbraith does a good job of balancing the theory and explicit examples in such a way that both novices and experts will learn something new. The third part of the book is entitled "Exponentiation, Factoring, and Discrete Logarithms" and as its title suggests it gives an overview of some of the best known algorithms for these problems, including using elliptic curves for factoring, using the Baby-step-giant-step method for solving discrete logarithm problems, and using Pollard Rho method and other pseudorandom walks to do both of these things. Again, most of this material appears many places in the literature and there is not much that is novel about Galbraith’s approach, but it is nice to have it compiled in one place.
There are also four chapters of the book about lattices and their use in public key cryptography. Many people believe that these lattice-based cryptosystems present a good alternative to RSA and factoring-based cryptosystems, especially as the threat of quantum computers inches closer to reality. These chapters define the computational problems needed for these cryptosystems, including asking whether a given vector is an element of a lattice, computing the shortest vector in a lattice, and finding the closest vector in a lattice to a given vector. Galbraith goes on to discuss the uses of these problems in cryptography as well as the best known algorithms to solve these problems. A final chapter in this section deals with Coppersmith’s method for finding small roots to polynomial equations. Coppersmith’s method is based on lattice reduction methods but can also be used to attack a vulnerability in the RSA cryptosystem.
The RSA and Rabin cryptosystems form the basis for Part VI of the book, described in “textbook” form as well as in a number of variations. Galbraith discusses a number of algebraic attacks on these systems as well as attempted forgeries to RSA signatures. He mentions a number of ways of trying to lessen the vulnerabilities to these attacks by, for example, choosing appropriate parameters. The final two chapters of Mathematics of Public Key Cryptography deal with some advanced topics related to elliptic and hyperelliptic curves. The first of these chapters discusses what it means for two elliptic curves to be isogenous and how, if one has an explicit isogeny between two elliptic curves one can relate the discrete logarithm problem on the elliptic curves to one another, thereby possibly making it easier to solve. The second set of topics deals with pairings on elliptic curves, which in turn leads to some interesting problems that one can define and base new cryptosystems on.
Galbraith’s book fits into a strange place in terms of its type of exposition. It is certainly more detailed and chatty than a reference book such as Cohen and Frey’s book but it is more terse and technical than the book of Hoffstein, Pipher, and Silverman despite having highly overlapping topics with both of these books. It has an extensive bibliography of 575 publications in the area and gives many nice explicit examples. It has a reasonable number of exercises, although they tend to be more of the form “complete the proof of this theorem” than explicit computations. I enjoy Galbraith’s exposition, and am very happy to have a copy of this book on my shelf — at the same time, there are not very many topics in this book that are not represented by other books on the shelf with it. Whether it stands out from the crowd to make it worth your time and money will depend a great deal on which of the other books you have and what your budget is.
Darren Glass is an Associate Professor of Mathematics at Gettysburg College, where he has been teaching a first year seminar on cryptography since 2007. He can be reached at email@example.com.
Part I. Background: 2. Basic algorithmic number theory
3. Hash functions and MACs
Part II. Algebraic Groups: 4. Preliminary remarks on algebraic groups
6. Tori, LUC and XTR
7. Curves and divisor class groups
8. Rational maps on curves and divisors
9. Elliptic curves
10. Hyperelliptic curves
Part III. Exponentiation, Factoring and Discrete Logarithms: 11. Basic algorithms for algebraic groups
12. Primality testing and integer factorisation using algebraic groups
13. Basic discrete logarithm algorithms
14. Factoring and discrete logarithms using pseudorandom walks
15. Factoring and discrete logarithms in subexponential time
Part IV. Lattices: 16. Lattices
17. Lattice basis reduction
18. Algorithms for the closest and shortest vector problems
19. Coppersmith's method and related applications
Part V. Cryptography Related to Discrete Logarithms: 20. The Diffie–Hellman problem and cryptographic applications
21. The Diffie–Hellman problem
22. Digital signatures based on discrete logarithms
23. Public key encryption based on discrete logarithms
Part VI. Cryptography Related to Integer Factorisation: 24. The RSA and Rabin cryptosystems
Part VII. Advanced Topics in Elliptic and Hyperelliptic Curves: 25. Isogenies of elliptic curves
26. Pairings on elliptic curves
Appendix A. Background mathematics