Next: Subset-Sum (Knapsack) problems and Up: Encryption techniques based on Previous: The Rivest-Shamir-Adleman public key   Contents

Subsections

## 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 and . In the original RSA paper, 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 and a plaintext enabled one to find and . Then one could factor as follows:
1. Choose any .
2. Compute . [Remember, we are assuming is publicly available. Furthermore, can't be too hard to compute, or the code would be impractical.]
3. Use the assumed method to obtain , .
In words, we are unable to distinguish between the situation in which is obtained from (easy) and the (presumably difficult) situation in which is obtained from .

Rabin has suggested an alternative to the RSA system in which there is a direct connection to factoring. As in RSA, is announced publicly, with primes , 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 are known, it is easy to compute all the given .
2. If we are given , , and all the , we can calculate , .
We are not able to obtain , from just one of the , so the approach based on and described above won't work. One drawback of this system is that, even with knowledge of and , 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.

proof of 1: Since , there is an integer with . If , then using Corollary 8:

Similarly if [], then . The are given from Corollary 4 by

proof of 2: If we know the , there will be two like and above with and  mod . Thus we can calculate to obtain .

One problem with this system is that a person with access to a black box'' that computes could quickly discover , even if we assume that the person trying to break the code gets only one of the , chosen randomly. The attacker keeps generating pairs , until he gets an with or .

### Computing square roots modulo a prime

In the previous section, we assumed the primes were of the form in order to make the square root calculation as easy as possible. However, square roots can be efficiently calculated for any prime.

Let , where is odd. Define the sets

If is a square, it must be in . Thus the sets and partition the squares. Furthermore, by starting with and squaring, it is possible to identify which member of the partition includes .

If ,

so it is easy to calculate a square root of . (when , all )

Let be a non-square mod . Since for all non-squares, it is easy to find one.

We argue by induction on that square roots can be efficiently calculated for . We have seen that this is the case for . If , there is an even with . Specifically, if ,

Since is even, division of a square root of by gives a square root of .

Next: Subset-Sum (Knapsack) problems and Up: Encryption techniques based on Previous: The Rivest-Shamir-Adleman public key   Contents
Translated from LaTeX by Scott Sutherland
2002-12-14