后量子密码学与抗量子算法 (PQC)

摘要： 量子计算的发展正从理论走向工程现实，基于大数分解和离散对数难题的传统公钥密码（如 RSA、ECC）在 Shor 算法下将失去安全性。本文首先从量子威胁与“先获取，后解密”（Harvest Now, Decrypt Later）风险出发，简要介绍后量子密码学（PQC）的基本概念与威胁模型；随后结合 NIST 标准化进程，系统梳理格基、编码基、哈希基、多变量和同源基等主要算法家族及代表算法；在此基础上，从性能、侧信道与故障注入攻击、硬件加速与实现安全等角度，分析工程落地中的关键挑战；最后对全球迁移时间线、密码敏捷性（cryptographic agility）及供应链依赖进行讨论，并给出未来几年中组织在架构与工程层面的迁移建议。

第一部分：量子威胁与 PQC 基础

1.1 量子计算对现有密码体系的威胁

目前广泛部署的公钥加密体系（如 RSA、椭圆曲线密码学 ECC）主要依赖以下难题的“经典计算困难性”来保证安全：

• 大数分解问题：给定 \(N = pq\)，从 \(N\) 中恢复大素数 \(p, q\) 在经典计算机上被认为在多项式时间内不可行；
• 离散对数问题：在有限域或椭圆曲线上，从公开的 \(g\) 和 \(g^x\) 推出指数 \(x\) 也被认为是困难的。

量子计算机在这类问题上具有根本性的优势。特别是 Shor 算法 证明：在一台具有足够容错能力的量子计算机上，可以在多项式时间内高效分解大整数和计算离散对数，从而从数学上瓦解 RSA/ECC 这一代公钥密码体系的安全基础。

更现实的威胁来自“先获取，后解密”（Harvest Now, Decrypt Later）模型：攻击者可以在今天大规模地窃取并存储使用现有密码保护的长期敏感数据（如医疗记录、金融交易、政府情报和知识产权），在未来量子计算机成熟之后再集中解密。这意味着，对于那些对保密期限要求超过 5–10 年的数据而言，即便量子计算机暂时不可用，今天仍然已经处在风险敞口之中 ¹²。

同时，量子算法对称加密的影响也不可忽视。Grover 算法可以在理论上以 \(O(\sqrt{N})\) 的复杂度加速穷举搜索，因此通常建议将对称密钥长度加倍（例如从 AES-128 升级到 AES-256），以在量子攻击模型下维持原有的安全强度 ³。

1.2 什么是后量子密码学 (PQC)？

后量子密码学（Post-Quantum Cryptography, PQC），又称抗量子密码学（quantum-resistant cryptography），指的是一类即使在拥有强大算力的量子计算机面前仍然保持安全的密码算法。与依赖大数分解或离散对数难题的传统公钥方案不同，PQC 基于若干目前被认为对经典和量子计算机都困难的数学问题，例如：

• 高维格上的最短向量问题（SVP）、最近向量问题（CVP）；
• 一般线性码的解码问题；
• 有限域上多元二次方程组的求解；
• 基于抗碰撞哈希函数的构造等。

PQC 的目标不是“利用量子力学”进行加密（那是量子密钥分发 QKD 的范畴），而是设计 在量子攻击者模型下仍然安全、同时可以在经典计算环境中部署 的算法。NIST 的标准化工作便是围绕这一路线展开的 ⁴⁵。

1.3 Shor 算法核心思想

Shor 算法的核心思想可以概括为三步：

1. 把大数分解问题转化为一个关于指数函数 \(f(x) = a^x \pmod{N}\) 的周期查找问题；
2. 利用量子并行和量子傅里叶变换（QFT）高效寻找该周期 \(r\)；
3. 在找到 \(r\) 后，通过数论恒等式从 \(a^{r/2} \pm 1\) 与 \(N\) 的最大公约数中恢复因子。

在经典世界中，直接寻找 \(f(x)\) 的周期需要指数时间，而在量子世界中，可以通过构造叠加态、对指数函数进行相位编码，再利用 QFT 把周期信息从相位“读出来”，从而在多项式时间内完成。形式化的过程如下：

