后量子密码｜趋势科技：向抗量子密码学迁移——比较抗量子算法方案

来源｜trendmicro.

图源｜Pixabay

编辑｜公钥密码开放社区

有错误的学习（LWE）基于将秘密信息表示为一组方程的想法，然后故意引入错误以隐瞒隐藏信息的真实值。对此有几种变体，例如环状有错误学习（RLWE）和模态有错误学习（MLWE）。

图1：在带错误学习中，输入值被噪声干扰，以生成输出值

我们可以将其视为一个函数，该函数接受输入值并输出结果。真实的函数由红线表示，是秘密的，我们添加噪声（用橙色表示）来生成输出值。对于更复杂的方程，错误使得准确恢复真实函数变得困难。

这个方案在一个数学网格（格子）中隐藏信息，这使得在没有正确钥匙的情况下极其难以解锁。图2展示了一个二维格子，其中向量b1和b2是基向量。格子问题需要通过组合这两个基向量来寻找最短的向量，以到达原点。

虽然在二维空间中可以解决，但已经相当困难，问题在更高维度中变得越来越复杂。这个问题被称为NP难题，这是一个术语，指的是一类没有已知高效算法能够在实际时间内解决的问题，但如果提供了解决方案（在我们讨论的情况下，一个作为钥匙的基向量），则可以在多项式时间内验证该问题。

图2.：晶格问题需要通过结合两个基向量来寻找最短向量，以到达原点向量

基于哈希的密码学是指基于哈希函数安全性的密码原语构造的通用术语。目前使用的所有密码哈希在使用足够大的密钥时都被认为是抗量子攻击的。通常，增加密钥大小就足够了，但密钥越大，哈希值对输入数据的唯一性就越强，最小的变化都会产生显著不同的哈希值。

因此，我们可以使用基于哈希的密码学来构造数字签名方案，例如Merkle签名方案、零知识证明（ZKP）和计算完整性证明（CIP）。Merkle和Lamport在1970年代开发的开创性工作已经探索了这一点，但这个想法和概念在寻找后量子密码学的过程中被“重新发现”并进一步完善。

基于编码的加密方法源于在嘈杂信道中纠正传输错误。我们不是在一个无意的嘈杂信道中，而是故意在包含隐藏纠错码的密文流中引入随机噪声。在不知道纠错方案的情况下，解码消息是非常困难的，这被称为解码问题。虽然基于编码的方法自1978年罗伯特·麦克艾利斯的研究以来就已经存在，但这个问题也被认为是NP困难的。目前也没有已知的量子解决方案可以在实际时间内解决这个问题。

椭圆曲线加密（ECC）是一种加密类型，它利用椭圆曲线上的点来加密消息和保护数据。ECC本身也会被量子计算破解，通过连接两个不同但相关的椭圆曲线，或者称为同态曲线。

图3：基于同态的密码学需要寻找两个椭圆曲线之间保持其数学性质的有理映射，以便这两条曲线能够安全地进行通信和共享信息

基于同态的加密是一种椭圆曲线密码学（ECC）的变体，它利用了这一概念；它依赖于能很容易构造一组同态和椭圆曲线，但给定椭圆曲线后却很难找到这些同态。秘密密钥是从随机选择的同态中派生的，公钥则是从这些同态的目标派生的。这种加密所用的密钥大小与当前密码学中使用的密钥大致相同，因此它成为保护数据的一个有吸引力的选择。

找到用于计算两个已知目标曲线上点的同态，类似于在迪菲-赫尔曼（DH）密钥交换协议中计算值的离散对数。寻找同态的问题与存在已知有效量子计算解决方案的问题之间没有关系，因此被认为是抗量子的。需要注意的是，这种对基于同态加密的描述是为了简洁而进行了简化；进一步的解释需要对椭圆曲线密码学进行更深入和更详细的探讨。

尽管目前尚不存在能够破解现有密码学的大型量子计算机，但我们仍需关注这一领域。

有一种场景下，攻击者可以截获所有连接的互联网流量，包括密钥协商和对称加密的数据流。未来当足够大的量子计算机出现时，攻击者能够从已捕获的互联网流量中找到共享密钥并解密数据流。我们称这种对前向保密性的攻击为“收割”攻击。因此，需要量子抗性密钥协商和数字签名方案。

美国国家标准与技术研究院（NIST）于2017年启动了后量子密码学的遴选过程，最初有近70个候选者，经过三轮评估后，到2022年缩减至15个候选者。其中8个仍在评估中，7个已计划标准化。

同样重要的是，2021年互联网工程任务组（IETF）讨论了在TLS 1.2中采用混合后量子密码学的方法，以减轻单一算法中未知弱点的风险。这一想法得到了德国联邦信息安全办公室（BSI）和法国国家信息系统安全局（ANSSI）的支持。

密钥交换密码学也称为密钥协商方法或密钥封装机制（KEM），用于在两方之间协商对称加密的密钥。我们目前使用的算法包括Diffie-Hellman和RSA。

在NIST后量子密码学标准化中的当前KEM入围者包括CRYSTALS-Kyber、NTRU和Saber（基于晶格），以及Classic McEliece（基于代码）。但在第三轮中，只有CRYSTALS-Kyber被选中标准化。

CRYSTALS-Kyber现被视为主要算法，已获得FIPS编号203。它是一种基于晶格的方案，使用LWE模块生成密钥。尽管NIST提交的方案基于2018年的论文，但其表现良好，并且其公钥大小相对较小，带宽要求较低。Kyber在软件实现中具有较快的密钥生成、封装和解封能力，适用于FPGA。尽管Yilei Chen提出了在量子计算机上解决晶格问题的算法，但Kyber结合了LWE以增强安全性，尽管这种组合仍是密码学中的新领域。

