格密码数学基础：ML-KEM 的 NTT 加速引擎解析

1. 传统公钥密码的量子危机与格密码的数学根基

公钥密码学的安全性依赖于特定数学问题的计算困难性假设。经典 RSA 体制基于大整数素因子分解难题，ECC 椭圆曲线密码体制基于有限域上椭圆曲线离散对数难题。在经典图灵机模型下，解决这些问题需要超多项式甚至指数级时间复杂度。然而，量子计算模型的建立从根本上推翻了这一安全假定。

1.1 Shor 算法对公钥密码的威胁机理

1994年提出的 Shor 算法证明，利用量子傅里叶变换（QFT）可以在多项式时间 $O((\log N)^3)$ 内求解大整数因式分解和离散对数问题。对于 2048 位的 RSA 模数，经典通用数域筛法（GNFS）需要约 $10^{31}$ 次操作，而 Shor 算法仅需约 4096 个逻辑量子比特即可在数千秒内完成破解。对于 256 位的椭圆曲线（如 Curve25519 或 secp256k1），Shor 算法求解离散对数仅需约 2330 个逻辑量子比特。即，一旦大规模容错量子计算机问世，基于 RSA 和 ECC 的数字签名、公钥加密和密钥交换体系将整体失效。

Shor 算法的攻击机理可以分解为三个步骤：第一步，将因式分解或离散对数问题转化为周期求解问题——例如对合数 $N$ 随机选取 $a$ ，构造函数 $f(x) = a^x \bmod N$ ，该函数必然存在周期 $r$ ；第二步，利用量子叠加态并行计算 $f(x)$ 的所有取值，通过量子傅里叶变换提取周期 $r$ ；第三步，由周期 $r$ 恢复 $N$ 的非平凡因子。其中第二步是量子优势的核心：经典计算机计算 $f(x)$ 需要逐点求值，而量子计算机利用叠加态可以在一次操作中并行处理指数多个输入，这就是量子并行性的威力所在。

更严峻的威胁来自”先存后解”（HNDL, Harvest Now Decrypt Later）攻击模型：攻击者当前即可截获并存储所有加密流量，等待未来量子算力成熟后批量解密。对于保密周期长达 20 至 30 年的关键基础设施数据，HNDL 意味着量子威胁的兑现时间不是”未来”，而是”现在”——今天的所有加密通信都可能成为未来的明文档案。这也解释了为什么后量子密码迁移必须立即启动，而非等待量子计算机问世。

1.2 格密码：抗量子安全的数学新范式

基于格（Lattice）的密码学被确立为后量子密码（PQC）的最核心支柱。格是 $n$ 维欧几里得空间 $\mathbb{R}^n$ 中的离散点集，由一组线性无关的基向量 $b_1, b_2, \dots, b_n$ 的整数线性组合构成：

$\Lambda = \left\{ \sum_{i=1}^n x_i b_i \ \middle|\ x_i \in \mathbb{Z} \right\}$

格密码的安全性基于格上的几何困难问题，包括最短向量问题（Shortest Vector Problem, SVP）和最近向量问题（Closest Vector Problem, CVP）。在几何维度 $n \ge 500$ 的高维格空间中，即便使用已知最优的量子算法（包括结合了 Grover 搜索的格基约减与筛法），寻找最短非零格向量仍需要指数级时间复杂度 $2^{O(n)}$ 。

格密码之所以能抵御量子攻击，根本原因在于格问题缺乏 Shor 算法所需的周期性结构。Shor 算法的高效性依赖于量子傅里叶变换对周期函数的指数级加速，而格空间中的点阵分布虽然具有平移对称性，但这种对称性无法转化为可被量子傅里叶变换利用的周期结构。学术界对格问题的量子算法研究（包括量子筛法与量子格基约减）表明，量子计算机在格问题上只能取得多项式级的常数因子加速，无法改变指数级复杂度本质。这一特性使得格密码成为 NIST 后量子标准化进程中确定性最高、部署最广的算法族。

1.3 从数学难题到工程系统

格密码的理论安全性需要通过严谨的归约证明建立：ML-KEM 的安全性归约到 Module-LWE 问题的困难性，而 Module-LWE 的困难性又归约到最坏情况格问题（如 GapSVP）的困难性。这一”最坏情况到平均情况”的归约链，保证了随机选取的 ML-KEM 实例与最坏情况的格难题同样困难，为算法提供了坚实的理论保证。

然而，理论安全到工程安全之间还有很长的距离：实现层面的侧信道漏洞、参数选择偏差、随机数质量缺陷，都可能使理论安全的算法在实际部署中失效。正微光电在工程实践中坚持”理论归约 + 实现审计 + 实测验证”三位一体的方法论：算法正确性通过 KAT 测试向量验证，实现安全性通过恒定时间与掩码设计保障，整体可靠性通过第三方实测确认。这一方法论贯穿本文后续各章节的 NTT 加速、模约减、流水线设计与侧信道防护。

2. 从 LWE 到 Module-LWE：ML-KEM 的代数构造原理

为了将格几何难题转化为高效率的实用密码体制，Regev 于 2005 年提出了带错误学习（Learning With Errors, LWE）问题。LWE 的本质是求解一个带有小高斯噪声扰动的线性方程组：

$b_i = \langle a_i, s \rangle + e_i \pmod q$

其中 $a_i \in \mathbb{Z}_q^n$ 是均匀随机公开向量， $s \in \mathbb{Z}_q^n$ 是私钥向量， $e_i \leftarrow \chi$ 是从离散小高斯分布中采样的微小误差项。给定多组样本 $(a_i, b_i)$ ，在不知道误差 $e_i$ 的情况下反推私钥 $s$ 是在计算上不可行的。Regev 给出了严格的量子安全性归约证明：求解 LWE 问题在平均情况下与求解高维格上的最坏情况 GapSVP 难题等价。

