我知道这将花费大量时间，但是只会执行一次。显然，计算这样的索引将花费大量时间，并且必须由拥有适当资源量的人来完成。有了公钥，您就可以查找两个素数，并因此立即检索到私钥。
然后打破256个AES会更容易，因为AES密钥通常使用RSA私钥。
是否可以建立这样的索引？也许使用世界上最快的计算机需要多长时间？
#1 楼
让我们暂时假设您可以构建一个包含所有素数的大型表。那...什么您将如何使用它？您将查找什么？不需要存储素数（它们可以即时再生；这是昂贵的划分）。但这是一种效率极低的分解算法。我们知道更好的因数分解算法（尽管如此，它仍然无法在2048位RSA模数的表面上产生丝毫刮擦）。当然，1024位素数的列表是如此之大，以至于存储它，甚至只是生成每个素数，都是荒谬的。大约有$ 2 ^ {1014} $个素数；接近$ 10 ^ {308} $。假设您是一个万能的但无聊的神灵，并且您决定使用存储设备存储这些质数，该存储设备对每个质数使用一个氢原子的大小（作为人类，我们当然不能在这么小的空间中存储那么多的信息空间，但是，嘿，这对于全能的上帝是小菜一碟）。已知宇宙的体积约为10 ^ {79} $ m3。氢原子的体积接近$ 10 ^ {-30} $ m3。因此，我们的怪异神性可以在整个宇宙中包装大约$ 10 ^ {109} $的值。他仍然需要$ 10 ^ {199} $个完整的Universe来存储它们。 $ 10 ^ {199} $是一个令人难以置信的数字（如果您的思想不受它的束缚，那么它一定已经受其他事物的束缚了）。它是千亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿的亿万亿亿美元的亿万亿。换句话说，很多。而且我们仍在谈论充满原子大小整数的完整宇宙。
#2 楼
不，建立破坏RSA的主要因素的索引根本不可行。即使我们考虑使用384位RSA（已使用但在20年前就可以破坏），该索引也需要包括160到192位素数的较大部分，因此模数的最小因子有机会出现在索引中。根据素数定理，此类素数的顺序为$ 2 ^ {185} $。现有最大的数据存储系统的容量约为$ 2 ^ {60} $位，因此，如果每个素数仅使用一位，则正确素数存在的几率约为$ 2 ^ {-125} $。
#3 楼
小于$ 2 ^ {2048} $的素数约为$ 2.27 \ cdot10 ^ {613} $。可观察的宇宙中有接近$ 9.4 \ cdot10 ^ {79} $原子。/>
即使您可以计算所有这些质数，也将没有任何存储它们的地方...
评论
$ \ begingroup $
为什么要计数原子？电子或质子不是原子，而是更小...对吗？
$ \ endgroup $
–mmm
11-10-24在9:56
$ \ begingroup $
@Hamidam：我的观点是，小于$ 2 ^ {2048} $的质数是$ 2.42 \ cdot10 ^ {533} $倍，是可观测宇宙中存在原子的数倍。除非我们可以将$ 2.42 \ cdot10 ^ {533} $位数据存储在单个原子中，否则我们要计数的内容并不重要。人类已知的最大原子是Ununoctium的同位素，它由530个亚原子粒子组成：118个质子，118个电子和294个中子。
$ \ endgroup $
–丹尼斯
11-10-24在10:58
#4 楼
您低估了一些东西，要么是攻击者必须生成和存储的素数，要么是在基于标准分解的密码系统中必须乘以的素数的大小。当前的建议建议使用$ 1024 $位的素数。根据此对math.stackexchange的回答，$ 1024 $位质数的数量约为$ 1.26 \乘以10 ^ {305} $。即使攻击者每秒能够生成十亿个素数，也不会花一周的时间来生成所有这样的素数，这将花费$ 4 \乘以10 ^ {288} $年，而且我也没有很好的方法来描述这个数字是巨大的。相比之下，宇宙中的粒子数量是什么。与之相比，即使是宇宙中粒子数量的立方也算不上什么。我什至没有在谈论存储这个巨大的列表或在其中搜索。评论
$ \ begingroup $
因此，基本上，“什么阻止了攻击者”这个问题的答案是：“现实”。
$ \ endgroup $
–Jörg W Mittag
17年2月14日在1:54
#5 楼
使用世界上最快的计算机可能需要多长时间进行排列？ $ 2 ^ {185} $个可能的质数，可用于构造一个$ 384 $位的RSA密钥对。因此，有$ 2 ^ {185 ^ 2} $个可能的RSA密钥对（因为密钥需要两个素数）。假设生成质数不花时间，并且您每秒可以生成$ 10 ^ {30} $个密钥对。要估算创建所有密钥对所需的时间，您可以使用$ 2 ^ {185 ^ 2} / 10 ^ {30} $来获取秒数。然后将其更改为更容易理解的名称（在本示例中为几个世纪），创建所有密钥对大约需要$ 7.63 \ cdot 10 ^ {71} $个世纪。
现在，只需为了说明这有多难，我们假设您每秒可以执行$ 10 ^ {100} $个密钥对。因此，创建索引仍需要花费$ 7625 $的年数。
因此，即使将自己限制为$ 384 $位的RSA，目前也没有足够的存储空间来存储所有可能的密钥对，并且它将接管创建索引七个世纪。我什至不想知道$ 2048 $位RSA的价格。
#6 楼
答案是不。从素数增长率的基本定理来看，证明相对简单。根据该定理，对于足够大的$ n $，约$ n / \ log（n）$个质数小于$ n $。因此，如果您尝试将$ n $的所有除数都小于$ \ sqrt {n} $，则必须尝试使用$ \ sqrt {n} / \ log（\ sqrt {n}）$质数。这大约是$ \ sqrt {n} / \ log {n} $个质数，而不是大约$ \ sqrt {n} $个可能的整数。如您所见，与强力相比，加速因子为$ O（\ log n）$。
还有其他分解方法，它们具有更好的渐近性能。最容易理解的是经过修正的费马因子分解，它具有渐近性能$ O（n ^ {1/3}）$ [Lehman]，实际上，可以将其降低为$ O（n ^ {1/4}）$ ，尽管没有众所周知的证据。更高级的方法（例如二次筛或通用数场）具有更好的渐近性能。这些更高级的方法不依赖于知道数字是否为质数。因此拥有素数列表并不能加快这些方法的速度。
评论
$ \ begingroup $
这些是数十亿美元的长期资产还是短期资产？ （如果我计算正确的话，请选择小比例尺。）
$ \ endgroup $
–PaŭloEbermann
11-10-23在21:56
$ \ begingroup $
规模小。通常，我会尝试使用英式英语（“颜色”，“中心” ...），但是对于数字，我会遵循美国的用法，以免我们的美国朋友误会。
$ \ endgroup $
–托马斯·波宁（Thomas Pornin）
11-10-24在0:48
$ \ begingroup $
再读一次这个答案，存储问题就更糟了！根据全息原理，体积中的最大信息密度与其半径（例如其表面积）的平方成正比，而不是与立方体（例如其体积）成正比。重新计算一下，我们只能在可观察的Universe中打包大约$ 10 ^ {84} $个值，并且需要$ 10 ^ {224} $个Universe来存储它们。当然，一旦将它们存储起来，就需要能够在需要时有效地对其进行查找，这完全是其他蠕虫的一种。
$ \ endgroup $
–斯蒂芬·托瑟（Stephen Touset）
16年1月5日在18:38
$ \ begingroup $
@ThomasPornin我正在再次阅读本文章，感谢您的思考和成熟水平。但是，让我们尝试进一步推动这一点。如果以其他方式解决存储问题怎么办？如果神决定不存储每个素数，而是决定存储足够的稀疏数字，让它跳到一个数字，然后从那里向上或向下走，那该怎么办？数据稀疏程度如何？可以说，给定5年时间开始创建这些稀疏索引，从任何位置进行实际搜索以找到正确的私钥的时间不得超过7天。这样可行吗？
$ \ endgroup $
–mmm
19年7月22日在17:58
$ \ begingroup $
生成计算机将能够随机生成，并且仅将找到的质数从下一个开始保留足够长的时间，从而删除较旧的质数。或从零+ 2移至无穷大，尽管这可能会使事物成为现实。到2 ^ 2048需要多长时间？
$ \ endgroup $
–mmm
19年7月22日在18:03