Past exam of the mathematics course of the University of Cambridge / 2022 / ii / Paper 2 / 12K / a / Solution

In the Rabin cryptosystem, the public key is $N=pq$ and encryption sends an encoded message $m$ toKnowing $p,q$, the receiver finds the two square roots modulo each prime and combines them with the Chinese remainder theorem to obtain four roots modulo $N$; prescribed redundancy identifies the intended one.

Omicron hasThe Chinese remainder theorem determines $m^2$ uniquely modulo $N{N}^{\prime }$ (assuming the independently generated moduli are coprime; a nontrivial gcd would itself factor them). Since $1\le m<N<N^{\prime }$, one has $m^2<N{N}^{\prime }$, so this residue is the ordinary integer $m^2$. Taking its positive integer square root recovers $m$.

This does not normally decrypt another ciphertext sent under only one modulus. The recovered pair reveals no nontrivial square root collision modulo that modulus and hence supplies no factorization; breaking a single Rabin instance remains equivalent to factoring its modulus.