如何在DH中獲取組生成器的順序？
對於 DH 參數素數，如果生成器 $ g $ 是2，我如何獲得訂單 $ q $ ?
發電機 $ g $ 意思是 $ g $ 生成組 $ \langle g \rangle =G $ . 因此組的順序 $ ord(G) $ 等於生成器的階數 $ ord(g) $ .
如果 $ 2 $ （或任何其他元素）不是生成器 $ \langle 2 \rangle \neq G $ 然後元素 $ 2 $ 在群操作下形成一個子群。然後的順序 $ 2 $ 必須劃分組的順序， $ ord(2) | ord(G) $ 由拉格朗日定理；
如果 $ H $ 是有限群的子群 $ G $ ，然後的順序 $ H $ 劃分順序 $ G $
Diffie-Hellman 密鑰交換可用於乘法和加法組。DHKE 表示乘法版本，ECDH 是在有限域上具有橢圓曲線的加法版本 $ E(K) $ .
對於乘法組要找到順序，將 $ ord(G) $ 然後找到最小的因子 $ x $ , $ x|ord(G) $ , 這樣 $ g^x = 1 $ ， 在哪裡 $ g^x $ 方法$$ g^x = \underbrace{a \cdot a \cdot a \cdots a}_{x\text{ times}}. $$
在像 ECC 這樣的添加劑組中，您需要檢查 $ [x]G = \mathcal{O} $ 在哪裡 $ \mathcal{O} $ 是曲線的單位元， $ G $ 是一個基本元素並且 $ [x]G $ 方法$$ [x]G = \underbrace{a + a + a + a}_{x\text{ times}}. $$
兩者都可以有效地檢查，
在 DHKE 中，在實踐中，我們選擇了一個安全的素數 $ p = 2 q +1 $ 在哪裡 $ q $ 是另一個素數，叫做索菲熱爾曼素數。在這種情況下，順序 $ G $ 只能被 2 整除並且 $ q $ ，那麼我們可以選擇 $ g $ 作為子群的生成者 $ H $ 有秩序的 $ q $ . 自從 $ q $ 是素數，那麼任何元素 $ H $ 是一個發電機。隨機取一個，或者找到最小的元素 $ x $ , 這樣 $ g^2 \neq 1 $ 和 $ g^q =1 $ 然後我們有一個生成器。
在安全的主要情況下，我們有 4 個可能的組訂單 $ {1,2,q,2q} $ 組是 $ {1},{1,-1} $ ，二次殘差和整個組。在這種情況下，找到一個有順序的生成器 $ q $ 二次殘差就夠了，二次非殘差就有 $ 2q $ 訂單，除了 $ {1,-1} $ . 要選擇生成器，可以使用二次餘數定律。結果在雨披的回答中；
這背後的理論是二次互惠定律的第二補充； $$ \begin{align}\left(\frac{2}{p}\right) = (-1)^{(p^2-1)/8} \label{1}\tag{1} \end{align} $$ 並且有上述陳述的基本證明和 $ \left(\frac{2}{p}\right) $ 是乘法傳奇符號。
- $ 2 $ 是平方模 $ p $ 當且僅當 $ p\equiv\pm 1\mod 8 $ 因此順序是 $ q $ .
- $ 2 $ 不是平方模 $ p $ 當且僅當 $ p\equiv\pm 3\mod 8 $ 因此順序是 $ 2q $ .
如果您正在尋找一些範例，請參閱RFC 2412，附錄 E ‘The Well-Known Groups’）。
在 ECDH 的情況下，過程有點複雜，我們不需要像 NIST P-224 那樣選擇具有素數有理點的曲線，其中每個元素都是生成器，但是，它沒有扭曲安全性和側通道免費蒙哥馬利梯子。