1. 随机选择 \(a\)，\(1 < a < N\)，若 \(\gcd(a, N) \neq 1\) 则已直接得到因子；
2. 构造 \(f(x) = a^x \pmod{N}\) 并在量子寄存器中对所有 \(x\) 形成叠加态 \(\sum_x \lvert x \rangle\)；
3. 计算 \(f(x)\) 并进行 QFT；
4. 通过测量获得与周期 \(r\) 相关的结果，并用经典算法求得 \(r\)；
5. 若 \(r\) 为偶数且 \(a^{r/2} \not\equiv -1 \pmod{N}\)，则因子可由 \[ p = \gcd\bigl(a^{r/2} - 1, N\bigr), \quad q = \gcd\bigl(a^{r/2} + 1, N\bigr) \] 恢复。

这条“经典降维 + 量子加速 + 经典后处理”的链路，是理解 RSA/ECC 在量子时代为何会失效的关键。

第二部分：PQC 算法家族概览

本部分从算法家族的视角，对 NIST 标准化进程中最核心的几类后量子算法进行梳理。

2.1 格基密码学 (Lattice-based Cryptography)

格基密码学是目前 PQC 中最重要、最成熟的方向，其安全性基于高维格上的困难问题，如短向量问题 (SVP) 和带误差学习问题 (LWE)。

典型代表包括：

• CRYSTALS-Kyber（ML-KEM）：密钥封装机制（KEM），适合在 TLS 等协议中做密钥协商；
• CRYSTALS-Dilithium（ML-DSA）：格基数字签名算法；
• Falcon（FN-DSA）：签名尺寸很小的格基签名算法。

格基算法的一般特点：

• 优点：
  • 在常见安全级别下，计算效率高、吞吐量好；
  • 结构灵活，易于拓展到全同态加密 (FHE)、零知识证明等高级密码原语；
  • 在 NIST 标准中占据主导地位，是业界“默认首选”的算法家族。
• 挑战：
  • 实现上多依赖数论变换 (NTT) 等高性能算子，容易在功耗、时间等维度上泄露信息，即存在侧信道风险；
  • 抵御侧信道攻击 (SCA) 和故障注入攻击 (FI) 的工程实现成本高 ⁶⁷。

2.1.1 Kyber 与 LWE 问题

Kyber 建立在 带误差学习 (Learning With Errors, LWE) 问题之上。可以直观理解为：> 给出很多“被加噪”的线性方程 \(A\mathbf{x} + \mathbf{e} = \mathbf{b}\)，其中噪声向量 \(\mathbf{e}\) 的模很小。已知 \(A\) 与 \(\mathbf{b}\)，在不知道噪声分布细节的前提下，想要精确恢复秘密向量 \(\mathbf{x}\) 被认为是困难的。

Kyber 在实际协议中的工作流程（省略具体维度与模数）大致为：

1. 密钥生成：
   • 选随机公共矩阵 \(A\)；
   • 选小向量 \(\mathbf{s}, \mathbf{e}\) 作为秘密；
   • 计算 \(\mathbf{t} = A\mathbf{s} + \mathbf{e}\)，公钥为 \((A, \mathbf{t})\)，私钥为 \(\mathbf{s}\)。
2. 封装：
   • 对方选随机小向量 \(\mathbf{r}, \mathbf{e}_1, e_2\)；
   • 计算 \[ \mathbf{u} = A^T \mathbf{r} + \mathbf{e}_1, \quad v = \mathbf{t}^T \mathbf{r} + e_2; \]
   • 从 \((\mathbf{r}, \mathbf{e}_1, e_2)\) 派生共享密钥 \(k\)，同时发送密文 \((\mathbf{u}, v)\)。
3. 解封装：
   • 拥有秘密 \(\mathbf{s}\) 的一方计算 \[ v - \mathbf{s}^T \mathbf{u} \approx k \]
   • 利用误差有界性的性质，通过纠错恢复出精确的 \(k\)。

整个过程本质上把“解带误差线性方程组”的困难性变成了“从带噪观测中恢复秘密向量”的问题，在经典与量子环境下都缺乏有效的多项式时间算法。

2.1.2 Dilithium 与 Fiat-Shamir 签名结构

Dilithium 使用基于 Module-LWE/SIS 的格结构，并采用 Fiat-Shamir with Aborts 技术来防止签名过程泄漏秘密向量的大小信息。其签名过程可以高度概括为：

