Rabin cryptosystem
= Rabin cryptosystem
{c}
{wiki}
The <Rabin cryptosystem> uses modular squaring with public modulus $N=pq$, where $p$ and $q$ are distinct odd <prime numbers> kept secret. The raw encryption map sends a message representative $m$ to
$$
c=m^2\pmod N.
$$
Knowing the <prime factorization> lets the receiver compute <modular square roots> modulo each prime and combine them by the <Chinese remainder theorem>. For a message coprime to $N$, its ciphertext has exactly four roots modulo $N$, corresponding to the two sign choices modulo each prime. A full encryption scheme therefore needs a specified message encoding or other rule to select the intended root; raw modular squaring by itself is four-to-one on the units.<Handbook of Applied Cryptography by Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone>[Section 8.3: Rabin public-key encryption and root ambiguity]{ref}
For example, $N=7\cdot11=77$ and $m=10$ give $c=23$. Its four roots are $10,32,45,67$ modulo $77$. The relation to <integer factorization> is especially direct: two roots that differ by more than an overall sign reveal a nontrivial factor through a <greatest common divisor>. The <Rabin-Williams scheme> is a more specific variant, rather than another name for every <Rabin cryptosystem>.