[Download postscript version]

 

A public key system as hard as factoring

It is possible in theory that there is some way of computing for the system in the previous section that does not involve determining p and q. In the original RSA paper [RSA78], the authors say

It may be possible to prove that any general method of breaking our scheme yields an efficient factoring algorithm. This would establish that any way of breaking our scheme must be as difficult as factoring. We have not been able to prove this conjecture, however.

To see the difficulties involved in trying to prove such a thing, suppose that one could show that knowledge of a ciphertext f(M) and a plaintext M enabled one to find p and q. Then one could factor n as follows:

1. Choose any M.
2. Compute f(M). (Remember, we are assuming f is publicly available. Furthermore, f(M) can't be too hard to compute, or the code would be impractical.)
3. Use the assumed method to obtain p, q.

In words, we are unable to distinguish between the situation in which f(M) is obtained from M (easy) and the (presumably difficult) situation in which M is obtained from f(M).

Rabin has suggested an alternative to the RSA system in which there is a direct connection to factoring. As in RSA, n=pq is announced publicly, with primes p, q kept secret. For technical reasons, we assume . The encoding function is

The way we avoid the difficulty described above is that there are four numbers with . The key facts are:

1. If p,q are known, it is easy to compute all the given f(M).
2. If we are given n, f(M), and all the , we can calculate p, q.

We are not able to obtain p, q from just one of the , so the approach based on M and f(M) described above won't work. One drawback of this system is that, even with knowledge of p and q, one can only say the number sent is one of the four , without being able to identify which one. In practice, this is not serious, since it is very unlikely that more than one of the would correspond to a feasible message.

Unfortunately, this cryptosystem is vulnerable to a chosen-plaintext attack, even if we assume that the person trying to break the code gets only one of the , chosen randomly. The attacker keeps generating pairs M, f(M) until he gets an with or q.