Return to Answer

This proof was published by Michael Rabin in 1979 in a technical report on a proposal for a public-key signature scheme to justify its security in relation to factoring. Unlike the trivially breakable RSA proposal (paywall-free) that preceded it, Rabin's signature scheme was the first signature scheme in history that still stands under modern scrutiny, provided suitable parameter sizes are chosen, through the use of hashing not merely as a method to compress large messages but as an integral part of security to destroy the structure of messages. Today, textbooks and Wikipedia consistently misrepresent Rabin's cryptosystem as a broken encryption scheme or as a broken hashless signature scheme, as if almost nobody has ever bothered to read the paper. Whether Rabin was the first to publish a proof that square roots enable factoring, I don't know—it seems likely that a number theorist before him would have come upon the same result.

This proof was published by Michael Rabin in 1979 in a technical report on a proposal for a public-key signature scheme to justify its security in relation to factoring. Unlike the trivially breakable RSA proposal (paywall-free) that preceded it, Rabin's signature scheme was the first signature scheme in history that still stands under modern scrutiny, provided suitable parameter sizes are chosen, through the use of hashing not merely as a method to compress large messages but as an integral part of security to destroy the structure of messages. Today, textbooks and Wikipedia consistently misrepresent Rabin's cryptosystem as a broken encryption scheme or as a broken hashless signature scheme, as if almost nobody has ever bothered to read the paper.

Whether Rabin was the first to publish a proof that square roots enable factoring, I don't know—Fermat wrote a letter to Mersenne in about 1643 observing that finding a way to write $n$ as a difference of squares leads to factorization, so it seems likely that a number theorist before Rabin would have come upon the same incremental refinement that a modular square root algorithm leads to a factoring algorithm. But, then again, until the development of public-key cryptography in the 1970s, perhaps there would have been little interest in that observation without a square root algorithm in the first place, which obviously we didn't have then and still don't have now!

Suppose you have a random algorithm $S(y, n)$ that can, with cost $C$ and success probability $\varepsilon$, compute a square root of a random quadratic residue $y$ modulo a product $n = pq$ of random primes. (For example, this algorithm can be derived from a Rabin signature forger in the random oracle model.) Can you use $S$ as a subroutine in a random algorithm $F(n)$ to factor $n$? Yes!

Define the algorithm $F(n)$ as follows:

1. Pick $0 \leq x < n$ uniformly at random.
2. Compute $y = x^2 \bmod n$.
3. Compute $\xi = S(y, n)$.
4. If $x \pm \xi \equiv 0 \pmod n$, fail; otherwise return $\gcd(x \pm \xi, n)$.

The cost of this algorithm is one random choice between $n$ possibilities, one squaring modulo $n$, $C$ (the cost of $S$), and one gcd with $n$—so this algorithm costs little more than any algorithm to compute square roots. What's the success probability?

Step 1 always succeeds. Step 2 always succeeds. Step 3 succeeds with probability $\varepsilon$. Step 4 is the interesting step.

• Every quadratic residue, like $y$, has up to four distinct square roots modulo $n$: two square roots modulo $p$, and two square roots modulo $q$. If we can find two distinct roots $x$ and $\xi$ of $y$—distinct by more than just sign—then since $x^2 \equiv y \pmod n$ and $\xi^2 \equiv y \pmod n$, we have $x^2 \equiv \xi^2 \pmod n$ with the nontrivial integer equation $$k n = x^2 - \xi^2 = (x + \xi) (x - \xi)$$ for some $k$. And further, we know that $n$ cannot divide $x \pm \xi$ since $x \pm \xi \not\equiv 0 \pmod n$. Thus $$n \mid (x + \xi) (x - \xi), \quad \text{but} \quad n \nmid x \pm \xi.$$ Consequently, since integers have unique factorization, $n = pq$ must share some but not all factors with $x \pm \xi$, so $\gcd(x \pm \xi, n)$ returns a nontrivial factor in the case that $x \pm \xi \not\equiv 0 \pmod n$.

There's about a 1/2 chance that $S$ returns $\pm x$ so that $x \pm \xi \equiv 0 \pmod n$: $S$ can't know which of the four square roots $x$ of $y$ we began with even if it wanted to thwart us. So step 4 succeeds with probability about 1/2, and the algorithm succeeds with probability about $\varepsilon/2$. If we retry until success, the expected number of trials to factor $n$ is about 2.

The same technique, alas, does not work to show that the RSA problem—inverting $x \mapsto x^e \bmod n$ when $\gcd(e, \phi(n)) = 1$—can't be much easier than factoring, because there is at most one $e^{\mathit{th}}$ root: by Bézout's identity, there exists some $d$ and $k$ such that $d e - k \phi(n) = \gcd(e, \phi(n)) = 1$, or $e d = 1 + k \phi(n)$, and so if $y \equiv x^e \pmod n$, then $$y^d \equiv (x^e)^d \equiv x^{ed} \equiv x^{1 + k\phi(n)} \equiv x \cdot (x^{\phi(n)})^k \equiv x \pmod n,$$ by Euler's theorem; consequently $x \mapsto x^e \bmod n$ is a bijection.

