量子对于后量子并不重要

你最近可能会听到很多关于后量子（PQ）密码学的消息，当没有人真正见过量子计算机时，很容易想知道为什么它如此重要。但即使量子计算机永远不会被制造出来，新的 PQ 标准也比它们传统的对应物更安全、更具弹性且更灵活。

量子计算机意义重大；随便问问，你就会得到一大堆意见。也许量子计算机正处于摧毁我们所知的公钥密码学的边缘。或者，在密码学上意义重大的量子计算机是不可能实现的。也许公钥密码学的终结不是现在，而只是二十年后的事情。或者，也许我们还有 50 或 60 年的时间，因为有用的量子计算机已经出现二十年了，而且我们预计这种情况不会很快改变。

这些关于量子计算机的观点和预测也导致了对后量子密码学的许多不同看法。也许我们现在就需要尽快过渡到后量子密码。也许后量子密码是一个白日梦，因为有人会找到一种方法来利用量子计算机来破解新的算法。也许一个主要的世界政府已经拥有一台量子计算机，但将其列为机密。

实际上，在我们看到一台具有密码学意义的量子计算机之前，很难知道它何时会出现。我们可以猜测，我们可以尝试根据我们目前掌握的有限数据进行推断，我们可以希望出现一种或另一种结果。但我们无法确定。

不过，这没关系，因为抗量子性并不是后量子密码的主要好处。

当前的研究和标准工作将产生更安全、更具弹性的密码算法，这些算法基于一组不同的密码学问题。这些算法受益于过去 40 年的实践经验，并提供用例的灵活性。末日预言者和量子怀疑论者都应该庆祝。

孤注一掷

担心量子计算机的人通常只关注一点，而且他们在这点上绝对是正确的：目前广泛使用的几乎所有公钥密码学都可能因量子计算中一些不确定但可能出现的进展而被破解。

粗略地说，最常用的公钥算法是基于三个问题：因式分解（RSA）、有限域离散对数（Diffie-Hellman）和椭圆曲线离散对数（ECDH 和 ECDSA）。这些都是一个更通用的计算问题的特殊实例，该问题称为隐藏子群问题。量子计算机擅长解决隐藏子群问题。它们真的很擅长。非常擅长，以至于如果有人制造出一台在许多研究人员看来规模似乎合理的量子计算机，他们就可以做各种卑鄙的事情。他们可以读取加密消息。他们可以冒充在线的可信组织。他们甚至可以使用它来构建一些加密形式的破解工具，而无需量子计算机。

但即使量子计算永远变得不够强大，无法破解当前的公钥，量子末日预言者的恐惧也是基于一个完全有效的观察：互联网几乎将其所有密码学的鸡蛋都放在了隐藏子群问题的单个篮子里。如果有人能够有效地解决隐藏子群问题，无论是通过量子计算机还是经典计算机，他们都将能够破解互联网上使用的大多数公钥密码学。

经常被忽视的是，在过去的 40 年里，隐藏子群篮子一直被证明不如我们预期的那么安全。

因式分解和离散对数的进展

在 1987 年的演讲 “从十字弓到密码学：技术阻止国家，” 中，Chuck Hammill 讨论了具有 200 位数字（约 664 位）的 RSA 密钥，他说地球上最强大的超级计算机也无法在 100 年内分解出一个这样的数字。PGP 1.0 的 Unix 版本 支持 992 位的 RSA 密钥作为其最高安全级别，称该密钥大小为“军用级”。

如今，美国国家标准与技术研究院 (NIST) 提供的公式 表明，664 位密钥仅提供约 65 位的安全性，并且坚定地掌握在积极的学术研究人员手中。一个 992 位的密钥仅提供约 78 位的安全性，并且据推测情报机构可以掌握它。

（PGP 1.0 中支持的最小密钥大小为 288 位，使用现成的软件（如 msieve）在现代台式计算机上大约 10 分钟即可破解。“商业级”密钥为 512 位，可以使用 AWS 在不到一天的时间内以不到 100 美元的价格进行分解。）

不断增加的密钥大小

为了应对多年来因式分解和离散对数算法的进步，我们通过做我们真正知道如何做的唯一事情来做出回应：增加密钥大小。如今，典型的 RSA 密钥大小为 2048 到 4096 位，大约是 Chuck Hammill 建议的三到六倍，是早期版本的 PGP 所谓的“军用级”RSA 密钥长度的两到四倍。美国国家安全局要求用于机密数据的 RSA 密钥不得短于 3072 位。NIST 公式表明，密钥需要 15,360 位长才能匹配 256 位 AES 密钥的安全性。

