Why am I getting a wrong output when implementing Feige-Fiat-Shamir ID protocol? 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.

Preparation:

N is given: 

77


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


Calculate x:

x = (r^2) * s % n = 67


Choose a either 0 or 1:

a1 = 1, a2 = 0, a3 = 0


Calculate y:

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.

Question:

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?
The first problem is, that you calculated $v_i$ wrong right at the start.
$$v_i = s_i^2 \mod n$$
This means:
$$v_1 = 5^2 = 25 \mod 77$$
$$v_2 = 12^2 = 67 \mod 77$$
$$v_3 = 37^2 = 60 \mod 77$$

Then at the end you have: 
$$(x \cdot \prod_i v_i^{a_i})  = 67 \cdot 25 \cdot 1 \cdot 1 = 58 \mod 77$$