= Repeated-message attack on the Rabin cryptosystem
{c}
{title2=$m^2\bmod N,\ m^2\bmod N'$}
For coprime moduli $N,N'$ and $0<m<\min(N,N')$, the <Chinese remainder theorem> recovers the integer $m^2$ uniquely in $[0,NN')$ 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.
Back to article page
