I am trying to implement the Feige-Fiat-Shamir identification protocol. I've read another posting here on this site and I tried to adapt - however the end results always fail to match. Maybe because aim doing Feige-Fiat-Shamir and not Fiat-Shamir? To get to the bottom of my problem, I therefore decided to post my own question.
N is given:
s are given:
s1 = 5, s2 = 12, s3 = 37
Compute v:v = (s^2) % n
v1 = v2, v2 = 58, v3 = 37
Now the round:
Select random r between 1 and n - 1 and s = 1, -1:
r = 12, s= 1
x = (r^2) * s % n = 67
Choose a either 0 or 1:
a1 = 1, a2 = 0, a3 = 0
y = (r * s^a) % n = 60
Now ,if y^2 equals (x * v^e) % n then it's accepted. However in my case
y^2 mod n = 58 (x * v^e) % n = 19
19+58 = 77, but I know that y^2 mod n should be 19 as well. Or that 58-19 should be N, which isn’t the case either.
Why don't these numbers match? What am I doing wrong here? Is it maybe because Feige-Fiat-Shamir is y2 = ±xva1 · ·van modN ? So if 58+19 = 77 or 58-19 = 77 the protocol works?