The Mathematics of Secrets
The subtitle of this book Cryptography from Caesar ciphers to digital encryption illustrates that cryptography has played a role in society of all times. Since antiquity, passing secret messages has been mainly of military interest. The simple cipher that is attributed to Caesar is probably much older. This military privilege lasted till around the middle of the 20th century. Then digital computers became part of society, first for big companies like banks, who needed failsafe communication between their computers, and later, as the digital computer conquered the daily life of individuals it became a standard procedure for practically every digital communication. Authentication and privacy has become everybody's concern. Often, mathematicians were involved in the design of cryptographic systems, even though for most of them, the mathematics are not complicated. Some modular arithmetic often suffices and for attacks, some statistics can help. In more recent systems prime numbers and elliptic curves enter the scene and there of course the mathematical challenges are a bit more substantial, but still manageable. History has shown that it has been a leapfrog pattern of copper and thief, of designer and attacker. If a new cryptosystem is designed it is used until it has been cracked by attackers, and then a new smarter system has to be designed. The newest threat for current systems is quantum computing, and designers are preparing to jump to a new system that can cope with that kind of attacks.
Analyzing cryptosystems involves three characters: Alice, Bob and Eve. Alice wants to send a secret message to Bob and Eve is eavesdropping, trying to read the message. So there are three stories to tell: How will Alice encrypt the message, how will Bob decrypt it, and what can Eve do to attack the system and intercept the message. Hiding the message involves codes and ciphers. In principle these are different. A code is a collection of many (perhaps thousands) of words that are used to replace words in the plaintext while a cipher describes how to replace letters (or short groups of letters) in the plaintext. A code is a kind of dictionary, while a cipher is more an algorithm. Steganography is another way of hiding a message by making it invisible (for example using invisible ink), but that is not covered in this book.
The contents of the book is pretty complete in surveying cryptography from antiquity till the current state of the art. In his introduction, the author explains that his first intention is not to be complete in all the details and in all the systems that ever existed, but he primarily wants to bring the mathematics involved to the foreground. And since these mathematics are relatively simple, the book should be accessible for anyone with a basic secondary school algebra course. The development of the contents is historical. So the first three chapters discuss historical ciphers that are not in use in their simplest form anymore, but they introduce the basic concepts that will be needed in the rest of the book when more complicated techniques are introduced. That begins around halfway the twentieth century when computers (mechanical or electronic) became involved. Also in each chapter the development is historical. Respecting the chronology throughout the book and in the chapters is a logical choice since it brings the increasingly complicated ideas as they were introduced historically. This makes it easy to understand why some modifications are needed and where the complication comes from. Each chapter also ends with a section Looking forward, linking it to future chapters and giving an outlook on what the potential use and challenges are for the techniques just introduced.
Describing in detail all the systems that are discussed in the book is not possible in this review. There are too many. Here is a crude outline. As said above, the first three chapters are mainly historical and introduce the reader to substitution ciphers. The Hill cipher (1929) is still in use as part of more complicated modern systems. Since frequency analysis can be used in attacks, a polyalphabetic version is a better option. Combination of such systems were used in the German Enigma machines during World War II where rotors applied successive ciphers to the plaintext. The next tool is a transposition cipher. The ciphertext is written in one or more tables row by row and read off column by column scattering patterns throughout the ciphertext. Claude Shannon (1916-2001), father of modern information theory, introduced a mixing function to create diffusion and confusion in cryptography. This should make it difficult to use a frequency analysis on the ciphertext or to detect a key if statistics are available. The systematic professional cryptosystems based on these principles are Feistel and SP-networks (a sequence of substitutions and permutations are applied during encryption), Examples are the DES standard (approved by NSA and published by NIST in 1976), and its improved version AES (2011).
The next chapter introduces stream ciphers. Here encryption of a block may depend on what has happened to previous blocks. Typical examples are the linear feedback shift register systems, which apply a linear filter to the bitstream. The problem here is the linearity. So, exponential ciphers try to introduce nonlinearity. Here the mathematics come to the foreground and we meet for example Fermat's little theorem, and the discrete logarithm problem. The drawback of these exponential ciphers is however that they are computationally demanding.
The crypto universe changed with the introduction of public-key systems. Bob has a private and a public key. Alice uses Bob's public key to encrypt the message. Bob's private key is needed to decrypt it. Eve does not have it and hence cannot read the message, and neither can Alice after she encrypted it. The idea is pioneered in the 1970's by R. Merkle, W. Diffie, and M. Hellman, but the breakthrough came from R. Rivet, A. Shamir, and L. Adelman with their RSA system (1978). These systems are based on a one-way function. This means that it represents a problem extremely difficult to solve, but once a solution is proposed, it is easily checked that it is indeed a solution to that problem. The problem acts like a safe. The public key can lock it but only the private key can unlock it. Hellman's problem was based on the discrete logarithm and in the RSA case it is prime number factorization for very large primes. It was only in 1996 that it was disclosed that J. Ellis had discovered public key cryptography already in 1969, but since he worked for the British equivalent of the NSA, he was bound by secrecy and could not communicate about it. There are other public key systems like the three pass protocol, or systems based on elliptic curves, and the same ideas can also be used for digital signatures (authentication problem).
In the last chapter the reader is briefly introduced to quantum computing. In this case the one-way functions, i.e., the "difficult problems" that hide the secret message are not based on prime factorization or discrete logarithms, but on much more difficult problems such as solving multivariate polynomial systems, or finding the closest point on a skew grid to some given point, not on that grid. If the dimensions are high enough, these problems are still hard, even with a quantum computer. The idea of the latter problem on grids, also called the closest vector problem, is used on a two-dimension grid as an example. Another technique is the BB85 (1985) protocol of C. Bennett and G. Brassard, elaborating an idea of S. Wiesner. This protocol uses the polarization of photons to encrypt the message.
There is an extensive appendix with references and notes. It contains suggestions for further reading, often taking a different approach to cryptography; it includes an extensive bibliography; and many pages with notes. The notes are references, quotes, or explanations, and they have a link to the page on which they comment, but there are no references on these pages to the notes. Thus while reading, you are not tempted to interrupt the flow of the text to look up the notes.
This is a marvelous way of illustrating the use of simple mathematics in an important application that has triggered the wit of the designers and the ingenuity of the attackers since antiquity. As the application became more and more important after computers entered the scene, mathematics became more and more involved. Someone with an elementary background, even if (s)he does not reach the end of the book, can come a long way on the path to where modern cryptography involves more advanced mathematics.