# bsy's Explanation of Why Rabin Function is Equivalent to Factoring

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.

## Rabin Function: Extracting Square Roots Equivalent To Factoring

Here's where some simple number theory kicks in. Below,
`^` and `_` denotes super- and sub- scripts. I
show that if an algorithm A exists which can find a square root of a
number modulo `pq`, then that algorithm can be used to
factor `pq` with a `1/2` probability; by
iterating, we can make the probability of extracting factors as close
to certainly as desired. This observation was originally due to M.
O. Rabin.
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.

*Lecture Notes on the Complexity of Some Problems in Number Theory
by Dana Angluin, Yale CS TR 243 Aug '82*, contains an excellent
description of many number theoretic algorithms.
@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")

[
search CSE |
CSE |
bsy's home page |
links |
webster |
MRQE |
google |
yahoo |
citeseer |
pgp certserver |
openpgp certserver |
geourl's
meatspace
]

bsy+www@bennetyee.org, last updated Mon Dec 13 23:22:08 PST 2004. Copyright 2004 Bennet Yee.

email bsy.