Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|improve this question
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
up vote 7 down vote accepted

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.

share|improve this answer

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.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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