我是否错误地认为 RSA 加密的安全性通常受到已知素数数量的限制？
要破解（或创建）私钥，必须组合正确的素数对。
是否不可能发布 RSA 使用范围内所有素数的列表？还是该列表足够大以使这种蛮力攻击不太可能？不会有“常用”的素数吗？
问问题
20524 次
2 回答
100
RSA 不会从已知素数列表中进行选择：它会生成一个新的非常大的数字，然后应用一种算法来找到一个几乎可以肯定是素数的附近数字。请参阅大型素数生成的有用描述）：
生成大素数的标准方法是采用预选的所需长度的随机数，应用费马测试（最好以 2 为底，因为它可以优化速度），然后应用一定数量的 Miller-Rabin 测试（取决于长度和允许的错误率，例如 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）。
于 2013-04-18T19:40:38.613 回答
8
随着新研究的出现，您的问题的答案变得更加有趣。在 David Adrian 等人最近发表的一篇论文“Imperfect Forward Secrecy:How Diffie-Hellman Fails in Practice”中发现@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 加密中可能有足够数量的素数，但实际上，如果您躲避某个民族国家，则会出现安全问题。
于 2015-10-16T17:00:03.877 回答