1. 生成随机“掩码”向量 \(\mathbf{y}\)，计算承诺 \(\mathbf{w} = A\mathbf{y}\)；
2. 计算挑战 \(c = H(m, \mathbf{w})\)；
3. 计算响应 \(\mathbf{z} = \mathbf{y} + c\mathbf{s}_1\)，同时检查 \(\mathbf{z}\) 的系数是否过大；
4. 若不满足阈值则“abort”重来，以保证最终公开的 \(\mathbf{z}\) 不会泄漏秘密 \(\mathbf{s}_1\) 的分布信息；
5. 验证方通过 \(\mathbf{w}' = A\mathbf{z} - c\mathbf{t}\) 与 \(c \stackrel{?}{=} H(m, \mathbf{w}')\) 来完成验证。

2.2 编码基密码学 (Code-based Cryptography)

编码基密码学的安全性源于对一般线性码的解码难题——在不知道结构的前提下，从带少量随机错误的码字中恢复原始消息，被认为是 NP-hard 的。

代表算法：

• McEliece、HQC 等。NIST 在第四轮标准化中选择了 HQC 作为额外的 KEM，旨在增强算法多样性 ⁸⁹。

编码基方案的典型特征：

• 优点：历史悠久，自 1978 年 McEliece 方案提出以来，其安全性假设经受了长期检验；
• 缺点：公钥尺寸通常较大，对带宽与存储较为敏感；
• 在资源受限设备上的性能与能效一般不如 Kyber 等格基方案 ¹⁰。

2.3 哈希基密码学 (Hash-based Cryptography)

哈希基签名方案仅依赖于抗碰撞哈希函数的安全假设，是构建“安全备胎”算法的天然候选。在 NIST 标准中，SPHINCS+ (SLH-DSA) 便承担了这一角色 ¹¹¹²。

其核心思路是：

• 利用一次性或少数次签名方案 (如 WOTS+) 作为基础；
• 通过默克尔树 (Merkle Tree) 和超树 (Hypertree) 结构，将大量一次性公钥“聚合”为一个短公钥；
• 签名时，通过提供认证路径来证明某次使用的一次性密钥确实隶属于这棵大树。

这种设计的代价是：签名尺寸大、签名生成较慢。因此在 TLS 这类需要高频握手的场景中，它通常仅作为备选方案 ¹³。

2.4 多变量与同源基密码学 (简述)

• 多变量密码学：基于有限域上解多元二次方程组的困难性。曾涌现出 Rainbow 等方案，但因多次出现严重攻击，目前在标准化进程中处于边缘地位。
• 同源基密码学：基于椭圆曲线之间的同源 (isogeny) 难题。典型例子 SIKE 曾因其极小的密钥尺寸而备受关注，但在 2022 年被高效攻击攻破，使得这一方向目前更多地回归学术研究探索，而非工程部署 ¹⁴¹⁵。

第三部分：NIST 标准化进程与最新进展

3.1 第一批 FIPS 标准（2024 年 8 月）

NIST 从 2016 年起启动后量子密码标准化项目，历经公开征集、三轮评审与攻防分析，并在 2024 年 8 月 13 日正式发布了首批三个联邦信息处理标准（FIPS） ¹⁶¹⁷：

• FIPS 203 – ML-KEM（CRYSTALS-Kyber）：
  • 用途：密钥封装机制（KEM），适用于 TLS 等密钥协商协议；
  • 数学基础：Module-LWE；
  • 特点：性能优异，密钥与密文尺寸在可接受区间，是目前工业界最广泛采用的 PQC KEM。
• FIPS 204 – ML-DSA（CRYSTALS-Dilithium）：
  • 用途：数字签名；
  • 数学基础：格上的 Module-LWE / Module-SIS；
  • 特点：实现相对简单、鲁棒性好，被推荐为“默认签名方案”。
• FIPS 205 – SLH-DSA（SPHINCS+）：
  • 用途：数字签名（备选）；
  • 数学基础：基于抗碰撞哈希函数；
  • 特点：签名尺寸大、性能较慢，但安全假设极为保守，是重要的“第二信源”。

3.2 第四轮选拔：HQC 与算法多样性策略

为了降低单一数学基础被攻破的系统性风险，NIST 在第三轮评审后继续开展了第四轮 KEM 评估，重点考察非格基的候选方案。2025 年 3 月，NIST 宣布选择编码基算法 HQC 作为额外的 KEM 进行标准化 ¹⁸¹⁹。

至此，NIST 的整体 PQC 算法组合策略可以概括为：

• KEM：以格基的 Kyber 为主，辅以编码基的 HQC 作为备份；
• 签名：以格基的 Dilithium 为主，辅以哈希基的 SPHINCS+ 作为备份，并保留格基的 Falcon 用于小签名场景 ²⁰；
• 核心思想：保持数学基础的多样性，形成“格基 + 编码基 + 哈希基”的三角支撑格局，避免单点故障 ²¹。

