有关各种研究人员和组织使用的关键强度估计的摘要，请参阅此站点。

您的“12μs 内的 512 位”完全是假的。让我们看看它来自哪里。1999 年是执行第一个 512 位通用因式分解的年份，由 RSA（该公司）发布并称为RSA-155（因为该数字由 155 个十进制数字组成 - 在二进制中，长度为 512 位） . 分解耗时 6 个月。在同年组织的Eurocrypt 活动中（5 月；当时 512 位因式分解工作已经开始但尚未完成），来自魏茨曼研究所的Adi Shamir展示了一种名为TWINKLE的理论设备据推测，这可能对分解工作有很大帮助。它应该包含大量以精心选择的频率闪烁的二极管，在一种黑管中。沙米尔带来了一个定制设备，从 10 米外看，它看起来就像一台咖啡机。他要求人们关掉灯，以便 Eurocrypt 与会者可以惊叹于以 2、3、5 和 7 秒为间隔闪烁的四个红色二极管。哦！啊！他们去了，尽管要建造的实际机器需要数百万个二极管和 10 或 100 GHz的频率。所以这个想法很有趣（至少对于以具有奇怪幽默感而闻名的密码学研究人员而言），但还没有超出理论草图步骤。沙米尔是一个伟大的表演者。

然而，TWINKLE 只是“帮助”。最著名的因式分解算法称为通用数域筛；接下来的两种算法是二次筛法和椭圆曲线法。512 位数字对于当今的技术来说是 QS 和 ECM 无法达到的，而对于 1999 年的技术来​​说更是如此。GNFS 非常复杂（从数学上讲），尤其是因为它需要仔细选择一些关键参数（“多项式选择”）。因此，非常聪明的大脑必须做出初步努力（使用大型计算机，但大脑在这里是最重要的）。之后，GNFS 由两部分组成，筛子和线性归约. 筛子可以在成百上千台机器上并行制造，这些机器必须仍然相对较大（在 RAM 中），但这是可行的。线性减少涉及使用一个太大而无法放入计算机的矩阵来计算事物（通过几个数量级，即使我们假设所述计算机具有 TB 的快速 RAM）。有一些算法可以将矩阵（非常稀疏）保持为压缩格式，并且仍然能够计算，但这很难。在 512 位因式分解中，筛分大约花费了总时间的 80%，但对于更大的数字，线性缩减是瓶颈。

TWINKLE 只是为了加快筛分部分。它对线性减少没有任何作用。换句话说，它加快了容易（相对而言）的部分。即使是 TWINKLE 增强的一半筛分速度也远不及 12μs。相反，它宁愿帮助将四个月的筛选工作减少到三周。以科学的方式，这很好，但不是破纪录的，特别是因为线性减少在较大尺寸中占主导地位。12μs 的数字似乎来自与更神秘的野兽量子计算机的混淆，如果可以构建具有 512 个“量子位”的 QC，则可以轻松分解大数字。D-Wave 最近宣布了一款具有 128 个量子比特的量子计算机，但事实证明这些不是“真正的”量子比特，它们不适合分解（理论上它们仍然可以在优化问题中做一些有效的近似，这很棒但基本上不适用于密码学，因为密码算法不适合近似值——它们的设计是为了让一个错误的位扰乱整个事情）。迄今为止，最好的“真实”QC 似乎是 IBM 的原型，据我所知，它有 5 个量子位，使其能够确定 15 等于 3 乘以 5。

当前的 RSA 因式分解记录是768 位整数，于 2009 年 12 月宣布。它花了四年时间，涉及目前生活在地球上的最聪明的数论家，包括 Lenstra 和 Montgomery，他们在这些圈子中有几分神一样的地位。我最近了解到 1024 位数字因式分解的参数选择已经开始（这是“聪明”的部分）；筛分在技术上是可行的（它会很昂贵，并且在许多大学集群上需要数年的计算时间），但是目前，没有人知道如何对 1024 位整数进行线性归约部分。所以不要指望很快就会出现 1024 位中断。

现在，如果可以使用功能强大的计算机（数十台大型 PC，以及至少一个时钟充满快速 RAM）和几个月的免费时间，使用已发布代码（例如Msieve ）的专业业余爱好者可能会实现 512 位分解时间; 基本上，“敬业的业余爱好者”的意思是“在一所富裕大学里无聊的计算机科学专业的学生”。任何超过 512 位的东西都是业余爱好者无法企及的。

摘要：在您的代码中，您可以返回“几乎无限”作为所有密钥长度的破解时间。典型的用户不会破坏 1024 位 RSA 密钥，现在不会，十年后也不会。地球上大约有十几个人可以以任何可信度声称，可以想象，以低但非零的概率，他们可能能够在 2020 年之前的某个未指定时间分解单个 1024 位整数.

