The aim of this chapter is to give a brief summary of some fundamental algorithms for arithmetic in finite fields. The intention is not to provide an implementation guide; instead, we sketch some important concepts and state some complexity results that will be used later in the book. We do not give a consistent level of detail for all algorithms; instead, we only give full details for algorithms that will play a significant role in later chapters of the book.

More details of these subjects can be found in Crandall and Pomerance [150], Shoup [497], Buhler and Stevenhagen [106], Brent and Zimmermann [95], Knuth [308], von zur Gathen and Gerhard [220], Bach and Shallit [21] and the handbooks [16, 376].

The chapter begins with some remarks about computational problems, algorithms and complexity theory. We then present methods for fast integer and modular arithmetic. Next we present some fundamental algorithms in computational number theory such as Euclid's algorithm, computing Legendre symbols and taking square roots modulo p. Finally, we discuss polynomial arithmetic, constructing finite fields and some computational problems in finite fields.

Algorithms and complexity

We assume the reader is already familiar with computers, computation and algorithms. General references for this section are Chapter 1 of Cormen et al. [136], Davis and Weyuker [154], Hopcroft and Ullman [265], Section 3.1 of Shoup [497], Sipser [509] and Talbot and Welsh [539].

Cryptography is an interdisciplinary field of great practical importance. The subfield of public key cryptography has notable applications, such as digital signatures. The security of a public key cryptosystem depends on the difficulty of certain computational problems in mathematics. A deep understanding of the security and efficient implementation of public key cryptography requires significant background in algebra, number theory and geometry.

This book gives a rigorous presentation of most of the mathematics underlying public key cryptography. Our main focus is mathematics. We put mathematical precision and rigour ahead of generality, practical issues in real-world cryptography or algorithmic optimality. It is infeasible to cover all the mathematics of public key cryptography in one book. Hence, we primarily discuss the mathematics most relevant to cryptosystems that are currently in use, or that are expected to be used in the near future. More precisely, we focus on discrete logarithms (especially on elliptic curves), factoring based cryptography (e.g., RSA and Rabin), lattices and pairings. We cover many topics that have never had a detailed presentation in any textbook.

Due to lack of space some topics are not covered in as much detail as others. For example, we do not give a complete presentation of algorithms for integer factorisation, primality testing and discrete logarithms in finite fields, as there are several good references for these subjects. Some other topics that are not covered in the book include hardware implementation, side-channel attacks, lattice-based cryptography, cryptosystems based on coding theory, multivariate cryptosystems and cryptography in non-Abelian groups.

One of the most powerful tools in mathematics is linear algebra, and much of mathematics is devoted to solving problems by reducing them to it. It is therefore natural to try to solve the integer factorisation and discrete logarithm problems (DLP) in this way. This chapter briefly describes a class of algorithms that exploit a notion called “smoothness”, to reduce factoring or DLP to linear algebra. We present such algorithms for integer factorisation, the DLP in the multiplicative group of a finite field and the DLP in the divisor class group of a curve.

It is beyond the scope of this book to give all the details of these algorithms. Instead, the aim is to sketch the basic ideas. We mainly present algorithms with nice theoretical properties (though often still requiring heuristic assumptions) rather than the algorithms with the best practical performance. We refer to Crandall and Pomerance [150], Shoup [497] and Joux [283] for further reading.

The chapter is arranged as follows. First, we present results on smooth integers, and then sketch Dixon's random squares factoring algorithm. Section 15.2.3 then summarises the important features of all algorithms of this type. We then briefly describe a number of algorithms for the discrete logarithm problem in various groups.

Smooth integers

Recall from Definition 12.3.1 that an integer is B-smooth if all its prime divisors are at most B. We briefly recall some results on smooth integers; see Granville [243] for a survey of this subject and for further references.

This chapter gives a thorough discussion of the computational Diffie–Hellman problem (CDH) and related computational problems. We give a number of reductions between computational problems, most significantly reductions from DLP to CDH. We explain selfcorrection of CDH oracles, study the static Diffie–Hellman problem, and study hard bits of the DLP and CDH. We always use multiplicative notation for groups in this chapter (except for in the Maurer reduction where some operations are specific to elliptic curves).

Variants of the Diffie–Hellman problem