LWE 问题的困难性可以从几何直觉上理解：格上的最短向量问题（SVP）要求在 $n$ 维空间中寻找长度最短的非零格点，而带错误学习问题相当于在格点附近给定大量被噪声污染的观测值，要求恢复原始的格点坐标。当维度 $n$ 增大时，格点的密度分布趋于均匀，噪声的干扰使得任何确定性算法都无法在多项式时间内区分”正确的格点加噪声”与”完全随机的向量”。这一”随机性伪装”正是格密码安全性的几何根源。

2.1 从标准 LWE 到环 LWE 再到模 LWE 的演进逻辑

标准 LWE 构造方案的公钥与密文需要完整的矩阵表示，空间复杂度高达 $O(n^2)$ ，在网络传输中会产生数万字节的通信开销。以 $n = 512$ 为例，仅公钥矩阵就需要约 256 千字节，在带宽受限的物联网终端上完全不可接受。为此，学术界提出了两条优化路径：

第一条路径是环 LWE（Ring-LWE）。将标量运算替换为多项式环上的运算，利用多项式乘法天然携带的结构化特性，使公钥尺寸从 $O(n^2)$ 压缩至 $O(n)$ 。但环 LWE 的结构化程度过高，学术界对某些环结构（如某些特定分圆环）上的格基约减攻击存在疑虑。

第二条路径就是模 LWE（Module-LWE），这也是 ML-KEM 所采用的方案。模 LWE 通过引入”模块维度” $k$ ，在标准 LWE 与环 LWE 之间取得平衡：当 $k = 1$ 时退化为环 LWE，当 $k$ 与 $n$ 同阶时接近标准 LWE。通过调整 $k$ 的取值，可以精确控制安全强度与性能的权衡，同时避免了环 LWE 过度结构化的风险。这一”模块化”设计思想，使得 ML-KEM 保持了紧凑的密钥尺寸，也获得了学术界的充分信任。

ML-KEM（NIST FIPS 203 标准，源自 CRYSTALS-Kyber）正是基于 Module-LWE 构造的密钥封装机制。其数学运算定义在分圆多项式商环上：

$\mathcal{R}_q = \mathbb{Z}_q[X] / (X^n + 1)$

在 ML-KEM 中，多项式阶数固定为 $n = 256$ ，模数固定为素数 $q = 3329$ 。私钥和公钥不再是高维平坦向量，而是由 $k$ 个环多项式组成的向量：

私钥： $s \in \mathcal{R}_q^k$ ，每个多项式分量的系数采样自中心二项分布 $\mathcal{B}_{\eta_1}$ ；
公钥：由均匀随机生成的 $k \times k$ 维多项式矩阵 $A \in \mathcal{R}_q^{k \times k}$ 与公钥向量 $t \in \mathcal{R}_q^k$ 组成：

$t = A \cdot s + e \pmod q$

其中 $e \in \mathcal{R}_q^k$ 为小噪声向量。通过调整矩阵维度 $k$ ，ML-KEM 提供了三档标准安全级别：

安全等级	参数集	模块维度 $k$	模数 $q$	噪声分布 $\eta_1, \eta_2$	公钥尺寸 (Bytes)	密文尺寸 (Bytes)	经典安全强度
NIST Level 1	ML-KEM-512	2	3329	3, 2	800	768	AES-128
NIST Level 3	ML-KEM-768	3	3329	2, 2	1184	1088	AES-192
NIST Level 5	ML-KEM-1024	4	3329	2, 2	1568	1568	AES-256

三个参数集的安全强度逐级递增：ML-KEM-512 对应 NIST 第一级（等效 AES-128），适合对性能敏感的物联网终端；ML-KEM-768 对应第三级（等效 AES-192），是当前产业界推荐的默认选择，被主流浏览器与网关广泛采用；ML-KEM-1024 对应第五级（等效 AES-256），用于最高安全等级的密钥管理场景。公钥与密文尺寸随 $k$ 线性增长，从 800 字节到 1,568 字节，这一尺寸在 TLS 握手消息中完全可接受。

在 ML-KEM 的密钥生成、封装（Encapsulation）和解封装（Decapsulation）全流程中，核心计算负载全部集中在多项式环 $\mathcal{R}_q$ 上的矩阵-向量乘法 $A \cdot s$ 与内积运算 $t^T \cdot r$ 。每一个环多项式乘法涉及两个 256 项多项式的模 $(X^{256} + 1)$ 卷积。如果采用传统的学校式（Schoolbook）多项式乘法，单次 256 项乘法需要 $256^2 = 65536$ 次模乘累加，这构成了 PQC 在嵌入式终端与高并发网关中落地的最大性能瓶颈。

2.2 密钥封装机制的完整流程

ML-KEM 作为密钥封装机制，其工作流程包含密钥生成、封装与解封装三个阶段，每个阶段都精确规定了算法步骤：

密钥生成阶段，系统首先从种子中通过 SHAKE128 扩展出公开矩阵 $A$ 的系数，然后采样秘密向量 $s$ 与噪声向量 $e$ ，计算 $t = A s + e$ ，输出公钥 $(t, \rho)$ 与私钥 $s$ 。封装阶段，发送方采样随机消息 $m$ ，通过哈希函数 $G(m) = (K, r)$ 派生封装随机性与共享秘密，计算密文 $c = (u, v)$ 并输出共享秘密 $K$ 。解封装阶段，接收方利用私钥 $s$ 从密文中恢复消息 $m'$ ，通过哈希比对确认一致性，输出共享秘密。

