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

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.

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")

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

Join the Blue Ribbon Anti-Censorship Campaign!