在 DH 和 ECDH 的情況下，如何為一個組找到一個生成器？
DH & ECDH 的第一步是選擇一個隨機素數 $ p $ . 然後你選擇一個發電機 $ g $ 為團體 $ \mathbb Z_p^* $ . 如何找到發電機？同樣在 ECDH 中，您需要找到一個生成橢圓曲線中所有點的生成器？這是怎麼做到的？
在乘法組中的Diffie-Hellman 密鑰交換（DHKE 或 DH）的情況下 $ \mathbb Z_p^* $ ，推薦的做法是選擇一個素數 $ p $ 和發電機 $ g $ 來自RFC 3526，它給出了比特大小的這些參數 $ k $ 的 $ p $ 在 $ {1536,2048,3072,4096,6144,8192} $ . 這些 $ (p,g) $ 遵守以下標準：
- $ p $ 是一個素數，使得 $ q=(p-1)/2 $ 是素數，即 $ p $ 一個安全的素數。由於元素的順序 $ g $ 該組的一個除數是 $ p-1 $ , 該順序只能是 $ 1 $ , $ 2 $ , $ q $ ， 或者 $ 2,q $ ，這簡化了查找¹/檢查候選人的順序 $ g $ :
- 如果 $ g\bmod p=1 $ ，然後的順序 $ g $ 是 $ 1 $ .
- 如果 $ g\bmod p=p-1 $ ，然後的順序 $ g $ 是 $ 2 $ .
- 如果 $ g^q\bmod p=1 $ ，然後的順序 $ g $ 是 $ q $ , 組訂單的一半。這樣的 $ g $ 在 RFC 3526 中使用。
- 否則（即如果 $ g^q\bmod p=p-1 $ ）， 的順序 $ g $ 是 $ 2,q $ ， 那是 $ g $ 是整個組的生成器。沒有充分的理由喜歡這樣 $ g $ ，並且它們的缺點是 $ a=g^x\bmod p $ , 判斷是否是微不足道的 $ x $ 通過檢查是否是偶數或奇數 $ a^q\bmod p $ 是 $ 1 $ 或不。
- 它被採摘 $ g=2 $ ， 因為
- 的低位 64 位 $ p $ 被設置。這可以用來簡化蒙哥馬利模乘法。結合（1）和 $ p>7 $ ，這意味著 $ p\bmod24=23 $ , 和的順序 $ g=2 $ 是 $ q $ . 值得注意的是，這違背了 OpenSSL 的檢查。
- 的高位 66 位 $ p $ 被設置，使 $ p $ 接近二的冪。這可用於簡化模減模 $ p $ ，通過使在基數歐幾里得除法中的商容易找到最可能正確的新數字/肢體 $ 2^b $ 為了 $ b\le32 $ （而且有點高）。
- 的下一個高位 $ p $ 很清楚，使 $ p $ 不太接近特殊數字欄位篩選器適用的 2 的冪。
- 其他位使 $ p $ 一個空無一物的號碼：對於一個 $ k $ -位模數，它被使用 $ p=2^k-2^{k-64}-1+2^{64},\left\lfloor2^{k-130}\pi+i\right\rfloor $ 用最小的 $ i $ 這樣 $ p\bmod3=2 $ [對於給定的 $ k $ 決定 $ i\bmod 3 $ ], $ p $ 是素數， $ q=(p-1)/2 $ 是素數，並且 $ 2^q\bmod p=1 $ .
當然， $ k $ 選擇作為DH的速度和安全性之間的折衷。 $ k=2048 $ 今天被認為是最低限度。消息大小隨著 $ k $ . 執行時間隨著 $ k^3 $ 在使用教科書乘法和秘密的 DH 的幼稚實現中，大小為 $ p $ . 雖然通過使用更好的乘法算法和更小的秘密可以顯著提高性能，但 DH 在 $ \mathbb Z_p $ 具有足夠安全參數的 ECDH 的有效實現優於其性能，請參見下一節。
注意：另一種做法是使用 $ (p,g) $ 使權力 $ g $ 模組 $ p $ 素數階Schnorr 群 $ q $ 尺寸遠小於 $ p $ ，但足夠安全。我們首先選擇素數 $ q $ 比特數大約是所需安全級別的兩倍，並且 $ p=2,q,r+1 $ 對於（甚至） $ r $ 製造 $ p $ 合適大小的素數（例如 256 位 $ q $ , 3072 位 $ p $ ）。我們挑選一些 $ h $ （例如 $ h=2 $ )，計算 $ g\gets h^r\bmod p $ , 並檢查這不是碰巧 $ 1 $ .
在 ECDH 的情況下，即在某個有限域上的橢圓曲線的點組中的 DH $ \mathbb F_{p^d} $ 為素數 $ p $ ，推薦的做法是從一些參考中選擇標準曲線和生成器。一個常見的是SEC2，它包括FIPS 186-4的 NIST 曲線。另一個是Curve25519。還有一個是RFC 5639，它給出了Brainpool 曲線。
限制為 $ d=1 $ （即曲線上 $ \mathbb F_p $ 對於一些大素數 $ p $ , 雖然沒有組中 DH 安全所需的那麼大 $ \mathbb Z_p^* $ )，實踐是使用素數階曲線 $ q $ ，使得除中性點以外的任何點 $ \infty $ 有訂單 $ q $ . 事實證明，生成器（又名基點）的選擇不會使離散對數問題變得更容易。實際選擇生成器的方式各不相同。有時它是秘密的，失去的，重新發現的，看看這個。
當我們不能或沒有選擇素數階曲線時，練習它使用已知階數的曲線形式 $ h,q $ 在哪裡 $ q $ 是素數並且 $ h $ 盡可能小。這樣可以很容易地檢查一個點的順序，並確定它是 $ q $ （或者確切地說 $ q $ ，這是典型的）。
如何找到曲線的順序（又名點計數）非常複雜。這就是我們有標準曲線的一個很好的原因。
¹ 查找訂單的一般方法 $ i $ 任意的 $ g $ 在 $ \mathbb Z_p^* $ 和 $ p $ 主要是測試 $ i $ 在除數之間按升序排列 $ p-1 $ （這樣的順序 $ \mathbb Z_p^* $ )，並停在第一個 $ i $ 和 $ g^i\bmod p=1 $ . 這可以推廣到任何組，並且當我們知道組順序的分解時適用。