没有人知道什么时候，但威胁加密的量子机器即将到来。以下是研究人员如何使用量子力学破解非对称密码学中的大整数。

量子计算继续存在于实际应用和理论推测之间的模糊空间，但它正在接近现实世界的使用。量子计算机更有趣的用例之一是现代互联网密码学。

量子计算和量子比特

量子计算之所以得名，是因为它依赖于亚原子粒子的特性，而亚原子粒子的规律对我们这些植根于宏观世界的人来说似乎很奇怪。特别是，量子计算机使用qubits（量子位）而不是我们从传统计算机系统中知道的二进制数字（位）。

量子比特本质上是概率性的，而比特是确定性的。一点最终归结为一个物理开关——尽管它非常小，只有几纳米。位是二进制的：开或关，真或假，0 或 1。

量子比特并非如此。

量子比特的物理基础可以是多种现象，例如电子的自旋或光子的极化。这是一个引人入胜的话题：连接想象和现实的线性方程领域。量子力学被认为是对潜在现实的解释，而不是描述，并且是高度计算复杂性的根源。

量子比特的状态被描述为两种可能状态的线性叠加。一旦观察到，状态就会被解析为真或假。但是，相同的输入不一定会解析为相同的输出，并且未观察到的状态只能用概率术语来描述。

从经典物理学的角度来看，更令人惊讶的是，量子计算机中的量子比特可以同时存在多个状态。当计算机对一个量子比特的状态进行采样时，它会分解为一个非此即彼（称为波函数崩溃）。

密码学中的量子计算

从科学和哲学的角度来看，所有这些都是相当有趣的。例如，量子计算机的功能验证了观察对粒子的影响，并表明确实，上帝确实在与宇宙掷骰子。但在这里，我们关注的是量子计算在我们日常生活中不断增加的能力的实际方面。未来几年，最深远的影响可能是密码学。

从量子计算到密码学最著名的途径是发生在 1994 年的理论突破：Shor 算法。从理论上讲，该算法展示了量子图灵机有效解决使用传统计算机难以解决的一类问题的能力：大整数的因式分解。

如果您熟悉Diffie-Hellman和 RSA 等非对称密码系统算法，您就会知道它们依赖于求解大数因子的难度。但是如果量子计算解决了这个问题呢？

用量子力学破解大整数

Shor 的算法和一些其他算法利用量子力学来破解非对称密码学核心的单向函数。绝热量子计算也被用于攻击分解。

Shor 和其他算法依赖于量子计算机凭借量子位居住在多种状态的能力。然后，他们以允许采样中高度概率的方式对这些量子比特（这会破坏它们的状态）进行采样。本质上，我们将“给定数字的因素是什么”这个问题交给了神秘的看不见的世界，在那里粒子属性可以以多种状态存在。然后，我们查询这些属性以获得最可能的答案。（是的，这确实有效。）

Shor 算法所分解的最大数是 21。绝热量子计算已成功分解了 143。

这些算法复杂且令人印象深刻，但到目前为止，它们的数量微不足道。RSA 的当前标准是 2048 位，也就是 617 位！然而，在攻击数字 143 时，研究人员在不知不觉中揭示了一种允许更大数字的方法，至少在理论上是这样。一个例子是56,153，与破坏现实世界密码系统所需的数量相比，这仍然是一个相对较小的数字。它还取决于不能用于所有数字的还原技巧。

对网络安全基础设施的威胁

我们现在所知道的是，对非对称算法的量子攻击的基本方面正在被解决。该技术将以多快的速度发展到可以接近更大数量的程度？

有趣的是，我们每天使用的对称算法（如 AES）并不十分容易受到量子算法的攻击。Grover 的算法是适用的算法。如果使用 256 位密钥，即使在理论上，也无法比经典算法进一步减少攻击这些算法所需的时间。

然而，大多数对称安全通信通过非对称交换建立其密钥。因此，当今的大多数网络流量都容易受到高级量子计算攻击。如果攻击者可以发现在交互开始时建立的密钥，那么再多的对称加密都将无用。

因此，对网络安全基础设施的威胁是真实存在的。让我们想一想游戏中的动态。首先要考虑的是纯粹的经济和访问。目前，只有现金充裕的组织才有能力修补这些东西。IBM、谷歌和中国的研究科学家正在争夺生产可行系统的领导地位，以及许多大学的努力。在幕后，像美国国家安全局这样的政府机构肯定不会闲着。事实上， NSA对公共密码学和量子计算问题有自己的看法。

不断发展的量子计算安全性

小规模参与者不太可能获得足以攻击现代非对称密钥的量子计算能力，直到大型机构完成它很久之后。这意味着我们处于一个很长一段时间内，安全基础设施可以响应量子计算的动态而发展。

没有人知道真正具有加密威胁的量子机器何时会出现，但它似乎很可能会发生。处理这个问题的两个标准是系统中量子比特的数量和这些量子比特的寿命。

量子比特受到所谓的退相干的影响。熵总是把电子和光子的微妙集合带走。问题是量子比特的数量和寿命都很难量化。对 RSA 2048 密钥进行实际的可重复攻击需要多少量子比特？有人说几十，有人说几百万。需要多少连贯性？有人说几百纳秒，有人说几分钟。

而所有这些都可以被前面提到的预处理算法的棘手使用等技术所颠覆。谁知道现在聪明的本科生正在想出一种新的方法。在量子机器上分解 143 的人直到两年后才意识到他们也破解了 56,153 。

后量子密码学

条条大路通后量子世界，很多人已经在为之努力。美国国家标准与技术研究院目前正在举办开发抗量子算法的竞赛。其中一些努力正在取得成果。

归根结底，基于越来越真实的结果，我们可以说对密码学的量子威胁是真实存在的。但就目前而言，它不仅仅是被反补贴力量所抵消。我们最终可能不得不告别一些我们心爱的旧算法，但新的算法将取代它们。

在接下来的十年里，这将是一场有趣的舞蹈。