1
$\begingroup$

I am trying to understand the Fiat-Shamir identification protocol, but have a problem with understanding how this protocol is supposed to be save, even if you repeat it several times. I am using algorithm's description from http://www.cs.rit.edu/~jjk8346/paper.pdf.

If I do the maths, A can always convince B without knowing s. The problem here is step 4. A just has to calculate $y=(x*v^e)^{\frac{1}{2}}$ and send it to B. Because now B will always accept this, since his condition is $y^2 = x*v^e \operatorname{mod} n \Longleftrightarrow (x*v^e)^{\frac{1}{2}*2} = x*v^e \operatorname{mod} n \Longleftrightarrow x*v^e = x*v^e \operatorname{mod} n$, which is always going to be true.

The problem is that on the right side of the equation $y^2 = x*v^e \operatorname{mod} n$ there are only values A knows, so for A it is no problem to put in something for $y$ so that the equation will always be correct.

|improve this question
$\endgroup$
2
$\begingroup$

A just has to calculate $y=(x*v^e)^{\frac{1}{2}}$ and send it to B.

Yes, if that was easy, the protocol would be breakable. However, finding square roots modulo a composite number is as difficult as factoring that number.

See: Quadratic residue problem on composite integers

|improve this answer
$\endgroup$
  • $\begingroup$ But for calcuating y you do not need to use modulo, B ist going to remove the square root before he uses modulo n since he uses y^2. I actually tried this with numbers a few times and it always worked. $\endgroup$ – user14951 Jun 10 '14 at 17:13
  • $\begingroup$ @user14951: So A calculates a normal square root of $x*v^e$? That's not usually even an integer... What do you mean? A must send B some number. $\endgroup$ – otus Jun 10 '14 at 17:19
  • $\begingroup$ For example: p=7, q=11, n=77, s=25, v=s^2 mod n = 9 (v is public); x is freely chosen by A, in this case x=9 would make sense for him (making it easy to calcuate the square root when choosing y), now given e=1, you could calcuate y=(x*v^e)^0,5 = (9*9)^0,5 = 9. If you now use the verification equation y^2 mod n = vx mod n and you get <=> 4 = 4. Because A can choose whatever x he wants, he could choose it in a way, that you get an integer out of the sqaare root of x and v. $\endgroup$ – user14951 Jun 10 '14 at 17:35
  • $\begingroup$ I just realized my mistake here, now you wont be able to calcuate the right y if b ist going to be 0. So in the end this just does not work, because most of the times the square root of x*v is no integer? This does make sense indeed, not sure why I did not come up with this myself. Well thank you very much for your help. $\endgroup$ – user14951 Jun 10 '14 at 18:14

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.