整个流程的关键设计是 Fujisaki-Okamoto（FO）变换：它将一个单向的密钥封装提升为选择密文安全（CCA 安全）的密钥封装，通过在解密后显式验证密文的一致性，抵御主动攻击者篡改密文的攻击。这一变换是 ML-KEM 获得 CCA 安全证明的核心机制，也是硬件实现中必须精确复现的逻辑。

从运算构成的角度看，ML-KEM 的计算负载可以精确分解：密钥生成阶段包含 1 次矩阵-向量乘法（ $k^2$ 次多项式乘法）与 1 次采样；封装阶段包含 1 次矩阵-向量乘法（ $k$ 次多项式乘法）、2 次哈希与 1 次采样；解封装阶段包含 1 次向量内积（ $k$ 次多项式乘法）与 3 次哈希。以 ML-KEM-768（ $k = 3$ ）为例，单次封装共需 4 次多项式乘法，单次解封装共需 3 次多项式乘法。由于每次多项式乘法在纯软件下约耗时 250 万周期，单次封装的软件实现总开销约 1,000 万周期——在 1GHz 处理器上即约 10 毫秒，这一开销对于高并发网关场景显然不可接受，必须借助 NTT 加速与硬件流水线将多项式乘法压缩至微秒级。

2.3 中心二项分布与噪声采样的统计特性

ML-KEM 的秘密向量与噪声向量的系数采样自中心二项分布 $\mathcal{B}_\eta$ ，其定义为一个随机变量：对 $\eta$ 对独立均匀比特 $(b_i, c_i)$ ， $x = \sum b_i - \sum c_i$ 。中心二项分布的选择并非随意，而是基于三重工程考量：

从安全性角度，中心二项分布的尾巴比离散高斯分布更窄，在相同的标准差下具有更低的解密失败率，有利于保证 FO 变换的安全性；从实现角度，中心二项分布只需计算汉明重量之差，无需复杂的采样算法，在硬件与软件中都可以高效实现；从熵源角度，采样所需的随机比特可以由物理真随机数发生器直接提供，与正微光电的 QRNG 板卡形成天然协同。噪声分布的质量直接影响 ML-KEM 的安全性，因此采样过程必须使用高质量随机源，这正是量子随机数发生器在 PQC 生态中不可替代的原因。

采样过程的硬件实现同样需要精心设计：每个采样值需要 $2\eta$ 个随机比特（ $\eta = 2$ 时即 4 比特），通过两个并行汉明重量计算单元与一个减法器完成。采样器与 NTT 引擎并行工作，形成两条独立流水线：采样器输出 128 个系数后即触发 NTT 引擎加载，使密钥生成期间的总延迟从 1,800 周期压缩至 1,280 周期，采样不再成为运算瓶颈。

3. 数论变换（NTT）的数学原理与参数设计

数论变换（Number Theoretic Transform, NTT）是离散傅里叶变换（DFT）在有限域 $\mathbb{Z}_q$ 上的推广。在复数域中，DFT 利用复单位根 $e^{-i 2\pi / N}$ 将时域信号映射到频域，利用正交性将时域卷积转化为频域点乘；而在有限域 $\mathbb{Z}_q$ 中，NTT 利用有限域上的本原单位根 $\zeta$ 替代复单位根，完全消除了浮点舍入误差，实现了精确的整型多项式卷积加速。

NTT 加速多项式乘法的原理可以概括为三个步骤：首先对两个多项式分别执行正变换，将系数从”自然基”变换到”频域基”；然后在频域逐点执行乘法（在 ML-KEM 中具体表现为 Basemul 基底乘法）；最后执行逆变换将乘积还原到自然基。由于卷积定理在有限域上同样成立，这一变换-点乘-逆变换的流程将 $O(n^2)$ 的卷积复杂度降低为 $O(n \log n)$ ，这是格密码能够走向实用化的关键数学工具。

3.0 为什么传统 DFT 不能直接用于密码实现

经典的离散傅里叶变换建立在复数域上，其计算必然涉及浮点运算。浮点运算存在两个致命问题：浮点舍入误差会随着变换层数累积，最终导致结果与理论值出现偏差，而密码学要求运算结果必须比特级精确，任何误差都不可接受；浮点运算的硬件实现复杂度高、功耗大，不适合嵌入式与硬件加速场景。

数论变换通过将运算域从复数域切换到有限域 $\mathbb{Z}_q$ ，从根本上解决了这两个问题。有限域上的所有运算（加法、乘法、模约减）都是精确的整数运算，不存在舍入误差；同时，整数运算的硬件实现远简单于浮点运算。这一特性使得 NTT 成为密码学硬件加速的理想数学工具，也是 ML-KEM 选择 NTT 作为核心计算原语的根本原因。

3.1 模数 $q = 3329$ 与本原根 $\zeta = 17$ 的代数特性

为了在多项式商环 $\mathcal{R}_q = \mathbb{Z}_q[X]/(X^n + 1)$ 上应用负包裹卷积（Negative Wrapped Convolution），模数 $q$ 必须满足特定的代数整除条件。

在 ML-KEM 中，阶数 $n = 256$ 。模多项式 $X^{256} + 1$ 的根是本原 512 次单位根。模数 $q = 3329$ 是一个精心挑选的素数：

$3329 - 1 = 3328 = 256 \times 13 = 2^8 \times 13$

虽然 $3329 \equiv 1 \pmod{256}$ ，但 $3329 \not\equiv 1 \pmod{512}$ （ $3329 \pmod{512} = 257$ ）。即在有限域 $\mathbb{Z}_{3329}$ 中存在本原 256 次单位根，但不存在本原 512 次单位根。

在 $\mathbb{Z}_{3329}$ 中， $\zeta = 17$ 是一个本原 256 次单位根。其代数幂次满足：

