Why am I getting a wrong output when implementing Feige-Fiat-Shamir ID protocol?

Question

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?

Answer 1

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$$