生成器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,而不是成正比的全阶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并计算resp.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必须是p的原根，算法才正确且可用。它确保对于每个数字0 <= x < p，都有一个不同的g ^x mod p值。也就是说，它确保g可以“生成”有限域中的每个值。

Answer 3

不要求用于Diffie-Hellman的生成器g是原始根,这也不是常见的选择.更受欢迎的是选择g以使其生成主要订单子组.即g的阶数是素数q,它是p-1的一个主要因子.

例如,已经选择为IKE提出的Diffie-Hellman组,使得p是安全素数并且g生成有序(p-1)/ 2的子群.

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