发电机的尺寸在Diffie-Hellman中是否重要？

#1 楼

Diffie-Hellman的安全性取决于使用DH的组，而不取决于该组使用的发电机。请参见《应用密码学手册》的注释3.53（第103章第3章）。

更多详细信息：对于DH，我们使用大小为$ q $的子组，该子组为$ p $（大素数），并将乘法作为组运算。对于$ 2 ^ n $的安全级别，$ q $的长度应为至少$ 2n $位的质数（或者，至少$ q $的质数应至少为$ 2n $位）。典型的参数大小是$ q $为160位，$ p $为1024位，$ q $为256位，$ p $为2048位。生成器$ g $是订单$ q $的元素。

当$ p $是“安全素数”时，这意味着$ \ frac {（p-1）} {2} $也是素数然后，我们定义$ q = \ frac {（p-1）} {2} $。在这种情况下，任何非零的$ g \ bmod p $（1和$ p-1 $除外）的阶为$ q $或$ 2q $，因此在$ 2 $和$ p-2之间的每个$ g $ $（含）是一个很好的DH生成器，可确保最佳安全性。因此，通常习惯选择$ g $，这会使计算更容易，通常$ g = 2 $或$ g = 3 $。

定义DH组的另一种方法是继承DSS（一种在该组中也起作用的签名算法）：我们首先选择一个适当大小（例如160位）的质数$ q $，然后通过将$ p = qr + 1 $设置为随机值来寻找$ p $正确大小的$ r $的值（以便$ p $具有我们所需的大小），直到我们达到质数$ p $。这允许使用较小的$ q $，从而较小的DH指数和更快的计算；另一方面，在这种情况下，我们不能自由选择生成器，因为只有$ q-1 $个生成器属于$ q $模$ p $阶的子组。因此，我们取一个随机值$ s $并计算$ g = s ^ {（p-1）/ q} \ bmod p $。这样会产生一个合适的生成器，但是却不是一个很小的生成器，例如$ 2 $或$ 3 $。 >
模幂运算使用“平方乘”算法。使用$ 2 $作为生成器可以简化乘法运算，但不能简化平方运算，它代表了绝大多数计算（尤其是在使用基于窗口的优化时）。使用$ g = 2 $可以很整洁，但并不意味着性能会有很大提高。

基于窗口的优化对乘法进行分组。基本上，您可以预先计算$ g ^ 2，g ^ 3 \ dots g ^ {15} $;然后，您进行平方运算，并且每四个平方乘以预计算的值之一。这是一个4位窗口，可以有更大的窗口。窗户的建造也有可能节省。这就是为什么平方占用超过CPU总成本的\ frac {2} {3} $，接近80或85％的原因。使用$ g = 2 $进行优化的工作相对较少。我个人还没有看到。几种协议（例如，用于IPsec的IKE）使用RFC 2412（附录E）中的“ Oakley组”，它们具有$ g = 2 $。