问如何计算破解RSA或DH所需的时间？

EN

本文给出了通用数域筛分解大整数的渐近公式。这是最有效的破译RSA密钥的算法，RSA密钥超过400位左右(因为当前的世界记录是768位，400位RSA密钥是相当弱的)。对于离散对数 (破坏DH)，最著名的算法也被称为“数字字段筛”，它与分解的算法非常相似。特别是，它具有相同的渐近复杂性。

但是，渐近公式并不能捕获所需的所有信息：

• 对于足够大的输入，一个渐近公式描述了根据输入的大小给出计算时间的函数的行为。它说，“当输入的大小向无穷大的方向增长时，复杂性会以类似于这个公式的方式增长”。但这仍然是一个近似，没有任何保证，你试图打破的实际RSA密钥是足够大的渐近公式是合理准确的。例如，对于300位整数，多多项式二次筛的速度比GNFS慢，但实际上比GNFS慢。这意味着300位整数不足以使渐近公式精确地对因式分解算法进行排序。
• 即使公式是准确的，它前面也有一个隐式乘法常数(如果你愿意的话，你可以将它命名为“每秒的运算数”)。因此，这个公式必须通过一个实际的实验来校准。说到这一点，尽管用于因式分解的GNFS和用于离散对数的NFS具有相同的渐近行为，但它们没有相同的“常数”，因此，在实践中，600位DH键似乎比600位RSA密钥更难打破(实际上，目前关于离散对数的世界记录是“只有”530位)。
• 时间复杂度公式只讨论操作，但不描述空间需求。在GNFS中，存储空间可能会变得很大，特别是对于算法的最后一部分(“线性代数”)，它是对庞大大小矩阵的概念上简单的操作(Gauss约简)；实际上，这一步骤受到RAM大小和速度以及在集群中移动数据的速度的限制。CPU不是瓶颈，时间复杂度公式只讨论CPU。
• 整个过程没有精简。该算法有几个步骤(多项式选择、筛选、线性代数)，虽然有很好的开源代码，但在关键时刻仍然需要聪明人的思考。要想打破因子分解的世界纪录，你需要马力，但也需要知道GNFS的来龙去脉的计算机科学家，全世界大概有上百个这样的人。

因此，估计RSA或DH密钥的中断时间的实用方法是从已发布的整数因式分解记录和离散对数记录中进行外推。

在这种“外推”方面已经做了很多工作，特别是在寻找对称和非对称密钥长度之间的“等价”(如：“1024位RSA密钥与160位哈希函数大致相同”)。有关由不同组织发出的结果建议的全面摘要，请参见本站 (带有在线计算器和多个指针)。鉴于我上面提到的各点，毫不奇怪的是，公布的建议实际上并不匹配.

2011年经常给出的综合建议是：“使用2048位RSA/DH/DSA密钥，这样你就可以享受一段时间了。”

这些断言总是带有一些假设，要么被阐明，要么隐含。

在大多数公钥算法中，从公钥导出私钥最好通过解决一些数学问题来完成(据目前所知)。

• 对于RSA来说，已知最快的打破方式是保理模量(它应该是两个大素数的乘积)。
• 对于DSA、迪夫-赫尔曼和ElGamals (签名，加密)来说，已知最快的破解方法是解决离散对数问题。

所以我们假设如下：

• 没有比解决相应问题更快的打破该方案的办法了。
• 没有算法能解决这些比我们现在所知道的要快得多的问题。
• 潜在对手的计算能力不会比摩尔定律所允许的要高得多。(还有一些替代的、更保守的计算方法，它们为每一项基本计算计算一些最低能量消耗，并设定了一个限制，如“将木星的质量转换为能量”之类。)

有了这些，我们就可以简单地计算出破解密钥所需的时间(平均)。