7
$\begingroup$

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?

|improve this question
$\endgroup$
  • $\begingroup$ Do you mean $B$ chooses random $m$, computes $r$ and sends $r$ to $A$. Then, @daniel $r$ is by definition a quadratic residue. $\endgroup$ – DrLecter Jan 19 '14 at 19:24
  • $\begingroup$ 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? $\endgroup$ – TI Jones Jan 19 '14 at 19:27
  • $\begingroup$ @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. $\endgroup$ – DrLecter Jan 19 '14 at 19:31
  • $\begingroup$ I understand your clarification, lets assume the challenger chooses $m$ and computes everything and sends r to A, is it still not useful? $\endgroup$ – TI Jones Jan 19 '14 at 19:40
9
$\begingroup$

A is acting as a square-root oracle in that protocol. We can use that oracle to factor $n$ and break the scheme.

Suppose you are an attacker that wants to impersonate A. You:

  • 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.

|improve this answer
$\endgroup$
4
$\begingroup$

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.

|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.