I was looking at the exercises of Cryptography theory and practice and I could not find the answer to this question anyone has an idea?
$\begingroup$
$\endgroup$
$\begingroup$
$\endgroup$
Well, here's one obvious attack:
Eve wants to impersonate Alice.
Bob wants Eve to prove that she's Alice. Bob gives a value $x$ to Eve
Eve turns around, and asks Alice to prove that she (Alice) is Alice. Eve gives $x$ to Alice
Alice gives the value $y$ to Eve
Eve then gives the value $y$ to Bob
Of course, that's not the attack that Stinson is looking for...
For the attack that Stinson is thinking of, here's a hint:
For a random quadratic residue $x$, how many values of $y$ are there s.t. $y^2 = x$?
Suppose Bob picks a random value $y$ and computes $x = y^2 \bmod n$ and gives it to Alice, what is the probability that Alice will compute a $y'$ that's neither $y$ nor $n-y$?
If Bob knows $y$ and $y'$, what could he do with those values? Hint: consider $y^2 - y'^2 = (y + y')(y - y')$