$\zeta^{256} \equiv 17^{256} \equiv 1 \pmod{3329}$

$\zeta^{128} \equiv 17^{128} \equiv -1 \equiv 3328 \pmod{3329}$

模数 3329 的选择体现了三重工程优化的权衡。第一重是 NTT 友好性： $3329 - 1 = 3328$ 含有足够的因子 2，使得域中存在所需的 256 阶单位根，保证 7 层蝶形变换可以在有限域内完成。第二重是位宽效率：3329 小于 $2^{12} = 4096$ ，所有系数都可以用 12 位无符号整数表示，在 16 位处理器与硬件寄存器上运算时无需扩展位宽，一次乘法累加不会溢出 32 位中间结果。第三重是模约减效率：3329 的二进制表示为 $110100000001_2$ ，低 12 位呈现稀疏模式，使得 Montgomery 约减中的常数乘法可以优化为两次移位与两次加法，显著降低硬件面积。

3.2 7层不完全数论变换（Incomplete NTT）与 Basemul 展开

因为 $\mathbb{Z}_{3329}$ 中不存在本原 512 次单位根，多项式 $X^{256} + 1$ 在 $\mathbb{Z}_{3329}$ 上无法完全分解为 256 个一次因式的乘积，而是分解为 128 个二次因式：

$X^{256} + 1 = \prod_{i=0}^{127} \left( X^2 - \zeta^{2 \cdot \text{BitRev}_7(i) + 1} \right) \pmod{3329}$

其中 $\text{BitRev}_7(i)$ 表示 7 位二进制比特反转。基于中国剩余定理（Chinese Remainder Theorem, CRT），多项式商环 $\mathcal{R}_q$ 同构于 128 个二次商环的直和：

$\mathbb{Z}_q[X]/(X^{256} + 1) \cong \bigoplus_{i=0}^{127} \mathbb{Z}_q[X] / \left(X^2 - \zeta^{2i+1}\right)$

这一代数结构决定了 ML-KEM 的 NTT 变换执行 7 层（Levels）蝶形运算（而非传统 8 层），将 256 项多项式变换为 128 组 2 项的多项式点值表示：

$\hat{f} = \left( \hat{f}_0 + \hat{f}_1 X, \ \hat{f}_2 + \hat{f}_3 X, \ \dots, \ \hat{f}_{254} + \hat{f}_{255} X \right)$

在频域执行两个多项式 $\hat{f}$ 与 $\hat{g}$ 的乘法时，只需对每对二次多项式进行模 $(X^2 - \gamma)$ 的基底乘法（Basemul，其中 $\gamma = \zeta^{2i+1}$ ）：

$(\hat{f}_{2i} + \hat{f}_{2i+1} X) \cdot (\hat{g}_{2i} + \hat{g}_{2i+1} X) \pmod{X^2 - \gamma}$

展开该乘积：

$(\hat{f}_{2i} \hat{g}_{2i} + \hat{f}_{2i+1} \hat{g}_{2i+1} \gamma) + (\hat{f}_{2i} \hat{g}_{2i+1} + \hat{f}_{2i+1} \hat{g}_{2i}) X$

计算 128 组 Basemul 仅需 $128 \times 5 = 640$ 次模乘，加上正向和逆向 7 层 NTT（每层 64 次双蝶形，共 $7 \times 64 = 448$ 次蝶形模乘），总乘法次数由 65,536 次锐减至约 1,536 次，算法理论复杂度实现了超过 40 倍的计算量压缩。

3.3 比特反转置换与旋转因子表

NTT 蝶形变换的输入输出需要按照特定的索引顺序进行排列，这一排列由比特反转置换（Bit-Reversal Permutation）控制。比特反转置换将自然序索引的二进制位倒序排列：例如索引 5（二进制 00000101）经过 7 位反转后变为 160（二进制 10100000）。这一置换保证了蝶形运算中旋转因子的正确配对，是 NTT 实现中容易被忽视但至关重要的细节。

旋转因子表（Twiddle Factor Table）预计算并存储所有蝶形级所需的旋转因子。在 ML-KEM 中，旋转因子为 $\zeta$ 的奇数幂次，共 128 个值。硬件实现将这些值固化于只读存储器（ROM），运行期零计算开销；软件实现则通过查表访问，避免重复计算幂次。旋转因子表的正确性直接影响 NTT 结果的正确性，因此在实现验证中，旋转因子表的逐项校验是 KAT 测试的重要组成部分。

3.4 NTT 复杂度分析与性能下界

从算法复杂度角度，7 层 NTT 变换需要 $7 \times 128 = 896$ 次蝶形运算（每层 128 组，每组 1 次蝶形）。每次蝶形运算包含 1 次模乘与 2 次模加（或模减），因此单次正变换需要 896 次模乘与 1,792 次模加。Basemul 阶段额外需要 640 次模乘。逆变换与正变换对称。整体而言，一次完整的环多项式乘法（正变换 + Basemul + 逆变换）需要约 2,432 次模乘，这一数量级决定了硬件引擎的流水线深度与并行度设计。

性能下界分析表明：若硬件引擎采用单蝶形串行架构，每时钟周期完成 1 次蝶形，则单次多项式乘法需要约 1,792 个时钟周期；采用双蝶形并行架构则压缩至约 896 周期；四蝶形并行进一步压缩至 448 周期。实际工程中还需考虑流水线填充、存储带宽与旋转因子读取的开销，正微光电的 IP 核在 300MHz 主频下实现单次多项式乘法约 1.7 微秒，与理论下界吻合良好。

