bsy is now at UCSD, and this page is no longer being maintained here.

Rabin's function is a public key cryptosystem for which the decryption was shown by Rabin to be equivalent to factoring. That is, unlike the RSA system, if you can decrypt messages encrypted by the Rabin function, you can also figure out the prime factors used in the modulus. The Rabin function is suitable for encryption but not digital signatures -- since the standard digital signature schemes require the signer to `decrypt' the message to be signed, this may be used by an attacker to obtain trial decryptions, leading to factorization. How this works should be clear once we go over the proof of why the Rabin function is equivalent to factoring.

Let `M` be the modulus, `M = pq`, `p`
and `q` primes known only to the recipient. The encryption
function is `E(m) = m^2`. Decryption is simply root
extraction. To find the square root modulo `M`, first find
roots modulo `p` and `q` individually using one
of the standard algorithms such as that due to Berlekamp
[Berlekamp] or that due to Adelman, Manders, and
Miller [AMM] and then apply the Chinese Remainder Theorem (CRT).

Note that `gamma`, the nontrivial square root of unity mod
`pq`, is exactly given by `(up-vq)`, where
`u` and `v` are coefficients found by the
extended euclidean algorithm such that `u p + v q = 1`.
Clearly, `gamma != +/- 1 mod M`, `gamma mod p =
1` and `gamma mod q = -1`, so `gamma^2 = 1 mod
M`.

(There are four square roots of unity modulo `pq` in all.
They can also obtained by solving the equations (via CRT):
`x = +/- 1 mod p` and `x = +/- 1 mod q`.)

Now, note that for any quadratic residue `t`, if
`s` is a root of `x^2 = t`, then so are
`-s`, `-gamma s`, and `gamma s`.
Suppose algorithm A finds square roots mod `pq`. To find
the factorization, generate a random `r`, and find `x
= A(r^2)`. With 1/2 probability, `r/x = +/- gamma`.
(`1/gamma = gamma`.) Having `+/- gamma`, we
compute `gcd((+/- gamma) - 1, pq)` --- `gamma =
up-vq` implies `gamma = 2up - 1 = 1 - 2vq`, thus the
`gcd` is one of `p` or `q`. The only
operations used are the arithmetic operations and `gcd`,
all of which are polynomial time.
This shows that if one can decrypt a message sent using Rabin's function,
then one can also factor products of two primes efficiently. Since
factoring is believed to be hard, so decrypting messages must also be
difficult.

@Article(Berlekamp, Key="Berklekamp", Author="E.~R. Berlekamp", Title="Factoring Polynomials Over Large Fields", Journal="Mathematics of Computation", Volume="24", Number="111", Pages="713--735", Year="1970") @InProceedings(AMM, Key="Adleman, Manders, Miller", Author="L. Adleman and K. Manders and G. Miller", Title="On Taking Roots In Finite Fields", BookTitle="Proceedings of the Nineteenth IEEE Symposium on Foundations of Computer Science", pages="715--177", Month="October", Year="1977")

| | | | |

bsy@cs.cmu.edu / bsy@cse.ucsd.edu, last updated 4 April 1996.

Join the Blue Ribbon Anti-Censorship Campaign!