Chaum-Pedersen 協議
我是初級軟體開發人員，我需要實現一個非常簡單的基於 Chaum-Pedersen ZKP 協議的身份驗證系統。我對密碼學一無所知，請您幫助我理解算法中的一件事。一個算法如下所示：
我只是無法得到什麼 $ q $ 是。我讀過 Cryptography: An Introduction by Nigel Smart 中的協議。有一句話：‘我們假設 $ g $ 和 $ h $ 生成素數組 $ q’ $ 但它對我沒有任何意義。我試過用Google搜尋“主要訂單組”，但它總是與證明它是循環的和其他東西有關。如果這個問題很愚蠢，我很抱歉，但我沒有其他人可以幫助我。如果有一個帶有數字的例子，那就太好了。
我覺得這裡不是提供初等數論教程的地方，所以我只討論與您的問題直接相關的方面。
當我們取一個素數時 $ p $ 和一個值 $ g $ （這不是 $ p $ )，那麼如果我們考慮值的序列 $ g^0 \bmod p, g^1 \bmod p, g^2 \bmod p, … $ ，然後我們發現在某個時刻，序列會回到 1，然後重新開始。我們稱順序為 $ g $ 我們在達到 1 之前經過的值的數量，即 $ g^q \bmod p = 1 $ ，這是最小值 $ q > 0 $ 滿足這一點。
所以，當斯馬特這麼說的時候 $ g $ 和 $ h $ 有相同的素數，他是說 $ g^q \bmod p = 1 $ , $ h^q \bmod p = 1 $ 和 $ q $ 是素數（在這兩種情況下，沒有更小的值 $ q $ ).
你怎麼找到這樣的 $ g, h, q $ ? 實際上，事實證明這並不難。 $ q $ 總會分開 $ p-1 $ 均勻；我們可以選擇一個素數 $ p $ 找到這樣一個質數 $ q $ 簡單的。此外，如果 $ q $ 是這樣一個素數，那麼對於任何值 $ u $ 沒有 $ p $ 作為一個因素，價值 $ j = u^{(p-1)/q} \bmod p $ 將是 1 或有訂單 $ q $ ; 所以找到價值 $ g, h $ 簡單。
你問了一個例子，我給你一個玩具 - 我們會挑選 $ p=23 $ 和 $ q=11 $ （注意 $ 11 $ 劃分 $ 23-1 $ 均勻），和 $ g=4 $ 和 $ h=9 $ （很容易驗證它們都具有訂單 11）。我們還選擇了一個秘密值 $ x $ （我們將選擇 6 個），並發布 $ y_1 = g^x \bmod p = 4^6 \bmod 23 = 2 $ 和 $ y_2 = h^x \bmod p = 9^6 \bmod 23 = 3 $
然後，證明者隨機選擇一個 $ k $ ，我們將任意選擇 $ k=7 $
然後證明者計算 $ r_1 = g^k \bmod p = 4^7 \bmod 23 = 8 $ 和 $ r_2 = h^k \bmod p = 9^7 \bmod 23 = 4 $ ，並傳輸那些。請注意，我們對這些計算取模 $ p $ - 這在協議中是隱含的（這種模運算是普遍理解的）。
現在，挑戰者選擇一個值 $ c $ ; 我們會選擇 $ 4 $ ; 並發送。
然後證明者計算 $ s = (k - c \cdot x) \bmod q = (7 - 4 * 6) \bmod 11 = 5 $ （注：在數學中， $ x \bmod q $ 操作總是返回之間的值 $ 0 $ 和 $ q-1 $ 以便 $ x - (x \bmod q) $ 是的倍數 $ q $ - 許多電腦語言不遵循這一點 - 這些語言是錯誤的），然後發送。
然後驗證者檢查 $ r_1 = 8 $ 是相同的 $ g^s \cdot y_1^c \bmod p = 4^5 \cdot 2^4 \bmod 23 = 8 $ 和 $ r_2 = 4 $ 是相同的 $ h^s \cdot y_2^c \bmod p = 9^5 \cdot 3^4 \bmod 23 = 4 $ ; 都簽出，所以這通過了。
您也這樣做，只是使用長度為數百位的值，而不是我給出的玩具範例。