使用Shor算法破解RSA

RSA是Internet上的标准加密算法。该方法是众所周知的，但极难破解。它使用两个密钥进行加密。公钥是打开的，客户端使用它来加密随机会话密钥。截获加密密钥的任何人都必须使用第二个密钥（私钥）对其进行解密。否则，那只是垃圾。会话密钥被解密后，服务器将使用它以更快的算法对其他消息进行加密和解密。因此，只要我们保持私钥的安全，通信就将是安全的。

RSA加密基于一个简单的想法：素数分解。将两个质数相乘非常简单，但是很难将其结果分解。例如，507,906,452,803的因素是什么？答案：566,557×896,479。

基于这种复杂性的不对称性，我们可以基于两个质数的乘积来分配公钥以对消息进行加密。但是在不知道主要因素的情况下，我们无法将消息解密为其原始意图。2014年，WraithX在Amazon EC2上使用了7,600美元的预算，并使用自己的资源来分解696位数字。我们可以在数月或一年内用可观的预算破解一个1024位密钥。这是毁灭性的，因为持有公钥的SSL证书可持续使用28个月。幸运的是，素因数分解问题的复杂度随密钥长度呈指数增长。因此，由于我们已经切换到2048位密钥，因此我们非常安全。

但您可能会猜到，其复杂性的诅咒已由Shor算法解决。Shor的算法于1994年发布。在此之前，量子计算更像是一种好奇心。Shor算法的引入确实改变了基调。它解决了经典计算机无法有效解决的实际问题。正是这种范式转移吸引了投资。虽然我们讨论了带有“待完成”预言功能的算法，但是Shor的算法确实是一个不错的选择。我们只是在等待具有足够量子位的量子计算机。

Shor的算法涉及许多学科。我们会尝试全面，希望您能以自己喜欢的速度前进。但是，由于我们已经涵盖了很多内容，因此我们不会涵盖每个实施细节。

RSA算法

以下是RSA算法。您现在可以说，如果我们知道如何有效地进行素分解，RSA将成为历史。

RSA算法

但是，我们确实需要理解以上几个术语。最大公约数（gcd）在两个数字之间找到最大公约数。例如，

如果没有共同因素，则两个数字互质。

“ mod ”是程序员熟悉的模运算符（例如14％10 = 4）。让我们回顾一些模数计算。

例如，

这些技巧很容易计算

素数分解复杂度

使用经典计算，我们能解决的最主要因素是：

其中n是表示质数乘积的位数。Shor的算法可以做到这一点

与门数有关

素数分解

但是要解决它，我们需要以一种不寻常的方式来正式化解决方案。让我们用以下公式找到21的素因。神奇地，这些方程式以数字7和3结尾，这就是我们的答案。

但是，这不是简单的运气。它们背后有许多数学理论。基本思想是找到一个数字（在我们的例子中为8），其平方等于右下角的项。

因此，让我们再次尝试好运。从随机猜测x = 2开始。首先，我们想知道x和N是否互质。可以使用Euclid算法来完成。以下是查找21和15之间的公因子的示例。

因此3是21和15的公因数，因此21和15不是互质的。如果x和21不是互素数，则gcd（x，21）将是素数之一，我们就完成了。但是不要期望它会在一个真正的问题中频繁发生。x最有可能与N互质。现在，我们计算以下幂函数系列。

即x = 2。

该函数的周期为6（r = 6），即函数值每隔6个值重复一次。如果r除以2，它将变为3。我们想要的数字8只是pow（2，3），即。pow（x，3）。

总而言之，我们从猜测开始 X 并验证它是否与 ñ。如果不是，我们使用gcd查找主要因素。否则，我们将计算幂函数的周期。

如果周期r是偶数，则我们要寻找的数字是pow（x，r / 2） -下面用红色下划线标出的数字。如果r不为偶数，则对x进行另一个猜测，然后重试。

在实践中，您应该有相当大的机会使期间变得均匀。考虑N = 15的情况。我们有

x的太多选择将引导我们找到正确的解决方案。赔率是非常有利的。困难的部分是找到模函数的周期。Shor的算法将我们带到一类称为有界错误概率多项式时间（BPP）的算法。在复杂度理论中，我们计算最坏情况的复杂度，即O（n）。实际上，存在一些问题，即使最坏的情况仍然是指数形式，在多项式时间中找到解也是常见的准则（但机会通常极小）。

不幸的是，通过经典计算无法轻易地找到上述模函数的周期。这就是量子计算的用武之地。

通过量子计算找到，甚至我们计算gcd。正如我们之前讨论过的那样，使用欧几里得算法很容易做到这一点。

但是，要了解期发现方法，我们首先需要涵盖一些基本概念。