量子计算机尚未商业化，也不容易构建，但它们有望超越当今现有的超级计算机。历史证明，即使是今天看起来很复杂的技术，未来也可能会走向商业化，建造和使用量子计算机现在肯定是不可行的，但未来可能并非总是如此。事实上，谷歌、IBM、微软等许多组织都在进行大量研究，以将量子计算机投入实际使用。

如果量子计算机准备好用于商业应用，它们将有什么用途，它们会产生什么影响？可以预见，它们的用途将是巨大的，这可能使许多行业受益，甚至改变我们的生活。一些可能受益的领域是人工智能和机器学习、计算化学、药物设计、天气预报，不胜枚举。

尽管量子计算机可以带来很多好处，但它们对公钥密码学构成了巨大的风险，公钥密码学是当今互联网上所有安全连接的支柱。

在本文中，我们将根据以下主题讨论预测量子计算机对公钥密码学的影响：

• 量子计算机
• 公钥密码学
• 对 PKI 的量子威胁
• Shor 和 Grover 算法
• 后量子密码学
• 后量子迁移

量子计算机

尽管量子计算机还处于起步阶段，但研究和发明的速度可以使它们在十年或两年内运行。量子计算机可以取代超级计算机，超级计算机是具有数千个经典 CPU 和 GPU 内核的经典计算机。2017 年，IBM 开始与客户合作开发采用量子电池技术的新一代电动汽车，旨在利用量子计算辅助材料发现减少大气中的碳排放。

量子计算机是使用量子态特性进行计算的系统。在当今的计算机和 PDA 设备中，数据以位表示为 0 或 1，但在量子计算机中，0 和 1 同时以不同的组合同时存在。同时存在的能力称为叠加。

量子比特由一个由电子自旋或质子方向构成的物理系统构成。电子在旋转时表现得像微小的磁铁，这种方向总是导致 0 指向上，1 指向下。类似地，光子的行为类似于电磁场，0 为水平偏振，1 为垂直偏振。自旋和定向的这些特性可以在许多不同的排列中找到，它们构成了量子计算的基础，并与称为量子纠缠的特性联系在一起。

在本文的其余部分，我们将看到量子计算机将如何影响作为所有安全连接主干的公钥密码学。

公钥密码学

公钥密码术 (PKC) 是当今通过 Internet 进行安全交互的基础。公钥密码学是非对称的，这意味着它使用两个密钥：一个是公共的，与所有人共享，另一个是系统用来证明其身份的私钥。客户端通过生成消息的哈希并使用公钥对其进行加密来向接收者发送消息。服务器使用其密钥（私钥）来解密消息，该消息只能由相应的私钥解密，而不能使用任何其他密钥解密，即使在中间人攻击的情况下也是如此。

服务器通过显示从证书颁发机构 (CA) 获得的证书向客户端证明它是预期的服务器，而不是其他服务器。CA 遵循所有必需的 PKI 标准和准则向服务器颁发证书并使用其私钥对其进行签名。客户端使用其信任库验证数字签名证书，其中包含 CA 共享的公钥。一旦证书被验证，客户端和服务器为会话的其余部分建立一个对称密钥，因为非对称密钥比对称密钥慢。

算法使用 CA 提供的密钥对纯文本进行加密和解密。以其发明者 Rivest、Shamir 和 Adelman命名的 RSA 算法是此类算法中使用最多的算法。

公钥和私钥都是素数。在非对称密钥设置中，取两个素数 p 和 q，它们构成了私钥。它们的乘积 p·q 构成公钥。小数 p 和 q 很容易找到它的质因数。例如，如果数字 15 作为公钥给出，那么将 15 分解为素数会产生 3 和 5。但是，如果同一个数字有 200 或 400 位数字，那么对于任何当前的经典算法来说，将其分解为素数都是困难的计算机，这将需要数百万或数万亿年。

对公钥密码学的量子威胁

分解素数的困难使得公钥密码学可以工作几十年而没有任何问题。但随着量子计算机的诞生，公钥密码学面临风险，因为将大量数分解为素数可能只需要几个小时。美国国家标准与技术研究院 (NIST) 预测3量子计算机将在十年内全面投入使用，它们将能够破解非对称密钥密码学。一旦分解成为可能，今天被认为安全的加密数据将很容易被解密。换句话说，一旦量子计算机可用，现在加密和存储的数据就可以被解密。

量子计算机中用于分解数字的算法是由数学家 Peter Shor 提出的。我们将在下一节讨论它对 PKC 的影响，以及 Grover 的算法。

