Suppose Alice has two primes $p$ and $q$ such that $p\equiv q \equiv 3 \pmod 4$. $n=p\cdot q$ is part of her certificate to identify her. A party say Bob, sends her a random quadratic residue ${}\bmod n$, say $x$. To identify her, Alice computes $y$, a square root of $x$ and send it to Bob. He simply verifies $y^2\equiv x\pmod n$.

This completes the verification but Bob can now impersonate Alice. I am stuck trying to find what information does calculating square root modulo $n$ leak. I am guessing it has something to do with the fact that $p\equiv q \equiv 3\pmod 4$.

My question is after this, how can Bob calculate a square root modulo $n?$ That is if someone, say Eve, sends Bob a quadratic residue ${}\bmod n$, say $z$, how can Bob calculate a square root, say $d$, i.e, $d^2\equiv z\pmod n$, i.e., how can Bob convince Eve that she is communicating with Alice?


The problem with the protocol isn't specifically that it allows Bob to perform square-roots on his own; it's that it allows Bob to deduce the factorization of $n$ with high probability (and with that, he can perform square-roots).

Here's how Bob would do this:

  • He selects a random value $0 < r < n$, computes $x = r^2 \bmod n$, and sends $x$ to Alice.

  • Now, $x$ actually has 4 square roots modulo $n$ (unless $x$ happens not to be relatively prime to $n$; that's improbable). Alice picks one of the four, and returns that value $y$ to Bob.

  • Bob now has two values $r$ and $y$ with $r^2 \equiv y^2 (\bmod\ n)$, or in other words, $r^2-y^2 = (r-y)(r+y) = kn$ for some integer $k$ (note: this equation is in the ring of integers, not in the ring of integers modulo $n$).

  • If $r \ne y$ and $r \ne -y$ (probability 0.5, because $r$ was selected randomly, and $y$ has 4 possible values, 2 of which satisfy one of the relations, and 2 of which satisfy neither), then $(r-y)(r+y)$ is a multiple of $n$, but neither $(r-y)$ nor $(r+y)$ is a multiple of $n$. Hence, one of $r-y$, $r+y$ must be a multiple of p, and the other must be a multiple of q.

That is, a straight-forward computation of $gcd( n, r+y )$ directly yields one of the prime factors of $n$.

This happens with probability 0.5; if Bob knows how Alice selects which of the four possible square roots (e.g. she always selects the one that is itself a quadratic residue), then he can increase this probability by putting conditions on the $r$ he selects.

| improve this answer | |
  • $\begingroup$ Thanks for this. I have one more doubt. To an observer who simply watches the exchange described above, I think the scheme is zero knowledge. Am I correct? because whatever information Bob has(as described above), no observer can have that. $\endgroup$ – TheNoob Oct 11 '13 at 23:48
  • $\begingroup$ @RahulRawat: yes, to someone just listening in, they cannot learn anything, and we can show that by using the standard zero knowledge proof; they can simulate an exchange (using only the public knowledge) that is indistinguishable from a real exchange. $\endgroup$ – poncho Oct 12 '13 at 2:05

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.