1.3. Public-key Cryptography

In this section, we give a short introduction to the realization of public-key cryptosystems. More specifically, we list some of the computationally intensive mathematical problems and describe how the (apparent) intractability of these problems can be used for designing key pairs. We use some mathematical terms that we will introduce later in this book.

1.3.1. The Mathematical Problems

The security of the public-key cryptosystems is based on the presumed difficulty of solving certain mathematical problems.

The integer factorization problem (IFP)

Given the product n = pq of two distinct prime integers p and q, find p and q.

The discrete logarithm problem (DLP)

Let G be a finite cyclic (multiplicatively written) group with cardinality n and a generator g. Given an element , find an integer x (or the integer x with 0 ≤ x ≤ n – 1) such that a = g^x in G. Three different types of groups are commonly used for cryptographic applications: the multiplicative group of a finite field, the group of rational points on an elliptic curve over a finite field and the Jacobian of a hyperelliptic curve over a finite field. By an abuse of notation, we often denote the DLP over finite fields as simply DLP, whereas the DLP in elliptic curves and hyper-elliptic curves is referred to as the elliptic curve discrete logarithm problem (ECDLP) and the hyperelliptic curve discrete logarithm problem (HECDLP).

The Diffie–Hellman problem (DHP)

Let G and g be as above. Given elements g^a and g^b of G, compute the element g^ab. As in the case of the DLP, the DHP can be applied to the multiplicative group of finite fields, the group of rational points on an elliptic curve and the Jacobian of a hyperelliptic curve.

We show in the next section how (the intractability of) these problems can be exploited to create key pairs for various cryptosystems. These computational problems are termed difficult, intractable, infeasible or intensive in the sense that there are no known algorithms to solve these problems in time polynomially bounded by the input size. The best-known algorithms are subexponential or even fully exponential in some cases. This means that if the input size is chosen to be sufficiently large, then it is infeasible to compute the private key from a knowledge of the public key in a reasonable amount of time. This, in turn, implies (not provably, but as the current state of the art stands) that encryption or signature verification can be done rather quickly (in polynomial time), but the converse process of decryption or signature generation cannot be done in feasible time, unless one knows the private key. As a result, encryption (or signature verification) is called a trapdoor one-way function, that is, a function which is easy to compute but for which the inverse is computationally infeasible, unless some additional information (the trapdoor) is available.

It is, however, not known that these problems are really computationally infeasible, that is, there is no proof of the fact that these problems cannot be solved in polynomial time. As a result, the public-key cryptographic systems based on these problems are not provably secure.

1.3.2. Realization of Key Pairs

In RSA and similar cryptosystems, one generates two (distinct) suitably large primes p and q and computes the product n = pq. Then φ(n) = (p – 1)(q – 1), where φ denotes Euler’s totient function. One then chooses a random integer e with gcd(e, φ(n)) = 1. There exists an integer d such that ed ≡ 1 (mod φ(n)). The integer e is used as the public key, whereas the integer d is used as the private key.

If the IFP can be solved fast, one can also compute φ(n) easily, and subsequently d can be computed from e using the (polynomial-time) extended GCD algorithm. This is why^[2] we say that the RSA cryptosystem derives its security from the intractability of the IFP.

^[2] The problem of factoring n = pq is polynomial-time equivalent to computing φ(n) = (p – 1)(q – 1).

In order to see how RSA encryption and decryption work, let the plaintext message be encoded as an integer m with 2 ≤ m < n. The ciphertext message is generated (as an integer) as c = m^e (mod n). Decryption is analogous, that is, m = c^d (mod n). The correctness of the algorithm follows from the fact that ed ≡ 1 (mod φ(n)). It is, however, not proved that one has to know d or φ(n) or the factorization of n in order to decrypt an RSA-encrypted message. But at present no better methods are known.

Let us now consider the discrete logarithm problem. Let G be a finite cyclic multiplicative group (as those mentioned above) where it is easy to multiply two elements, but where it is difficult to compute discrete logarithms. Let g be a generator of G. In order to set up a random key pair over such a group, one chooses the private key as a random integer d, 2 ≤ d < n, where n is the cardinality of G. The public key e is then computed as an element of G as e = g^d.

Applications of encryption–decryption schemes based on the key pair (g^d, d) are given in Chapter 5. Now, we only remark that many such schemes (like the ElGamal scheme) derive their security from the DHP instead of the DLP, whereas the other schemes (like the Nyberg–Rueppel scheme) do so from the DLP. It is assumed that these two problems are computationally equivalent (at least for the groups of our interest). Obviously, if one assumes availability of a solution of the DLP, one has a solution for the DHP too (g^ab = (g^a)^b). The reverse implication is not clear.

1.3.3. Public-key Cryptanalysis

As we pointed out earlier, (most of) the public-key cryptosystems are not provably secure in the sense that they are based on the apparent difficulty of solving certain computational problems. It is expedient to know how difficult these problems are. No non-trivial complexity–theoretic statements are available for these problems, and as such it is worthwhile to study the algorithms known till date to solve these problems. Unfortunately, however, many of the algorithms of this kind are often much more complicated than the algorithms for building the corresponding cryptographic systems. One needs to acquire more mathematical machinery in order to understand (and augment) these cryptanalytic algorithms. We devote Chapter 4 to a detailed discussion on these algorithms.

In specific situations, one need not always use these computationally intensive algorithms. Access to a party’s decryption equipment may allow an adversary to gain partial or complete information about the private key by watching a decryption process. For example, an adversary (say, the superuser) might have the capability to read the contents of the memory holding a private key during some decryption process. For another possibility, think of RSA decryption which involves a modular exponentiation. If the standard square-and-multiply algorithm (Algorithm 3.9) is used for this purpose and the adversary can tap some hardware details (like machine cycles or power fluctuations) during a decryption process, she can guess a significant number of the bits in the private key. Such attacks, often called side-channel attacks, are particularly relevant for cryptographic applications based on smart cards.

A cryptographic system is (believed to be) strong if and only if there are no good known mechanisms to break it. It is, therefore, for the sake of security that we must study cryptanalysis. Cryptography and cryptanalysis are deeply intertwined and a complete study of one must involve the other.