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")
firstname.lastname@example.org, last updated