RSA素数与最大已知素数

Question

本周发现了一个新的最大(mersenne)素数-

最大已知素数现在是2^57,885,161 − 1，自从上一个最大的质数被发现以来，花了5年的时间才找到它。

但是我们知道，各种非对称加密算法都需要大得离谱的素数，这些素数被用作臭名昭著的p和q因素。例如，1024位RSA需要两个512位素数.

但是，如果这篇文章是正确的，则声称我们只能枚举~1.7M素数。

这与密码素数生成是如何解决的？

Answer 1

除了经常使用概率机制来生成RSA密钥，而不是证明p和q是素数之外，还有其他一些要求，例如p和q不应该太接近。

在Mersenne素数的上下文中，值得注意的是，通常情况下，p或q都不是Mersenne素数，即对于RSA密钥生成，如果使用证明p或q的素数的机制，则应避免只适用于Mersenne素数的机制。

Mersenne素数的问题是，Mersenne素数相对较少，因此分解p或q变得微不足道。

Answer 2

同样值得注意的是，特定的RSA实现通常使用某种筛子和素数测试来获得它们的素数。这些步骤通常是：

1. 生成适当大小的随机奇数n作为候选。
2. 检验n的原始性。
3. 如果n是复合的，则返回第一步。

第二步可以通过“真”或“概率”检验来完成。有趣的读物是“应用密码学手册：http://cacr.uwaterloo.ca/hac/”第4章。