cryptography - 生成器 G 要求是 Diffie Hellman 算法中的原始根模 p

Question

经过搜索，我发现自己对 Diffie Hellman 算法中 P 和 G 的使用感到困惑。要求P是素数，G是P的原根。

我知道安全性是基于分解两个非常大的素数的结果的难度，所以我对此没有任何问题。然而，关于 G 成为 P 的原始根的目的似乎很少有可用信息。谁能回答为什么存在这个要求（如果可能，请提供参考资料）？它只是增加了安全性吗？鉴于共享密钥显然可以用 p 和 g 的任意组合创建，即使是非质数组合，我觉得这很有趣。肯定只能是为了安全？如果是这样，它是如何增加的？

提前致谢

丹尼尔

Answer 1

如果g不是p的本原根，则g只会生成GF _p的子群。这对系统的安全属性有影响：系统的安全性将仅与GF _p中的g阶成正比，而不是与GF _p的全阶成正比。

举个小例子：选择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并计算相应的值。A = g ^a和B = g ^b。为了暴力破解这一点，攻击者应该期望尝试a（或b）在 1 和p -1 之间的所有可能值，直到他找到一个产生A（或B）的值。但由于g不是模p的原始根，他只需要尝试值 1、2 和 3 即可找到解a'使得A = g ^a'。秘密是s = g ^ab = (g ^a ) ^b = (g ^a' ) ^b = g ^a'b = (g ^b ) ^a' = B ^a'，攻击者现在可以计算出来。

Answer 2

没有要求用于 Diffie-Hellman 的生成器 g 是一个原始根，这甚至不是一个常见的选择。更流行的是选择 g 以便它生成一个素数阶子组。即g的阶是一个素数q，它是p-1的一个大素数。

例如，已选择为IKE提出的 Diffie-Hellman 群，使得 p 是安全素数，并且 g 生成阶 (p-1)/2 的子群。

选择 g 作为大素数阶子群的生成器的一个动机是，这允许做出决定性的 Diffie-Hellman 假设。如果 g 是原始根，则该假设不成立，这使得对已实现协议的分析更加困难。

Answer 3

Diffie-Hellman 的安全性不是基于保理的难度。它基于计算一般离散对数的（假设的）难度。

g必须是p的原始根，算法才能正确和可用。它确保对于每个数字0 <= x < p，都有一个不同的g ^x mod p值。也就是说，它确保g可以“生成”有限域中的每个值。