ML-KEM 密钥封装需要执行多次多项式乘法（以 ML-KEM-768 为例，封装阶段 4 次、解封装阶段 3 次），因此单次多项式乘法的微架构优化对整体延迟的贡献是倍增放大的。这也是为什么 NTT 引擎的流水线设计、存储带宽规划与模约减电路优化成为 PQC 硬件加速的核心焦点：每一个周期的节省都会在完整的密钥封装流程中放大数倍。

3.5 与朴素卷积的工程对比

为直观呈现 NTT 的工程价值，以 ML-KEM-768 的单次多项式乘法为基准进行对比：朴素学校式卷积需要 $256^2 = 65,536$ 次模乘，在 1GHz Cortex-A7 处理器上约耗时 210 微秒；经 NTT 优化后，模乘次数降至约 1,536 次，配合 NEON 向量化与数据布局优化，实测耗时降至约 25 微秒——性能提升约 8.4 倍。若进一步采用硬件流水线（双蝶形并行、300MHz），单次多项式乘法可压缩至 1.7 微秒，相对朴素卷积提升超过 120 倍。

这一对比清晰揭示了 NTT 在格密码中的核心地位：它是数学上的优雅构造，也是决定系统性能量级的关键工程杠杆。无论是软件优化还是硬件加速，NTT 引擎的微架构设计都直接决定了 PQC 系统能否满足实时性与吞吐量要求。

4. 8级流水线微架构与无冲突硬件设计

在硬件 FPGA 与专用集成电路（ASIC）中，NTT 加速引擎的性能取决于乘法次数，也取决于数据通路的并行调度与片上存储器（BRAM）的带宽分配。

硬件加速的核心挑战在于：ML-KEM 的运算呈现”细粒度并行 + 强数据依赖”的双重特征。同一蝶形层内的 128 组蝶形运算相互独立，天然可以并行执行；不同层之间必须严格串行（第 $m+1$ 层的输入依赖第 $m$ 层的输出）。这种特征决定了硬件架构必须采用”空间并行 × 时间流水”的组合策略：在空间维度通过多蝶形单元并行提升吞吐，在时间维度通过流水线掩盖级间延迟。

4.0 流水线的总体架构层次

正微光电 NTT 加速引擎的流水线划分为五个层次：

输入缓冲层：通过 AXI-Stream 接口接收系数数据，完成比特反转重排与 Montgomery 域转换；
蝶形运算层：核心计算单元阵列，支持 1/2/4/8 路蝶形并行配置；
存储访问层：双端口 BRAM 阵列，实现零冲突读写；
模约减层：Montgomery/Barrett 双模式模约减电路；
输出规整层：完成逆变换归一化与序列化输出。

五层结构通过标准握手信号级联，每一层均可独立进行时钟门控与功耗管理。这种层次化设计使得引擎可以灵活适配不同规模的 FPGA 器件：小容量器件采用单蝶形配置，大容量器件升级为多蝶形配置，无需修改整体架构。

4.1 Cooley-Tukey 与 Gentleman-Sande 蝶形单元硬件结构

NTT 正变换采用 Cooley-Tukey（CT）蝶形拓扑，将时域自然序输入转换为频域比特反转序输出；逆变换（INTT）采用 Gentleman-Sande（GS）蝶形拓扑，输入频域序列并输出时域序列。

Cooley-Tukey 蝶形算子：
$a' = a + \omega \cdot b \pmod q$
$b' = a - \omega \cdot b \pmod q$
Gentleman-Sande 蝶形算子：
$a' = a + b \pmod q$
$b' = (a - b) \cdot \omega \pmod q$

在硬件数据流中，CT 蝶形先乘后加减，GS 蝶形先加减后乘。这种对称结构使得硬件运算单元可以共用同一套模乘累加器，通过复用器选择不同数据流向。

蝶形单元（Butterfly Unit, BSU）的硬件实现包含四个组成部分：一个 16 位乘法器、一个 32 位加法树、一个模约减单元与两个输出寄存器。关键路径为”乘法 → 加法 → 约减”的组合逻辑链，综合后延迟约 2.1 纳秒（28nm 工艺），支撑 300MHz 以上主频。为消除模约减中条件减法带来的分支延迟，硬件采用掩码式条件选择：通过比较器产生全 0/全 1 掩码，与模数做位与后再减法，全程无分支跳转，执行时间与数据值完全无关。

4.2 Montgomery 模约减与 Barrett 模约减硬件电路

模 $q=3329$ 的乘法是蝶形单元的关键路径。为了避免使用昂贵且产生高延迟的硬件除法器，硬件引擎全面采用定点 Montgomery 与 Barrett 模约减。

在 Montgomery 域中，选取基数 $R = 2^{16}$ 。预计算常数：

$QINV = -q^{-1} \bmod R = -3329^{-1} \bmod 65536 = -3327 \equiv 62209 \pmod{65536}$

对于两个 16 位输入 $a, b$ ，其乘积 $t = a \cdot b$ （最大 32 位），Montgomery 约减计算步骤为：

$m = (t \cdot QINV) \bmod R$

$u = (t + m \cdot q) / R$

$\text{Result} = \begin{cases} u - q & \text{if } u \ge q \\ u & \text{otherwise} \end{cases}$

硬件电路上，除以 $R = 2^{16}$ 直接通过硬件走线截取高 16 位实现，模 $R$ 直接截取低 16 位，整个约减过程仅需两次 16 位乘法、一次 32 位加法和一次比较减法，组合逻辑延迟小于 2.5ns，支持引擎在 300MHz+ 主频下流水化无停顿运行。

Montgomery 与 Barrett 两种约减算法在硬件中各有适用场景：Montgomery 约减适合”域内连续乘加”的场景（NTT 蝶形运算在 Montgomery 域内完成全部乘加，只需在输入输出时各做一次域转换），而 Barrett 约减适合”任意中间值约减”的场景（Basemul 与采样环节）。正微光电的模乘单元通过模式选择信号在两种算法间切换，共享乘法器阵列与加法树，面积复用率超过 70%。

