Breaking hashless variant of the Rabin Signature system with chosen message attack I heard that we can break the Rabin Signature system using chosen-message attack. For a message $M$ that is a quadratic residue modulo $N$, the signature is $x$ such that $x^2 \equiv M \pmod N$. I can't find a message to ask for its signature in order to spoof my message $M$.

Any suggestions?
Here's how the attack works:


Select a random value $y$
Compute $a = y^2 \bmod n$
Ask for the signature of $a$, that is $x$ with $x^2 = a$
If $x \ne y$ and $x + y \ne n$, then $\gcd(n, x+y)$ is a proper factor of $n$


The last step will succeed with probability $\approx 0.5$.  You can make it probability 1 if you select a $y$ with Jacobi symbol -1.