# Quadratic Residues in identification setting

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.

• 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. – TheNoob Oct 11 '13 at 23:48
• @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. – poncho Oct 12 '13 at 2:05