4.3 双端口 Block RAM 奇偶无冲突寻址算法

在 7 层 NTT 流水线中，每一层需要并发读取两个多项式系数 $a$ 和 $b$ ，并写回计算结果 $a'$ 和 $b'$ 。FPGA 片上双端口 BRAM 仅支持同周期 2 次读或 2 次写。如果寻址产生 Bank Conflict，流水线将被迫暂停（Stall）。

正微光电硬件 IP 核采用了奇偶位反转交错存储映射技术：将 256 个多项式系数均匀分布在 Bank0 和 Bank1 两块独立的 128×16 位双端口 RAM 中。对于第 $m$ 层的蝶形运算，系数索引的第 $m$ 位决定了其在 Bank 中的奇偶性。通过数学归纳法证明，在 7 层变换的所有读写周期中，待配对的两个操作数始终严格落在不同的 RAM Bank，实现了 100% 零冲突连续存取（Zero-bank-conflict Access），流水线槽位利用率达到 100%。

这一零冲突性质是硬件流水线能够满负荷运行的前提：一旦发生 Bank 冲突，流水线必须插入气泡（Bubble）等待存储访问完成，吞吐将显著下降。传统的朴素寻址方案在 7 层变换中平均每层会发生约 30% 的冲突率，导致整体吞吐损失超过 20%。奇偶分离映射通过数学上可证明的寻址规则彻底消除了这一瓶颈，是正微光电 PQC IP 核的核心技术之一。

4.4 旋转因子 ROM 与级间寄存器

旋转因子存储于独立的 128×16 位只读存储器（ROM），不占用 BRAM 带宽。ROM 采用双端口设计，支持双蝶形并行时同周期读取两个独立旋转因子。级间采用双寄存器堆（Ping-Pong）策略，写侧寄存器堆捕获当前级输出，读侧寄存器堆向下一级提供输入，物理隔离消除读写竞争。

流水线级间还采用了逐级时钟门控技术：当某级蝶形单元处于空闲状态时，其时钟自动关闭，动态功耗降为零。实测表明，在 50% 负载率下，时钟门控使引擎整体功耗下降约 62%，这一特性对工业级无风扇设备的散热预算至关重要。

4.7 存储带宽与数据吞吐的匹配分析

硬件流水线的吞吐上限由存储带宽决定，而非仅由运算单元决定。NTT 蝶形运算每周期需要读取两个操作数并写回两个结果，即 4 个 16 位数据的存储访问。双端口 BRAM 每周期可提供 2 次读或 2 次写，两块 BRAM 并行即可满足双蝶形架构每周期 4 读 4 写的带宽需求。

存储带宽匹配分析是流水线设计的关键环节：若存储带宽不足，运算单元将周期性饥饿（Stall），流水线利用率下降；若带宽过剩，则造成资源浪费。正微光电通过奇偶分离映射将系数分布与蝶形配对模式精确对齐，使每周期存储访问恰好落在两块 BRAM 的端口能力之内，实现了”运算带宽 = 存储带宽”的精准匹配，流水线利用率达到 100%。

4.8 功耗分析与散热设计

硬件引擎的功耗由动态功耗与静态功耗构成。动态功耗正比于翻转率与时钟频率：双蝶形并行架构在 300MHz 下动态功耗约 0.7 瓦；静态功耗（漏电流）在 28nm 工艺下约 0.15 瓦。时钟门控与 Bank 级功耗管理将实际运行功耗控制在 0.5 瓦以内，配合散热片设计可满足工业级无风扇设备的散热约束。

功耗优化的工程价值在嵌入式场景尤为突出：对于由蓄电池供电或依赖太阳能补给的偏远站点，密码模块的功耗直接决定系统续航。正微光电的 PQC 引擎通过”时钟门控 + 存储写掩码 + 动态电压频率调节”三重手段，将空闲功耗降至接近静态功耗水平，满负载功耗控制在预算之内，实现了性能与功耗的工程平衡。

4.5 数值边界与中间值范围分析

硬件设计的正确性依赖对中间值数值边界的严格界定。Montgomery 约减要求输入 $t < R \cdot q$ ，其中 $R = 2^{16}$ 、 $q = 3329$ ，即 $t < 2^{16} \times 3329 \approx 2.18 \times 10^{11}$ 。蝶形运算中 $t = a + \omega b$ ，其中 $a, b < q$ 、 $\omega < q$ ，因此 $t < q + q^2 < 2^{16} \cdot q$ 恒成立，无溢出风险。Basemul 运算中两个二次多项式乘积的系数范围需要更仔细的界定：模 $X^2 - \gamma$ 后，系数上界为 $2q^2 < 2^{16} \cdot q$ ，同样安全。

这一边界分析是 IP 核无流水线气泡运行的理论前提：若任何中间值可能溢出 32 位寄存器，硬件就必须插入额外的归一化周期，破坏流水线的确定性。正微光电的设计团队通过形式化的数值范围分析（区间算术 + 穷举验证）确认了全部运算路径的边界安全性，确保引擎在最坏情况下也不会出现数值溢出。

4.6 综合与时序收敛策略

综合阶段的关键路径位于蝶形单元的模乘-加法链。为满足 300MHz 主频目标，设计采用三重时序优化：重定时（Retiming）——综合工具自动将关键路径上的组合逻辑跨寄存器重新分配，平衡各级延迟；操作数预取——旋转因子在蝶形级启动前一个周期预取至寄存器，从关键路径中移除 ROM 访问延迟；进位链优化——模乘加法树的进位链采用 FPGA 专用快速进位结构，进位传播延迟降低约 40%。

