= Solution
For <Rabin cryptosystem>, choose primes $p,q\equiv3\pmod4$, publish $N=pq$, and encrypt $x$ as $x^2\bmod N$. The factors let the receiver take square roots modulo $p$ and $q$ and combine them using the <Chinese remainder theorem>; redundancy identifies the intended one of four roots.
For <RSA cryptosystem>, choose $N=pq$, select $e$ coprime to $\varphi(N)$ and $d$ with $ed\equiv1\pmod{\varphi(N)}$. Encrypt $x$ as $x^e$ and decrypt by raising to $d$ modulo $N$. Rabin inversion is provably equivalent to factoring, while ordinary RSA lacks that reduction; Rabin's disadvantage is its fourfold decryption ambiguity.
Back to article page
