為什麼在實施 Feige-Fiat-Shamir ID 協議時輸出錯誤？

我正在嘗試實現 Feige-Fiat-Shamir 辨識協議。我在這個網站上閱讀了另一篇文章，我試圖適應——但最終結果總是不匹配。也許是因為目標是做 Feige-Fiat-Shamir 而不是 Fiat-Shamir？為了深入了解我的問題，因此我決定發布我自己的問題。

準備：

N 給出：

77

s 給出：

s1 = 5, s2 = 12, s3 = 37

計算 v:v = (s^2) % n

v1 = v2, v2 = 58, v3 = 37

現在輪到：

在 1 和 n - 1 和 s = 1, -1 之間選擇隨機 r：

r = 12, s= 1

計算 x：

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

選擇 0 或 1：

a1 = 1, a2 = 0, a3 = 0

計算 y：

y = (r * s^a) % n = 60

現在，如果 y^2 等於 (x * v^e) % n 則它被接受。但是在我的情況下

y^2 mod n = 58
(x * v^e) % n = 19

19+58 = 77，但我知道 y^2 mod n 也應該是 19。或者 58-19 應該是 N，但也不是這樣。

問題：

為什麼這些數字不匹配？我在這裡做錯了什麼？是不是因為 Feige-Fiat-Shamir 是 y2 = ±xva1 ··van modN ？那麼如果 58+19 = 77 或 58-19 = 77 協議有效嗎？

第一個問題是，你在一開始就計算錯誤。

這意味著： 在一世 $ v_i $ 在一世=s2一世反對n

$$ v_i = s_i^2 \mod n $$在1=52=25反對77$$ v_1 = 5^2 = 25 \mod 77 $$ 在2=122=67反對77$$ v_2 = 12^2 = 67 \mod 77 $$ 在3=372=60反對77$$ v_3 = 37^2 = 60 \mod 77 $$ 然後在最後你有： (X⋅∏一世在一個一世一世)=67⋅25⋅1⋅1=58反對77

$$ (x \cdot \prod_i v_i^{a_i}) = 67 \cdot 25 \cdot 1 \cdot 1 = 58 \mod 77 $$

引用自：https://crypto.stackexchange.com/questions/37647