[终端安全]-7 后量子密码算法

本文参考资料来源：NSA Releases Future Quantum-Resistant (QR) Algorithm Requirements for National Security Systems > National Security Agency/Central Security Service > Article

Commercial National Security Algorithm Suite 2.0” (CNSA 2.0) Cybersecurity Advisory (CSA)

（第6文终端安全之应用安全，稍后时日补上）

1 CNSA2.0

CISA、NIST 和 NSA 敦促各个行业安全应用开始为实施后量子密码学做准备。NSA发布了《商业国家安全算法套件 2.0》(CNSA 2.0) 未来抗量子 (QR) 算法要求，如下所示：

备注：

Crystal-Kyber算法标准，可参照NIST.FIPS.203.ipd.pdf(draft)

Crystal-Dilithium算法标准，可参照NIST.FIPS.204.ipd.pdf(draft)

附：以下为CNSA1.0发布算法需求

2 Crystal-Kyber

Crystal-Kyber 是一种基于格的加密方案用于密钥封装机制（KEM），可高效安全且适应未来量子计算攻击。

1）数学原理

Crystal-Kyber 基于Learning with Errors（LWE）和Ring-LWE问题，这些问题在量子计算机上被认为是难解的。Ring-LWE 难题，对于环 R =Z[x]/(x^n + 1) 和模数q，给定一个秘密向量  s∈R_q 和多个采样  (a_i, b_i = a_i s + e_i)模q，其中 a_i 是从 R_q 中均匀分布的随机元素，e_i是从某个误差分布中采样的错误向量，目标是从 (a_i, b_i) 中恢复 s 。

1.1）公钥生成：pk = a s + e mod q

1.2）加密过程：c_1 = a r + e_1 mod q；c_2 = pk r + e_2 + m⌊q/2⌋mod q

1.3）解密过程：m' = c_2 - s c_1 mod q；m = Decode(m')

2）算法步骤

2.1）参数生成：模数 q 、环的度 n 和误差分布χ。

   

2.2）密钥生成：

   - 生成一个随机多项式 a ∈ R_q 。

   - 选择秘密多项式 s, e 从χ中采样。

   - 计算公钥 pk = a s + e 。

   - 私钥为 sk = s 。

2.3）加密：

   - 选择随机多项式 r, e_1, e_2 从χ中采样。

   - 计算密文 c_1 = a r + e_1 和 c_2 = pk r + e_2 + m⋅ ⌊q/2⌋，其中m 是明文消息。

2.4）解密：

   - 计算 m' = c_2 - s c_1 。

   - 解码 m' 得到明文消息m 。

3）硬件实现

多项式运算单元：实现多项式乘法、加法、减法和模运算；使用Number Theoretic Transform (NTT)加速多项式乘法。

随机数生成器：用于生成密钥和随机噪声。

模运算模块：实现模q运算，用于多项式系数的约束。

存储单元：用于存储密钥、多项式系数和中间运算结果。

3 Crystal-Dilithium

Crystal-Dilithium 是一种基于格的数字签名方案，它的设计目标是提供高效和安全的签名和验证过程，适应未来量子计算攻击。

1）数学原理

Crystal-Dilithium 基于Module Learning with Errors（Module-LWE）和Module Short Integer Solution（Module-SIS）难题。对于环R =Z[x]/(x^n+1)和模数q，Module-LWE 问题定义如下：给定一个秘密矩阵S∈Rqk×l和多个采样A_i, B_i = A_i S + E_i模q，其中A_i是从 Rqk×l中均匀分布的随机矩阵，E_i 是从某个误差分布中采样的错误矩阵，目标是从(A_i, B_i)中恢复S。

1.1）公钥生成：pk = A S + E mod q

1.2）签名过程：W = A y mod q； c = H(W, μ)； z = y + c S mod q

1.3）验证过程：W' = A z - c pk mod q；验证 c = H(W', μ)

2）算法步骤

2.1）参数生成：

   - 模数 q 、环的度 n 和误差分布χ。

   - 选择参数k 和l 。

   

2.2）密钥生成：

   - 生成随机矩阵A ∈Rqk×l。

   - 选择秘密矩阵 S, E 从χ 中采样。

   - 计算公钥 pk = A S + E 。

   - 私钥为 sk = S 。

2.3）签名：

   - 选择随机矩阵 y 从某个分布中采样。

   - 计算 W = A y 并计算 c = H(W, μ)，其中 H是哈希函数，μ是消息。

   - 计算签名 z = y + c S。如果 z 的系数太大，则重新生成 y 并重复。

   - 最终签名为 (μ, z, c) 。

