Fundamentals of Cryptography

The desire of governments, generals, and even private individuals to communicate in a fashion that prevents private communications from being read by others goes back millennia. The ability of third parties to read messages not intended for them, or for messages to be unreadable by third parties, has frequently changed the path of history. The use of technology in the last 200 years has changed the process of communicating messages, first with the telegraph, then with wireless, and now with the internet. With telegraph systems based on wires, a third party needed physical access to the communication medium. With wireless radio, the transmission became public, and the need for secure communications increased. With messages sent in packets over the internet, literally anyone can be eavesdropping from anywhere in the world. In this chapter we will briefly cover some of the history, and we will define basic terms and uses that will continue through the book.

Until the computer age, making and breaking ciphers was a task that required extreme concentration and care. Search trees based on guesses can be programmed on computers and run at high speed, where we can use the computer’s speed and the ease of keeping track of the data in data structures to allow us not to care too much about following low probability paths. The cost in time and effort to search using pencil and paper would have demanded much better guesses as to the correct path down the tree. Cryptanalysis in the first half of the twentieth century required knowledge of language patterns and frequency statistics, and both encryption and decryption had to be processes that could easily be remembered and followed. In this chapter we will describe some classical ciphers (that would be easily attacked with a program running on a desktop computer) as well as some statistical characteristics of language that could be used to attack these now-outdated ciphers. There are two basic forms of simple cipher. In a substitution cipher , one substitutes for each letter in the underlying alphabet another symbol (perhaps a different letter in the same alphabet, or sometimes another symbol entirely). In a transposition cipher , the letters of the underlying alphabet remain the same, but their order is transposed into a different order. In this, one can take the term “letter” to mean a single letter or perhaps a pair of letters. We distinguish at the outset a codebook from a cipher, although the two can be closely related. Traditional codebooks were a form of making communications secret by substituting a fixed length (often five) sequence of numbers for each of the individual words in the message. One can think of such a codebook as a substitution cipher in which the symbols are words (of variable length, of course) for which one substitutes numerical symbols. We will also mention only briefly (right here) the notion of steganography, where a message is hidden in some seemingly innocuous communication. One version of this would be a letter in which the hidden message was the sequence of first letters of words of the text. A more modern reverse version of steganography is digital watermarking, in which a digital pattern is inserted into a document, usually an image document, so that the provenance of the image can be authenticated if it is illegally taken without attribution or royalty. This is not unlike the apparent inclusion of intentional errors in maps, say, so that the owner of the map’s copyright could argue that the map had been illegally copied. The author wishes very much that he had kept the road map of Louisiana (where he grew up) that showed a road south from Venice, Louisiana, and a bridge across the Mississippi to reach Pilottown. No such road or bridge has ever existed; Pilottown is where the Mississippi River pilots meet the incoming vessels and take the conn on the way up the river to the Port of New Orleans, and where on the outward voyage they turn over the conn to the seagoing pilots. The “city” can only be reached by water; there is no road south from Venice and no bridge across the Mississippi.

Modern cryptography is largely based on the mathematicals of modular arithmetic, congruences, and the arithmetic in the integers modulo prime numbers or products of (usually) two large prime numbers. In this chapter we cover the basic number theory that appears in both symmetric and asymmetric cryptographic systems: divisibility and congruences, greatest common divisor, exponentiation, and the Euler totient. Our emphasis is on mathematical theorems that must be understood and used, rather than on their proofs, unless the method or constructions in the proofs are relevant to cryptography itself. Although we treat this as background mathematics, we point out that the reader can readily generate examples for all the principles that are covered as well as find examples that demonstrate why the assumptions made are necessary and the conclusions tightly drawn.

