Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer 1

up vote 2 down vote accepted

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

share|improve this answer
    
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 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 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 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 at 18:14
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.