1
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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

|improve this answer|||||
$\endgroup$
  • $\begingroup$ how did i calculate vi wrong? isn't it 25 mod 77? which is 52? $\endgroup$ – Timo N. Jul 11 '16 at 14:48
  • $\begingroup$ ah now i get it :) thx! $\endgroup$ – Timo N. Jul 11 '16 at 15:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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