next up previous
Next: Cryptosystems Based on Discrete Up: Mathematical Models in Public-Key Previous: Theory and Models

Cryptosystems Based on Integer Factorization

  Given two primes, say p = 863 and q = 877, it is an easy process to multiply them by hand to get the product n = 756851. However, it is not nearly so easy to determine by hand the factors p and q from only a knowledge of the product 756851. In a similar fashion, if p and q are large, say 1,000 digits each, then a computer can readily find the 2,000 digit product (since multiplying two k-digit numbers requires at most tex2html_wrap_inline854 operations), but even the fastest of today's computers cannot generally determine the factors from only the product. This leads us to consider two central problems in the history of mathematics, namely the problems of (a) determining whether a given integer is a prime, and (b) determining the factorization into primes of a given integer. These two problems have been attacked by some of the best mathematicians of all time, including the great C. F. Gauss (1777-1855) who wrote [9]:
The problem of distinguishing prime numbers from composite numbers and of resolving the latter into their prime factors is known to be one of the most important and useful in arithmetic. It has engaged the industry and wisdom of ancient and modern geometers to such an extent that it would be superfluous to discuss the problem at length tex2html_wrap_inline856 Further, the dignity of the science itself seems to require solution of a problem so elegant and so celebrated.
Gauss wrote these words some 175 years before primality testing and the integer factorization problem were applied to modern day cryptography, so as important as they were in Gauss' day, they are even more important today.

It is clear from his words that Gauss realized that primality testing was a different problem from that of integer factorization, and since his time, significant progress has been made on both of these problems. For example, there is an efficient probabilistic algorithm called the Rabin-Miller test (see [3, ]) which can recognize a composite number of say 1,000 digits without ever factoring that number, and the primality of a number can also be determined efficiently [1, ]. There have also been developed over the years much improved factoring algorithms [13], but despite this progress, factoring a general composite number with as few as say 200 digits is still out of reach of the fastest computers using the best algorithms known today.

It is not our purpose here to delve into the theory of primality testing and integer factorization (for which we refer the reader to [13, 20] for recent developments). Instead, we simply wish to emphasize that it is easy to generate and multiply large prime numbers but it is not generally possible to factor the resulting answer in reasonable time; that is, integer multiplication appears to be a one-way function. This belief forms the basis for several public-key cryptosystems. We will discuss two of these after reviewing several ideas from modular arithmetic.

Let n be a positive integer and let tex2html_wrap_inline862 denote the ring of integers modulo n. It turns out that exponentiation in this ring is easy; i.e., for any tex2html_wrap_inline866 and positive integer e, the computation of tex2html_wrap_inline870 can be done efficiently. We demonstrate how this is done with an example.
The above idea can be generalized to show that tex2html_wrap_inline878 can be computed with tex2html_wrap_inline880 squarings and at most tex2html_wrap_inline880 multiplications, where tex2html_wrap_inline884 is the length of e in its binary representation. So, for any tex2html_wrap_inline866 and e>0, tex2html_wrap_inline870 can be computed efficiently.

Now consider the reverse of the operation of exponentiation modulo n. Assuming n is specified, two different problems arise: (a) given tex2html_wrap_inline898 and tex2html_wrap_inline900, find an integer x (if one exists) such that tex2html_wrap_inline904; and (b) given e and tex2html_wrap_inline900, find x (if one exists) such that tex2html_wrap_inline912. These two problems are intrinsically different and each of them leads to a public-key cryptosystem.

Problem (a) is called the discrete logarithm problem modulo n and is believed hard for almost all n. (For certain values of n it is easy; e.g., when n has only small prime factors or when n is a prime but n-1 has only small prime factors.) We will discuss this problem and its relation to the ElGamal system in the next section.

Problem (b) asks for the computation of an eth root of an integer y modulo n. This is easy when the complete factorization of n is known but believed hard otherwise. For cryptographic purposes, the most important case is when n is the product of two large (distinct) primes and this is the case we shall develop here. (Our discussion can be readily generalized to the situation where n is square-free.) The RSA system arises when we examine this situation with tex2html_wrap_inline938 and the Rabin system comes from considering the case in which e divides tex2html_wrap_inline942. Here tex2html_wrap_inline942 is the familiar Euler tex2html_wrap_inline946-function which equals the number of integers in tex2html_wrap_inline948 that are relatively prime to n. When n = pq with p and q distinct primes, it is given by tex2html_wrap_inline958.

Assume then that n= pq and let e be an integer with tex2html_wrap_inline938. Then there exists an integer d such that tex2html_wrap_inline968. Using Fermat's little theorem, it is straightforward to show that
This means that for any tex2html_wrap_inline970, tex2html_wrap_inline972 is an eth root of x modulo n; hence an eth root of x can be computed efficiently provided d is known. Thus an important question is whether d be computed efficiently.

The answer is yes if n can be factored but no otherwise. To explain this statement, first assume that the complete factorization of n into primes is known. Then tex2html_wrap_inline942 can be computed quickly. By applying the extended Euclidean algorithm [3] to e and tex2html_wrap_inline942, it is easy to find d such that tex2html_wrap_inline968. Conversely, assume that a number d is known with tex2html_wrap_inline968. Then tex2html_wrap_inline1006 is a multiple of tex2html_wrap_inline942. By Exercise 9.3, n can be easily factored using tex2html_wrap_inline1012. Hence computing d from e and n is equivalent to factoring n. Therefore, the factors of n provide a trap-door for inverting the function tex2html_wrap_inline1024 defined as
where tex2html_wrap_inline1026 denotes the smallest nonnegative integer congruent to tex2html_wrap_inline1028 modulo n.

