New answers tagged


I'll assume this is not homework. It's actually quite simple: Pick a random value $r$ Compute $s = r^2 \bmod n$, and submit $s$ to the Rabin decryptor Since $s$ is a Quadratic Residue, the Rabin decryptor will return some value $t = \sqrt{s} \bmod n$. Now, $s$ has four square roots (assuming $n$ has two prime factors and you didn't happen to pick an $r$ ...

Top 50 recent answers are included