在Diffie-Hellman密钥交换中，步骤之一涉及计算素数$ p $的原始根。考虑到$ p $可能很大，怎么办？

是否有某种算法或方程式？

#1 楼

在一般情况下，为了确保Diffie-Hellman的适当安全，我们需要一个值$ g $，使得$ g $的阶数（最小整数$ n \ geq 1 $使得$ g ^ n = 1 \ mod p $ ）是足够大的素数$ q $的倍数。 “足够大”表示“如果我们针对$ t $位安全性，其长度至少为$ 2t $位”。由于$ n $必须除以$ p-1 $，因此$ q $除以$ p-1 $。

我们通常想知道$ q $，因此先生成$ q $，然后生成$ p $。即，我们创建一个大小为$ 2t $位的随机质数$ q $，然后为$ r $的随机值生成$ p = qr + 1 $，直到达到质数为止。这是生成DSA密钥参数的操作，这些参数与Diffie-Hellman密钥参数具有相同的结构（请参阅DSA标准）。请注意，产生一个随机素数$ p $会以压倒性的概率产生一个“足够大”的$ q $（但是我们不知道$ q $的值，只是非常不可能最大的素数$ p -1 $小于$ 2t $位）。

然后，要获得“生成器” $ g $，我们可以使用任意随机整数模$ p $：$ q $的概率如果$ 1 / q $不是除以非零随机整数$ p $的阶数的除数，即很小，以至于您在实践中不会遇到它（Diffie-Hellman的总体安全性取决于获得的实际可能性事件的发生率要比那高出数十亿倍）。但是，有些人在遇到概率时会感到紧张，如果我们测试生成器，将会感到更加安全。然后，过程变为：创建一个随机整数$ u $取模$ p $并计算$ g = u ^ {（p-1）/ q} \ mod p $。如果$ g = 1 $，则使用新的随机$ u $再​​试一次（这是非常不可能的事件，您将无法练习）；否则，可以很容易地看出$ g $的订单正好是$ q $，因此对于Diffie-Hellman来说是很好的生成器。

另一种方法是获得一个非常大的$ q $，即生成$ p $，使得$ p = 2q + 1 $并且$ q $是质数。然后，我们将$ p $称为“强素数”。可以看出，随机非零整数$ g $取模$ p $的顺序为$ 1 $，$ 2 $，$ q $或$ 2q $；订单$ 1 $仅可能与$ g = 1 $一起使用，订单$ 2 $仅可能与$ g = p-1 $一起使用。对于Diffie-Hellman，其他任何整数模$ p $都可以。特别是，您可以将$ g = 2 $用作生成器，这可以提高计算速度。

但是，实际上，获取$ p $和生成器的最快方法是放弃产生它们。如果您重复使用先前生成的$ p $，$ q $和$ g $，则Diffie-Hellman（或DSA）没有安全问题；几个人可以为各自的密钥对共享这些值，但这丝毫不会削弱系统。因此，您可以选择“标准”值，例如RFC 2409（第6.2节）或RFC 5114（第2.1至2.3节）中所述的内容。

评论

$ \ begingroup $
如果尝试$ p = 2q + 1 $，q是否仍需要$ 2t $位长？
$ \ endgroup $
– Broseph
16年1月29日，下午1:27
$ \ begingroup $
@Broseph：实际上$ q $的长度必须大于$ 2t $位。原因是离散对数可以通过两种方式打破：一般地（基于$ q $的大小）或索引演算（基于$ p $的大小）。索引演算是次指数的，这意味着您必须使$ p $更大。实际上，要获得“ 80位安全性”，您需要$ q $至少为160位，而$ p $至少应为1000位。如果您选择$ p = 2q + 1 $，则$ p $的条件很重要（对于1000位$ p $，999位$ q $是过大的，但是您需要$ p $这么大）。
$ \ endgroup $
–托马斯·波宁（Thomas Pornin）
16年1月29日，下午1:47
$ \ begingroup $
Nit：素数$ p $，其中$ p = 2q + 1 $和$ q $也素数称为“安全”（$ q $是Sophie-Germain）；加密“强”素数也满足其他条件，这些条件不再被认为是理想的。
$ \ endgroup $
–dave_thompson_085
17年11月1日在7:25


#2 楼

我们选择$ p $使得$ p = 2k + 1 $，其中$ k $也是素数。找到这样的$ p $相对较快。

然后$ \ mathbb {Z} ^ * _ p $中的任何数字都将具有$ {2，k，2k，1 } $

我们选择一个随机数$ x $并检查$ x，x ^ 2，x ^ k \ not \ equiv 1 \ pmod {p} $。如果是这样，则$ x $是$ p $的原始根，否则，我们将重新开始。

如果选择随机数，很快就会找到一个。原始根的数量为$（k-1）\ approx p / 2 $，因此每次尝试击中原始根的概率约为1/2。

#3 楼

我会赞同托马斯关于重用标准DH组（来自RFC 2409或RFC5114）的建议。

但是，我还要补充一点，对于Diffie-Hellman，您不需要以下元素的原始元素：群组。相反，您需要一个生成较大素数阶的元素。我在Diffie-Hellman中的回答，一定是发电机吗？解释原因。
事实上，标准的DH组有大量的主要订单。