We can now describe the RSA cryptosystem, which bases its security on the belief that the class of functions tex2html_wrap_inline1032 are trap-door one-way functions.
We also need a rule for generating a random pair of public and private keys (e,n) and (d,n), but this is not difficult. We have mentioned that primality testing can be done efficiently and further there are many primes with a given number say of t digits (by the prime number theorem). This means that one can generate a t-digit prime as follows. Choose a random number of t digits and test it for primality. If it is not prime, repeat the procedure until a prime is obtained. In this way one can get a pair of primes p and q of any desired size. Then defining n=pq and N=(p-1)(q-1), one may choose a random integer tex2html_wrap_inline1078 such that tex2html_wrap_inline1080. For this e, it is a simple matter to compute d with tex2html_wrap_inline1086. Then (e,n) is a public key and (d,n) is the corresponding private key.

We should point out that, even though computing d from e and n is equivalent to factoring n, it has not been proven that inverting tex2html_wrap_inline1032 is equivalent to computing d or factoring n, as there may exist some other method to compute eth roots modulo n without factoring n or computing d. This raises the following research question.

Open Problem. Given a composite integer n and a positive integer e with tex2html_wrap_inline938, prove or disprove that computing eth roots modulo n is equivalent to factoring n.

We next consider the case in which e divides tex2html_wrap_inline942, used in the Rabin system. Here, the function tex2html_wrap_inline1032 is no longer a permutation on tex2html_wrap_inline948 since for a given e and y, there can be several x that map to the same y under tex2html_wrap_inline1032. However, if e is small relative to n, say tex2html_wrap_inline1148 for some constant c, then it can be proved that finding the inverse images of y under tex2html_wrap_inline1032 is equivalent to factoring n. Thus, if e is (say) one of 2, 3, 5, 6, 7, then tex2html_wrap_inline1032 is a candidate trap-door one-way function where the factors of n again provide the trap-door for inverting tex2html_wrap_inline1032. Such trap-door one-way functions can be used to build up public-key cryptosystems; indeed, the Rabin system uses only the function tex2html_wrap_inline1168 and is described as follows.

To decrypt a ciphertext under the Rabin system, we need to describe how to compute square roots modulo n given the factors of n. The idea is to compute square roots modulo each prime factor of n separately and then use the Chinese remainder theorem to combine them to get a square root modulo n. Suppose that tex2html_wrap_inline1202 has a square root modulo n. Then c also has square roots modulo p and q. Moreover, if r and s are some square roots of c modulo p and q, respectively, and if a and b are integers such that ap+bq=1, then it is easy to check that
is a square root of c modulo n for any choice of + and - signs. This gives four square roots of c. It can be shown that c has exactly four square roots if and only if tex2html_wrap_inline1242 and c has at least one square root modulo n. To get the correct plaintext one just needs to check which of the roots is in tex2html_wrap_inline548.

It remains to show how to compute square roots modulo a prime p. But this is also easy, especially when tex2html_wrap_inline1252, for then tex2html_wrap_inline1254 is a square root of c whenever c is a quadratic residue in tex2html_wrap_inline1260: that is, tex2html_wrap_inline1262 for some tex2html_wrap_inline1264. If p is congruent to 1 modulo 4, square roots modulo p can also be computed efficiently but will not be described here (see [3, 5] for details). Hence computing square roots modulo n=pq is easy when p and q are known.

We conclude this section by showing that if one can compute square roots modulo n then one can actually factor n; that is, we show that computing square roots modulo n is equivalent to factoring n. This also provides a nice example illustrating the power of randomness in computing. Suppose that there is an algorithm tex2html_wrap_inline1288 which, when presented a quadratic residue tex2html_wrap_inline970, outputs a square root of x in tex2html_wrap_inline948, denoted by tex2html_wrap_inline1296. (One may think of tex2html_wrap_inline1288 as an algorithm, a black box, or an oracle.) Then n can be factored by the following simple algorithm. First, pick a nonzero element tex2html_wrap_inline1302 uniform randomly and compute tex2html_wrap_inline1304. Next, input x to tex2html_wrap_inline1288 and get tex2html_wrap_inline1310. Then compute tex2html_wrap_inline1312. It can be shown that for each run of the algorithm, the computed number h is a proper factor of n with probability at least 1/2. If the algorithm is run t times, then the probability of getting a factor of n is at least tex2html_wrap_inline1324. Thus for t=10, the chance of finding a factor of n is over tex2html_wrap_inline1330! Therefore n can be factored quickly.

As we have indicated, breaking the Rabin system is equivalent to factoring integers. This is the first example of a public-key cryptosystem with provable security against a passive adversary who can only eavesdrop. Compared to the RSA system, the encryption in Rabin system is more efficient (only one square), and the decryption costs approximately the same as in RSA. However, the same proof above shows that the Rabin system is totally insecure against an active adversary who can mount a chosen ciphertext attack. Under this attack, an adversary chooses some (possibly many) ciphertexts and asks for the corresponding plaintexts, then deduces from them the secret key. The reader should be able to see why this attack works against the Rabin system. Because of this, the Rabin system is not used in practice.

next up previous
Next: Cryptosystems Based on Discrete Up: Mathematical Models in Public-Key Previous: Theory and Models

Shuhong Gao
Sun Oct 17 11:04:53 EDT 1999