We present some computational problems related to CDH, and prove reductions among them. The main result is to prove that CDH and Fixed-CDH are equivalent. Most of the results in this section apply to both algebraic groups (AG) and algebraic group quotients (AGQ) of prime order r (some exceptions are Lemma 21.1.9, Lemma 21.1.15 and, later, Lemma 21.3.1). For the algebraic group quotients G considered in this book then one can obtain all the results by lifting from the quotient to the covering group G′ and applying the results there.

A subtle distinction is whether the base element g ∈ G is considered fixed or variable in a CDH instance. To a cryptographer it is most natural to assume the generator is fixed, since that corresponds to the usage of cryptosystems in the real world (the group G and element g ∈ G are fixed for all users). Hence, an adversary against a cryptosystem leads to an oracle for a fixed generator problem.

This chapter is about algorithms to solve the discrete logarithm problem (DLP) and some variants of it. We focus mainly on deterministic methods that work in any group; later chapters will present the Pollard rho and kangaroo methods, and index calculus algorithms. In this chapter, we also present the concept of generic algorithms and prove lower bounds on the running time of a generic algorithm for the DLP. The starting point is the following definition (already given as Definition 2.1.1).

Definition 13.0.1 Let G be a group written in multiplicative notation. The discrete logarithm problem (DLP) is: given g, h ∈ G find a, if it exists, such that h = ga. We sometimes denote a by logg(h).

As discussed after Definition 2.1.1, we intentionally do not specify a distribution on g or h or a above, although it is common to assume that g is sampled uniformly at random in G, and a is sampled uniformly from {1, …, #G}.

Typically, G will be an algebraic group over a finite field Fq and the order of g will be known. If one is considering cryptography in an algebraic group quotient then we assume that the DLP has been lifted to the covering group G. A solution to the DLP exists if and only if h ∈ 〈g〉 (i.e., h lies in the subgroup generated by g). We have discussed methods to test this in Section 11.6.

The goal of lattice basis reduction is to transform a given lattice basis into a “nice” lattice basis consisting of vectors that are short and close to orthogonal. To achieve this, one needs both a suitable mathematical definition of “nice basis” and an efficient algorithm to compute a basis satisfying this definition.

Reduction of lattice bases of rank 2 in ℝ2 was given by Lagrange and Gauss. The algorithm is closely related to Euclid's algorithm and we briefly present it in Section 17.1. The main goal of this section is to present the lattice basis reduction algorithm of Lenstra, Lenstra and Lovász, known as the LLL or L3 algorithm. This is a very important algorithm for practical applications. Some basic references for the LLL algorithm are Section 14.3 of Smart [513], Section 2.6 of Cohen [127] and Chapter 17 of Trappe and Washington [547]. More detailed treatments are given in von zur Gathen and Gerhard [220], Grötschel, Lovász and Schrijver [245], Section 1.2 of Lovász [356], and Nguyen and Vallée [416]. I also highly recommend the original paper [335].

The LLL algorithm generalises the Lagrange–Gauss algorithm and exploits the Gram–Schmidt orthogonalisation. Note that the Gram–Schmidt process is not useful, in general, for lattices since the coefficients μi,j do not usually lie in ℤ and so the resulting vectors are not usually elements of the lattice. The LLL algorithm uses the Gram–Schmidt vectors to determine the quality of the lattice basis, but ensures that the linear combinations used to update the lattice vectors are all over ℤ.

The aim of this chapter is to briefly present some cryptosystems whose security is based on computational assumptions related to the integer factorisation problem. In particular, we study the RSA and Rabin cryptosystems. We also present some security arguments and techniques for efficient implementation.

Throughout the chapter we take 3072 bits as the benchmark length for an RSA modulus. We make the assumption that the cost of factoring a 3072-bit RSA modulus is 2128 bit operations. These figures should be used as a very rough guideline only.

The textbook RSA cryptosystem

Box 24.1 recalls the “textbook” RSA cryptosystem, which was already presented in Section 1.2. We remind the reader that the main application of RSA encryption is to transport symmetric keys, rather than to encrypt actual documents. For digital signatures we always sign a hash of the message, and it is necessary that the hash function used in signatures is collision resistant.

In Section 1.3 we noted that the security parameter κ is not necessarily the same as the bit-length of the RSA modulus. In this chapter it will be convenient to ignore this, and use the symbol κ to denote the bit-length of an RSA modulus N. We always assume that κ is even.

As we have seen in Section 1.2 certain security properties can only be satisfied if the encryption process is randomised.