量子计算机在商业层面还没有就绪，制造起来很困难，但它们的性能有望远远超过今天的超级计算机（注 1）。历史证明，今天看起来很复杂的技术迟早都会在未来商业化，现在就制造并使用量子计算机肯定是不可行的，但未来可能就不一样了。事实上，包括谷歌、IBM、微软在内的许多组织正在做大量研究工作，努力推动量子计算机技术实用化。
如果量子计算机为商业应用准备就绪，它们会有哪些用途，又会产生怎样的影响呢？可以预见的是，它们的用途会十分广泛，可能让许多行业从中受益，甚至改变我们的生活。一些可能受益的领域有人工智能和机器学习、计算化学、药物设计、天气预测……等等（注 6）。
虽然量子计算机有很多好处，但它们对公钥加密技术构成了巨大的威胁，而公钥加密是当今互联网上所有安全连接的支柱。
在这篇文章中，我们将根据下面列出的主题，讨论量子计算机对公钥加密技术可能产生的影响：
量子计算机
公钥加密技术
量子计算对 PKI 的威胁
舒尔算法和格罗弗算法
后量子时代的加密技术
后量子时代的技术迁移
量子计算机
尽管量子计算机技术尚处于初始发展阶段，但业界在这一领域研究和发明的速度可以让它在十到二十年内投入使用（注 3）。量子计算机可以取代拥有成千上万个经典的 CPU 和 GPU 内核的经典计算机。2017 年，IBM 开始与客户合作开发新一代电动汽车，其采用量子电池技术，旨在利用量子计算辅助的材料发现方法减少大气中的碳排放（注 5）。
量子计算机是利用量子态的特性来进行计算的系统。在今天的计算机和 PDA 设备中，数据以比特表示为 0 或 1；但在量子计算机中，0 和 1 在同一时间以不同的组合同时存在。同时存在的能力被称为叠加态（注 2）。
量子比特是由电子的自旋或质子的方向构成的物理系统。电子在自旋时，表现得像微小的磁铁，这种取向总是导致 0 指向上，1 指向下。同样地，一个光子的行为就像一个电磁场，0 为水平极化，1 为垂直极化。这些自旋和方向的属性可以在许多不同的排布中找到，从而形成了量子计算的基础，并与一种被称为量子纠缠的属性联系在一起（注 2）。
在后文中，我们将看到量子计算机会如何影响公钥加密技术这一所有安全连接的支柱。
公钥加密
公钥加密（PKC）是当今互联网上安全互动的基础。公钥加密是不对称的，这意味着它使用两个密钥：一个是公开的，与所有人共享，另一个是系统用来证明用户身份的私钥。客户端生成一条信息的哈希值，用公钥对其加密后向接收方发送信息。服务器使用它的密钥（即私钥）解密信息，即使在中间人攻击（注 4）的情况下也只能用相应的私钥来解密。
服务器展示从证书颁发机构（CA）获得的证书，向客户证明它是预定的服务器，而不是其他什么人。CA 遵循所有必要的 PKI 标准和准则来向服务器颁发证书，并用其私钥签名。客户端用信任存储验证数字签名的证书，其中包含由 CA 共享的公钥。一旦证书被验证，客户端和服务器就为其余的会话建立一个对称密钥，因为非对称密钥的速度比对称密钥慢。
由 CA 提供的密钥被算法用来加密和解密纯文本。RSA 算法（以其发明者 Rivest、Shamir 和 Adelman 的名字命名）是这类算法中使用最多的（注 4）。
公钥和私钥都是质数。在非对称密钥设置中有两个质数，即 p 和 q，它们构成私钥。它们的乘积 p·q 构成了公钥。对于较小的数字 p 和 q 来说，要找到它们乘积的质因数是很容易的。例如，如果数字 15 被作为公钥，那么将 15 分解成质数就会得到 3 和 5。但是，如果一个数字有 200 或 400 位，那么将其因式分解为质数对于任何当前的经典计算机来说都是极为困难的，需要数百万乃至数万亿年才能计算出来。
量子对公钥加密的威胁
质数因式分解的难度使得公钥加密技术在几十年来没有遇到任何问题。但随着量子计算机的诞生，公钥加密技术开始面临风险，因为量子计算机将大数分解成质数可能只需要几个小时。美国国家标准与技术研究所（NIST）预测（注 3），量子计算机将在十年内完全投入使用，它们将能够打破非对称密钥加密的堡垒。一旦大数的质因数分解成为可能，今天被认为足够安全的加密数据将很容易被解密。换句话说，一旦有了量子计算机，现在加密存储的数据就可以被解密。
量子计算机中用于质因数分解的算法是由数学家舒尔（Peter Shor）提出的。我们将在下一节讨论它对 PKC 的影响，同时也会讨论格罗弗（Grover）的算法。
舒尔和格罗弗的算法
彼得-舒尔展示了如何使用量子计算机来计算一个数字的因数，其效果是将所需时间从数以年计减少到小时计的水平。舒尔的算法可以用来针对非对称密钥，这是 PKI 的基础。如果舒尔的算法成为现实，那么储存在任何地方的所有现有密钥和数据都需要重新加密。
舒尔的算法将影响用来生成用于加密数据的会话密钥的密钥交换过程。窃听者可以记录下加密的会话，以后当量子计算机可用时就可以轻松解密。窃听者还可以伪造客户用来认证服务器证书的数字签名，导致数据完整性破坏和认证损失。
舒尔的算法包括以下步骤。
选择一个随机的正整数 m。使用欧氏方法计算最大公约数 GCD(m, N)，其中 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，那么 m 就是 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。例如：
1 * 4 mod 15 = 4
4 * 4 mod 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。
f₂ = GCD (p-1, N)即 f₂ = GCD(3,15) = 3。
另一方面，格罗弗的非结构化密钥搜索算法（注 4）可以影响对称密钥加密。格罗弗的算法使用振幅放大法来搜索列表中的一个项目。虽然经典计算机需要 N/2 或 N 个步骤，但格罗弗的放大技巧只需要 N 的平方根个步骤。平方的速度提升可以节约从长列表中搜索项目的时间，但该算法必须按顺序执行才能实现其完整的二次方速度提升。
由于量子计算机中有许多并行处理过程，格罗弗的算法就不能应用了，因为它需要串行处理。考虑到串行处理，格罗弗算法对对称密钥加密的影响就不那么重要了，而使用 AES 128 仍将是安全的。事实上，AES 中使用的对称密钥可以用格罗弗的算法进行暴力破解，对于 128 位的对称加密密钥来说大约需要 2 的 64 次方次迭代，对于 256 位的密钥来说大约需要 2 的 128 次方次迭代。因此，使用一个双倍长度的对称密钥可以预防未来的量子攻击。
后量子时代的加密技术
为了应对量子算法带来的挑战，后量子时代的加密技术（注 4）将致力于使量子计算机难以破解数字签名。
业界已经提出了一些后量子加密（PQC）解决方案，如基于格子、基于代码、多元多项式加密和基于哈希的签名（注 4）。大多数 PQC 算法将使用更大的密钥，例如，比今天所用的 128 位密钥更大的 AES 加密。如果需要更大的密钥，各种互联网协议，如传输层安全（TLS）协议或互联网密钥交换协议就都要修改。但是，正如 NIST 的《后量子加密报告》（NISTIR 81051）所总结的那样，上述提案都没有证明自己是解决量子威胁的完美方案。
由于一些实现层面的限制，我们很可能会对不同类型的应用使用不同的算法。其中一个例子是密钥大小：一个较大的密钥可能适合某些应用，但不适合其他应用。PQC 将为新的应用开发不同的标准，以便同时应对传统和量子解密挑战。
在业界积极研究现有加密技术的解决方案的同时，另一个完全不同的解决方案已经浮出水面：量子密钥分发（QKD）（注 4）。在网络中，当两方通过安全通道通信时，窃听者仍然有可能查看密码文本。 有了 QKD，网络在发送任何安全信息之前就可以检测到窃听者，并且可以在第一时间阻止双方的通信。当窃听者扰动网络时会影响到量子态，从而让通信双方知会这种扰动。
量子密钥分发是在执行 PQC 算法过程中安全地传输对称密钥的过程。 对于经典系统来说，在量子时代，通过一个不受信任的媒介来分享秘密的对称密钥是一大挑战。QKD 就试图解决这个问题。事实上，使用非 RSA 或 ECC 的公钥方案存在不同的密钥分发算法，但 QKD 提供了根植于物理定律的安全保证。此外，它将对量子攻击具有弹性。原因是 QKD 是使用光的量子态对数据编码来实现的，这对攻击者来说是不可能破解的（注 5）。
在 PQC 时代，应用程序应该能够处理一种以上的加密算法，这样就能同时处理量子密码和经典密码。使用混合密钥机制将使新的应用程序能够在保持传统标准的同时保护自己免受量子威胁。最终，企业需要为一系列新的加密标准做好准备。
后量子时代的技术迁移
从经典加密向量子安全加密的迁移必须分阶段进行。这一过程包括了编制一份 10 年或 20 年后使用的应用程序清单，以及为实现后量子加密技术准备迁移和执行计划。组织在考虑其长期路线图中的新项目时都应考虑到量子威胁。迁移必须在完全了解资产的情况下进行，并在考虑到量子威胁的情况下对其进行评估。在某些情况下，组织可能依赖于第三方软件，这需要对应的评估工作，并应将其列为迁移计划的一部分。以 PKI 战略为例，CA 不会改变，但实现方式会有所不同。
在准备迁移计划的同时必须做一个完整的评估，其中包括决定该应用是否需要迁移。事实上，在重新设计的过程中，有些系统可以退役或淘汰。大多数组织的应用都遵循 PKI 策略，由 CA 颁发的证书需要重新颁发量子安全证书。在某些情况下，应用程序可能需要考虑向后兼容以支持混合证书。
如果一个 PKI 准备好了支持新的量子安全加密技术，信任证书和证书链验证必须随之更新。当使用 PKI 的组织准备迁移到量子安全的 PKI 时，中间证书和根证书必须在存储里更新。所以，在迁移到量子安全的 PKI 之前，迁移计划应该考虑到 CA 的迁移计划。在安全通信中使用的存储数据需要被迁移，因为它们容易受到未来量子攻击的影响。组织可以进行风险分析，发现的无形资产都可以转移到预定的隔离区。
这些标准还没有就绪，但行业正在加快研究步伐。标准迟早会做好准备，所有人都应该准备好迁移到新标准。一旦新标准出台，各组织也开始遵守新的 PKI 标准，证书的用户和生成自签名证书的组织就应该意识到这种变化，并为迁移做好准备。向新标准的迁移工作需要对现有 PKI 标准和即将到来的量子安全标准有充分理解。
总结
在这篇文章中，我们对当前的 PKC 架构做了简短介绍，并分析了量子计算机对公钥加密可能产生的影响。
尽管量子计算技术还处于起步阶段，但它们的进一步发展可以让它们以合理的成本实现商业化，并产生巨大影响。当这一天到来时，所有的公钥和私钥都将暴露在量子威胁之下，这对每个组织来说都是巨大的风险。虽然公钥用户不知道他们的数据是如何以安全方式传输的，但无论每个人身处何种角色，了解量子计算的趋势和它可能对加密产生的影响都是非常重要的。
了解尚未到来的新量子安全加密标准，并知道该如何迁移到新标准，对从首席执行官到实现工程师的每个角色来说都至关重要。迁移工作涉及到预算、规划、迁移、开发、实现、执行，及确保混合实现就绪等诸多细节。
参考文献
ai.googleblog（2019 年 10 月 23 日）：使用可编程超导处理器的量子霸权
微软 Azure：叠加，和纠缠
NIST：计算机安全资源中心
每个人都应该知道的量子计算顶级应用（2020 年 3 月 20 日）
作者介绍
Joseph Stephen Savariraj 是一名首席软件工程师，他在不同的组织中有超过 18 年的经验。他多年来一直在电信、航空航天、金融组织等许多领域提供咨询服务。他被授予世界著名的专业管理证书，并以其技术经验交付了许多利基产品。他也是框架开发团队的一员，是旅游行业 XML 的共同创始人之一。他热衷于网络安全领域，并撰写了很多关于安全的文章。
原文链接：An Introduction to Post-Quantum Public Key Cryptography
中国开发者画像洞察研究报告 2024
分析开发者的行为模式、工作价值、职业发展等内容，帮助整个行业生态更深入地理解开发者，为他们提供更精准...
评论