Rabin cryptosystem

Rabin encryption sends $m$ to $m^2$ modulo a product of two secret primes. Decryption computes the four square roots by the Chinese remainder theorem.

For coprime moduli $N,N^{\prime }$ and $0<m<\min (N,N^{\prime })$, the Chinese remainder theorem recovers the integer $m^2$ uniquely in $[0,N{N}^{\prime })$ from the two ciphertexts. An ordinary integer square root then recovers the message. If distinct semiprime moduli share a factor, their greatest common divisor instead reveals factors of both moduli. Learning one message in the coprime case does not by itself give a general factoring algorithm or a decryption key for other ciphertexts.

If $N=pq$ and $x^2\equiv y^2(\mathrm{mod}N)$ while $x\not\equiv \pm y(\mathrm{mod}N)$, thenand $\gcd (x-y,N)$ is a nontrivial factor of $N$.

For $N=pq$ with distinct odd primes, choose a uniform unit $x$ and give only $x^2\mathrm{mod}N$ to an oracle returning any square root $y$. Conditional on this square, $x$ is uniform among four roots and independent of the oracle's choice. With probability one half, $y$ is not $\pm x$, and $\gcd (x-y,N)$ is a nontrivial factor. Thus full inversion of the squaring map yields randomized integer factorization; this reduction does not equate arbitrary partial leakage with full inversion.

If a purported authentication service returns a square root of every chosen square modulo a Rabin modulus, a verifier who knows one root obtains a different root with substantial probability and can factor the modulus. Repeating the challenge therefore reveals the private key.