后量子密码

量子计算将破坏现有系统的安全基础

互联网和其他通信系统的功能依赖于安全和有效的加密算法。这些算法允许互联网实体之间进行保密通信和身份验证。如高级加密标准（AES）之类的对称加密算法通过使用通信方之间的共享密钥来提供保密。公钥加密提供用于导出共享密钥的密钥协商算法（例如，Diffie-Hellman），以及用于验证每个实体的身份的数字签名算法（例如，RSA算法）。

RSA和Diffie-Hellman的安全性基于计算意义上的困难问题，例如大整数因子分解问题和离散对数问题。使用传统计算机和经典算法，这些困难问题难以解决。即使考虑到摩尔定律，人们仍然认为，除非在分解算法方面取得非常显着的进步，否则RSA，Diffie-Hellman和其他此类算法都是长期安全的。

1994年发明的Shor算法改变了这一点。这是一种求解大整数因子分解的算法，其关键步骤只能在量子计算机上运行。如果可以构建足够大规模的量子计算机来运行Shor算法，则可以非常有效地分解大整数，进而使得RSA和Diffie-Hellman之类的相关算法被彻底攻破。这对互联网安全会造成巨大的影响。据估计，如果某些关键技术难题得以解决，则可以用一个具有二千万量子比特（qubit）的量子计算机来彻底破解2048比特的RSA算法[1]。不过目前实验性质的量子计算机仅包含大约50个量子比特。

由于量子计算机研发过程的不确定性，目前尚不能确认实用的量子计算机什么时候能够成为现实。衡量发展进程的一个里程碑是量子霸权的概念：在这个预想的时间节点，量子计算机首次能够在实践中解决传统计算机无法解决的任务。在数十亿美元研究资金的支持下，工业界现在预测量子霸权可以在未来几年内实现[2]。虽然这并不意味着我们的公钥算法即将面临被破坏的危险，但这意味着行业需要开始准备过渡到量子安全算法（后量子密码），从而避免受到Shor算法和其他量子算法的影响。

我们注意到，即使面对量子计算机的强大能力，对称密钥算法仍然是安全的。据估计，量子计算可以将对称密钥的有效长度减半，这意味着像AES-256这样的算法将保持足够的安全性，短期内无需替换。

引入后量子密码以增强安全性

华为计划尽早将量子安全算法引入其产品中，以确保其产品的长期安全性。最重要的一点是为密钥协议引入安全的后量子算法，这是因为存在前向攻击的可能：攻击者可以把当前密钥协商过程的消息存储下来，等到量子计算机成为现实时，再对历史数据进行恢复。这意味着如果继续使用传统的密钥协商算法，在实现量子计算机之前进行的会话可能不满足前向安全性。

华为正在关注后量子算法的各种标准化活动。当前，一个著名的标准化工作正在进行中：在全球学术界的帮助下，分析大量的候选算法以制定一套标准。预计此标准化工作将于2024年完成。

我们计划在次标准化工作结束之前将一些候选算法试验性地引入我们的产品中，以应对对密钥协商过程的囤积攻击。考虑到候选算法的属性，可以将其分为六类。每个类别对算法的安全性的实现特性和成熟度都存在一定的差异。这六个类别是：

• 基于哈希的算法。此类算法只能用于签名。其中一个限制是每个私钥仅可用于生成有限数量的签名，需要继续研究如何优化和使用。基于哈希的算法的优点是，其安全性比较容易理解和分析。
• 基于多变量的算法。这类算法只能用于签名。虽然这类算法可以产生尺寸非常小的签名，但许多多变量算法的安全性还不是很清楚，有待进一步深入研究。
• 基于格的算法，例如NTRU签名方案。基于格的算法可用于签名和密钥交换算法。普通格的特征并不是最优的，虽然引入代数结构可以减小密钥大小，但可能影响安全性。
• 基于超奇异同源的算法，提供了基于特殊椭圆曲线代数结构上的后量子密钥交换算法。这是一类算法的特点是速度较慢但密钥较短。
• 基于编码的算法，如McEliece加密算法，在安全性方面比较保守。通过精心选择的参数，该算法的安全性自1978年发明以来并未受到威胁。它的特点是公钥尺寸较大，但适用于长期密钥很少改变的密钥交换场景。其他类型的基于编码的算法，例如基于低密度奇偶校验码的算法，可以在提供高安全性的同时显着减小公钥的大小。
• 其它类型的算法，如Rainbow签名算法，基于零知识证明和轻量级分组密码算法。

后量子迁移

在如何处理密钥交换消息的前向安全问题方面有几种选择。首先，可以从当前的标准化活动中选取一种当前呼声较高的候选密钥协商算法，立即取代Diffie-Hellman，但这会带来安全风险：随着学术界的进一步研究，该算法有可能会在未来几年受到攻击。其次，可以选择推迟几年，直到标准化活动结束再引入后量子算法。在这种情况下，密钥交换消息的前向安全问题仍然存在。

第三种选择是实现混合方案，该方案同时基于Diffie-Hellman和某个候选的后量子密钥协商算法得到两个不同会话密钥，然后将两者混合推导出最终的会话密钥。这样可以显著降低潜在的风险。因为如果最终量子计算机成为现实：首先，它不可能直接攻破后量子部分的密钥；另一方面，如果在过渡期间发现后量子算法的安全问题，则Diffie-Hellman算法可以提供一层额外的保护。

理想情况下，后量子安全的混合密钥交换算法应直接实现到目前广泛使用的协议中，如TLS或IPsec。然而，与传统算法相比，后量子算法在实现难度和参数特性（例如，密钥尺寸很大或带宽消耗较高）方面比较复杂。实际的实现方案需要仔细研究协议和优化算法，降低使用混合密钥交换方案对各方面性能指标的影响。