= Solution
A <Rabin cryptosystem> chooses Blum primes $p,q$, publishes $N=pq$, and encrypts $m$ as $c=m^2\bmod N$. Decryption takes square roots modulo $p$ and $q$, combines them with CRT, and uses redundancy to select the intended one of four roots. Here $2355^2\equiv25\pmod{2773}$, while the obvious root is $5$. Thus
$$
\gcd(2355-5,2773)=47,\qquad\gcd(2355+5,2773)=59.
$$
So $2773=47\cdot59$ is factored, allowing all future square roots and hence all ciphertexts to be decrypted.
Back to article page
