后量子密码学——新算法“在 60 分钟内完成”

我们写过关于 PQC 的文章，简称 后量子密码学，之前几次。

如果你错过了过去几年媒体​​对所谓量子计算的兴奋……

…它是（如果您原谅某些专家可能会认为鲁莽的过度简化）一种构建可以跟踪的计算设备的方式 多种可能的结果 同时进行计算。

非常小心，也许还有一点运气，这意味着您可以重写某些类型的算法以找到正确的答案，或者至少正确地丢弃一大堆错误的答案，而无需尝试和测试所有可能的结果一个接一个。

假设实际上可以构建一个适当强大且可靠的量子计算设备，则可以使用两个有趣的密码分析加速：

• Grover 的量子搜索算法。 通常，如果您想搜索一组随机排序的答案以查看您的答案是否在列表中，您可能希望在最坏的情况下浏览整个列表，然后才能获得明确的答案。 例如，如果您想找到 128 位 AES 解密密钥来解密文档，则需要搜索所有可能密钥的列表，从 000..001, ..2, ..3，依此类推，一直到 FFF..FFF （16 字节的价值 FF)，以确保完成问题。 换句话说，你必须预算来尝试所有 2¹²⁸ 在找到正确的密钥或确定没有密钥之前可能的密钥。 然而，格罗弗的算法，在一台足够大且功能强大的量子计算机的情况下，声称能够用 平方根 通常的努力，从而破解密码，理论上，只需 2⁶⁴ 而是尝试。
• Shor 的量子分解算法。 几种当代加密算法依赖于这样一个事实，即两个大素数相乘可以快速完成，而将它们的乘积重新划分为您开始使用的两个数字则几乎是不可能的。 要了解这一点，请尝试使用纸笔将 59×87 相乘。 可能需要一分钟左右才能将其取出（答案是 5133），但这并不难。 现在尝试另一种方式。 比如说，将 4171 分成两个因数。 更难！ （它是 43×97。）现在想象一下用一个 600 位长的数字来做这件事。 粗略地说，你一直试图将 600 位数字除以每个可能的 300 位素数，直到你中了大奖，或者发现没有答案。 然而，Shor 的算法承诺用 对数 平时的努力。 因此，分解多个 2048 二进制数字所花费的时间应该是分解 1024 位数字的两倍，而不是分解 2047 位数字的两倍，这代表了巨大的加速。

应对威胁

格罗弗算法的威胁可以简单地通过平方来增加你正在使用的数字的大小，这意味着你的加密哈希或对称加密密钥中的位数加倍。 （换句话说，如果您认为 SHA-256 现在很好，则使用 SHA-512 将提供抗 PQC 的替代方案。）

但是 Shor 的算法不能那么容易被反击。

一个 2048 位的公钥需要它的大小以指数方式增加，而不是简单地通过平方，所以不是 2×2048=4096 位的密钥，要么你需要一个不可能大小为 2 的新密钥²⁰⁴⁸ 位…

…或者你必须采用一种全新的后量子加密系统，而 Shor 的算法并不适用。

那么，美国标准机构 NIST 一直在运行 PQC“竞争” 自2017年下半年以来。

该过程对所有人开放，欢迎所有参与者，公开发布所有算法，公开审查不仅是可能的，而且 积极鼓励:

征求提议。 [2017-11-30 关闭]。 […] 新的公钥加密标准旨在指定一个或多个额外的未分类、公开披露的数字签名、公钥加密和密钥建立算法，这些算法在全球范围内可用，并且能够保护敏感的政府信息在可预见的未来，包括在量子计算机出现之后。

经过三轮提交和讨论， NIST宣布，在 2022 年 07 月 05 日，它选择了四种算法，它认为是立即生效的“标准”，所有算法都具有悦耳的名字： CRYSTALS-KYBER, CRYSTALS-Dilithium, FALCON及 SPHINCS+.

第一个 （CRYSTALS-KYBER) 被用作所谓的 关键协议机制 (KEM)，其中公共通信通道的两端安全地制作一次性私有加密密钥，用于秘密交换会话的数据价值。 （简单的说： 窥探者只是得到切碎的卷心菜，所以他们不能窃听谈话.)

其他三种算法用于 数字签名，从而您可以确保您在您的终端得到的数据与发送者在另一端输入的数据完全匹配，从而防止篡改并确保完整性。 （简单的说： 如果有人试图破坏或弄乱数据，你就会知道.)

需要更多算法

在公布新标准的同时，NIST 还公布了 第四轮 在其竞争中，进一步提出了四种算法作为可能的替代 KEM。 （请记住，在撰写本文时，我们已经有三种经过批准的数字签名算法可供选择，但只有一种官方 KEM。）

这些曾经是： BIKE, Classic McEliece, HQC 和 SIKE.

有趣的是， McEliece 算法 早在 1970 年代，美国密码学家 Robert Mc Eliece 就发明了该密码，他于 2019 年去世，当时 NIST 的竞赛已经开始。

然而，它从未流行起来，因为与当时流行的替代方案 Diffie-Hellman-Merkle 算法（DHM，有时只是 DH）相比，它需要大量的关键材料。

不幸的是，三个第四轮算法之一，即 SIKE, 好像被破解了。

在一篇题为 对 SIDH 的有效密钥恢复攻击（初步版本），比利时密码学家 Wouter Castryk 和 Thomas Decru 似乎对 SIKE 算法造成了致命的打击

如果您想知道，SIKE 是 超奇异同基因密钥封装, SIDH 代表 超奇异同源 Diffie-Hellman, 的特定用途 SIKE算法 因此，通信通道的两端执行类似 DHM 的“加密”来交换一堆公共数据，允许每一端派生一个私有值以用作一次性秘密加密密钥。

我们不打算在这里解释攻击； 我们将重复该论文的主张，即：

非常松散地说，这里的输入包括密钥建立密码舞中的参与者之一提供的公共数据，以及该过程中使用的预先确定的（因此是众所周知的）参数。

但是提取的输出（信息称为 同源性 φ 上面）应该是该过程中从未公开的部分——所谓的私钥。

换句话说，仅从公共信息（例如在密钥设置期间公开交换的数据）来看，密码学家声称能够恢复其中一位参与者的私钥。

一旦你知道了我的私钥，你就可以轻松且无法察觉地伪装成我，因此加密过程被破坏了。

显然，密钥破解算法需要大约一个小时来完成它的工作，它只使用一个 CPU 内核，具有您在日常笔记本电脑中可以找到的那种处理能力。

当配置为满足 1 级（NIST 的基本加密安全等级）时，这与 SIKE 算法背道而驰。

怎么办呢？

什么！

（这是个好消息。）

正如该论文的作者所建议的那样，在注意到他们的结果仍然是初步的之后， “就目前的情况而言，对于任何公开生成的基本曲线，SIDH 似乎都已完全崩溃。”

（这是坏消息。）

然而，鉴于 SIKE 算法尚未得到正式批准，它现在可以适应这种特殊的攻击（作者承认这是可能的），或者干脆完全放弃。

无论 SIKE 最终发生了什么，这都很好地提醒了我们为什么尝试发明自己的加密算法会充满危险。

这也是为什么专有加密系统的一个典型例子 依赖于算法本身的保密性 在 2022 年维护他们的安全是完全不可接受的。

如果像 SIKE 这样的 PQC 算法在全球专家的研究和探索中幸存了五年以上，尽管被特别披露以便接受公众审查……

......那么就没有必要问自己，当你的自制、隐藏的加密算法被释放到野外时，它的表现如何！

---