DLP 的推薦 NIST 模數是如何選擇/計算的？
NIST建議為具有 3072 位模數的 DLP 使用 256 位私鑰指數。從這個答案看來，私鑰數字的範圍是通過計算素數模數得出的 $ 2⋅p $ 在哪裡 $ p $ 是 256 位素數，然後添加 $ 1 $ 結果（例如 $ 2p+1 $ ）。如果結果 $ n $ 是一個素數並且 $ a $ 在 $ a^2 \pmod{n} \ne 1 $ ，那麼我們可以使用 $ n $ 作為模數。
我認為私鑰（256 位）和模數（3072 位）之間推薦大小的差異與通用數字欄位篩子攻擊有關，它與模數的大小有關，而不是與私鑰指數。所以模數需要比私鑰指數大得多。
我的問題是3072的模數是如何得出的？當然不是要實現我自己的，而是要了解它是如何工作的。例如，是否簡單地選擇一個 3071 位素數，將其乘以 $ 2 $ 並添加 $ 1 $ ，測試結果是否為素數？如果是素數，則檢查是否 $ a^2 \pmod{n} \ne 1 $ ，如果不是，那麼我們可以選擇 $ 2 $ 對於基數，至少為 256 位的隨機私鑰指數，並且知道最好的攻擊仍然需要 $ \sqrt{2^{256}} $ 蠻力求冪來確定私鑰指數？
3072 位模數是如何得出的？
找到最小的 $ c $ 這樣$$ p = 2^n - 2^{n - 64} - 1 + 2^{64} (\lfloor 2^{n - 130} \pi\rfloor + c) $$和 $ q = (p - 1)/2 $ 是素數，並且 $ p \equiv 7 \pmod 8 $ . 在這種情況下， $ n = 3072 $ 所以 $ c = 1690314 $ .
利用 $ g = 2 $ 作為發電機。
（這裡 $ \pi = \int_{-1}^1 dx/\sqrt{1 - x^2} = 4/[1 + \mathrm K_{i=1}^\infty i^2/(2i - 1)] $ 按照慣例。）
為什麼是這個形狀？
這遵循RFC 2412附錄 E 的過程，並匹配RFC 3526的第 15 組：
- 我們選擇 $ p $ 成為一個安全的素數——也就是說，選擇 $ p $ 以便 $ q = (p - 1)/2 $ 也是素數——所以唯一的子群階是 $ {1, 2, q, 2q} $ ，這限制了Lim-Lee 主動小子群攻擊。
- 我們選擇 $ p \equiv 7 \pmod 8 $ 因此，根據二次互反定律， $ g = 2 $ 有素數 $ q $ ， 自從 $ g = 2 $ 是一個方便的基數，複合階子群會洩露一些秘密指數。
（如果你的鑰匙是 $ h \equiv g^x \pmod p $ 和 $ g $ 生成整個群或複合階子群，而不是除以下之外的素數階子群 $ {-1,1} $ ，那麼很容易判斷是否 $ x $ 通過測試是否是偶數或奇數 $ h^{(p - 1)/2} \equiv 1 \pmod p $ 或不; 同樣的想法推廣到復合 $ q $ .) 3. 我們選擇沒有特別好的圖案的形狀來防止SNFS 攻擊。 4. 我們從RFC 2412流程中專門選擇半剛性RFC 3526組，並具有特定的 nothing-up-my-sleeves 常數 $ \pi $ -而不是 $ e $ 或者 $ \sqrt 2 $ 或者 $ \cos 1 $ 或者，更糟糕的是，隨機選擇的位 - 稍微增加一點信心，認為首選中沒有後門。
實際上，更好的是，我們只使用基於橢圓曲線的 X25519，它更快、更安全，並且沒有像這樣的魔法常數 $ \pi $ !