Shor 和 Grover 算法

Peter Shor展示了如何使用量子计算机对数字进行因式分解，从而将所需的时间从数年减少到数小时。Shor 算法可用于针对非对称密钥，这是 PKI 的基础。如果 Shor 的算法变得实用，那么任何存储在任何地方的现有密钥和数据都需要重新加密。

Shor 的算法会影响密钥交换以生成用于加密数据的会话密钥。窃听者可以记录加密会话，然后当量子计算机可用时，轻松解密它。窃听者还可以伪造客户端用来验证服务器证书的数字签名，从而导致数据完整性和身份验证丢失。

Shor 算法包括以下步骤：

选择一个随机正整数m。使用欧几里得方法(m, N)计算最大公约数GCD ，其中N是自然数集N={1, 2, 3, 4, 5…….}。如果最大公约数GCD(m, N) != 1，则获得的值是N的重要因子。但是如果GCD(m, N) = 1，那么我们需要确定周期。

这一步涉及找到函数f(x) = a^x mod N的周期 r，也就是说，我们需要找到r的最小值，使得f(x)= f(x+r)。此步骤只能与量子计算机一起使用。

如果r是奇数，那么我们需要从头开始，否则我们将继续下一步。

如果m^r/2 + 1 = 0 mod N ，那么我们需要再次进入步骤 1，否则我们需要使用欧几里得算法计算(m^r/2-1, N)的最大公约数。最后，我们获得了N的所有非平凡因子。

让我们用一个例子来总结一下上述步骤。

第 1 步- 让要分解的数字为 N，在我们的例子中 N 为 15。

第 2 步- 选择一个介于 1 和 N 之间的随机数让我们称之为 m，即在 1 和 15 之间让我们取 m=4。

第 3 步- 找到 GCD(N,m)。我们可以使用欧几里得除法算法来找到它。如果 GCD 不等于 1，则它是 N 的因子。在我们的示例中，GCD(15,4) = 1，因此我们进入下一步。

第 4 步- 在这一步中，我们需要找到最小的正整数 r，如果 f(x) = kˣ mod N，则f(a) = f(a+r)。这可以在我们的示例中实现，如下所示。

步骤 4.1 - 让我们定义一个变量q =1。然后我们将计算q*m mod N。如果余数为 1，让我们继续下一步，否则我们重复该步骤，直到通过将 q 的值设置为我们从上一步获得的提醒来获得提醒，如下所示：

1 * 4 模 15 = 4

4 * 4 模 15 = 1

由于我们进行了两次转换来获得提醒 1，因此r的值为2。如果r是奇数，我们返回步骤 2并为m选择不同的值，否则我们继续下一步。

第 5 步- 要找到因子f1和f2，我们使用 f₁ = GCD (p+1, N) 和 f₂ = GCD (p-1, N)。为了找到值p，我们定义 p 等于第(r/2) 次变换中的余数。在我们的例子中，它是 4，即第(2/2) 次变换。

第 6 步- N 即 15 的因数是

f₁ = GCD (p+1, N)，即 f₁ = GCD(5,15) = 5。

f2 = GCD (p-1, N) 是 f1 = GCD(3,15) = 3。

另一方面，Grover 的非结构化密钥搜索算法4可能会影响对称密钥加密。Grover 的算法使用幅度放大来搜索列表中的项目。虽然它需要经典计算机 N/2 或 N 步，但 Grover 的放大技巧只需要 N 步的平方根。二次加速可以节省从长列表中搜索项目的时间，但该算法必须按顺序执行才能实现其完全二次加速。

由于量子计算机中发生了很多并行处理，因此不能应用 Grover 算法，因为它需要串行处理。如果考虑串行处理，那么 Grover 算法对对称密钥加密的影响就不那么重要了，使用 AES 128 将保持安全。事实上，AES 中使用的对称密钥可以使用 Grover 算法进行暴力破解，对于 128 位对称加密密钥大约需要 264次迭代，或者对于 256 位密钥大约需要 2128次迭代。因此，拥有双倍长度的对称密钥可以防止未来的量子攻击。

后量子密码学

为了应对量子算法带来的挑战，后量子密码学旨在让量子计算机难以破解数字签名。

