Chapter Summary

This chapter deals with the algorithmic details needed for setting up public-key cryptosystems. We study algorithms for selecting public-key parameters and for carrying out the basic cryptographic primitives. Algorithms required for cryptanalysis are dealt with in Chapters 4 and 7.

We start the chapter with a discussion on algorithms. Time and space complexities of algorithms are discussed first and the standard order notations are explained. Next we study the class of randomized algorithms which provide practical solutions to many computational problems that do not have known efficient deterministic algorithms. In the worst case, a randomized algorithm may take exponential running time and/or may output an incorrect answer. However, the probability of these bad behaviours of a randomized algorithm can be made arbitrarily low. We finally discuss reduction between computational problems. A reduction helps us conclude about the complexity of one problem relative to that for another problem.

Many popular public-key cryptosystems are based on working modulo big integers. These integers have sizes up to several thousand bits. One can not represent such integers with full precision by built-in data types supplied by common programming languages. So we require efficient ways of representing and doing arithmetic on big integers. We carefully deal with the implementation of the arithmetic on multiple-precision integers. We provide a special treatment of computation of gcd’s and extended gcd’s of integers. We utilize these arithmetic functions in order to implement modular arithmetic. Most public-key primitives involve modular exponentiations as the most time-consuming steps. In addition to the standard square-and-multiply algorithm, certain special tricks (including Montgomery exponentiation) that help speed up modular exponentiation are described at length in this section.

In the next section, we deal with some other number-theoretic algorithms. One important topic is the determination of whether a given integer is prime. The Miller–Rabin primality test is an efficient algorithm for primality testing. This algorithm is, however, randomized in the sense that it may declare some composite integers as primes. Using suitable choices of the relevant parameters, the probability of this error may be reduced to very low values (≤ 2^–80). We also briefly introduce the deterministic polynomial-time AKS algorithm for primality testing. Since we can easily check for the primality of integers, we can generate random primes by essentially searching in a pool of randomly generated odd integers of a given size. Security in some cryptosystems require such random primes to possess some special properties. We present Gordon’s algorithm for generating cryptographically strong primes. The section ends with a study of the Tonelli–Shanks algorithm for computing square roots modulo a big prime.

Next, we concentrate on the implementation of the finite field arithmetic. The arithmetic of a field of prime cardinality p is the same as integer arithmetic modulo p and is discussed in detail earlier. The other finite fields that are of interest to cryptology are extension fields of characteristic 2. In order to study the arithmetic in these fields, one first requires arithmetic of the polynomial ring . We discuss the basic operations in this ring. Next we talk about algorithms for checking irreducibility of polynomials and for obtaining (random) irreducible polynomials in . If f(X) is such a polynomial of degree d, the arithmetic of the field is the same as the arithmetic of modulo the defining polynomial f(X). In order that a finite field is cryptographically safe, we require q – 1 to have a prime factor of sufficiently big size (160 bits or more). Suppose that the factorization of q – 1 is provided. We discuss algorithms that compute the order of elements in , that check if a given element is a generator of the cyclic group , and that produce random generators of . We end the study of finite fields by discussing a way to factor polynomials over finite fields. The standard algorithm comprising the three steps square-free factorization, distinct-degree factorization and equal-degree factorization is explained in detail. The exercises cover the details of an algorithm to compute the roots of polynomials over finite fields.

The arithmetic of elliptic curves over finite fields is dealt with next. Each operation in the elliptic curve group can be realized by a sequence of operations over the underlying field. The multiple of a point on an elliptic curve can be computed by a repeated double-and-add algorithm which is the same as the square-and-multiply algorithm for modular exponentiation, applied to an additive setting. We also discuss ways of selecting random points on elliptic curves. We then present two algorithms for counting points in an elliptic curve group. The SEA algorithm is suitable for curves over prime fields, whereas the Satoh–FGH algorithm works efficiently for curves over fields of characteristic 2. Once we can determine the order of an elliptic curve group, we can choose good elliptic curves for cryptographic usage.

In the next section, we study the arithmetic of hyperelliptic curves. We describe ways to represent elements of the Jacobian by pairs of polynomials and to do arithmetic on elements in this representation. We also discuss two algorithms for counting points in a Jacobian.

In the last section, we address the issue of generation of pseudorandom bits. We define the concept of cryptographically strong pseudorandom bit generator and provide an example, namely the Blum–Blum–Shub generator, which is cryptographically strong under the assumption that taking square roots modulo a big composite integer is computationally intractable.