（但是，很容易搞砸 RSA 或任何使用 RSA 的应用程序的实现，以至于可以恢复它所持有的机密数据，而无需担心 RSA 密钥。如果您使用 1024 位 RSA 密钥，您可以确定，当您的应用程序被黑客入侵时，它不会通过 RSA 密钥分解。）

简短回答：最简单的方法是使用素数定理，但请注意这是一个近似值。估计尝试每个素数需要多长时间；每个素数的时间*素数为您提供总时间。这将为您提供蛮力搜索的估计。

您还可以使用二次筛或一般数字字段筛的运行时间估计。这将为您估计破解 RSA 数字的人实际使用的因式分解算法。

长背景：

数论时间！

首先，让我们看一下您所说的数字的大小。给定 2^3 = 8，即二进制 1000，我们可以看到这是一个四位数，这是可能的最小值。因此，2^2 = 4 是一个 3 位数 (100)。因此，对于给定的 x，确保我们有足够位的最小可能值为 2^(x-1)。2^2047 = . 这就是您在这里处理的数字的大小，即n 被考虑在内。

那么下一个大问题是如何构造n？n=pq正如您从 RSA 的定义中知道的那样，因此您正在寻找两个素数作为该数字的因数。那么问题就变成了我们如何确定一个数字是素数并且我们可以数它们吗？

所以根据定义，一个数是不可约的，如果对于任何x小于它的数，\gcd(p, x)= 1，除了x=1. 但是，我们可以对此进行改进。你应该很快意识到，对于任何数字，它要么是素数，要么不是素数。如果它不是素数，那么它和至少一个素数的 gcd 必须大于 1（否则它将是素数）。我们由此得出结论，任何非素数整数都必须能被一组素数整除。正式的数学证明实际上并没有那么大的飞跃。

这被称为算术基本定理并稍微简化了问题。所以现在，当计算一个数字是否是素数时，我们不再需要尝试每个数字，只需要我们已经知道的数字是素数！

这显然仍然很慢，所以让我们再做一次观察 - 给定因素成对出现，两个数字中的较低者至多是该数字的平方根。如果我们仅限于 N（自然数集），它表示我们需要检查的最大可能值的上限。所以现在，对于任何数字 N，我们必须从 2 开始搜索每个整数，并针对我们在该列表中确定为素数的每个数字前往 sqrt(N)。然后，如果我们找到一个素数，我们就可以推断它是否因数 N 本身。我不会估计它的运行时间，因为我无疑会说错话，但这需要很长时间。

现在你看到了 RSA 的力量。选择一个非常大的素数，你最终会有很长的路要走。按照目前的情况，我们必须从 2 开始，这显然很糟糕。

素性测试旨在使用各种技术改进这一点。天真的方法是我们刚刚讨论过的方法。我认为对这些技术的详细讨论可能更适合数学，所以让我总结一下：所有的运行时都是垃圾，用它来计算素数是可怕的。

因此，我们不能可靠地计算质数的数量而不是永远小于一个数字，因为它实际上类似于整数分解。以某种方式计算素数的函数呢？

输入\pi(n) = \frac{n}{\log(n) - 1.08366}, 一次尝试质数定理是质数的近似值。然而，正是如此；这种函数的目的是准确计算素数的数量，但目前它只是给你一个估计。出于您的目的，这可以被认为足够好。

但是，它绝对仍然是一个近似值。看看这篇文章的其余部分。除其他外，其他估计取决于黎曼假设。

好的，那么，整数分解呢？嗯，迄今为止第二好的方法称为二次筛，最好的方法称为通用数域筛。这两种方法都涉及到一些相当高级的数学；假设您认真考虑分解质数，我会阅读这些内容。当然，您应该能够将两者的估计值用作使用素数定理的改进，因为如果您要分解大素数，您希望使用这些而不是蛮力搜索。

但我想知道量子？

好，可以。假设我们能够实现Shor 算法，那么量子计算机上的整数分解可以在非常短的时间内完成。然而，我应该指出，这需要一台量子计算机。据我所知，开发能够破解 RSA 的规模的量子计算机目前还有一段路要走。请参阅量子计算发展。

在任何情况下，Shor 的算法都会以指数方式更快。它上的页面为您提供了运行时间的估计值，您可能希望将其包含在估计值中。

另一种选择是创建一个包含可能键的大型数据库并将其用作查找表。显然你甚至不需要所有的素数，只需几个就可以让你通过很大比例的互联网流量。

来源：https ://freedom-to-tinker.com/blog/haldermanheninger/how-is-nsa-break-so-much-crypto/