如何估算破解RSA加密所需的时间？

#1 楼

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

您的“ 12位微秒中的512位”是完全虚假的。让我们看看它的来历。 1999年是对RSA（该公司）发布的一项挑战（称为RSA-155）进行首次512位通用分解的一年（因为该数字包含155个十进制数字-二进制，长度为512位） 。该分解花费了6个月的时间。在同年（5月；当时512位因数分解工作已经开始但尚未完成）举办的Eurocrypt活动上，来自魏茨曼研究所的Adi Shamir提出了一种称为TWINKLE的理论装置，据说可以帮助在分解工作中花费了很多。它应该包括大量的二极管，它们以一种黑色的管子以精心选择的频率闪烁。沙米尔（Shamir）带来了一个自定义设备，该设备在10米外的地方看起来像一台咖啡机。他要求人们关闭灯，以使Eurocrypt的与会者可以惊叹于四个红色二极管，分别以2、3、5和7秒的间隔闪烁。哦！和啊！尽管实际要制造的机器将需要数以百万计的二极管，并且频率在10或100 GHz内，但他们还是选择了。因此，这个想法很有趣（至少对于密码学的研究人员来说，这是众所周知的幽默感），但是还没有超出理论上的概图步骤。沙米尔（Shamir）是个很棒的表演者。

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

TWINKLE只是为了加快筛分速度。它与线性减少无关。换句话说，它可以加快容易的零件（相对而言）的速度。即使是TWINKLE增强的筛分一半也离12μs不远。取而代之的是，它将有助于将四个月的筛选工作减少到三个星期。以科学的方式讲，这是好的，但不是破纪录的，特别是因为线性缩小在较大尺寸中占主导地位。 12μs的数字似乎来自与更神秘的野兽Quantum Computer（量子计算机）的混淆，如果可以构建具有512个“量子位”的QC，它可以轻松分解大量数字。 D-Wave最近宣布了一种具有128个量子比特的量子计算机，但事实证明，这些不是“真实的”量子比特，因此不适合分解（理论上，它们仍然可以对优化问题进行一些有效的近似，这非常好）但基本上不适用于密码技术，因为密码算法不适合近似法-密码算法的设计是为了使单个错误的比特扰乱整个事物。到目前为止，最好的“真实” QC似乎是IBM的原型，据我所记得，它具有5个量子位，从而使它能够确定15等于3的5倍。

当前RSA因式分解记录为768位整数，于2009年12月公布。历时四年，涉及目前生活在地球上最聪明的数字理论家，包括伦斯特拉和蒙哥马利，他们在这些圈子中有些像神一样。我最近了解到，已经开始为1024位数字分解进行参数选择（这是“聪明”的部分）。筛分在技术上是可行的（在许多大学群集中这将是昂贵的并且要花费数年的计算时间），但是目前，没人知道如何对1024位整数进行线性缩减。因此，不要指望很快就会有1024位中断。

现在，如果一个业余爱好者可以使用强大的计算机（几十个大型PC，至少一个时钟充满快速RAM）并且可以使用几个月的免费时间，那么使用已发布的代码（例如Msieve）的业余爱好者可以实现512位分解。时间;基本上，“业余爱好者”是指“在富裕的大学中无聊的计算机科学专业的学生”。超出512位的任何内容都是业余爱好者无法接受的。

摘要：在您的代码中，您可以为所有密钥长度的破解时间返回“实际上是无限的”。一个典型的用户不会在现在也不会在十年内破解1024位RSA密钥。地球上大约有十二个人可以以任何可信度声称可以想象的可能性很小，但非零，他们可以在2020年之前的某个未指定时间分解一个1024位整数。

（但是，使用RSA破坏RSA或任何应用程序的实现非常容易，以至于可以完全不用担心RSA密钥地恢复持有的机密数据。如果您使用1024位RSA密钥，则可以确保当您的应用程序被黑客入侵时，不会通过RSA密钥分解。）

#2 楼

