# Fiat-Shamir security problem question

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.

## 1 Answer

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.

• 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. – user14951 Jun 10 '14 at 17:13
• @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. – otus Jun 10 '14 at 17:19
• 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. – user14951 Jun 10 '14 at 17:35
• 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. – user14951 Jun 10 '14 at 18:14