生成大质数需要多长时间？

Question

在2ghz双核奔腾笔记本电脑上运行bigint的C实现，无需任何程序集，SSE等；期望质数创建的平均时间是多少？

大于512位的素数需要30秒正常吗？

2048、4096位等呢？

来自安全性堆栈交换问题56214

我最近生成了一些自定义Diffie Hellmann参数，这些参数基本上只是长质数（在下面的情况下为4096位）。
由于这一代花费了大约2个小时，所以它不可能是即时生成的。

这是典型的吗？-2小时生成一个4096位密钥...

Answer 1

不，4小时绝对不是典型的时间。

大随机素数的生成取决于以下条件：

1. 随机数发生器中的速度和熵
2. 用于测试候选者素数的算法
3. 实施
4. 和运气

使用的随机数生成器非常重要。特别是对于长期密钥，可能是您需要包含大量熵的随机位生成器。例如/dev/random，这可以通过访问linux操作系统来实现。有一个不幸的问题：/dev/random可能会阻塞，直到收集到足够的熵为止。取决于系统的速度可能非常快还是非常慢。

现在，第二个是算法。当产生新的DH 参数时，通常通常使用一种产生所谓的安全素数的方法。现在生成安全的质数比生成可能的质数要困难得多。但是，该质数仅用于DH参数，而不用于密钥对本身。因此，通常不需要生成安全的灌注。您可以简单地使用一组预先计算甚至命名的参数。

该实现也可以有所作为。尽管它不会改变复杂性的顺序，但是如果实现比快速实现慢一千倍，它仍然可能影响结果。密码学内部并非闻所未闻。较慢的解释语言可能比硬件加速版本或使用CPU或实际上GPU的矢量指令直接运行的版本慢得多。

此外，查看数字是否为质数的唯一方法是测试该数字。没有仅生成素数的确定性方法。这样做的问题在于，尽管有很多很多素数可用，但是找到一个素数仍然需要很长时间。这就是运气因素的来源：测试的第一个数字可能是质数，但也可能是在找到一个数字之前要经过大量的数字。因此，最后该过程的运行时间是不确定的。

对于C程序，在2个小时内生成4096位的安全素数似乎有点麻烦。但是，如果它运行的是非常老的CPU，没有任何SSE，则不一定意味着任何根本上的错误。但是，为512位素数占用30秒的时间非常长。在我的笔记本电脑上，OpenSSL命令行仅花费0.015（幸运）至1.5（不幸）秒之间的时间（但这就是Core i7）。

笔记：

• RSA通常要求两个素数是密钥大小的一半，而这些素数通常不是安全的素数。因此，生成DH密钥对（具有新参数）将比生成相同大小的RSA密钥对花费更长的时间。
• 如果可能，请尝试使用预定义的DH参数。不幸的是，openssl命令行似乎不支持命名的DH参数。仅DSA密钥对支持此功能。
• 如果需要速度，请尝试使用预定义参数的椭圆曲线DH。生成密钥几乎与生成256个随机位（例如，对于P-256曲线）一样快。直到Quantum Crypto逐渐失效，这些密钥将比其上的DH密钥强得多。