如果生成器的階只有小的素因子，為什麼 Diffie-Hellman 不安全？
在security SE 的這篇文章中，Tom Leek 提到，為了讓 Diffie-Hellman 成為該集團的安全秩序 $ g $ 至少應該有一個主要因素 $ 2k $ 位長，在哪裡 $ k $ 是安全參數。
為什麼會這樣？順序 $ g $ 必須很大，否則離散對數很容易。但我看不出任何其他原因 $ g $ 應該有一個很大的素因數。為什麼至少應該是 $ 2k $ 位長（而不是 $ k $ 位長）？
它還說私鑰 $ a $ 和 $ b $ 也應該是 $ 2\text{k} $ 位長。它們應該很大，否則離散對數會很容易。但他們為什麼要 $ 2\text{k} $ 位長，而不是 $ \text{k} $ 位長？
- 但是我看不出為什麼 g 的順序應該有一個大的素因數的任何其他原因。
讓 $ p $ 為 Diffie-Hellman 模數。命令 $ q $ 由生成的子組的 $ g $ 必須至少有一個大的素因子來阻止Pohlig-Hellman 算法的使用。該算法的複雜度$$ \mathcal O\left(\sum_i {e_i(\log n+\sqrt p_i)}\right) $$在哪裡 $ e_i $ 是素數的冪 $ p_i $ . 簡而言之，較大的一個 $ p_i $ s 複雜度越高。
- 為什麼它應該至少有 2k 位長（而不是 k 位長）？
這 $ \text{k} $ -bit 是目標安全所必需的。對離散對數問題的一般攻擊有 $ \mathcal{O}(2^\text{k/2}) $ 複雜性，因此您至少需要從 $ 2\text{k} $ .
**注意：**安全素數 $ p = 2q+1 $ 保證順序 $ g $ 是 $ q $ 或者 $ 2q $ .
- 它還說私鑰 a 和 b 也應該是 2k 位長。
不， $ 2\text{k} $ -bit 用於選擇 $ a $ 和 $ b $ 沒有必要。從這個答案中可以看出；
標準的決策 Diffie-Hellman 假設適用於以下情況： $ g^{x_a} $ 和 $ g^{x_b} $ 均勻分佈在組中（應該是素數子組）。
在這個答案的評論中還有一個連結的文章（短指數 Diffie-Hellman 問題）。