简短的回答：最简单的方法是使用素数定理，但要知道这是一个近似值。估计尝试每种素数需要多长时间；每素数的时间*素数的总和。这将为您提供蛮力搜索的估算值。这将为您估算人们打破RSA编号实际使用的分解算法。

背景知识：

编号理论时间！看一下你在说的数字的大小。给定2 ^ 3 = 8（二进制数为1000），我们可以看到这是一个四位数，这是可能的最小值。因此，2 ^ 2 = 4是一个3位数（100）。因此，对于给定的x，确保我们有足够的位的最小可能值为2 ^（x-1）。 2 ^ 2047 = 16158503035655503650357438344334975980222051334857742016065172713762327569433945446598600705761456731844358980460949009747059779575245460547544076193224141560315438683650498045875098875194826053398028819192033784138396109321309878080919047169238085235290822926018152521443787945770532904303776199561965192760957166694834171210342487393282284747428088017663161029038902829665513096354230157075129296432088558362971801859230928678799175576​​150822952201848806616643615613562842355410104862578550863465661734839271290328348967522998634176499319107762583194718667771801067716614802322659239302476074096777926805529798115328.这是一些你在这里处理的大小，即n的大小被分解。

接下来最大的问题则是如何为n构建？正如您从RSA的定义中了解到的那样，您正在寻找两个质数作为该数字的因子。那么问题就变成了我们如何确定一个数是质数，我们可以对它们进行计数吗？

因此，根据定义，对于任何小于n=pq的数字，如果x = 1（\gcd(p, x)除外），则该数字是不可约的。但是，我们可以对此进行改进。您应该很快意识到对于任何数字，它都是素数还是不是素数。如果它不是素数，则它的gcd和至少一个素数必须大于1（否则它将是素数）。由此我们得出结论，任何非素数整数必须可被一组素数整除。形式上的数学证明实际上并不是从这里开始的那么大的飞跃。

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

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

现在您将看到RSA的优势。选择一个非常大的素数，您将有很长的路要走。按照目前的情况，我们必须从2开始，这显然很糟糕。

原始性测试旨在使用多种技术来改善这种情况。天真的方法是我们刚刚讨论过的方法。我认为对这些技术进行详细的讨论可能更适合数学，所以让我总结一下：所有运行时都是垃圾，用它作为计数素数的方法将是可怕的。因此，我们不能可靠地算出素数的数目，而不能不花一整天，因为它实际上类似于整数分解。关于以某种方式对质数进行计数的函数呢？

输入x=1，一次尝试质数定理，它近似于质数。然而，正是这样；该函数的目的是精确计算素数，但目前它仅是一个估计。为了您的目的，这可能已经足够好了。

但是，它仍然绝对是近似值。看一下本文的其余部分。除其他事项外，其他估计还取决于黎曼假设。

那么，整数因式分解又如何呢？好吧，迄今为止，第二好的方法称为二次筛，最好的方法称为常规数场筛。这两种方法都涉及一些相当高级的数学。假设您认真考虑素数分解，我将继续阅读这些内容。当然，您应该能够将这两个估计值用作质数定理的改进，因为如果要考虑大质数，则要使用这些而不是蛮力搜索。 />但是我想了解量子吗？

好吧，很公平。假设我们将能够实现Shor算法，那么在量子计算机上进行整数分解就可以在很短的时间内完成。我应该指出，但是，这需要一台量子计算机。据我所知，开发能够破解RSA的大规模量子计算机目前还遥遥无期。请参阅量子计算的发展。

无论如何，Shor的算法将成倍地提高速度。它的页面为您提供了运行时间的估计，您可能希望将其包括在估计中。

#3 楼

另一种选择是创建一个包含可能的键的大型数据库，并将其用作查找表。显然，您甚至都不需要所有的素数，仅需几个便可以使您通过很大一部分的互联网流量。

资料来源：https://freedom-to-tinker.com/blog/haldermanheninger / how-is-nsa-breaking-so-uchuch-crypto /