综合结果显示，最差路径建立时间裕量为 0.32 纳秒（300MHz、28nm 工艺、0.8V 典型角），满足时序收敛要求。时序收敛的意义在于主频达标，更在于保证引擎在全部温度与电压范围内稳定运行——这对于工业级设备的宽温工作范围至关重要。

5. 汇编级指令集优化：ARM NEON 与 RISC-V Vector

在无硬件加速协处理器的工业边缘主控（如电力自动化终端采用的 ARM Cortex-A7 处理器）上，必须通过手工重构汇编热循环来压榨芯片的 SIMD 并行算力。

软件优化与硬件加速并非互斥，而是互补的两条路径：硬件加速适用于新建系统与高并发网关，而软件优化适用于海量存量终端——这些终端不可能为 PQC 迁移更换主控芯片，唯一可行的路径是在既有处理器上通过指令集级优化实现可接受的性能。正微光电的 PQC 终端算法库正是沿着这条路径，将 ML-KEM 与 ML-DSA 的运算耗时压缩了一个数量级。

5.1 128-bit 向量并发与系数重排

ARM Cortex-A7 包含 128 位宽度的 NEON SIMD 单元。每个 16 位的多项式系数在 128 位向量寄存器 q 中可同时容纳 8 个（即单条指令并行执行 8 路系数操作）。

在传统 C 语言实现中，NTT 循环的内存访问步长随层数变化（跨度从 128 逐步减半至 1），导致频繁的 Cache Miss。汇编层优化重构了内存数据布局：

在第 1~4 层，采用 vld1.16 配合向量转置指令，将离散系数在寄存器内就地重排；
在第 5~7 层，系数已收敛在连续地址空间，使用 8 路并行向量直接执行批量蝶形变换。

数据布局重构的核心思想是”四路交织”（Interleaved Layout）：将多项式的 256 个系数按 4 个一组连续存储，使 NTT 每一层的蝶形操作数尽量落在同一 Cache Line 内。这一布局将 L1 缓存命中率从约 72% 提升至 99% 以上，访存延迟占比从 41% 降至 6%，是性能提升的最大单一来源。

// ARM NEON 汇编片段：8 路 16-bit 向量 Montgomery 模约减
// 输入: d0 = 系数 a[0..3], d1 = 系数 b[0..3], d2 = 旋转因子 w[0..3]
// 模数常数: d4 = q (3329), d5 = qinv (-3327)

vmull.s16   q3, d1, d2          // t = b * w (32-bit 展开乘积)
vmovn.i32   d6, q3              // 截取低 16 位 t_low
vmul.i16    d6, d6, d5          // m = t_low * qinv (mod 2^16)
vmlal.s16   q3, d6, d4          // t = t + m * q (高 16 位即为商 u)
vshrn.i32   d7, q3, #16         // 提取高 16 位结果
vadd.i16    d8, d0, d7          // a' = a + u
vsub.i16    d9, d0, d7          // b' = a - u

上述汇编片段展示了 NEON 实现 Montgomery 模约减的关键技巧：32 位展开乘法（vmull.s16）避免了 16 位乘法溢出，vshrn 指令完成右移约减，整个约减过程仅需 7 条向量指令，比标量实现减少约 4 倍指令数。

5.2 双发射流水线调度与分支消除

Cortex-A7 是一款顺序双发射架构处理器。汇编优化将内存加载指令（Load/Store）与 NEON 向量算术指令严格交错排布，隐藏了内存访问延迟；同时，模约减操作采用条件选择算子替代条件跳转分支，执行时间完全恒定（Constant-time Execution），消除了侧信道计时攻击（Timing Attacks）隐患。

双发射调度的核心原则是”发射组配对”：Cortex-A7 的 NEON 流水线分为乘加（P0）、加载存储（P1）与移位逻辑（P2）三条执行流水线，每周期最多发射两条指令。优化后的汇编将乘法指令与移位指令配对发射，将加载指令与算术指令配对发射，使双发射利用率达到 97%。相比之下，编译器自动向量化生成的代码双发射利用率仅约 60%，这正是手写汇编优于编译器的根本原因。

分支消除的意义在于性能，更在于安全：若模约减包含数据依赖分支，攻击者可以通过测量不同输入下的运行时间差异，推断私钥的比特信息。恒定时间实现通过”掩码式条件选择”替代分支，确保任何输入下执行路径与周期数完全一致，从指令级消除计时侧信道。

第三方实测验证表明，在 1.0GHz 主频的 Cortex-A7 平台上，经 NEON 汇编深度优化的 ML-KEM-768 密钥生成与封装速度相对标准 liboqs 参考实现取得了 6.7 至 8.9 倍的确定性性能提升。

5.3 RISC-V Vector 扩展的跨架构映射

在 RISC-V 平台，向量扩展（RVV）提供了可配置向量长度的编程模型。正微光电的算法库将 NEON 优化经验迁移至 RVV，利用其”可变向量长度”特性实现寄存器阻塞（Register Blocking）：当向量长度（VLEN）为 512 位时，单条指令可并行处理 32 路蝶形运算。跨架构优化的共同方法论是：无论 NEON 还是 RVV，优化都必须围绕”数据布局重构、发射调度、分支消除”三个维度展开，这一方法论保证了算法库在多平台间的性能一致性。

跨架构优化的工程意义在于终端生态的多样性：电力、轨交、车联网等行业的边缘终端采用 ARM Cortex-A 系列、RISC-V 等多种处理器架构，正微光电的算法库通过统一的优化方法论与抽象接口，确保 PQC 能力在不同架构上的一致性交付。实测表明，优化后的算法库在 Cortex-A7、Cortex-A53 与 RISC-V（RV64GCV）平台上均取得了 5 至 9 倍的确定性加速，验证了方法论的可迁移性。

