可以公平地假设，在这40年中，某些三字母组织已将其大量资源用于“破坏” RSA。一种蛮力方法可能是枚举每个可能的密钥对，这样，在遇到已知要使用特定公钥加密的消息时，他们只需查找关联的私钥即可解密该消息。签名可以类似地伪造。
这个假设有多合理？在过去的40年中，枚举每个可能的{1024,2048,4096}位密钥对需要多少计算资源？我认为最好避免讨论，而将问题留给幽灵是否可以将这种资源用作练习，以供读者参考。
#1 楼
小于$ x $的素数数量大约为$ \ frac {x} {\ ln x} $。因此，$ 512 $位素数的数量（大约是$ 1024 $位模所需的长度）大约为：
$$ \ frac {2 ^ {513}} {\ ln 2 ^ {513} }-\ frac {2 ^ {512}} {\ ln 2 ^ {512}} \约2.76×10 ^ {151} $$
RSA模数（即两个不同的对因此素数）为：
$$ \ frac {（2.76×10 ^ {151}）^ 2} {2} -2.76×10 ^ {151} = 1.88×10 ^ {302} $现在考虑一下可观察的宇宙包含约$ 10 ^ {80} $个原子。假设您可以将每个原子用作CPU，并且每个CPU可以枚举一个模数/毫秒。要枚举所有$ 1024 $位RSA模数，您需要：
\ begin {eqnarray *}
1.88×10 ^ {302} ms / 10 ^ {80}＆=＆1.88× 10 ^ {222} ms \\
＆=＆1.88×10 ^ {219} s \\
＆=＆5.22×10 ^ {215} h \\
＆= ＆5.95×10 ^ {211} \ text {years}
\ end {eqnarray *}
作为比较：宇宙大约是$ 13.75×10 ^ 9 $岁。
这不是资源问题，根本不可能。
此外，这样做也没有任何意义。有更快的方法来找到密钥。实际上，存在用于分解整数的具有次指数运行时间的算法。
评论
$ \ begingroup $
您忘了在计算中除以2。 $ \：$无论如何，可以严格显示（即，不使用任何近似值）可能的1024位RSA模数大于$ 10 ^ {302} $（即使素数必须是不同的）。 $ \; \; $
$ \ endgroup $
–user991
2012年6月25日上午8:50
$ \ begingroup $
您在第一个$ 10 ^ {80} $处打了一个错字-MIA为零。
$ \ endgroup $
–托马斯
2012年6月25日在8:52
$ \ begingroup $
注意：不能正确回答标题中的真实问题！
$ \ endgroup $
–fgrieu♦
2012年6月25日上午11:40
$ \ begingroup $
仍然略有下降：5.22e215小时= 2.18e214天= 5.96e211年。 （但+1可供参考。）
$ \ endgroup $
–dave_thompson_085
15年2月13日在20:43
$ \ begingroup $
@ dave_thompson_085“稍微”降低了两个数量级。 ：D修复它。 （尽管是5.95495，所以是5.95）
$ \ endgroup $
– Maeher
15年2月14日在10:46
#2 楼
正如其他答案所指出的那样，问题中描述的蛮力技术是没有希望的。但是，有更好的技术可以攻击RSA密钥，包括GNFS。因此，即使1024位RSA密钥提供了相当大的安全性，它们也不再被认为可以完全避免受到可预测的学术努力的影响，甚至不能认为完全不受三字母代理机构的保护。请参阅我对今天有多大的RSA密钥被认为安全的详细答案。对于新系统，请使用任何适用的建议，或参考本网站上专门针对密钥长度建议的众多建议之一。
此外，有时用户可以利用密钥生成器中的漏洞，或攻击RSA。以不涉及整数分解的方式：窃取私钥；通过差分功率分析，定时或故障攻击将其提取；或利用填充不足的优势。另请参阅对RSA密码系统的二十年攻击。
更新：过去40年中进行的计算工作可帮助进行新的攻击，因为这些方法已经制定出来，但是（对于任何已知的实用方法）都是计算方法。攻击特定密钥所花费的精力对攻击另一个密钥没有用，就像知道$ 1234567890221 = 23801 \ cdot 51870421 $并不能真正帮助找到$ 1234567890197 $的分解一样。
评论
$ \ begingroup $
感谢您提供所有其他链接-很多非常有用的读物！我想我的观点是，是否不仅考虑了从零起点突破当今RSA的挑战，而且还考虑了40年的努力？
$ \ endgroup $
– eggyal
2012年6月25日12:30
$ \ begingroup $
@eggyal：我更新了答案。
$ \ endgroup $
–fgrieu♦
2012年6月25日13:27
$ \ begingroup $
谢谢，但是我的意思是说，一旦发现您提供的分解因子，就可以将其应用于需要分解给定产品的任何地方。在四十年来拥有大量计算资源的情况下，可以发现许多这样的因式分解。我发现@Maeher的回答在反驳这一论点时更具说服力，因为它帮助我认识到，即使对于1024位RSA模数，也需要生成和存储这样的因式分解的数量如此之大，以至于甚至根本不希望这样做与已知密钥的冲突。
$ \ endgroup $
– eggyal
2012年6月25日在13:46
评论
是否真的需要尝试某些条件才能将其视为“已成为一种方法”？ $ \ hspace {1 in} $即使您具有无限的计算能力，您也将没有空间来存储所有这些公钥/私钥对（我将为您腾出半数学文章，将所需空间与宇宙中质子的数量进行比较）。许多人很难理解$ 2 ^ {2048} $的数字有多大，这是一个常见错误。相反，一种更实用的方法是尽可能多地获取现实生活中的公共密钥，并尝试找到它们之间的共同因素。它实际上是由于不良的密钥生成实践而起作用的。
相关问题：碰撞前有多少个RSA密钥？