An Introduction to Mathematical Cryptography

This book is devoted to public key cryptography, whose principal goal is to allow two or more people to exchange confidential information even if they have never met and can communicate only via a channel that can be monitored by an adversary. In particular, in a public key system anyone can encrypt and send a message, but only one person is able to decrypt.

The concept of public key encryption was first made public in 1976 by W. Diffie and M. Hellman (although it was discovered by J. Ellis at the British Government Communications Headquarters in 1969, his discoveries were declassified only in 1997). This astonishing idea rests on the properties of certain mathematical functions, which are relatively easy to compute, while their inverses are much harder, specifically because their computation requires a much longer time. A typical example of this phenomenon is multiplication (easy) versus the factorization of a very large prime into a product of primes (very hard).

The three main mathematical themes in the book are:

1. Modular arithmetic;
2. Arithmetic of elliptic curves;
3. Lattice theory.

They constitute the mathematical core of the public key cryptosystems analyzed in the book: RSA; Diffie-Hellman; ElGamal; NTRU (the latter was actually invented  by the authors).

The material is very well organized, and it is self-contained: no prerequisites in higher mathematics are needed. In fact, everything is explained and carefully covered, including both such fundamentals as Euclid’s algorithm and less elementary notions such as probability theory, elliptic curves and lattices in vector spaces.

Every algorithm is carefully illustrated through numerical examples; practical implementation in a programming language is not, however, within the scope of the book. The underlying mathematics is very well explained; there is no formalism beyond the necessary, and there is abundance of examples and proposed exercises at the end of each chapter.

We mentioned above the existence of “functions” (loosely speaking), whose inverse is hard to compute. Several examples of such a situation arise from number theory, and among them the following are discussed in some depth in this book:

1. the discrete logarithm problem
2. the factorization of very large integers (related in turn to primality testing)
3. the search of a shortest vector in a lattice

These are real mathematical challenges, and there is a vast amount of current research on them. An extensive bibliography and a final chapter giving a very short overview of further developments in the field invite the reader to pursue further the study of these fascinating subjects of research.

This book is ideal as a textbook for a course aimed at undergraduate mathematics or computer science students. For classes in which students have a stronger background, the basic material may be omitted, leaving time for some of the more advanced topics.

Fabio Mainardi earned a PhD in Mathematics at the University of Paris 13. His research interests are Iwasawa theory, p-adic L-functions and the arithmetic of automorphic forms. He may be reached at mainardi2002@yahoo.fr.