多年来，有限域离散对数密钥大小在很大程度上与 RSA 密钥大小保持一致。这是因为解决这两个问题的最佳算法是相同的：使用通用数字域筛 (GNFS) 的索引微积分。边缘存在一些差异，但大部分艰苦的工作是相同的。值得指出的是，有限域离散日志密码系统还有一个额外的缺点：计算有限域中的一个离散日志的成本与计算大量离散日志的成本大致相同。

在过去 15 年左右变得越来越流行的椭圆曲线，并没有像因式分解和离散对数系统那样发生密钥大小的变化。谢天谢地，索引微积分不能很好地转化为椭圆曲线，但是 椭圆曲线离散对数是一个开放的研究领域。

实施风险

除了缺乏问题多样性之外，另一个担忧是当前算法很挑剔，并且容易出现细微的实现故障。

听着，我们是 Trail of Bits。我们因说“ fuck RSA ”而有点出名，我们这样说主要是因为 RAS 充满了地雷 。有限域 Diffie-Hellman 在参数选择和弱子群攻击方面存在细微的问题。椭圆曲线密码系统容易受到曲线外攻击、弱子群攻击以及与错误参数选择相关的攻击。

更糟糕的是，每一种 这些算法都需要仔细注意，以避免计时侧信道攻击！

总而言之，这些陷阱和细微的失败模式使当前的公钥原语成为开发人员的绝对雷区。密码库通常将其底层功能称为“ hazmat ”，这并不罕见。这一切都发生在你进入更高级别的协议之前！

许多实现问题至少可以通过使用良好的标准来部分缓解。例如，Curve25519 专门设计用于快速、恒定时间的实现，以及防止曲线外和弱子群攻击的安全性。用于网络流量的大多数有限域 Diffie-Hellman 密钥交换都是使用少量旨在缓解弱子群攻击的标准化参数集完成的。与加密和签名相关的已知 RSA 攻击的不断增加的集合可以（通常）通过使用经过良好测试和审核的 RSA 库（实现最新标准）来缓解。

良好的标准提供了极大的帮助，但它们实际上只是掩盖了这些密码系统的一些根深蒂固的属性，这些属性使它们难以使用并且错误地使用它们很危险。尽管如此，尽管错误造成的后果以及高质量开源库的可用性，Trail of Bits 仍然经常在我们的代码审查中发现这些算法的危险缺陷实现。

后量子密码提供的功能

那么为什么后量子密码要好得多？了解正在进行的 NIST 后量子密码标准化工作很有帮助。

问题的多样性

首先，即将发布的 NIST 标准基于多种数学问题：

• CRYSTALS-KYBER、CRYSTALS-DILITHIUM 和 Falcon 基于格问题：各种环上的短整数解 (SIS) 和带误差学习 (LWE)。
• SPHINCS+ 基于 SHA-256 和 SHA-3 哈希函数的二次原像攻击的难度。

此外，NIST 正在尝试标准化一个或多个额外的签名算法，可能基于不同的问题。提交的文件包括基于与椭圆曲线同源、纠错码和多元二次方程相关问题的签名算法。

到下一阶段的标准化结束时，我们可以期望拥有至少基于三到四个不同数学问题的算法。如果其中一个选定的问题要归因于量子或经典算法的进步，则可以很容易地获得替换方案，这些替换方案极不可能受到对已失败的密码系统的攻击的影响。

现代设计

我们今天看到的后量子提案是在事后诸葛亮的情况下制定的。现代密码系统设计人员已经看到了当前公钥密码学在实践中失败的无数种方式，并且这些经验正在融入到最终设计的结构中。

以下是一些示例：

• 许多后量子算法被设计为易于实现恒定时间实现，从而降低了定时攻击的风险。
• 许多算法通过使用 SHAKE 等确定性函数扩展 nonce 值来减少对随机数生成器 (RNG) 的依赖，从而防止对不安全 RNG 的依赖。
• NIST 决赛入围者中非均匀分布的随机抽样技术已完全指定，并已作为标准化工作的一部分进行了分析，从而降低了依赖于有偏差抽样的攻击风险。
• 许多后量子算法在其输入中是完全确定性的（这意味着使用相同的 nonce 加密或签名相同的值将始终产生相同的结果），从而减少了 nonce 重用问题以及如果重用值则信息泄漏的风险。
• 许多算法被设计为允许快速轻松地生成新密钥，从而更容易提供前向保密性。
• 每个针对后量子密码系统的严肃提案都列出了一小组安全参数化，而不是邀请开发人员设计自己的参数。

