Breaking the RSA system

Solving this one RSA challenge does not mean the RSA system is not a viable method of secure communications. However, the security of the RSA system relies on two as of yet unproven conjectures:

1.

The difficulty of decoding RSA messages is equivalent to that of factoring n. (In fact, you know a little more about the enciphering process; the exponent e is known and it is assumed that e is relatively prime to (p-1)(q-1). It is possible this could lead to a deciphering without factoring n, or it is possible this could ease the task of factoring n.)

2.

Factoring large integers is extremely difficult. (In fact, the progress over the last decade has shown that it is not as difficult as it used to be thought.)

To understand the above issues, it is necessary to study the underpinnings of complexity theory, the theory of measuring the difficulty of solution of various problems. The input to a problem may be measured by the number N of 0-1 bits needed to precisely write it down. For instance, in determining the primality or explicit factorization of a number n, the number of bits needed is essentially $\log_2 n$ which is a constant multiple of $\ln n$. For a particular algorithm, we may then compute the total number M of steps necessary to solve the problem, if indeed it does in fact solve the problem. What we mean by ``steps'' can be rigorously defined by means of the concept of a Deterministic (one-tape) Turing Machine (see [5]).

We say an algorithm is polynomial-time (or ``in P'') if there is a polynomial p(N) such that a solution is always arrived at with $M \leq p(N)$ steps. In the case of factoring or checking the primality of n, we can say more simply there should be a constant C so that

$$M \leq O( (\ln n)^C )$$

A problem is said to belong to the class P if there is a polynomial-time algorithm that solves the problem. The problem of deciding whether or not a given number n is prime is widely believed to belong to P, although this has not yet been proved. However, extremely fast algorithms are known, running in time

$$O( (\ln n)^{C\ln \ln n} )$$

by means of either the Adleman-Pomerance-Rumely-Cohen-Lenstra algorithm or Goldwasser-Kilian-Atkin-Morain algorithm (see [2]). These algorithms make it possible with commonly available computer systems to prove or disprove the primality of numbers of 1000 digits in a fairly short time. There have also been several strong theoretical results recently that give evidence that primality checking does indeed belong to P, including

Theorem 1 (G. Miller, 1976, [7])   If the Extended Riemann Hypothesis is true, then the problem of primality checking belongs to P.

Finally, as a demonstration of the practicality of primality checking, the number theory system PARI takes less than a second on a SPARCstation to prove that RSA-129 is composite.

Factoring is apparently a much harder problem. However, if we can in some mystical way guess a proper factor m of n, the algorithm of dividing m into n runs in polynomial-time (i.e. takes less than $O( (\ln n)^C)$ steps for some C). This aspect of the problem of factoring means that it belongs to the class of Nondeterministic Polynomial-time problems, or NP for short. The most important open problem in theoretical computer science today is to determine whether or not P=NP. There are certain problems in NP which are the most difficult in a certain sense. If any one of these problems, known as NP-complete problems, can be shown to belong to P, then all problems in NP belong to P. An example of such a problem is the Traveling Salesman Problem. It is suspected but not yet known that factoring is NP-complete.

The best known algorithms for factoring have an expected running time which is ``subexponential'', namely

$$O\big( e^{(\ln n)^{1/2} (\ln \ln n)^{1/2} (1+o(1))} \big)$$

With the invention of the Number Field Sieve by Pollard (not yet implemented), it is believed that the exponents may be replaced by 1/3 and 2/3, respectively. The factoring of RSA-129 now demonstrates that any number of roughly 130 digits may be factored in a ``reasonable'' amount of time.

The lack of certainty in our faith concerning the relative difficulty of primality checking versus factoring should cause a queasy feeling among the codemakers. The other leading public-key cryptosystem, the Merkle-Hellman system based on the knapsack problem, was broken by Adi Shamir in 1984, when he demonstrated a polynomial-time algorithm for uncovering the hidden key ([9]). Still, the RSA system is so widely respected that its commercialization has great momentum. The patents are controlled by a company called RSA Data Security, Inc., based in Redwood City, California, which has recently negotiated some large contracts with major computer vendors. The breaking of RSA-129 for now means only that much larger keys will be chosen; the disadvantage of larger keys will be added time and cost to the deciphering and enciphering procedure.