離散對數 Fiat-Shamir 參數選擇
根據Fiat-Shamir 啟發式，該算法有兩個參數：大素數 $ p $ 和原根 $ g $ . 於是出現了幾個問題：
- 質數應該有多大 $ p $ 是？如何選擇 $ p $ 這樣，例如 Pohlig–Hellman 算法或其他已知算法就無法破解它？
- 如何選擇原根 $ g $ ? 據我所知，這是一個NP問題
- 使用相同的值是否安全 $ p $ 和 $ g $ 幾個挑戰？
Fiat-Shamir 啟發式是從互動式知識證明方案構造非互動式證明（或簽名）方案的通用方法。符合 Fiat-Shamir 啟發式的互動式方案的一個範例是 Schnorr 組中的schnorr 辨識協議。這就是我解釋這個問題的方式（其他答案討論了 Fiat-Shamir 啟發式的更一般的觀點）。
Schnorr 群是素數階的子群 $ q $ , 和生成器 $ g $ ,乘法群的模某個素數 $ p $ . 那個主要組 $ \mathbb Z_p^* $ 有訂單 $ \varphi(p)=p-1 $ . 由於子群的階除群階， $ q $ 必須是素數除法 $ p-1 $ . 自從 $ g $ 是一個生成器，它必須是這樣的 $ g^q\equiv1\pmod p $ 和 $ g\not\equiv1\pmod p $ . Schnorr 群通常表示為三個整數 $ (p,q,g) $ .
質數應該有多大 $ p $ 是？如何選擇 $ p $ 這樣，例如 Pohlig–Hellman 算法或其他已知算法就無法破解它？
為了使 Schnorr 群具有密碼學意義，離散對數問題在 Schnorr 群中一定很困難。這意味著抵制已知的 DLP 算法。實際上確定所需大小的算法 $ p $ 在 Schnorr 組中是GNFS的 DLP變體，它是專門用於 $ \mathbb Z_p^* $ . 目前記錄是一個 795 位的位 $ p $ ，並且目前應用程序的最小推薦大小為 2048 位，或“2030 及以後”為 3072 位。
這也是必要的 $ q $ 足夠大，以至於Pollard 的 DLP rho是不可行的。它的成本大約是 $ \Theta(\sqrt q) $ 組乘法。因此建議至少 224 位或 256 位 $ q $ .
這些要求足以確保Pohlig-Hellman算法不懼怕。這是因為 Pohlig-Hellman 需要在每個階子組中求解一個 DLP $ q^k $ 和 $ k\ge 1 $ , $ q $ 素數，和 $ q^k $ 劃分基組的順序；和 $ k=1 $ 是最簡單的情況。
如何選擇原根 $ g $ ?
這種機率多項式時間算法將執行以下操作：
- 選擇隨機素數 $ q $ 所需大小
- 隨機選擇偶數 $ r $ 為素數 $ p=qr+1 $ 所需大小
- 隨機選擇 $ s $ 在 $ [2,p-2] $ , 併計算 $ g=s^{(p-1)/q}\bmod p $ ， 直到 $ g\ne1 $ （幾乎可以肯定）
- 作為一致性檢查，驗證 $ g^q\bmod p=1 $ （除非有錯誤，否則成立）。
使用相同的值是否安全 $ p $ 和 $ g $ 幾個挑戰？
是的。知道 Schnorr 組中特定 DLP 的解決方案顯然無助於解決同一 Schnorr 組中的其他不相關的隨機 DLP（仍有可能在幾個 DLP 之間攤銷一些預計算，但這是微不足道的）。
為什麼使用 Schnorr 組而不是安全素數更好 $ p $ ?
一個安全的總理 $ p $ 對應於 $ p-1=2q $ ， 或者 $ r=2 $ 在上面。雖然從技術上講，這仍然符合 Schnorr 團體的定義，但它並沒有滿足 Schnorr 團體的一個關鍵動機：擁有訂單 $ q $ 比尺寸小得多 $ p $ . 這很有趣，因為指數在 $ \mathbb Z_q $ ，因此更短 $ q $ 導致更快的求冪、更短的秘密和（在 Fiat-Shamir 啟發式的常見變體中）更短的簽名。此外，搜尋 $ p $ 稍微多一些。據我們所知，使用足夠大的 Schnorr 群 $ q $ 和 $ p $ 與使用安全素數一樣安全 $ p $ 大小相當。