有多少素数(可用于RSA加密)？

Question

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

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

是否无法发布RSA使用范围内所有素数的列表？或者这个列表足够大,以使这种暴力攻击不太可能？难道不会有"常用"素数吗？

Answer 1

RSA不从已知素数列表中选择:它生成一个新的非常大的数字,然后应用算法来查找几乎肯定是素数的附近数字.看到这个有用的大型素数的描述):

生成大素数的标准方法是采用所需长度的预选随机数,应用费马测试(最好用基数2,因为它可以针对速度进行优化),然后应用一定数量的米勒 - 拉宾测试(取决于长度和允许的错误率,如2-100)得到一个非常可能是素数的数字.

(你可能会问为什么,在这种情况下,当我们尝试找到越来越大的素数时,我们没有使用这种方法.答案是最大的已知素数有超过1700万个数字 - 远远超过通常使用的非常大的数字在密码学中).

至于是否可以进行冲突 - 现代密钥大小(取决于您所需的安全性)范围从1024到4096,这意味着质数范围从512到2048位.这意味着您的素数大约为2 ^ 512:超过150位数.

我们可以非常粗略地估计素数的密度1 / ln(n)(见这里).这意味着在这些10^150数字中,有大约10^150/ln(10^150)素数,2.8x10^147可以选择的素数 - 当然超过你可以放入任何列表!!

所以是的 - 该范围内的素数数量惊人地巨大,并且实际上不可能发生碰撞.(即使你生成了一万亿个可能的素数,形成了一个septillion组合,它们中任何两个素数相同的素数就是10^-123).

Answer 2

随着新研究的出现，对您问题的答案变得更加有趣。在最近的一篇文章“不完美正向保密：如何的Diffie-Hellman实践失败”的大卫·阿德里安等人都发现@ https://weakdh.org/imperfect-forward-secrecy-ccs15.pdf访问的关于2015年10月16日，研究人员可以看出，尽管RSA的1024位密钥集可能有足够数量的质数，但由于实现的原因，整个密钥集中存在更多的密钥组。

我们估计即使在1024位的情况下，给定民族国家的资源，这些计算也是合理的。数百万台服务器使用少量固定或标准化组。对单个1024位组执行预计算将允许在18％的流行HTTPS站点上进行被动窃听，而第二组将允许对66％的IPsec VPN和26％的SSH服务器进行流量解密。对已发布的NSA漏洞的仔细阅读表明，该机构对VPN的攻击与这种突破是一致的。我们得出结论，转向更强大的密钥交换方法应该是Internet社区的优先事项。

研究还表明，TLS中的一个漏洞可能使中间人攻击者将加密降级到512位。

因此，在回答您的问题时，纸上的RSA加密中可能有足够数量的质数，但实际上，如果您躲开民族国家，就会遇到安全问题。