# Why is this authentication procedure using Rabin crypto not useful?

A friend asked me the following, pointing out that the method is not very useful (my problem is I do not see why it is not good):

• Consider a person A which chooses $n$ as the public key for the Rabin crypto-system.
• We want to be sure that we are communicating with person A so we send her a random item $r\equiv m^2 \mod n$.
• Person A receives $r$ and decodes it using the factorization of $n$ and finds a square rot $m_1$ of $r$.
• A then sends us $m_1$ and we check $r\equiv m_1^2 \mod n$.

Why is this not useful?

• Do you mean $B$ chooses random $m$, computes $r$ and sends $r$ to $A$. Then, @daniel $r$ is by definition a quadratic residue. – DrLecter Jan 19 '14 at 19:24
• I am not 100% sure how this can be interpreted, but in the case that $r$ is a quadrtic residue, is there anything strange in the method? – TI Jones Jan 19 '14 at 19:27
• @TIJones I just wanted to clarify if you mean the challenger chooses $m$, computes $r\equiv m^2 \pmod N$ and sends $r$ as a challenge to $A$? Because then, the issue raised by daniel is not an issue anymore since $r$ is is by definition a quadratic residue. – DrLecter Jan 19 '14 at 19:31
• I understand your clarification, lets assume the challenger chooses $m$ and computes everything and sends r to A, is it still not useful? – TI Jones Jan 19 '14 at 19:40

A is acting as a square-root oracle in that protocol. We can use that oracle to factor $n$ and break the scheme.
• Pick a random $m$;
• Send $m^2$ to A;
• Compute $p = \gcd(m_1 - m, n)$, thus factoring $n$.
This works with probability $1/2$ for each attempt.
Because $r$ is not guaranteed to be a Quadratic Residue, so for random $r$ there wouldn't be $m_1$ such that $r \equiv m_1^2(\mod n)$, therefore authentication will be impossible in this case.