我是否错误地认为，总的来说，RSA加密的安全性受已知素数数量的限制？
要破解（或创建）私钥，必须组合正确的一对素数。
是否不可能发布使用RSA的范围内所有素数的清单？还是该列表足够大，使得这种暴力攻击变得不太可能？会不会存在“常用”的素数？
有多少个质数可以用于RSA加密？
52
- pinhead
3
2这个问题似乎不是关于编程的，因此被认为是不相关的。 - jww
加密学相关问题：RSA 密钥在发生碰撞之前有多少个？ - CodesInChaos
还有：RSA中的质数是如何生成的？ - veljkoz
2个回答
103
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个可供选择的质数-肯定比您能够放入任何列表中的要多得多！
因此是的-在该范围内的质数数量是惊人的庞大，并且碰撞实际上是不可能的。（即使你生成了一万亿个可能的质数，形成一个千万亿的组合，它们中任意两个都成为相同的质数的机会将是10^-123）。
引用如下： “生成大质数的标准方法是取所需长度的预选随机数，应用费马测试（最好使用基数为2，因为它可以优化速度），然后应用一定数量的米勒-拉宾测试（取决于长度和允许的误差率，例如2^-100），以得到一个极有可能是质数的数字。”
（你可能会问，在这种情况下，我们为什么不在尝试寻找越来越大的质数时使用这种方法。答案是，已知的最大质数有超过1700万位数，远远超出了加密中通常使用的非常大的数字。）
至于是否存在碰撞-现代密钥大小（取决于所需的安全性）范围从1024到4096，这意味着质数范围从512到2048位。这意味着您的质数约为2^512：超过150位数。
我们可以使用1/ln(n)（请参阅此处）非常粗略地估算质数的密度。这意味着，在这些10^150个数字中，大约有10^150/ln(10^150)个质数，计算出来是2.8x10^147个可供选择的质数-肯定比您能够放入任何列表中的要多得多！
因此是的-在该范围内的质数数量是惊人的庞大，并且碰撞实际上是不可能的。（即使你生成了一万亿个可能的质数，形成一个千万亿的组合，它们中任意两个都成为相同的质数的机会将是10^-123）。
- David Robinson
12
5@pinhead：看一下我的最新更新。这个规模的质数可以非常容易地适应内存——它们的范围从1到4 kb。但是可能的质数列表（估计约为10^147）即使你使用宇宙中的每一个原子来存储不同的位也无法放得下。 - David Robinson
6“which means the prime numbers range from 512 to 2048” - 我认为你的意思是512到2048位的质数范围。 - Nick Johnson
3非常好的回答。问题在于它假定有一个完美的伪随机数生成器(PRNG)来生成足够数量的唯一数字来派生质数。实际上，PRNG通常不如它们应该的那样好，由于熵的缺乏或由于错误的实现。因为RSA公钥包含生成日期，所以你已经知道了一部分熵，这进一步有助于限制可能的随机数范围。这是一个很好的例子，表明可能存在比人们预期的RSA密钥更少的情况：http://lwn.net/Articles/482089/。 - Hans Dampf
许多公钥包含版本信息，以便您知道生成密钥所使用的软件和版本。如果此版本在密钥生成中存在已知漏洞，则可以进一步帮助您破解它。 - Hans Dampf
@Taurus 10^150，不是150。 - David Robinson
显示剩余7条评论
8
随着新的研究成果的发布，你的问题的答案变得更加有趣。在David Adrian等人最近发表的论文“Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice”中，该研究团队发现，尽管RSA的1024位密钥集合中可能有足够数量的素数可用，但由于实现原因，存在一些更有可能被使用的密钥组。论文可以在以下链接中找到： https://weakdh.org/imperfect-forward-secrecy-ccs15.pdf （2015年10月16日访问）。
我们估计，即使对于1024位情况，也可以通过国家级资源进行计算。数百万服务器使用少量的固定或标准化组；对一个单独的1024位组进行预计算将允许被动监听18％的受欢迎HTTPS站点，并且第二个组将允许解密66％的IPsec VPN和26％的SSH服务器的流量。仔细阅读公开的NSA泄露文件表明，该机构对VPN的攻击与已经实现此类突破是一致的。我们得出结论，采用更强的密钥交换方法应该是互联网社区的优先事项。
该研究还显示了TLS的一个缺陷，可能会允许中间人攻击者将加密降级为512位。
因此，回答你的问题，在RSA加密上理论上可能有足够数量的素数，但实际上如果你要隐藏不受国家监控，存在安全问题。
我们估计，即使对于1024位情况，也可以通过国家级资源进行计算。数百万服务器使用少量的固定或标准化组；对一个单独的1024位组进行预计算将允许被动监听18％的受欢迎HTTPS站点，并且第二个组将允许解密66％的IPsec VPN和26％的SSH服务器的流量。仔细阅读公开的NSA泄露文件表明，该机构对VPN的攻击与已经实现此类突破是一致的。我们得出结论，采用更强的密钥交换方法应该是互联网社区的优先事项。
该研究还显示了TLS的一个缺陷，可能会允许中间人攻击者将加密降级为512位。
因此，回答你的问题，在RSA加密上理论上可能有足够数量的素数，但实际上如果你要隐藏不受国家监控，存在安全问题。
- Sir David J. Garretson M.S.
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接