这些是故意的、精心制定的决定。每一个都基于过去 40 年左右出现的真实世界的失败。在密码学中，我们经常将这些失败情景称为“自杀手枪”，因为它们使你很容易搬起石头砸自己的脚；较新的设计会竭尽全力使其难以做到这一点。

用例灵活性

新的算法带来了新的权衡，并且在后量子标准中可以找到很多权衡。基于哈希的签名可以运行到 50 KB，但公钥很小。像 McEliece 这样的基于代码的系统具有小的密文，并且可以快速解密 - 但公钥可能达到数百 KB。

这种不同的权衡给开发人员带来了很大的灵活性。对于速度和带宽很重要但 ROM 空间便宜的嵌入式设备，McEliece 可能是密钥建立的一个不错的选择。对于处理器时间便宜，但每次连接节省几个网络活动字节可以转化为真正节省的服务器场，NTRUSign 可能是签名的一个不错的选择。有些算法甚至提供多个参数集来满足不同的需求：SPHINCS+ 包括用于相同安全级别的“快速”签名和“小”签名的参数集。

后量子的缺点：不确定性

当然，一个很大的担忧是每个人都在尝试标准化相对较新的密码系统。如果行业（或 NIST）选择了不安全的东西怎么办？如果他们选择的东西明天就会崩溃怎么办？

这个想法甚至会让人感到可怕地合理。RAINBOW 在被破解之前进入了 NIST PQC 标准化工作的第三轮。SIKE 在被破解之前进入了（计划外的）第四轮。

有些人担心新的标准可能会遭受与 RAINBOW 和 SIKE 相同的命运，但要等到它在行业中被广泛采用之后。

但这是一个可怕的事实：我们已经面临这种风险。从数学的角度来看，没有证据表明 RSA 模不能轻松分解。事实上，没有证据表明破解 RSA（就像今天使用的那样）等同于分解（事实上，情况恰恰相反）。完全有可能有人明天发布一种算法，完全破坏 Diffie-Hellman 密钥交换。有人可能会在下个月发表一篇聪明的论文，展示如何恢复私有 ECDSA 密钥。

更可怕的事实？如果你稍微眯起眼睛，你会发现因式分解和有限域离散对数已经发生了重大突破。如上所述，GNFS 的进步已经推动 RSA 和 Diffie-Hellman 密钥大小增加了二十多年。在 1994 年被认为是好的的密钥在 2024 年被认为是可笑的。来自旧密码朋克时代的 RSA 和 Diffie-Hellman 已经被破解。你只是没有注意到它们被破解了，因为这花了 30 年的时间，而密钥一直在变得更大。

我不想听起来自鸣得意。在过去的几年里，认真的研究人员付出了很多努力来研究新的后量子系统。而且，当然，他们可能会遗漏一些东西。但是，如果你真的担心有人会找到一种方法来破解 SPHINCS 或 McEliece 或 CRYSTALS-KYBER 或 FALCON，你可以继续使用当前的算法一段时间。或者你可以切换到 混合密码系统，它以一种应该保持安全的方式将后量子和前量子方法结合在一起，只要两者都不被破坏。

总结一下

对量子计算机的恐惧可能被夸大了，也可能没有。我们现在还不知道。但是，后量子密码研究和标准化工作的影响是，我们已经从一个篮子中取出了一堆鸡蛋，并且我们正在构建一组更加多样化和现代化的篮子。

后量子标准最终将用不因最细微之处而崩溃的算法取代旧的、更挑剔的算法。几个常见的实现错误来源将被消除。开发人员将能够选择算法来适应广泛的用例。如果数学上的突破导致其中一种算法变得不安全，则各种新的数学基础提供了一个“备用计划”。之后，量子算法并不是万能药，但它们肯定可以治疗我们在 Trail of Bits 看到的许多令人头疼的问题。

忘记量子计算机，而关注后量子密码的研究和标准化，因为它是什么：一种多样化和现代化的努力。

• 原文链接： blog.trailofbits.com/202...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～