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 &lt; r &lt; 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.