獲取 Diffie-Hellman 生成器
在關於 Diffie-Hellman 的 Wikipedia 文章中，該算法需要較大的素數模數， $ p $ ，和一個發電機， $ g $ , 是的原根 $ p $ .
就我的數論知識而言，要找到素數的原根，首先需要確定素數的素因數 $ \phi(p) $ ， 或者 $ p-1 $ .
顯然，2分 $ \phi(p) $ ，但在那之後，您將面臨分解一個與原始位數相同的數字的問題 $ p $ .
我的印像是，系統的安全性首先取決於找到大數的質因數的難度。
我錯過了什麼？
Diffie Hellman 不依賴於大數分解的難度（有點*）。
它依賴於這樣一個事實，即到目前為止，人類還沒有已知的有效算法可以有效地推導出數字的離散對數。給定一個元素 $ y \in G $ 其中 G 是素數階的循環群 $ q $ , 求一個數在計算上是不可行的 $ x \in Z^*_q $ 這樣 $ y = g^x $ .
他們這裡的關鍵點是組的順序必須是素數。這意味著該組 $ Z^*_p $ 對於任何素數都不安全 $ p $ 因為它的順序顯然不是素數。
為了解決這個問題，可以選擇一個素數 $ p $ 這樣 $ p= kq + 1 $ . 這意味著存在一個唯一的子群（稱為schnorr 群） $ Z^*_p $ 有秩序的 $ q $ 因為對於每個除數恰好存在一個子群 $ φ(p) = p-1 $ .
為該組找到一個生成器是微不足道的。選擇一個隨機值 $ 1 <h < p $ 這樣 $ h^r \mod{p} \neq 1 $ . 如果你找到這樣一個數字，那麼這個不等式意味著 $ h $ 大於 $ r $ . 然而，唯一可能的順序大於 $ r $ 是 $ q $ . 因此 $ h $ 有訂單 $ q $ 並且可以生成一個安全的子群 $ Z^*_p $ . 如果 $ h^r \mod{p} = 1 $ 然後簡單地生成另一個隨機 $ h $ 然後再試一次，直到找到生成器。
可以證明，如果組的階只有小的素因數，那麼離散對數問題比其他組更容易解決。然而，通過選擇一個大素數順序的子組，就像我們上面所做的那樣，通過選擇 $ p= kq + 1 $ 意味著我們生成的子組只有一個*大因子（本身），這反過來意味著您不必擔心這些因子分解攻擊。
您錯過了選擇 g 的一方也必須選擇 p。