Modern cryptography relies, for its ability to convert plaintext into ciphertext that appears to be random sequences of symbols, on the basic notions of abstract algebra. We introduce in this chapter the basics of groups, rings, and fields, including subgroups, cyclic groups, the order of elements, and Lagrange’s Theorem. A group is a set that is closed under an operation that is usually referred to (and often is) either as addition or as multiplication, with additional properties. A ring has both an addition and a multiplication, but which may not have an operation that resembles division. A field has all the characteristics we normally associate with doing arithmetic. All three are in some sense merely descriptions in the abstract of ordinary arithmetic. Proofs will to a large extent be left to later, or not done at all. And since we are interested more in using groups, rings, and fields than in proving theorems about them as algebraic objects, this chapter can be viewed largely as simply providing definitions for and formal statements of the truth of what we observe when doing the operations for encrypting and decrypting.

We will do square roots modulo primes using primitive roots and exponents. This is a little different from the way that is done in many references, but we want to emphasize that it is the world of additive exponent arithmetic that is important. Modulo a prime p, the exponents work additively modulo \(p-1\). When we get to RSA encryption, in which we have a modulus \(N = pq\) for two large and unknown primes p and q, we cannot play the same exponent games as with primes because \(\phi (N) = (p-1)(q-1)\) is not \(N-1\), and it is the \(\phi (N)\) that determines the arithmetic on the exponents. In the later chapters on factoring and elliptic curves, it will be computationally beneficial to be able to determine whether an integer is or is not congruent to a square modulo a modulus N. Fortunately, determining whether an integer is a square modulo a prime, or determining that an integer is not a square modulo a composite number, can be done by a process that resembles the gcd and has the same logarithmic complexity.

In this chapter we extend beyond integers modulo primes to consider finite fields of characteristic 2. For a more extensive presentation of finite fields, the reader should consult Lidl and Niederreiter [1]. For a different presentation of finite fields of characteristic 2, the reader could consult Golomb [2]. Finite field arithmetic in characteristic 2 is used in the Advanced Encryption Standard (AES). It can be preferable in other cryptosystems, because computer hardware works in binary, and thus the underlying arithmetic operations needed to encrypt and decrypt can be very fast.

Elliptic curves are one of the more elegant objects in algebra. A background of the underlying arithmetic of curves is necessary for cryptography, because they are used for (at least) three purposes: for factoring integers, for cryptography itself, and for key exchange. The arithmetic of elliptic curves parallels in many ways the arithmetic of integers modulo primes or composites, at least. In this chapter we present an introduction to elliptic curves as background for later chapters that use them for cryptographic purposes.

We have remarked earlier that actually doing cryptography requires combining mathematics and computing. In this chapter we describe several algorithms and computational tricks that make it possible to do the discrete mathematics that is cryptography on computers that have not necessarily been designed to provide robust support for discrete mathematics. This chapter covers a few of these tricks and algorithms necessary for understanding how one might actually do cryptography in the real world. The first set of tricks has been used extensively in testing integers for primality, using the bit patterns of the integers to eliminate the need for modular reduction. Multiprecise arithmetic is needed for much of modern cryptography, with modular reduction and multiplication dominating the cost of arithmetic. Multiplication itself is done with fast methods like the FFT, which we cover here, and reduction can be dealt with by Montgomery multiplication, which essentially extends the Mersenne prime trick to all integer moduli.

In a symmetric cryptosystem, the key used for encrypting a message is the same as the key used for decrypting a message. Although this does place a burden of proper key management and security on the users of such a cryptosystem, there have been two major cryptosystems, the Digital Encryption Standard (DES) and the Advanced Encryption Standard (AES), promulgated by the National Institute of Standards and Technology. DES was controversial due to the manner in which it was promulgated, and it has largely been superseded by the AES, about which almost no controversy exists. AES is currently in wide use in part because it is the NIST standard and in part because its design makes it fast and usable on a variety of platforms with different computational capabilities. This chapter covers the technical aspects of AES. Code for AES and test results appear in Appendix B so that code testing can be done and the encryption process observed.

