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?


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')$


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.