Suppose you have a random algorithm $S(y, n)$ that can, with cost $C$ and success probability $\varepsilon$, compute a square root of a random quadratic residue $y$ modulo a product $n = pq$ of random primes. (For example, this algorithm can be derived from a Rabin signature forger in the random oracle model.) Can you use $S$ as a subroutine in a random algorithm $F(n)$ to factor $n$? Yes!

Define the algorithm $F(n)$ as follows:

1. Pick $0 \leq x < n$ uniformly at random.
2. Compute $y = x^2 \bmod n$.
3. Compute $\xi = S(y, n)$.
4. If $x \pm \xi \equiv 0 \pmod n$, fail; otherwise return $\gcd(x \pm \xi, n)$.

The cost of this algorithm is one random choice between $n$ possibilities, one squaring modulo $n$, $C$ (the cost of $S$), and one gcd with $n$—so this algorithm costs little more than any algorithm to compute square roots. What's the success probability?

Step 1 always succeeds. Step 2 always succeeds. Step 3 succeeds with probability $\varepsilon$. Step 4 is the interesting step.

• Every quadratic residue, like $y$, has up to four distinct square roots modulo $n$: two square roots modulo $p$, and two square roots modulo $q$. If we can find two distinct roots $x$ and $\xi$ of $y$—distinct by more than just sign—then since $x^2 \equiv y \pmod n$ and $\xi^2 \equiv y \pmod n$, we have $x^2 \equiv \xi^2 \pmod n$ with the nontrivial integer equation $$k n = x^2 - \xi^2 = (x + \xi) (x - \xi)$$ for some $k$. And further, we know that $n$ cannot divide $x \pm \xi$ since $x \pm \xi \not\equiv 0 \pmod n$. Thus $$n \mid (x + \xi) (x - \xi), \quad \text{but} \quad n \nmid x \pm \xi.$$ Consequently, since integers have unique factorization, $n = pq$ must share some but not all factors with $x \pm \xi$, so $\gcd(x \pm \xi, n)$ returns a nontrivial factor in the case that $x \pm \xi \not\equiv 0 \pmod n$.

There's about a 1/2 chance that $S$ returns $\pm x$ so that $x \pm \xi \equiv 0 \pmod n$: $S$ can't know which of the four square roots $x$ of $y$ we began with even if it wanted to thwart us. So step 4 succeeds with probability about 1/2, and the algorithm succeeds with probability about $\varepsilon/2$. If we retry until success, the expected number of trials to factor $n$ is about 2.

This proof was published by Michael Rabin in 1979 in a technical report on a proposal for a public-key signature scheme to justify its security in relation to factoring. Unlike the trivially breakable RSA proposal (paywall-free) that preceded it, Rabin's signature scheme was the first signature scheme in history that still stands under modern scrutiny, provided suitable parameter sizes are chosen, through the use of hashing not merely as a method to compress large messages but as an integral part of security to destroy the structure of messages. Today, textbooks and Wikipedia consistently misrepresent Rabin's cryptosystem as a broken encryption scheme or as a broken hashless signature scheme, as if almost nobody has ever bothered to read the paper. Whether Rabin was the first to publish a proof that square roots enable factoring, I don't know—it seems likely that a number theorist before him would have come upon the same result.

The same technique, alas, does not work to show that the RSA problem—inverting $x \mapsto x^e \bmod n$ when $\gcd(e, \phi(n)) = 1$—can't be much easier than factoring, because there is at most one $e^{\mathit{th}}$ root: by Bézout's identity, there exists some $d$ and $k$ such that $d e - k \phi(n) = \gcd(e, \phi(n)) = 1$, or $e d = 1 + k \phi(n)$, and so if $y \equiv x^e \pmod n$, then $$y^d \equiv (x^e)^d \equiv x^{ed} \equiv x^{1 + k\phi(n)} \equiv x \cdot (x^{\phi(n)})^k \equiv x \pmod n,$$ by Euler's theorem; consequently $x \mapsto x^e \bmod n$ is a bijection.

Suppose you have a random algorithm $S(y, n)$ that can, with cost $C$ and success probability $\varepsilon$, compute a square root of a random quadratic residue $y$ modulo a product $n = pq$ of random primes. (For example, this algorithm can be derived from a Rabin signature forger in the random oracle model.) Can you use $S$ as a subroutine in a random algorithm $F(n)$ to factor $n$? Yes!

Define the algorithm $F(n)$ as follows:

1. Pick $0 \leq x < n$ uniformly at random.
2. Compute $y = x^2 \bmod n$.
3. Compute $\xi = S(y, n)$.
4. If $x \pm \xi \equiv 0 \pmod n$, fail; otherwise return $\gcd(x \pm \xi, n)$.

The cost of this algorithm is one random choice between $n$ possibilities, one squaring modulo $n$, $C$ (the cost of $S$), and one gcd with $n$—so this algorithm costs little more than any algorithm to compute square roots. What's the success probability?