已经提出了几种后量子密码学 (PQC) 解决方案，例如基于格的、基于代码的、多元多项式密码学和基于散列的签名4。大多数 PQC 算法将使用更大的密钥大小，例如，密钥大于当今 128 位密钥的 AES。如果需要较大的密钥大小，则必须对各种 Internet 协议进行更改，例如传输层安全 (TLS) 协议或 Internet 密钥交换。但是，正如 NIST 的后量子密码学报告(NISTIR 81051) 所总结的那样，上述提议均未证明是解决量子威胁的完美解决方案。

由于许多实现限制，我们可能会对不同类型的应用程序有不同的算法。一个这样的例子是密钥大小：大密钥可能适用于某些应用程序，但不适用于其他应用程序。PQC将为新应用开发不同的标准，以应对传统和量子挑战。

虽然正在进行积极的研究以找到现有密码学的解决方案，但已经提出了另一种完全不同的解决方案：量子密钥分发 (QKD) 。在网络中，当两方通过安全通道进行通信时，仍然有可能被邪恶的人看到密文。使用 QKD，可以在发送任何安全信息之前检测到窃听者，并且可以首先停止两方之间的通信。当窃听者干扰时，它会影响量子态，从而两方会知道这种改变。

量子密钥分发是在 PQC 算法执行期间安全传输对称密钥的过程。对于经典系统，通过不受信任的介质共享秘密对称密钥在量子时代将是一个挑战。QKD 试图解决它。事实上，使用非 RSA 或 ECC 的公钥方案存在不同的密钥分发算法，但 QKD 提供植根于物理定律的安全保证。此外，它将对量子攻击具有弹性。其原因是 QKD 是通过使用光的量子态对数据进行编码来实现的，这对于攻击者来说是不可能破解的5。

在 PQC 时代，应用程序应该能够处理一种以上的密码算法来处理量子密码和经典密码。使用混合密钥机制将使新应用程序能够在保持传统标准的同时保护自己免受量子威胁。最终，组织需要为新的加密标准做好准备。

后量子迁移

从经典密码学到量子安全密码学的迁移必须分阶段进行。这包括编制一份将在 10 年或 20 年后使用的应用程序清单，以及为实施后量子密码学准备迁移和执行计划。该组织应考虑其长期路线图中的任何新项目，并考虑到量子威胁。迁移必须在完全了解资产的情况下完成，并根据量子威胁对其进行评估。在某些情况下，组织可能依赖需要评估的第 3 方软件，并且应该将其列为迁移计划的一部分。例如，在 PKI 策略的情况下，CA 不会改变，但实施会有所不同。

在准备迁移计划时，必须进行完整的评估，包括决定是否需要迁移应用程序。事实上，在重新设计期间，某些系统可能会退役或过时。大多数组织的应用程序都遵循 PKI 策略，CA 颁发的证书需要用量子安全证书重新颁发。在某些情况下，应用程序可能需要考虑向后兼容性以支持混合证书。

如果 PKI 准备好支持新的量子安全加密，则必须更新信任证书和证书链验证。当使用 PKI 的组织准备迁移到量子安全 PKI 时，必须在存储中更新中间证书和根证书。因此，迁移计划应在迁移到量子安全 PKI 之前考虑 CA 的迁移计划。用于安全通信的存储数据需要迁移，因为它们容易受到未来的量子攻击。可以进行风险分析，如果发现任何无形资产，可以将其转移到确定的隔离区。

标准尚未到位，但研究的步伐正在加快。该标准最终将准备就绪，每个人都应该准备好迁移到它。一旦新标准到位，并且组织遵守新的 PKI 标准，证书的用户和生产自签名证书的组织应该意识到这一变化并为迁移做好准备。向新标准的迁移涉及了解现有的 PKI 标准和即将引入的量子安全标准。

结论

在本文中，我们简要介绍了当前的PKC架构，并描述了量子计算机可能对公钥密码学产生的影响。

尽管量子计算机还处于起步阶段，但它们的进一步发展可以使它们以合理的成本在商业上可用，并产生多重影响。当那一天到来时，所有公钥和私钥都将面临量子威胁，这对每个组织来说都是一个巨大的风险。尽管公钥用户不知道他们的数据如何以安全的方式传输的内部机制，但了解量子计算的增长及其可能对密码学产生的影响对每个人来说都是关键，无论他们的角色如何。 

了解什么以及如何迁移到新的、即将到来的量子安全加密标准对每个人都至关重要，从 CEO 到实施它的工程师。迁移涉及预算、规划、迁移、开发、实施、执行和确保混合实施到位。

---煤油灯科技victorlamp.com翻译整理---