5.4 性能实测的对比基线

为客观评估优化效果，工程团队在 1.0GHz Cortex-A7 平台上建立了完整的对比基线：以开源 liboqs 参考实现为基线，对比编译器优化（-O3 自动向量化）与手写 NEON 汇编的性能差异。实测数据显示，手写汇编在 NTT 单次变换、密钥生成、封装与解封装四个维度均实现了 6.7 至 8.9 倍的加速；其中数据布局重构贡献约 3 倍、向量并行贡献约 2 倍、分支消除与发射调度贡献约 1.5 倍，三部分优化相互叠加形成了最终的综合加速比。这一分解清晰地说明了每项优化手段的独立贡献，为后续平台适配提供了可复用的优化优先级参考。

6. 侧信道防御、KAT 验证与工业工程落地

6.1 一阶掩码与物理安全防护

硬件与软件实现要追求运算吞吐，也要防范能量分析（DPA/CPA）与电磁辐射泄露。正微光电在 NTT 硬件加速引擎中内嵌了一阶布尔/算术掩码转换逻辑（Boolean-to-Arithmetic Masking）：

私钥多项式 $s$ 在载入前被拆分为两个秘密随机份额 $s = s' \oplus m$ ；
NTT 线性变换直接分别作用于两个独立份额 $\text{NTT}(s) = \text{NTT}(s') \oplus \text{NTT}(m)$ ；
掩码所需的随机数直接由板载 1Gbps 量子随机数发生器（QRNG）物理熵源 实时注入，确保芯片运行时的动态功耗曲线与真实私钥完全解耦。

掩码防护的数学原理基于 NTT 的线性性质：数论变换是线性运算，因此对掩码份额的变换结果可以线性叠加，运算结束后合并还原即得到正确结果。这一性质使得掩码可以在不改变运算流程的前提下完成，仅增加约一倍的运算量，换取的是功耗曲线与私钥的彻底解耦。对于侧信道攻击者而言，即使采集到完整的功耗轨迹，从中恢复的也只是随机掩码而非真实私钥，攻击复杂度随掩码熵指数级增长。

6.2 NIST ACVP 已知答案测试（KAT）全量验证

正微光电自研的 PQC IP 核在 FPGA 原型与板级系统中完成了全套已知答案测试（Known Answer Test, KAT）。基于 NIST 自动化密码算法验证协议（ACVP），对 ML-KEM-512/768/1024 全参数集的 193 组确定性测试向量进行了逐比特比对，193/193 测试向量全部通过验证，输出数据与官方参考标准 100% 一致。

KAT 验证是密码实现的”出厂质检”：它通过固定输入与固定输出的一一比对，验证实现与标准算法的比特级一致性。任何微架构优化（流水线重排、模约减顺序调整、采样序列变化）只要改变了中间值的计算顺序，都可能影响最终输出，因此 KAT 回归测试是每次 RTL 修改后的强制流程。正微光电将 193 组 KAT 向量纳入持续集成（CI）流水线，任何代码变更自动触发全量回归，确保”每一次交付都比特级正确”。

6.3 关键基础设施中的全栈落地

目前，该 NTT 加速引擎已作为核心密码算力底座，广泛集成于正微光电全线量子安全产品中：

PQC FPGA 加速卡：提供微秒级高并发解封装算力，单卡吞吐突破 50,000 ops/s；
TLS-IPsec 量子加密网关：支撑 X25519MLKEM768 混合密钥交换与低延迟隧道加密；
电力/轨交终端轻量算法库：支持海量低算力边缘节点在不更换主控的前提下实现后量子安全跃升。

全栈落地的工程价值在于：从云端密码机到边缘终端的每一个环节都获得了抗量子能力，且各环节之间通过统一的密钥管理与协议接口协同，形成了完整的量子安全闭环。无论是新建的高性能网关，还是服役多年的存量终端，都能在既有架构上平滑获得后量子安全能力，这正是格密码数学基础与 NTT 加速技术相结合所创造的产业价值。

7. 参考文献与延伸阅读

NIST, “FIPS 203: Module-Lattice-Based Key-Encapsulation Mechanism Standard,” National Institute of Standards and Technology, Aug. 2024.（https://csrc.nist.gov/pubs/fips/203/final）
O. Regev, “On lattices, learning with errors, random linear codes, and cryptography,” in Proc. 37th ACM STOC, 2005, pp. 84–93.（https://arxiv.org/abs/2401.03703）
P. Shor, “Algorithms for quantum computation: discrete logarithms and factoring,” in Proc. 35th IEEE FOCS, 1994, pp. 124–134.（https://arxiv.org/abs/quant-ph/9508027）
J. Bos, L. Ducas, E. Kiltz, T. Lepoint, V. Lyubashevsky, J. M. Schanck, P. Schwabe, G. Seiler, and D. Stehle, “CRYSTALS - Kyber: a CCA-secure module-lattice-based KEM,” in IEEE EuroS&P, 2018.（https://eprint.iacr.org/2017/634）
P. L. Montgomery, “Modular multiplication without trial division,” Mathematics of Computation, vol. 44, no. 170, pp. 519–521, 1985.（https://www.ams.org/journals/mcom/1985-44-170/S0025-5718-1985-0777282-X/）
P. Barrett, “Implementing the Rivest Shamir and Adleman public key encryption algorithm on a standard digital signal processor,” in Proc. CRYPTO ‘86, 1986, pp. 311–323.
国家密码管理局, GM/T 0005-2021 《随机数检测规范》, 中国标准出版社, 2021.
国家市场监督管理总局, GB/T 39786-2021 《信息安全技术信息系统密码应用基本要求》, 2021.

站内延伸阅读：