2.4）验签：

   - 计算 W' = A z - c pk 。

   - 检查 c = H(W', μ) 是否成立。如果成立验证通过；否则验证失败。

3）硬件实现

多项式运算单元：实现多项式乘法、加法、减法和模运算；使用NTT加速多项式乘法。

哈希单元：实现SHA-3和Keccak函数，用于消息哈希和挑战生成。

随机数生成器：用于生成随机挑战和密钥。

存储单元：用于存储密钥、多项式系数、哈希值和中间运算结果。

4 基于哈希的数字签名算法

XMSS（eXtended Merkle Signature Scheme）和 LMS（Leighton-Micali Signature）是两种基于Merkle树的哈希函数数字签名方案，被NSA推荐用于软件和固件签名。

备注：参照[终端安全]-1 总体介绍 ，[终端安全]-5 移动终端之操作系统安全，终端设备的安全启动非常重要。XMSS和LMS作为后量子密码算法，用于在软件和固件中实现安全的数字签名和认证功能以防止恶意软件或未经授权对固件的修改，同时可应对未来可能出现的量子计算攻击。

1）XMSS

XMSS使用一棵 Merkle 树来组织多个一次性签名（WOTS+，Winternitz One-Time Signatures），每个叶子节点对应一个一次性签名的公钥，每次签名一个消息后对应的 OTS 就不能再使用；XMSS基于哈希函数的抗碰撞性和 Merkle 树的结构安全性高，适用于需要处理大量签名的应用如区块链。

1.1）密钥生成

- 参数选择：选择安全参数，包括哈希函数（通常是SHA-256或者SHA-3等安全的哈希函数）、树的高度、叶子节点哈希链长度（WOTS+ 参数）等；生成一个随机的种子作为生成所有私钥相关信息的起点。

- 生成主私钥和公钥：使用种子和适当的参数，通过哈希函数生成主私钥，通常是一个随机数或特定格式的数据。通过主私钥使用同样的哈希函数生成对应的主公钥。

- 生成签名树：根据选择的树高度生成Merkle树结构，每个叶子节点存储一个哈希链，用于后续签名生成过程中的一次性使用。

1.2）签名生成

- 消息哈希：使用选择的哈希函数对消息进行哈希，得到消息的摘要。

- 生成签名链：根据消息的哈希值确定要使用的Merkle树中的叶子节点索引，从选定的叶子节点开始使用哈希函数链生成一系列的哈希值，形成签名链并更新对应的叶子节点的哈希值、Merkle树的内部节点，确保树的完整性。

1.3）签名验证

- 消息哈希：使用同样的哈希函数对接收到的消息进行哈希得到摘要。

- 验证签名：根据签名中的一部分信息（通常是与签名相关的部分）确定要验证的叶子节点索引，使用公钥和相应的Merkle树中的哈希值，验证从选定的叶子节点到根节点的哈希值链是否与签名中的哈希链一致。如果验证成功说明签名有效，否则签名无效。

2）LMS

LMS使用HORS（Hash to Obtain Random Subsets）来生成签名，适用于嵌入式系统和IoT设备。

2.1）密钥生成

- 参数选择：选择安全参数，包括哈希函数（通常是SHA-256或者SHA-3等安全的哈希函数）、签名树的高度和哈希函数链长度；生成一个随机的种子作为生成所有私钥相关信息的起点。

- 生成主私钥和主公钥：使用种子和适当的参数通过哈希函数生成主私钥；通过主私钥使用同样的哈希函数生成对应的主公钥。

- 生成认证路径：根据签名树的高度生成一系列的认证路径，认证路径是从叶子节点到根节点的哈希值链，用于验证签名。

2.2）签名生成

- 消息哈希：使用选择的哈希函数对消息进行哈希得到摘要。

- 计算签名：根据消息哈希值的一部分（例如最低位的一些比特）选择要使用的签名树的叶子节点，使用哈希函数链生成一系列的哈希值，直到生成根节点的哈希值。结合消息摘要生成最终的数字签名。

2.3）签名验证

- 消息哈希：使用同样的哈希函数对接收到的消息进行哈希，得到消息的摘要。

- 验证签名：依据签名中的一部分信息（通常是与签名相关的部分）选择相应的签名树节点，使用公钥和事先生成的认证路径，验证从选定的叶子节点到根节点的哈希值链是否与签名中的哈希链一致。如果验证成功说明签名有效，否则签名无效。