cryptography - 有多少个质数(可用于 RSA 加密)？

Question

我是否错误地认为 RSA 加密的安全性通常受到已知素数数量的限制？

要破解(或创建)私钥，必须组合正确的素数对。

是否不可能发布 RSA 使用范围内的所有素数列表？或者该列表是否足够大以使得这种暴力攻击不太可能发生？难道不会有“常用”素数吗？

Answer 1

RSA 不会从已知素数列表中进行选择:它会生成一个新的非常大的数字，然后应用算法来查找附近几乎肯定是素数的数字。请参阅this useful description of large prime generation ):

The standard way to generate big prime numbers is to take a preselected random number of the desired length, apply a Fermat test (best with the base 2 as it can be optimized for speed) and then to apply a certain number of Miller-Rabin tests (depending on the length and the allowed error rate like 2−100) to get a number which is very probably a prime number.

(你可能会问，在这种情况下，当我们尝试找到越来越大的素数时，为什么我们不使用这种方法。答案是，最大的已知素数 has over 17 million digits - 甚至远远超出了通常的非常大的数字用于密码学)。

至于是否可能发生冲突 - 现代 key 大小(取决于您所需的安全性)范围从 1024 到 4096，这意味着素数范围从 512 到 2048 位。这意味着您的素数约为 2^512:长度超过 150 位。

我们可以使用1/ln(n)非常粗略地估计素数的密度(参见here)。这意味着在这些 10^150 数字中，大约有 10^150/ln(10^150) 个素数，计算出来为 2.8x10^147 可供选择的素数 - 当然比您可以放入任何列表中的还要多!!

所以是的 - 该范围内的素数数量惊人地巨大，并且碰撞实际上是不可能的。 (即使您生成了一万亿个可能的素数，形成了七十亿个组合，其中任何两个是相同素数的机会也将是 10^-123)。