Step 1 always succeeds. Step 2 always succeeds. Step 3 succeeds with probability $\varepsilon$. Step 4 is the interesting step.

• Every quadratic residue, like $y$, has up to four distinct square roots modulo $n$: two square roots modulo $p$, and two square roots modulo $q$. If we can find two distinct roots $x$ and $\xi$ of $y$—distinct by more than just sign—then since $x^2 \equiv y \pmod n$ and $\xi^2 \equiv y \pmod n$, we have $x^2 \equiv y^2 \pmod n$ with the nontrivial integer equation $$k n = x^2 - \xi^2 = (x + \xi) (x - \xi)$$ for some $k$. And further, we know that $n$ cannot divide $x \pm \xi$ since $x \pm \xi \not\equiv 0 \pmod n$. Thus $$n \mid (x + \xi) (x - \xi), \quad \text{but} \quad n \nmid x \pm \xi.$$ Consequently, since integers have unique factorization, $n = pq$ must share some but not all factors with $x \pm \xi$, so $\gcd(x \pm \xi, n)$ returns a nontrivial factor in the case that $x \pm \xi \not\equiv 0 \pmod n$.

There's about a 1/2 chance that $S$ returns $\pm x$ so that $x \pm \xi \equiv 0 \pmod n$: $S$ can't know which of the four square roots $x$ of $y$ we began with even if it wanted to thwart us. So step 4 succeeds with probability about 1/2, and the algorithm succeeds with probability about $\varepsilon/2$. If we retry until success, the expected number of trials to factor $n$ is about 2.

The same technique, alas, does not work to show that the RSA problem—inverting $x \mapsto x^e \bmod n$ when $\gcd(e, \phi(n)) = 1$—can't be much easier than factoring, because there is at most one $e^{\mathit{th}}$ root.

Suppose you have a random algorithm $S(y, n)$ that can, with cost $C$ and success probability $\varepsilon$, compute a square root of a random quadratic residue $y$ modulo a product $n = pq$ of random primes. (For example, this algorithm can be derived from a Rabin signature forger in the random oracle model.) Can you use $S$ as a subroutine in a random algorithm $F(n)$ to factor $n$? Yes!

Define the algorithm $F(n)$ as follows:

1. Pick $0 \leq x < n$ uniformly at random.
2. Compute $y = x^2 \bmod n$.
3. Compute $\xi = S(y, n)$.
4. If $x \pm \xi \equiv 0 \pmod n$, fail; otherwise return $\gcd(x \pm \xi, n)$.

The cost of this algorithm is one random choice between $n$ possibilities, one squaring modulo $n$, $C$ (the cost of $S$), and one gcd with $n$—so this algorithm costs little more than any algorithm to compute square roots. What's the success probability?

Step 1 always succeeds. Step 2 always succeeds. Step 3 succeeds with probability $\varepsilon$. Step 4 is the interesting step.

• Every quadratic residue, like $y$, has up to four distinct square roots modulo $n$: two square roots modulo $p$, and two square roots modulo $q$. If we can find two distinct roots $x$ and $\xi$ of $y$—distinct by more than just sign—then since $x^2 \equiv y \pmod n$ and $\xi^2 \equiv y \pmod n$, we have $x^2 \equiv \xi^2 \pmod n$ with the nontrivial integer equation $$k n = x^2 - \xi^2 = (x + \xi) (x - \xi)$$ for some $k$. And further, we know that $n$ cannot divide $x \pm \xi$ since $x \pm \xi \not\equiv 0 \pmod n$. Thus $$n \mid (x + \xi) (x - \xi), \quad \text{but} \quad n \nmid x \pm \xi.$$ Consequently, since integers have unique factorization, $n = pq$ must share some but not all factors with $x \pm \xi$, so $\gcd(x \pm \xi, n)$ returns a nontrivial factor in the case that $x \pm \xi \not\equiv 0 \pmod n$.

There's about a 1/2 chance that $S$ returns $\pm x$ so that $x \pm \xi \equiv 0 \pmod n$: $S$ can't know which of the four square roots $x$ of $y$ we began with even if it wanted to thwart us. So step 4 succeeds with probability about 1/2, and the algorithm succeeds with probability about $\varepsilon/2$. If we retry until success, the expected number of trials to factor $n$ is about 2.

The same technique, alas, does not work to show that the RSA problem—inverting $x \mapsto x^e \bmod n$ when $\gcd(e, \phi(n)) = 1$—can't be much easier than factoring, because there is at most one $e^{\mathit{th}}$ root: by Bézout's identity, there exists some $d$ and $k$ such that $d e - k \phi(n) = \gcd(e, \phi(n)) = 1$, or $e d = 1 + k \phi(n)$, and so if $y \equiv x^e \pmod n$, then $$y^d \equiv (x^e)^d \equiv x^{ed} \equiv x^{1 + k\phi(n)} \equiv x \cdot (x^{\phi(n)})^k \equiv x \pmod n,$$ by Euler's theorem; consequently $x \mapsto x^e \bmod n$ is a bijection.