但这不是很容易破解的钥匙吗？即使列表容器为1,000,000个素数（我认为不太可能），在典型的台式计算机上检查所有组合也只需要几个小时。
我误解了哪一部分？
#1 楼
您不使用预先生成的素数列表。正如您所注意到的那样，这很容易破解。您要使用的算法将类似于以下内容（请参见HAC中的注释4.51，另请参见crypto.SE的答案）：生成一个随机的$ 512 $奇数位，例如$ p $
测试$ p $是否为质数；如果是，返回$ p $;在测试约$ Log（p）/ 2 \ sim 177 $个候选对象后，预计会发生这种情况
否则设置$ p = p + 2 $，转到2
还有其他生成方法灌注（例如，如果步骤2失败，请执行步骤1，然后转到步骤1）。我概述的方法不过是OpenSSL使用的方法。
有关RSA密钥生成的官方，公共标准，请参阅FIPS 186-4第5.1节和附录B.3.1。
评论
$ \ begingroup $
并不需要10个星期就能产生一个素数？在这些数量级上，我希望素数相隔数光年！另外-您如何测试素数？最后我听说蛮力是唯一的实际方法（尽管进行了一些优化，但仍然有一些优化），这意味着大约为O（2 ^ 512）。
$ \ endgroup $
– Vilx-
2012年1月1日13:29
$ \ begingroup $
@ Vilx-，请记住，OpenSSL完全符合我的描述，因此必须快速。有很多概率素数测试（请参阅我链接到的HAC文档）。一个是米勒-拉宾（Miller-Rabin），很快。通过这些测试，您可以任意接近p为质数的概率为1。最后，素数的分布足够密集，足以使所描述的算法相当快（请参见en.wikipedia.org/wiki/Prime_number_theorem）。
$ \ endgroup $
– Mikeikeazo
2012年3月1日13:48在
$ \ begingroup $
@Vilx大素数很常见。您只需要查看几百个候选人。
$ \ endgroup $
– CodesInChaos
2012年3月1日14:15
$ \ begingroup $
@ Vilx-根据素数定理，x附近的素数之间的距离约为ln（x）。对于1024位数字，它是1024 * ln（2），或大约710。因此，检查某个较大的1024位数字附近的每个奇数，我们期望必须检查大约355个数字才能找到质数。对于计算机，这几乎没有任何作用。
$ \ endgroup $
– BlueRaja-Danny Pflughoeft
2012年3月1日下午16:50
$ \ begingroup $
该算法（按目前的状态）生成具有明显偏差分布的质数：与复合质数恰好位于其下方的质数比其他质数的可能性更大。通常首先选择一个中等大小的随机秘密$ s $，然后在步骤3中将$ p = p + 2 $替换为$ p = p + 2s $。 $ s \ approx \ log_2（p）$足以避免该偏差。实际上，$ s $通常是选择的两个更大的秘密辅助素数$ p_1 $和$ p_2 $的乘积，这样我们将以$ p \ equiv1 \ pmod {p_1} $和$ p \ equiv-1 \结尾pmod {p_2} $。
$ \ endgroup $
–fgrieu♦
15年6月11日在8:23
#2 楼
“我知道典型的方法是使用预先生成的大素数列表。”这也是我的想法。但是我没有考虑过我们可以选择多少个素数。事实证明，您可以从带有1024位RSA密钥的
~2.8x10^147素数和带有4096位RSA密钥的约~7.0x10^613中选择。然后，您最多可获得4.9x10^1227个质数对。这个数目是巨大的，那么您不应该只浏览列表。最初的答案是David Robinson在Stackoverflow上发表的：
关于碰撞是否可能发生-现代钥匙大小（取决于您所需的安全性）的范围从1024到4096，这表示素数的范围从512到2048。这意味着您的素数约为2 ^ 512：超过150位数字。
我们可以使用1 / ln（n）非常粗略地估计素数的密度（请参见此处）。这意味着在这10 ^ 150个数字中，大约有10 ^ 150 / ln（10 ^ 150）个质数，可以算出2.8x10 ^ 147个质数可供选择-肯定比您在任何列表中都能容纳的要多！ br />所以，是的-该范围内的质数非常大，并且实际上不可能发生碰撞。 （即使您生成了一万亿个可能的素数，形成一个九十亿个组合，它们中的任何两个成为相同素数的机会也将是10 ^ -123）。
#3 楼
关键是密码库用于确定数字是否为质数的测试是概率性的。也就是说，如果测试使用随机选择的值（“见证”）作为测试的基础。如果测试通过，则该数字可能是素数，但可能不是。我们可以用新的“见证人”重复进行相同的测试，如果测试再次通过，那么我们将增加确定性。我们可以继续进行多次测试，直到达到所需的确定性水平。因此，可能使用的素数实际上不是素数。但是它不太可能不会严重影响密钥的安全性。
评论
$ \ begingroup $
但是，快速的概率测试只是答案的一半。方便的素数是如此密集，密度为$ \ frac {1} {\ ln {n}} $，否则我们可以快速检查素数无关紧要，因为我们实际上从不选择素数进行检查和验证。
$ \ endgroup $
–托马斯
2012-12-11 18:22
$ \ begingroup $
@tylerl：关于security.SE，我认为ECDHE比ECDHA更普遍。 $ \：$
$ \ endgroup $
–user991
2013年6月30日10:17在
$ \ begingroup $
@RickyDemer我想您可能已将此评论附加到错误的答案（和错误的网站）上。
$ \ endgroup $
– tylerl
2013年6月30日19:58在
$ \ begingroup $
好吧。 $ \：$我没有$ \：$ security.SE帐户。 $ \; \; \; $
$ \ endgroup $
–user991
13年6月30日在20:51
$ \ begingroup $
实际上，有确定性的方法可以找到与概率测试一样快的大素数。因此，通常使用概率方法的事实与RSA密钥生成速度如此之快无关。
$ \ endgroup $
–雨披
13年7月29日在20:12
#4 楼
您可以在生成随机大数后使用GMP库中可用的next_prime函数。这里是链接：https://gmplib.org/manual/Number-Theoretic-Functions.html
评论
$ \ begingroup $
最好不要这样做。您将对选择的素数引入偏见。
$ \ endgroup $
–SquareRootOfTwentyThree
15年7月11日在19:54
$ \ begingroup $
@SquareRootOfTwentyThree虽然确实引入了对素数的偏倚，但与之前的素数之间有很大的差距，但该偏倚极小，并且被认为不可利用。
$ \ endgroup $
–森林
19年5月26日在23:23
$ \ begingroup $
@forest可以通过辅助渠道利用
$ \ endgroup $
–SquareRootOfTwentyThree
19年5月28日在8:35
$ \ begingroup $
@SquareRootOfTwentyThree至少略读本文，看来该攻击适用于两种素数生成方法。
$ \ endgroup $
–森林
19年5月28日在9:04
$ \ begingroup $
“最严格的[对策]是[[]]生成独立于其前身的每个主要候选项（→伪算法1）”
$ \ endgroup $
–SquareRootOfTwentyThree
19年5月28日在20:46
#5 楼
我已经在Python中实现了生成随机可证明素数的Maurer算法（请参阅Menezes等，《应用密码学手册》），如比较所示，该算法仅比通过使用Miller-Rabin测试（只能提供素数（极有可能是素数）表示目前在实践中通常用于RSA的大小素数。因此，Python的解释速度不是很快，但是对于普通人而言，它们只需要为RSA等生成一些大素数就可以了，但是在当前情况下这没什么大不了的。我的代码PROVABLEPRIME可在以下位置获得：http：/ /s13.zetaboards.com/Crypto/topic/7234475/1/
评论
$ \ begingroup $
太好了。但是...并不能真正回答问题。 ：P
$ \ endgroup $
– Vilx-
15年10月17日在18:48
$ \ begingroup $
@Vilx：你是对的。我是直接在上面的mikeazo帖子上发表评论，我想这是对您的OP的回答。
$ \ endgroup $
–沉莫功
2015年10月18日在10:03
评论
+1。有相同的精神障碍。从产品中排除两个素数非常困难，但是找到大素数却很容易。虽然不是那么直观。@Vilx，您好，虽然这个问题在这里成为话题，但在我们的兄弟站点-Cryptography上，它仍然会更多。
有关为什么使用质数列表不好的更多背景信息，请参见此博客文章和文章“罗恩错了，惠特错了”。该问题的答案描述了可以找到多大的素数。