Classic McEliece于2017年提出，基于1978年的原始算法，与许多基于LWE和晶格的方案不同，仍在考虑标准化。

基于同源的SIKE也进入下一轮，但因发现攻击而被撤回。目前没有其他基于同源的方案参与，但研究仍在继续。

基于晶格的FrodoKEM和NTRU Prime被指定为替代方案，但不会被标准化。尽管FrodoKEM已退出NIST-PQC竞赛，德国BSI和法国ANSSI仍认为其是一个好的候选者，并有呼吁在NIST第四轮中重新考虑。

数字签名方案在NIST标准化过程中被称为SIG，CRYSTALS-Dilithium、FALCON和SPHINCS+已被选中标准化。

CRYSTALS-Dilithium是基于Fiat-Shamir范式的晶格方案，使用短密钥和签名，便于在各种CPU上实现，被NIST强烈推荐。

FALCON也是基于晶格的方案，基于“哈希和签名”范式，尽管需要浮点运算，结构复杂，但在验证签名时速度快，被选为低带宽高安全需求的替代方案。

SPHINCS+基于多种哈希方案组合，生成短公钥，但签名速度慢且长，存在参数攻击问题，被NIST选中作为替代方案，需谨慎使用。

互联网工程任务组（IETF）提出了自己的SIG算法：XMSS（RFC 8391）和LMS（RFC 8708），但预计这些算法会成为小众选择，NIST和FIPS标准将占主导地位。

KEM的替代方案是量子密钥交换（QKE），通过粒子纠缠建立共享密钥，如果被监听将无效。此算法被称为BB84，需专用硬件和光纤传输介质。

2023年，Toshiba、BT Group和汇丰银行在伦敦测试了使用QKE的安全连接，未来该技术可能用于大型计算中心之间的连接。

Open Quantum Safe（OQS）项目将所有决赛入围者和一些替代候选者添加到liboqs，一个开源的量子安全密码算法C库。支持多种CPU，但较小的IoT处理器支持有限。

Open Quantum Safe还分叉了OpenSSL和SSH项目，添加了相应的库以进行兼容性和性能测试，但liboqs尚不推荐用于生产环境。

许多商业密码学供应商已开始实施PQC，具体信息可在PKI Consortium网站查看。Cloudflare和AWS声称已实施决赛算法，Signal和Apple也开始使用Kyber。

过去十年，加密连接已从可选变为几乎无处不在。更改加密算法的任务变得更加复杂。

随着量子计算机的威胁增加，确保前向保密性变得至关重要。今天，一些产品已开始集成PQC算法。Google最近在Chromium 116版中集成了CRYSTALS-Kyber，其他基于Chromium的浏览器也将支持PQC。一些云提供商如Google、Amazon和Cloudflare也已在服务器端启用相同算法，确保未来的前向保密性。

图4.：Chrome升级前Cloudflare的PQC协商测试页面

图5：Cloudflare PQC协商测试页面在升级并手动激活Kyber算法后

供应商将使用初步库或其自身的实现为我们进行许多PQC迁移；然而，企业应了解其暴露面和威胁模型，以确保一些遗留应用程序不会阻碍升级。一个成熟的组织应有一个升级其密码学的计划，无论出于何种原因。

最终，这是一个业务战略决策，取决于公司的威胁模型。如果前向保密性对组织至关重要，则早期采用PQC至关重要。如果不是，企业可以选择等待供应商实施PQC并逐步在其系统中推出。涉及业务领导的知情决策将确保其成功。

升级到新算法的第一步是识别密码算法的使用情况。为了升级到后量子密码学，首先需要查看现有的公钥密码学。我们需要知道哪些自管理的密码学被使用，由谁，在哪里，及其用于哪些资产。还必须确定被加密资产的相应价值。

接下来，我们需要知道系统如何相互通信：如果服务器支持PQC但客户端不支持，则企业无法强制执行PQC。尽管最大的云提供商在积极行动，但某些服务可能不会得到更新，这需要确定。

我们知道所有PQC算法都有更大的密钥尺寸，并且与现有算法相比需要更多的CPU和内存容量来计算。性能影响是需要建立大量连接的服务器上的一个问题。服务器硬件需要扩展，或者可能需要加密协处理器，如果这些存在于PQC中。一些云提供商将TLS连接卸载到专门的服务器，这也可以缓解问题。

企业需要了解各自业务的风险。需要考虑的一些问题包括：

• 某些应用程序是否有超出量子计算机预期出现时间的前向保密性要求？

  
  

• 是否需要重新签署任何文件或代码，系统能否理解PQC签名？

  
  

• 这些评估应汇总在报告中，作为帮助确定进一步优先行动的参考。

在执行之前，需要测试升级计划，以识别和协商每个库将使用的算法，并启用和监控日志，以确保在预期时使用PQC算法。对连接进行压力测试，以查看更大的密钥和较低的性能是否会产生负面影响也是一个重要测试。

NIST最有可能在2024年或2025年标准化PQC算法。德国BSI、法国ANSSI和日本CRYPTREC可能会采用相同的指南。在此之前，我们不期望任何PQC算法被集成到主流密码库中，但现在仍是开始计划后量子密码学的好时机。

我们不能确定何时会出现足够大的量子计算机，甚至不确定在未来几代人中这一目标是否可实现。虽然这听起来很遥远，但在企业中更改密码学并非易事，应该尽早着手。此外，如果我们更好地理解我们的密码学态势，特别是考虑到如此多的安全依赖于良好的密码学，益处已经显而易见。