3.3 新增签名算法与后续工作

2024 年 10 月，NIST 宣布 14 个“新增数字签名算法”候选进入第二轮评估 ²²²³，涵盖多变量、基于承诺与零知识证明等多种思路。这些工作不会立即取代 ML-DSA/SLH-DSA，而是更多地填补尺寸、性能和特殊应用场景上的空白，为长远的算法冗余提供备选项。

第四部分：性能、实现与工程安全挑战

4.1 性能维度对比

在工程实践中，PQC 算法的性能主要体现在：

• 密钥/公钥/密文/签名的尺寸（字节数）；
• 密钥生成、封装/解封装、签名/验证的耗时与吞吐量；
• 在资源受限设备上（嵌入式、物联网）的能耗与占用。

综合现有评测结果 ²⁴²⁵，可以粗略给出如下对比表：

在 TLS 1.3 集成测试中，Dilithium/Falcon 的握手延迟通常只比 RSA-2048 高出 7–11% 左右，而 SPHINCS+ 可能慢两个数量级 ²⁶。在嵌入式设备上，基于 LWE 的 Kyber 在速度与能效方面普遍优于 HQC/BIKE 等编码基方案 ²⁷。

4.2 侧信道攻击与故障注入攻击

PQC 算法在数学上的安全性，并不等同于其在物理实现中的安全性。恰恰相反，为了追求高性能而采用的高度优化的计算结构（如 NTT），往往会在功耗、时序或电磁辐射上暴露出可被利用的微小差异。

近期研究表明 ²⁸²⁹³⁰：

• 对 Kyber、Dilithium 的高性能实现进行差分功耗分析 (DPA) 和模板攻击，可以有效恢复秘密多项式或向量；
• 对 Dilithium 等采用“abort 重试”机制的签名算法，通过故障注入攻击 (如在特定循环中跳过检查) 可以在收集极少量错误签名后，快速恢复私钥；
• 一些号称“常数时间”的实现，可能因编译器优化或 CPU 微架构的动态行为，实际上仍存在可被利用的时序泄漏。

因此，PQC 部署的重心正在从“选择算法”转向“安全实现”：

• 需要严格的常数时间编码实践；
• 需要综合运用掩码 (masking)、随机化 (shuffling) 等多种手段来对抗功耗、电磁和时序等多维度的侧信道攻击；
• 最终需要在 HSM/TPM 等硬件安全模块中引入专门的 PQC 侧信道对策，以建立可信的硬件安全根 ³¹³²。

4.3 硬件加速与可信根

从长远看，后量子安全将深度依赖硬件提供的信任基础：

• 利用硬件中的 TRNG（真随机数发生器）生成高质量随机数；
• 利用 HSM/TPM 实现密钥的安全存储与操作隔离；
• 在 FPGA/ASIC 中实现高吞吐、低能耗的 PQC 加速，同时在硬件层面实现侧信道缓解 ³³³⁴³⁵。

NIST 的加密算法验证计划（CAVP）已开始将 ML-KEM、ML-DSA 等纳入 FIPS 140-3 模块验证范围 ³⁶，这意味着未来通过合规审计的“安全产品”，不仅要“支持 PQC 算法”，还要在硬件层面满足一整套抗侧信道和可靠性要求。

第五部分：全球迁移与密码敏捷性

5.1 迁移时间线与政策驱动

各国政府和大型科技公司已给出了相对明确的时间表 ^3738394041：

• 多数政府机构以 2035 年前完成全面 PQC 迁移 为共识目标；
• 若考虑数据保密需求（例如 5–10 年）和 CRQC 可能在 2030 年前后出现的风险，许多指南建议 2025 年左右就要完成关键数据路径的量子加固 ⁴²⁴³；
• Microsoft 等大型厂商将自身目标设定为 比政府路线图提前约两年，以适应云平台对全球客户的合规要求 ⁴⁴⁴⁵。

5.2 密码敏捷性与混合部署模式

后量子迁移并非一次性的“算法替换”工程，而是要构建一套 能够持续演进的密码学基础设施，其核心是 密码敏捷性 (Cryptographic Agility)。这意味着：

