生成器 G 要求是 Diffie Hellman 算法中模 p 的原根
经过搜索，我发现自己对 Diffie Hellman 算法中 P 和 G 的使用感到困惑。要求 P 是素数，G 是 P 的原根。
我知道安全性是基于对两个非常大的素数的结果进行因式分解的难度，所以我对此没有任何问题。然而，关于 G 成为 P 的原根的目的似乎很少有可用的信息。任何人都可以回答为什么存在这个要求（如果可能的话提供参考文献）？它只是增加安全性吗？鉴于显然可以使用 p 和 g 的任何组合（甚至不是质数的组合）来创建共享密钥，我觉得这很有趣。肯定只是为了安全吧？如果是这样，它是如何增加的？
预先感谢
丹尼尔
Having searched, I've found myself confused by the use of P and G in the Diffie Hellman algorithm. There is requirementy that P is prime, and G is a primitive root of P.
I understand the security is based on the difficulty of factoring the result of two very large prime numbers, so I have no issue with that. However, there appears to be little available information on the purpose of G being a primitive root of P. Can anyone answer why this requirement exists (with references if possible)? Does it just increase the security? Given that shared keys can be created with apparently any combination of p and g, even ones that are not prime, I find this intriguing. It can surely only be for security? If so, how does it increase it?
Thanks in advance
Daniel
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
如果g不是p的原根，则g只会生成GFp。这会对系统的安全属性产生影响：系统的安全性只会与 GFp 中的 g 阶数成正比与 GFp 的全阶成正比。
举一个小例子：选择p=13 和g=3。
GF_13 中 3 的阶数为 3（3^1=3、3^2=9、3^3=1）。
按照 Diffie-Hellman 的常规步骤，Alice 和 Bob 应该分别选择 1 和 p-1 之间的整数 a、b 并计算 resp。 A = ga 和 B = gb >。为了暴力破解，攻击者应该尝试尝试 1 到 p-1 之间的所有可能的 a（或 b）值，直到找到产生A（或B）的值。但由于g不是模p的原根，他只需要尝试值1、2和3就可以找到解决方案a'A = ga'。秘密是s = gab = (ga)b =(ga')b = ga'b< /strong> = (gb)a' = Ba',攻击者现在可以计算出。
If g is not a primitive root of p, g will only generate a subgroup of GFp. This has consequences for the security properties of the system: the security of the system will only be proportional to the order of g in GFp instead of proportional to the full order of GFp.
To take a small example: select p=13 and g=3.
The order of 3 in GF_13 is 3 (3^1=3, 3^2=9, 3^3=1).
Following the usual steps of Diffie-Hellman, Alice and Bob should each select integers a, b between 1 and p-1 and calculate resp. A = ga and B = gb. To brute force this, an attacker should expect to try all possible values of a (or b) between 1 and p-1 until he finds a value that yields A (or B). But since g was not a primitive root modulo p, he only need to try the values 1, 2 and 3 in order to find a solution a' so that A = ga'. And the secret is s = gab = (ga)b =(ga')b = ga'b = (gb)a' = Ba', which the attacker can now calculate.
不要求用于 Diffie-Hellman 的生成器 g 是原根，这甚至不是常见的选择。更流行的是选择 g 使其生成素数阶子群。即g的阶是一个素数q，它是p-1的一个大素因数。
例如，为 IKE 提议的 Diffie-Hellman 组已被选择，使得 p 是安全的prime 和 g 生成 (p-1)/2 阶子群。
选择 g 作为大素数阶子群的生成器的一个动机是，这允许使
决策性 Diffie-Hellman 假设。如果 g 是原根，则该假设不成立，这使得对所实现的协议的分析变得更加困难。
There is no requirement that the generator g used for Diffie-Hellman is a primitive root nor is this even a common choice. Much more popular is to choose g such that it generates a prime order subgroup. I.e. the order of g is a prime q, which is a large prime factor of p-1.
For example the Diffie-Hellman groups proposed for IKE have been chosen such that p is a safe prime and g generates the subgroup of order (p-1)/2.
One motivation for choosing g as a generator of a big prime order subgroup is that this allows to make
the decisional Diffie-Hellman assumption. This assumption does not hold if g is a primitive root, and that makes the analysis of the implemented protocols somewhat harder.
Diffie-Hellman 的安全性并非基于分解的难度。它基于计算一般离散对数的（假设）难度。
g 必须是 p 的原根，算法才正确且可用。它确保对于每个数字 0 <= x < p，有一个独特的值 gx mod p。也就是说，它确保g可以“生成”有限域中的每个值。
The security of Diffie-Hellman is not based on the difficulty of factoring. It is based on the (assumed) difficulty of calculating general discrete logarithms.
g must be a primitive root of p for the algorithm to be correct and useable. It ensures that for every number 0 <= x < p, there is a distinct value of gx mod p. That is, it ensures that g can "generate" every value in the finite field.