A public key system as hard as factoring

It is possible in theory that there is some way of computing $f^{-1}$ for the system in the previous section that does not involve determining $p$ and $q$. 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 $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 ${p,q}\equiv{3}\hbox{ (mod }{4})$. The encoding function is

$${f(M)}\equiv{M^2}\hbox{ (mod }{n})$$

The way we avoid the difficulty described above is that there are four numbers $M_1,M_2,M_3,M_4$ with $f(M_i){\equiv} f(M)$. The key facts are:

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

We are not able to obtain $p$, $q$ from just one of the $M_i$, 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 $M_i$, without being able to identify which one. In practice, this is not serious, since it is very unlikely that more than one of the $M_i$ would correspond to a feasible message.

proof of 1: Since ${p}\equiv{3}\hbox{ (mod }{4})$, there is an integer $k$ with $4k=p+1$. If ${x}\equiv{\left(f(M)\right)^k}\hbox{ (mod }{p})$, then using Corollary 8:

$$x^2{\equiv} \left(\left(M^2\right)^k\right)^2{\equiv} {M^{4k}}\equiv{M^2}\hbox{ (mod }{p})$$

Similarly if ${y}\equiv{\left(f(M)\right)^L}\hbox{ (mod }{q})$ [$4L=q+1$], then ${y^2}\equiv{M^2}\hbox{ (mod }{q})$. The $M_i$ are given from Corollary 4 by

$$\begin{array}{llll} {M_1}\equiv{x}\hbox{ (mod }{p})&{M_2}\equ... ...y}\hbox{ (mod }{q})&{M_4}\equiv{-y}\hbox{ (mod }{q})\end{array}$$

proof of 2: If we know the $M_i$, there will be two like $M_1$ and $M_3$ above with ${M_1+M_3}\equiv{0}\hbox{ (mod }{p})$ and $M_1+M_3\not{\equiv}0$ mod $q$. Thus we can calculate $(M_1+M_3,n)$ to obtain $p$.

One problem with this system is that a person with access to a ``black box'' that computes $f^{-1}$ could quickly discover $p,q$, even if we assume that the person trying to break the code gets only one of the $M_i$, chosen randomly. The attacker keeps generating pairs $M$, $f(M)$ until he gets an $M_i$ with $(M+M_i,n)=p$ or $q$.

Computing square roots modulo a prime

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

Let $p-1=2^ke$, where $e$ is odd. Define the sets

$$\begin{array}{ll}S_0=\{a\vert{a^e}\equiv{1}\hbox{ (mod }{p})\... ...\{a\vert{a^{2^{k-2}e}}\equiv{-1}\hbox{ (mod }{p})\} \end{array}$$

If $a$ is a square, it must be in $S_{k-1}$. Thus the sets $S_0$ and $T_i$, $0\le i\le k-2$ partition the squares. Furthermore, by starting with $a^e$ and squaring, it is possible to identify which member of the partition includes $a$.

If $a\in S_0$,

$$\left(a^{(e+1)/2}\right)^2{\equiv} a^e a{\equiv} a,$$

so it is easy to calculate a square root of $a$. (when $p=4n+3$, all $a\in S_0$)

Let $b$ be a non-square mod $p$. Since ${b^{2^{(k-1)}e}}\equiv{-1}\hbox{ (mod }{p})$ for all non-squares, it is easy to find one.

We argue by induction on $i$ that square roots can be efficiently calculated for $a\in S_i$. We have seen that this is the case for $S_0$. If $a\in S_{i+1}\setminus S_i=T_i$, there is an even $m$ with $ab^m\in S_{i-1}$. Specifically, if $m=2^{k-1-i}$,

$$\left(ab^m\right)^{2^ie}{\equiv} a^{2^ie}b^{2^{k-1}e}{\equiv}(-1)(-1) {\equiv}1$$

Since $m$ is even, division of a square root of $ab^m$ by $b^{m/2}$ gives a square root of $a$.