• 协议层面支持在不修改业务逻辑的前提下，动态、安全地协商和切换算法套件；
• 服务与 API 提供“算法抽象层”，而非将具体算法名称硬编码在业务代码中；
• 能够通过策略快速禁用或启用某些算法，以响应新出现的漏洞或合规要求。

在当前过渡阶段，业界最普遍采纳的策略是 混合部署模式 (Hybrid)：

• 在 TLS 1.3 等协议中使用类似 X25519MLKEM768 的混合密钥交换组，将经典密钥交换 (如 X25519) 与 PQC KEM (如 ML-KEM) 的结果组合在一起，共同生成会话密钥 ⁴⁶⁴⁷；
• 这种模式确保了：即使未来 PQC 算法或经典算法中某一个被攻破，通信仍然可以依赖另一方的安全性；
• 协议协商过程需要被谨慎设计，以防止攻击者通过降级攻击 (Downgrade Attack) 强迫通信双方仅使用不安全的传统算法 ⁴⁸。

5.3 供应链与第三方依赖

迁移的难点之一在于：

你的系统是否真正“量子安全”，取决于你依赖的所有库、平台和供应商是否也完成了迁移。

实践建议包括 ⁴⁹⁵⁰⁵¹：

• 把 PQC 要求写入采购与合同条款，要求合作伙伴提供 PQC 路线图；
• 定期审计第三方软件物料清单（SBOM），识别仍在使用 RSA/ECC 的组件；
• 对关键基础设施（金融、通信、能源等）联合推进跨组织的迁移演练。

第六部分：未来展望与实践建议

6.1 高级密码原语与未来方向

格基密码学不仅为 KEM 与签名提供了坚实基础，也为以下前沿方向奠定了后量子安全的基石：

• 全同态加密 (FHE)：允许在密文上直接进行计算，其安全性同样可以基于 LWE 等格难题 ⁵²；
• 零知识证明 (ZKPs)：后量子安全的 ZKP 方案，目前多采用格基与哈希基构造，是零信任架构、隐私计算和区块链等领域的重要安全组件 ⁵³⁵⁴；
• 与其他技术的融合：PQC 正在逐步融入安全多方计算、区块链和隐私计算等新兴技术栈的密钥协商与身份认证层 ⁵⁵⁵⁶。

同源基、多变量等“非主流”家族，虽然在当前标准化浪潮中处于边缘，但从长期看，它们仍可能在某些细分场景或作为防御格基突破的“第二梯队”中发挥其独特的价值 ⁵⁷⁵⁸。

6.2 对工程团队的实践建议

结合上文分析，面向实际的工程与架构落地，可以概括为以下几点建议：

1. 立即启动密码资产清查：梳理系统中使用密码的所有位置（协议、库、硬件、安全模块、第三方依赖等），并标记出保护长期敏感数据的关键路径 ⁵⁹⁶⁰；
2. 优先升级对称加密与密钥管理：尽快将对称算法统一升级到 AES-256 级别，并重新审视密钥的生命周期管理流程 ⁶¹⁶²；
3. 在核心链路中试点混合 KEM：在 TLS/VPN/内部微服务通信等关键链路上，分阶段引入 ML-KEM 与经典密钥交换的混合方案；
4. 评估并引入支持 PQC 的硬件安全模块：特别是在金融、政务和云平台等高安全要求的场景中，应将密钥操作迁移到通过 FIPS 140-3 验证、并内建侧信道缓解措施的安全硬件 (HSM/TPM) 中 ⁶³⁶⁴；
5. 构建密码敏捷性平台：从架构层面将算法选择与业务逻辑解耦，避免硬编码；
6. 建立供应链协同机制：定期评估供应商的 PQC 准备情况，并将 PQC 迁移要求纳入整体的安全与合规路线图 ⁶⁵⁶⁶⁶⁷。

结语

后量子密码学已经从理论研究进入了标准制定与大规模部署的实战阶段。以 Kyber/Dilithium/SPHINCS+ 为代表的第一批标准算法，标志着“量子安全公共基础设施”的初步成型；而 HQC 等方案的加入，则体现了对长期系统性风险的前瞻性防御。

当前，真正的挑战已从“我们有什么算法可用？”转变为“我们如何安全、可验证地实现和运维这些算法？”，以及“如何在复杂的全球供应链和监管环境下完成协同迁移？”。对于任何关注 5-10 年数据保密性的组织而言，窗口期已经非常有限：现在就开始规划与实验，是避免在量子时代陷入被动的唯一现实选择。

参考资料