The notion of an asymmetric encryption system dates to the 1970s, with the first and still primary version of asymmetric encryption being the RSA algorithm of Rivest, Shamir, and Adleman. In asymmetric encryption, an encryption key that is made public is used to encrypt a message that is sent to the owner of the public key. That owner then uses a privately held key to decrypt. The RSA algorithm relies on a choice of two large primes p and q, multiplied together to produce a modulus \(N = pq\). The public encryption key e and private decryption key d are chosen so that \(e d \equiv 1 \pmod {\phi (N)}\). Current knowledge of the mathematics is that if N and e are public, but p, q, and d are kept private, then decrypting a message requires factoring N into p times q, and that is computationally hard. In this chapter we lay out the foundation of the RSA process, with an example, and we comment on the current records in factoring as a estimate of the security of RSA.

The security of the RSA cryptosystem is based on the difficulty of factoring integers N that are the products of two large primes p and q. If p and q are chosen well, then factoring N is indeed hard, but there are also factoring methods that work very quickly on certain kinds of integers. In order to ensure security of an RSA system, one must be careful to choose an N that does not succumb to one of the faster methods. We will discuss the Pollard rho and Pollard \(p-1\) methods first. These are not only used in general for factoring, but have been generalized to be applicable in other attacks against cryptographic systems. We then move on to CFRAC, a precursor to the state-of-the-art factoring method that is the primary topic of Chap. 12.

In Chap. 11 we described several factoring methods. Each will succeed in factoring some integers, but none of these is a state-of-the-art method that we would expect to succeed on a well-chosen RSA \(N = pq\). Even the best of these, CFRAC, suffers from the need to do trial division that will fail most of the time to provide any forward motion toward factoring N. In this chapter we discuss sieve methods for factoring. The primary computational benefit of a sieve method is that all the computational steps taken actually work toward finding factors, and that a sieve, stepping at constant stride through an array in memory, is highly efficient at the very lowest levels of a computing process. We discuss the Quadratic Sieve and the Multiple Polynomial Quadratic Sieve, and then finish with a nod to the current best method for factoring large “hard” integers, the Number Field Sieve.

With symmetric cryptography, it is necessary for the two parties who wish to communicate to have access to a common key so that one party can encrypt a message and the other party can decrypt the message. This would limit the ability of two parties who have not communicated in the past to engage in the kind of secure communication necessary for electronic commerce, for example. In this chapter we describe how number-theoretic constructs that create seemingly-random sequences of integers can be used to allow two parties to exchange information that would allow them to agree upon a common cryptographic key, even if no other communication has taken place between them. This exchange of key information can be done by exponentiation modulo a large prime number, in a manner similar to that of RSA encryption, or using elliptic curve groups in the same fashion. We will also cover the basics of the index calculus method that can be used, although with difficulty, to attack this kind of key exchange.

The first proposed asymmetric encryption scheme was that of Rivest, Shamir, and Adleman, using exponentiation in the group of integers modulo the product of two large primes. Koblitz and Miller independently proposed the use of the groups of points on elliptic curves. In this chapter we cover the algorithm for using curves for cryptography both for encryption and for key exchange. Since the arithmetic to do point addition is expensive, we include the formulas for adding points efficiently. Finally, we include the Pohlig-Hellman attack, which should not be successful if the curves are chosen properly, and the Pollard rho attack, which is the current best attack on the elliptic curve discrete log problem.

With the publication of Peter Shor’s seminal paper that factoring and discrete log computations would be entirely feasible on a quantum computer, and with advances in the building of quantum computers, there has been a focus on what is referred to as “post-quantum cryptography”. Among the most viable candidates for post-quantum cryptography are cryptosystems based on the problem of finding short vectors in lattices. In this chapter we outline briefly why quantum computers can make RSA-type cryptosystems obsolete and how lattices can be used in cryptography. We concentrate on perhaps the best-known lattice system, NTRU, and explain how it is used and why attacks on it still seem computationally infeasible.

Shortly after the original RSA paper [1], a question was posed by Rivest, Adleman, and Dertouzos [2]: would it be possible to have a database of encrypted information (such as financial or health data), stored in an external location, that would nonetheless allow computations on the encrypted data without decrypting it? This would permit, for example, external storage, and computation on the encrypted data stored at the external site, without having to trust the owner or operator of the external site.\(\mathbb {R}^{3}\)