简介一套面向密码学学习与开发者的NTRU-397加密算法实现资源包基于NTRU非对称加密体系聚焦397维多项式环上的密钥生成、加密与解密流程。压缩包共500个文件核心代码以255个C源文件、130个头文件和82个Python脚本为主辅以Makefile构建脚本、NIST测试配置及说明文档整体约274KB结构清晰便于按模块查阅。算法部分覆盖参数生成、公私钥构造、随机多项式选取及环运算等关键环节适合用于理解NTRU-397与标准NTRU在参数和性能上的差异。压缩包内含源码、文档、示例数据与测试用例可帮助读者从底层实现到实际调用快速上手也可为同类格密码算法的工程化提供参考。目前已有316人浏览学习适合密码学入门研究者、信息安全专业学生及对后量子密码感兴趣的开发者。1. 为什么是NTRU-397一个不走NTT路线的后量子公钥加密实现当 RSA 和 ECC 在 Shor 算法面前集体失守之后NTRU 大概是密码学界最早“反着用”格问题的方案加密时把噪声和秘密多项式藏进环 Z_q[x]/(x^N-1) 里要恢复明文就得在 NTRU 格上找一个足够短的向量。这套思路在 1996 年被提出三十年后不仅没被淘汰还进了 NIST 后量子标准化的决赛圈靠的就是它加密、解密都只有多项式乘法和模约减没有大整数幂模运算那种重负载。压缩包 ntru-master_NTRU-397_ntru_ 正是这个方向的一份独立实现数字 397 是多项式环的维度 N它不是 2 的幂说明实现刻意绕开了 NTT-friendly 的参数包里那几个 poly_rq_mul_toom4_k2x2.c、poly_rq_mul_k2x4.c 文件就是为这种“别扭”维度服务的 Toom-4 与 Karatsuba 分治乘法。想读 NTRU 源码或者研究非二次幂环上的多项式乘法调度这份代码都是比标准 NTT 实现更有代表性的样本。2. 从文件清单反推 NTRU-397 的代码结构owcpa、KAT 与三种底层的分工压缩包没有附带太多目录说明但十个 .c 文件已经足够把设计意图讲清楚。owcpa.c 是主体poly_rq_mul_* 是一族多项式乘法实现fips202.c 和 rng.c 是现代 KEM 实现里的基础设施PQCgenKAT_kem.c 和 test_owcpa.c 则分别是验证与自测入口。把它们串起来看这是一个典型的 NIST 后量子竞赛参考实现布局底层环运算、OW-CPA 封装、KEM 变换、KAT 生成四层各司其职。文件在实现里的角色owcpa.cNTRU 的 OW-CPA 方案核心密钥生成、加密、解密poly_rq_mul_toom4_k2x2.c多项式乘法优化Toom-4 与 2x2 Karatsuba 混合poly_rq_mul_k2x4.c多项式乘法的另一种分块策略2 段 x 4 段crypto_sort_int32.c常数时间 int32 排序用于带重量约束的采样fips202.cFIPS 202SHA-3/SHAKE实现提供哈希与随机扩展rng.cNIST 规格的 AES-CTR DRBG负责 KAT 可复现随机序列PQCgenKAT_kem.cNIST KAT 生成读请求文件输出响应文件校验一致性test_owcpa.c加解密功能自测test_gp_compat.cgeneric/portable 版本与优化版本的兼容性比对speed.c密钥生成、封装、解封装的周期计时2.1 crypto_sort_int32.c常数时间排序到底在解决什么问题NTRU 族的私钥多项式通常要求“恰好有指定数量的非零系数”而不是随便生成。最直接的做法是生成一批随机数再反复拒绝直到满足重量约束但这会让运行时间依赖秘密值侧信道一眼看穿。更常见的做法是给每个位置挂一个随机标量按标量排序后取前 w 个下标作为非零系数位置crypto_sort_int32.c 提供的就是这种常数时间归并排序。/* 假设要生成重量为 w 的三元私钥多项式 f */ int32_t tagbuf[NTRU_N]; /* 每个位置挂一个随机标签按标签排序后取前 w 个下标 */ crypto_sort_int32(tagbuf, NTRU_N); for (int i 0; i NTRU_W; i) { uint16_t idx tagbuf[i] (NTRU_N - 1); /* 落到有效下标范围 */ f[idx] 1; }这块逻辑要说明两点crypto_sort_int32 排序的是“位置对应标签”而非系数本身归并排序在 int32 上每轮比较次数固定不因输入秘密值产生分支这是它被选中的核心理由。移植这段代码时常见的坑是换了平台后忘记检查 int32 回绕行为导致私钥重量差一两个系数表象就是偶发解密失败而不是完全解不开排查起来要费不少功夫。2.2 fips202.c 与 rng.cNTRU-397 为什么离不开 SHA-3 和 DRBGowcpa.c 只保证“单向”安全要把 NTRU 用成抗 CCA 的 KEM还要做 Fujisaki-Okamoto 变换加密前先用 SHAKE 把随机种子和明文搅在一起解密后再重新封装一遍判断密文是否一致。fips202.c 几乎是此类 KEM 的标准配置它提供的 SHAKE128/256 承担两个职能把随机种子扩展成多项式系数以及在 FO 变换里充当随机预言机。我读这类代码的习惯是先看 fips202.c 有没有被裁剪。如果保留了完整的 Keccak-f[1600] 轮函数说明做 KAT 时 SHAKE 输出和 NIST 参考实现一致不能为了速度把轮数改少否则 rsp 文件第一字节就会对不上。rng.c 则是 NIST PQC 统一规格的 AES-CTR DRBGPQCgenKAT_kem.c 每次运行都会先用固定种子初始化它再确定性生成密钥和密文。KAT 校验比对的就是这个确定性随机序列所以 rng 必须有 bit 级可重现性任何字节序改动都会让整个响应文件从头到尾错位。2.3 poly_rq_mul_k2x4.c 与 toom4_k2x2.c为什么一套方案放两个乘法文件在多项式环 Z_q[x]/(x^N-1) 上做乘法最慢的地方是卷积。对 N397 这种素数维度不能像 Kyber 那样直接上 NTTNTT 要求 N 能整除某个 2 的幂次还要在模 q 下存在原根而 NTRU 的 q 往往取 2 的幂。于是实现回到分治算法k2x4 与 toom4_k2x2 是同一问题的两个变体toom4_k2x2 把两个操作数分别切成 4 段和 2 段再做混合分治k2x4 则是不对称地切成 2 段与 4 段。两套乘法对外暴露相同的符号我在做基准时会用对象文件替换的方式来测而不是在源码里改函数指针# 方案A用 k2x4 版本参与链接 gcc -O3 -marchnative -c poly_rq_mul_k2x4.c -o poly_rq_mul.o # 方案B换成 toom4 版本重新编译其他文件不动 gcc -O3 -marchnative -c poly_rq_mul_toom4_k2x2.c -o poly_rq_mul.o两个文件不能同时进链接否则 poly_rq_mul 符号会冲突。用同一个目标文件名替换比维护两个 Makefile 变量省事得多。3. owcpa.c 核心流程密钥生成、加密、解密的环运算拆解owcpa 是 One-Way Chosen-Plaintext Attack 的缩写它是一层“裸”的公钥加密只防被动窃听不防主动篡改。NTRU-KEM 会在它上面再套 FO 变换所以 owcpa.c 里的三个函数有着非常清晰的边界owcpa_keypair 生成密钥owcpa_enc 加密owcpa_dec 解密。3.1 密钥生成与 NTRU 格密钥生成的第一步是选两个三元多项式 f 和 g系数落在 {-1, 0, 1}其中 f 在模 q 下可逆。公钥 h 由 h g · f^{-1} mod q 得到私钥是 (f, g)。整个过程在 R_q Z_q[x]/(x^N-1) 上完成求逆用扩展欧几里得算法随机字节经过采样后成为候选的 f、g不满足可逆条件就重新采样。三元系数的选择不是随意为之解密时要靠小系数多项式的卷积结果不碰 q 边界系数范围越大解密失败概率越高。这里有一个安全维度值得展开h 公开后攻击者要在已知 h 的情况下找一个短的 (f, g) 满足 g ≡ f·h (mod q)这等价于在由 h 构造的 NTRU 格中找短向量。N397 比 NTRU-HRSS 的 701 小不少密钥更短、运算更快但安全强度更依赖 q 和重量参数的精细配合。调大 N 或调大 q 都能提升安全性代价完全不同调 N 是平方级拖慢乘法调 q 只是线性增加系数位宽所以参数微调时优先动 q。3.2 加密与封装加密时拿到明文 m编码成三元多项式选一次性随机多项式 r计算 c r·h m (mod q)。这里的加法和乘法都在 R_q 上做换言之卷积结果要折叠回 N 个系数并逐系数模 q。符号含义典型规模N多项式环维度397q整数模数通常取 2 的幂2048 或 4096f, g私钥短多项式三元重量受限h公钥 h g·f^{-1} mod q稠密多项式r加密随机短多项式三元或小整数系数m明文三元多项式每系数在 {-1,0,1}c密文 c r·h m mod q系数在 [0,q)3.3 解密中心化取模才是关键解密端拿到密文 c 后第一件事是计算 f·c mod q展开来看f·c f·(r·h m) r·(f·h) f·m r·g f·m (mod q)因为 r、g、f、m 全是小系数多项式r·g f·m 的每个系数绝对值都远小于 q/2。此时只要把结果按中心化取模修回 (-q/2, q/2]卷积就不会触发 q 的折叠得到一个真实的整数多项式再逐系数 mod 3 就还原出明文 m。写成代码核心就是这一步/* 解密f*c mod q 后中心化到 (-q/2, q/2] */ for (int i 0; i NTRU_N; i) { int32_t v f0c_mod_q[i]; /* 中心化把区间从 [0,q) 搬到 (-q/2, q/2] */ if (v q / 2) v - q; if (v -q / 2) v q; /* 此时 v 是 r*g f*m 的真实整数系数未发生模 q 折叠 */ dec[i] (v % 3 3) % 3; }参数说明f0c_mod_q 是 f 和 c 卷积后已经取模到 [0,q) 的系数中心化阈值是 q/2边界上的系数会因取模方向产生一位差异所以参数选择必须让系数撞边界的概率远低于 2^{-128}。要估算余量可以看 r·g 和 f·m 的系数上界若 f、g、r、m 的非零系数个数分别为 df、dg、dr、dm 且都是 ±1那么单个系数的绝对值上界约为 min(df,dg) min(df,dm)这个值比 q/2 小得多才有安全余量。实现在设计时也会让 f 在模 3 意义下可逆解密时对 f mod 3 的处理就可以省略。3.4 为什么 owcpa 还要再套一层 KEMowcpa 本身不抗主动攻击攻击者翻转密文 c 的某些系数解密结果会变化这种 malleability 在真实协议里很容易被利用。上层 FO 变换的做法是封装时计算 (k, r) G(m, h)用 r 加密解封装时先解出 m再用同样的 G 重新生成 r 并重新加密与收到的密文对比不一致就返回失败。PQCgenKAT_kem.c 里能看到的就是这一层逻辑它在 owcpa 外面包了密文一致性校验把安全性提升到 IND-CCA2。4. 在 N397 的环上做乘法Toom-4 与 Karatsuba 的分治拆法N397 是个素数这意味着多项式乘法没法靠 NTT 一步到位也不适合直接套 16 点分块 SIMD。poly_rq_mul_toom4_k2x2.c 和 poly_rq_mul_k2x4.c 这两个文件的命名已经把“切几段”和“每段用什么算法”的组合关系写在里面了。4.1 朴素卷积与分治乘法的复杂度对比教科书式卷积对两个 N 项多项式需要 N^2 次乘加397 维下一轮乘法约 15.7 万次乘加解密要做若干次这样的乘法性能瓶颈非常明显。Toom-4 的思路是把多项式拆成 4 段通过求值、点乘、插值三步把两个四段多项式的乘法转换成 7 次小乘法加若干线性组合小乘法还可以递归使用 Karatsuba这就是 k2x4 里“2”和“4”并存的原因每次分裂都可以选择不同的段数。策略子乘法次数渐进复杂度适用场景教科书卷积164段 x 4段O(n^2)段长很短拆分无收益Karatsuba 2x23每段切 2O(n^1.585)中等长度代码结构简单Toom-47每段切 4O(n^1.404)N397 附近性价比最优Toom-3 的复杂度是 O(n^1.465)子乘法 5 次NTRU-397 选择 Toom-4 是因为段长接近 100 时7 次小乘法的额外求值/插值开销已经被摊薄综合成本低于 Toom-3。4.2 求值与插值的实现骨架Toom-4 选定求值点 0、1、-1、2、-2、∞ 后两个段多项式 A 和 B 各算 6 个点值这些点值来自段系数的加减和移位然后做 7 次短乘法再做线性插值还原出乘积的 7 段。伪代码可以这样理解/* NTRU-397 乘法骨架a 拆 4 段b 拆 2 段 */ int16_t a4[4][BSZ4], b2[2][BSZ2]; unpack_397_to_4x(a4, a); /* 每段约 99 项最后一段短 */ unpack_397_to_2x(b2, b); /* b 切成 2 段每段约 198 项 */ /* 求值在 0, 1, -1, 2, -2, inf 处得到组合值 */ eval_toom4(a4, A_ev, ev_pts); eval_karatsuba2(b2, B_ev, ev_pts); /* 7 次短多项式乘法 */ for (int i 0; i 7; i) short_mul(AB_ev[i], A_ev[i], B_ev[i]); /* 插值并折叠 mod x^397-1 */ interpolate_toom4(c, AB_ev);这里最容易出错的环节是最后的折叠。插值得到的乘积长度约为 793 项保存回 N397 之前必须做 mod (x^397-1) 的循环卷积折叠。折叠的本质是下标模 397 累加很多实现错在顺序先模 q 再折叠会丢失进位信息正确做法是先完成索引折叠、再对每个系数模 q。4.3 k2x4 与 toom4_k2x2 的取舍从命名推断k2x4 更适合公钥 h 稠密、随机多项式 r 相对稀疏的场景稠密操作数拆成 4 段充分并行稀疏操作数拆成 2 段减少无谓的子乘法toom4_k2x2 则更均衡两边的拆分粒度一致。实际选型不能凭感觉要看 speed.c 里 poly 操作的分项计时。需要提醒的是比较两个乘法实现时编译器标志必须完全一致-O3 和 -O2 的差异有时比两种分治算法的差距还大。5. 复现编译、KAT 回归与 speed.c 基准测试的完整流程把源码变成能在本机跑起来的程序是从“能看懂”跨到“能验证”的关键一步。包内没有现成 Makefile常见做法是手写一个最小构建脚本按功能拆成多个可执行文件。5.1 最小构建脚本CC ? gcc CFLAGS ? -O3 -stdc99 -Wall -Wextra -marchnative # 注意两个乘法实现只能二选一避免 poly_rq_mul 符号冲突 MUL_OBJ poly_rq_mul_k2x4.o # MUL_OBJ poly_rq_mul_toom4_k2x2.o OBJS fips202.o rng.o crypto_sort_int32.o owcpa.o $(MUL_OBJ) speed: speed.c $(OBJS) $(CC) $(CFLAGS) $^ -o $ PQCgenKAT_kem: PQCgenKAT_kem.c $(OBJS) $(CC) $(CFLAGS) $^ -o $ test_owcpa: test_owcpa.c $(OBJS) $(CC) $(CFLAGS) $^ -o $参数说明-marchnative 会把乘法里的移位和加法编译成当前 CPU 支持的指令KAT 结果不应因 CPU 不同而变化因为算法确定性speed.c 的周期数则会随 CPU 明显变化报告基准时必须注明 CPU 型号和编译器版本。owcpa.o 依赖两个乘法实现之一提供 poly_rq_mul 符号两个都编进来会直接链接失败。5.2 三条验证命令步骤命令预期结果基本连通./test_owcpa 10001000 轮加解密全部成功失败数为 0兼容性./test_gp_compatgeneric 版与优化版输出一致无 diffKAT 一致性./PQCgenKAT_kem sha256sum PQCkemKAT_*.rsprsp 文件哈希与基线一致第一次跑 KAT 前先把 rsp 文件存一份基线之后任何改动都以“rsp 无变化”作为回归通过的标准。我移植这类代码时rsp 的 diff 往往能精确定位到某个字节比如请求文件里某个作为密钥种子的字节多了一次移位多半是 rng.c 或采样函数对字节序的处理与原实现不一致。这类问题用 log 排查效率极低直接 diff 两个 rsp 文件一眼就能看出错位起点。5.3 speed.c 给出的优化目标speed.c 通常对 keypair、enc、dec 分别计时。NTRU-397 这类小维度参数下enc 和 dec 应该在几万到几十万周期量级具体看乘法实现keypair 因为有求逆运算会显著更慢。优化时先跑一遍得到基线再替换 MUL_OBJ 重新编译对比 dec 周期变化。如果换了乘法实现后 KAT 也变了那不是性能优化是引入了 bug先别管速度回到 6.1 的 KAT 回归排查。6. 换乘法实现后如何用最小代价自检 NTRU-397改一个乘法文件、换一个编译器版本或者换一台 CPU对 NTRU 实现来说都不算大改动但它足以让解密失败率从数学上可忽略变成实际报错。最小自检路径我推荐三步KAT 回归、系数余量断言、带统计的随机测试。6.1 把 KAT 的 rsp 当作唯一真值替换乘法实现之前先跑一次原始版本保存 rsp 基线./PQCgenKAT_kem sha256sum PQCkemKAT_*.rsp baseline.sha # 替换 poly_rq_mul_k2x4.c 为 poly_rq_mul_toom4_k2x2.c 后重新编译 ./PQCgenKAT_kem sha256sum -c baseline.sha如果哈希不一致优先检查两个位置一是插值后的环折叠顺序二是中心化取模的边界方向。分治实现在这两个环节最容易写反而且是那种“10 次里有 1 次错”的隐蔽 bug普通自测很难触发。6.2 在解密端加一行系数范围断言运行时开销几乎可以忽略的检查是在 owcpa_dec 里记录中心化后的最大系数与 q/2 比较看余量还有多少。int max_coef 0; for (int i 0; i NTRU_N; i) { int32_t v center(fc[i]); /* 中心化到 (-q/2, q/2] */ if (abs(v) max_coef) max_coef abs(v); dec[i] mod3(v); } if (max_coef q / 4) printf(dec margin warning: %d/%d\n, max_coef, q / 2);这个打印值直接反映当前参数离解密失败边界有多远。如果 max_coef 长时间接近 q/2先检查随机多项式 r 的采样重量是不是被翻倍了而不是急着调 q。重量翻倍会让 r·g 的系数上界线性上升是这类警告最常见的触发原因。6.3 把两份对象文件放同一张基准表里比最后把两种乘法的速度结果并列记录而不是先后记两个数。清掉构建目录分别用 k2x4 和 toom4_k2x2 各构建一次跑 5 次 speed 取中位数对比 dec 周期。如果两个版本差距在 2% 以内固定用代码可读性更好的那版长期维护只有差距超过 10% 时才值得为“快版”多维护一套乘法代码。用数据而不是第一印象选实现改完代码顺手把 rsp 哈希留在提交信息里下次任何人动到乘法层都能直接跑回归确认没有破坏正确性。本文还有配套的精品资源点击获取 NTRU-397后量子加密实现解析：非NTT环上的多项式乘法与KEM设计
简介一套面向密码学学习与开发者的NTRU-397加密算法实现资源包基于NTRU非对称加密体系聚焦397维多项式环上的密钥生成、加密与解密流程。压缩包共500个文件核心代码以255个C源文件、130个头文件和82个Python脚本为主辅以Makefile构建脚本、NIST测试配置及说明文档整体约274KB结构清晰便于按模块查阅。算法部分覆盖参数生成、公私钥构造、随机多项式选取及环运算等关键环节适合用于理解NTRU-397与标准NTRU在参数和性能上的差异。压缩包内含源码、文档、示例数据与测试用例可帮助读者从底层实现到实际调用快速上手也可为同类格密码算法的工程化提供参考。目前已有316人浏览学习适合密码学入门研究者、信息安全专业学生及对后量子密码感兴趣的开发者。1. 为什么是NTRU-397一个不走NTT路线的后量子公钥加密实现当 RSA 和 ECC 在 Shor 算法面前集体失守之后NTRU 大概是密码学界最早“反着用”格问题的方案加密时把噪声和秘密多项式藏进环 Z_q[x]/(x^N-1) 里要恢复明文就得在 NTRU 格上找一个足够短的向量。这套思路在 1996 年被提出三十年后不仅没被淘汰还进了 NIST 后量子标准化的决赛圈靠的就是它加密、解密都只有多项式乘法和模约减没有大整数幂模运算那种重负载。压缩包 ntru-master_NTRU-397_ntru_ 正是这个方向的一份独立实现数字 397 是多项式环的维度 N它不是 2 的幂说明实现刻意绕开了 NTT-friendly 的参数包里那几个 poly_rq_mul_toom4_k2x2.c、poly_rq_mul_k2x4.c 文件就是为这种“别扭”维度服务的 Toom-4 与 Karatsuba 分治乘法。想读 NTRU 源码或者研究非二次幂环上的多项式乘法调度这份代码都是比标准 NTT 实现更有代表性的样本。2. 从文件清单反推 NTRU-397 的代码结构owcpa、KAT 与三种底层的分工压缩包没有附带太多目录说明但十个 .c 文件已经足够把设计意图讲清楚。owcpa.c 是主体poly_rq_mul_* 是一族多项式乘法实现fips202.c 和 rng.c 是现代 KEM 实现里的基础设施PQCgenKAT_kem.c 和 test_owcpa.c 则分别是验证与自测入口。把它们串起来看这是一个典型的 NIST 后量子竞赛参考实现布局底层环运算、OW-CPA 封装、KEM 变换、KAT 生成四层各司其职。文件在实现里的角色owcpa.cNTRU 的 OW-CPA 方案核心密钥生成、加密、解密poly_rq_mul_toom4_k2x2.c多项式乘法优化Toom-4 与 2x2 Karatsuba 混合poly_rq_mul_k2x4.c多项式乘法的另一种分块策略2 段 x 4 段crypto_sort_int32.c常数时间 int32 排序用于带重量约束的采样fips202.cFIPS 202SHA-3/SHAKE实现提供哈希与随机扩展rng.cNIST 规格的 AES-CTR DRBG负责 KAT 可复现随机序列PQCgenKAT_kem.cNIST KAT 生成读请求文件输出响应文件校验一致性test_owcpa.c加解密功能自测test_gp_compat.cgeneric/portable 版本与优化版本的兼容性比对speed.c密钥生成、封装、解封装的周期计时2.1 crypto_sort_int32.c常数时间排序到底在解决什么问题NTRU 族的私钥多项式通常要求“恰好有指定数量的非零系数”而不是随便生成。最直接的做法是生成一批随机数再反复拒绝直到满足重量约束但这会让运行时间依赖秘密值侧信道一眼看穿。更常见的做法是给每个位置挂一个随机标量按标量排序后取前 w 个下标作为非零系数位置crypto_sort_int32.c 提供的就是这种常数时间归并排序。/* 假设要生成重量为 w 的三元私钥多项式 f */ int32_t tagbuf[NTRU_N]; /* 每个位置挂一个随机标签按标签排序后取前 w 个下标 */ crypto_sort_int32(tagbuf, NTRU_N); for (int i 0; i NTRU_W; i) { uint16_t idx tagbuf[i] (NTRU_N - 1); /* 落到有效下标范围 */ f[idx] 1; }这块逻辑要说明两点crypto_sort_int32 排序的是“位置对应标签”而非系数本身归并排序在 int32 上每轮比较次数固定不因输入秘密值产生分支这是它被选中的核心理由。移植这段代码时常见的坑是换了平台后忘记检查 int32 回绕行为导致私钥重量差一两个系数表象就是偶发解密失败而不是完全解不开排查起来要费不少功夫。2.2 fips202.c 与 rng.cNTRU-397 为什么离不开 SHA-3 和 DRBGowcpa.c 只保证“单向”安全要把 NTRU 用成抗 CCA 的 KEM还要做 Fujisaki-Okamoto 变换加密前先用 SHAKE 把随机种子和明文搅在一起解密后再重新封装一遍判断密文是否一致。fips202.c 几乎是此类 KEM 的标准配置它提供的 SHAKE128/256 承担两个职能把随机种子扩展成多项式系数以及在 FO 变换里充当随机预言机。我读这类代码的习惯是先看 fips202.c 有没有被裁剪。如果保留了完整的 Keccak-f[1600] 轮函数说明做 KAT 时 SHAKE 输出和 NIST 参考实现一致不能为了速度把轮数改少否则 rsp 文件第一字节就会对不上。rng.c 则是 NIST PQC 统一规格的 AES-CTR DRBGPQCgenKAT_kem.c 每次运行都会先用固定种子初始化它再确定性生成密钥和密文。KAT 校验比对的就是这个确定性随机序列所以 rng 必须有 bit 级可重现性任何字节序改动都会让整个响应文件从头到尾错位。2.3 poly_rq_mul_k2x4.c 与 toom4_k2x2.c为什么一套方案放两个乘法文件在多项式环 Z_q[x]/(x^N-1) 上做乘法最慢的地方是卷积。对 N397 这种素数维度不能像 Kyber 那样直接上 NTTNTT 要求 N 能整除某个 2 的幂次还要在模 q 下存在原根而 NTRU 的 q 往往取 2 的幂。于是实现回到分治算法k2x4 与 toom4_k2x2 是同一问题的两个变体toom4_k2x2 把两个操作数分别切成 4 段和 2 段再做混合分治k2x4 则是不对称地切成 2 段与 4 段。两套乘法对外暴露相同的符号我在做基准时会用对象文件替换的方式来测而不是在源码里改函数指针# 方案A用 k2x4 版本参与链接 gcc -O3 -marchnative -c poly_rq_mul_k2x4.c -o poly_rq_mul.o # 方案B换成 toom4 版本重新编译其他文件不动 gcc -O3 -marchnative -c poly_rq_mul_toom4_k2x2.c -o poly_rq_mul.o两个文件不能同时进链接否则 poly_rq_mul 符号会冲突。用同一个目标文件名替换比维护两个 Makefile 变量省事得多。3. owcpa.c 核心流程密钥生成、加密、解密的环运算拆解owcpa 是 One-Way Chosen-Plaintext Attack 的缩写它是一层“裸”的公钥加密只防被动窃听不防主动篡改。NTRU-KEM 会在它上面再套 FO 变换所以 owcpa.c 里的三个函数有着非常清晰的边界owcpa_keypair 生成密钥owcpa_enc 加密owcpa_dec 解密。3.1 密钥生成与 NTRU 格密钥生成的第一步是选两个三元多项式 f 和 g系数落在 {-1, 0, 1}其中 f 在模 q 下可逆。公钥 h 由 h g · f^{-1} mod q 得到私钥是 (f, g)。整个过程在 R_q Z_q[x]/(x^N-1) 上完成求逆用扩展欧几里得算法随机字节经过采样后成为候选的 f、g不满足可逆条件就重新采样。三元系数的选择不是随意为之解密时要靠小系数多项式的卷积结果不碰 q 边界系数范围越大解密失败概率越高。这里有一个安全维度值得展开h 公开后攻击者要在已知 h 的情况下找一个短的 (f, g) 满足 g ≡ f·h (mod q)这等价于在由 h 构造的 NTRU 格中找短向量。N397 比 NTRU-HRSS 的 701 小不少密钥更短、运算更快但安全强度更依赖 q 和重量参数的精细配合。调大 N 或调大 q 都能提升安全性代价完全不同调 N 是平方级拖慢乘法调 q 只是线性增加系数位宽所以参数微调时优先动 q。3.2 加密与封装加密时拿到明文 m编码成三元多项式选一次性随机多项式 r计算 c r·h m (mod q)。这里的加法和乘法都在 R_q 上做换言之卷积结果要折叠回 N 个系数并逐系数模 q。符号含义典型规模N多项式环维度397q整数模数通常取 2 的幂2048 或 4096f, g私钥短多项式三元重量受限h公钥 h g·f^{-1} mod q稠密多项式r加密随机短多项式三元或小整数系数m明文三元多项式每系数在 {-1,0,1}c密文 c r·h m mod q系数在 [0,q)3.3 解密中心化取模才是关键解密端拿到密文 c 后第一件事是计算 f·c mod q展开来看f·c f·(r·h m) r·(f·h) f·m r·g f·m (mod q)因为 r、g、f、m 全是小系数多项式r·g f·m 的每个系数绝对值都远小于 q/2。此时只要把结果按中心化取模修回 (-q/2, q/2]卷积就不会触发 q 的折叠得到一个真实的整数多项式再逐系数 mod 3 就还原出明文 m。写成代码核心就是这一步/* 解密f*c mod q 后中心化到 (-q/2, q/2] */ for (int i 0; i NTRU_N; i) { int32_t v f0c_mod_q[i]; /* 中心化把区间从 [0,q) 搬到 (-q/2, q/2] */ if (v q / 2) v - q; if (v -q / 2) v q; /* 此时 v 是 r*g f*m 的真实整数系数未发生模 q 折叠 */ dec[i] (v % 3 3) % 3; }参数说明f0c_mod_q 是 f 和 c 卷积后已经取模到 [0,q) 的系数中心化阈值是 q/2边界上的系数会因取模方向产生一位差异所以参数选择必须让系数撞边界的概率远低于 2^{-128}。要估算余量可以看 r·g 和 f·m 的系数上界若 f、g、r、m 的非零系数个数分别为 df、dg、dr、dm 且都是 ±1那么单个系数的绝对值上界约为 min(df,dg) min(df,dm)这个值比 q/2 小得多才有安全余量。实现在设计时也会让 f 在模 3 意义下可逆解密时对 f mod 3 的处理就可以省略。3.4 为什么 owcpa 还要再套一层 KEMowcpa 本身不抗主动攻击攻击者翻转密文 c 的某些系数解密结果会变化这种 malleability 在真实协议里很容易被利用。上层 FO 变换的做法是封装时计算 (k, r) G(m, h)用 r 加密解封装时先解出 m再用同样的 G 重新生成 r 并重新加密与收到的密文对比不一致就返回失败。PQCgenKAT_kem.c 里能看到的就是这一层逻辑它在 owcpa 外面包了密文一致性校验把安全性提升到 IND-CCA2。4. 在 N397 的环上做乘法Toom-4 与 Karatsuba 的分治拆法N397 是个素数这意味着多项式乘法没法靠 NTT 一步到位也不适合直接套 16 点分块 SIMD。poly_rq_mul_toom4_k2x2.c 和 poly_rq_mul_k2x4.c 这两个文件的命名已经把“切几段”和“每段用什么算法”的组合关系写在里面了。4.1 朴素卷积与分治乘法的复杂度对比教科书式卷积对两个 N 项多项式需要 N^2 次乘加397 维下一轮乘法约 15.7 万次乘加解密要做若干次这样的乘法性能瓶颈非常明显。Toom-4 的思路是把多项式拆成 4 段通过求值、点乘、插值三步把两个四段多项式的乘法转换成 7 次小乘法加若干线性组合小乘法还可以递归使用 Karatsuba这就是 k2x4 里“2”和“4”并存的原因每次分裂都可以选择不同的段数。策略子乘法次数渐进复杂度适用场景教科书卷积164段 x 4段O(n^2)段长很短拆分无收益Karatsuba 2x23每段切 2O(n^1.585)中等长度代码结构简单Toom-47每段切 4O(n^1.404)N397 附近性价比最优Toom-3 的复杂度是 O(n^1.465)子乘法 5 次NTRU-397 选择 Toom-4 是因为段长接近 100 时7 次小乘法的额外求值/插值开销已经被摊薄综合成本低于 Toom-3。4.2 求值与插值的实现骨架Toom-4 选定求值点 0、1、-1、2、-2、∞ 后两个段多项式 A 和 B 各算 6 个点值这些点值来自段系数的加减和移位然后做 7 次短乘法再做线性插值还原出乘积的 7 段。伪代码可以这样理解/* NTRU-397 乘法骨架a 拆 4 段b 拆 2 段 */ int16_t a4[4][BSZ4], b2[2][BSZ2]; unpack_397_to_4x(a4, a); /* 每段约 99 项最后一段短 */ unpack_397_to_2x(b2, b); /* b 切成 2 段每段约 198 项 */ /* 求值在 0, 1, -1, 2, -2, inf 处得到组合值 */ eval_toom4(a4, A_ev, ev_pts); eval_karatsuba2(b2, B_ev, ev_pts); /* 7 次短多项式乘法 */ for (int i 0; i 7; i) short_mul(AB_ev[i], A_ev[i], B_ev[i]); /* 插值并折叠 mod x^397-1 */ interpolate_toom4(c, AB_ev);这里最容易出错的环节是最后的折叠。插值得到的乘积长度约为 793 项保存回 N397 之前必须做 mod (x^397-1) 的循环卷积折叠。折叠的本质是下标模 397 累加很多实现错在顺序先模 q 再折叠会丢失进位信息正确做法是先完成索引折叠、再对每个系数模 q。4.3 k2x4 与 toom4_k2x2 的取舍从命名推断k2x4 更适合公钥 h 稠密、随机多项式 r 相对稀疏的场景稠密操作数拆成 4 段充分并行稀疏操作数拆成 2 段减少无谓的子乘法toom4_k2x2 则更均衡两边的拆分粒度一致。实际选型不能凭感觉要看 speed.c 里 poly 操作的分项计时。需要提醒的是比较两个乘法实现时编译器标志必须完全一致-O3 和 -O2 的差异有时比两种分治算法的差距还大。5. 复现编译、KAT 回归与 speed.c 基准测试的完整流程把源码变成能在本机跑起来的程序是从“能看懂”跨到“能验证”的关键一步。包内没有现成 Makefile常见做法是手写一个最小构建脚本按功能拆成多个可执行文件。5.1 最小构建脚本CC ? gcc CFLAGS ? -O3 -stdc99 -Wall -Wextra -marchnative # 注意两个乘法实现只能二选一避免 poly_rq_mul 符号冲突 MUL_OBJ poly_rq_mul_k2x4.o # MUL_OBJ poly_rq_mul_toom4_k2x2.o OBJS fips202.o rng.o crypto_sort_int32.o owcpa.o $(MUL_OBJ) speed: speed.c $(OBJS) $(CC) $(CFLAGS) $^ -o $ PQCgenKAT_kem: PQCgenKAT_kem.c $(OBJS) $(CC) $(CFLAGS) $^ -o $ test_owcpa: test_owcpa.c $(OBJS) $(CC) $(CFLAGS) $^ -o $参数说明-marchnative 会把乘法里的移位和加法编译成当前 CPU 支持的指令KAT 结果不应因 CPU 不同而变化因为算法确定性speed.c 的周期数则会随 CPU 明显变化报告基准时必须注明 CPU 型号和编译器版本。owcpa.o 依赖两个乘法实现之一提供 poly_rq_mul 符号两个都编进来会直接链接失败。5.2 三条验证命令步骤命令预期结果基本连通./test_owcpa 10001000 轮加解密全部成功失败数为 0兼容性./test_gp_compatgeneric 版与优化版输出一致无 diffKAT 一致性./PQCgenKAT_kem sha256sum PQCkemKAT_*.rsprsp 文件哈希与基线一致第一次跑 KAT 前先把 rsp 文件存一份基线之后任何改动都以“rsp 无变化”作为回归通过的标准。我移植这类代码时rsp 的 diff 往往能精确定位到某个字节比如请求文件里某个作为密钥种子的字节多了一次移位多半是 rng.c 或采样函数对字节序的处理与原实现不一致。这类问题用 log 排查效率极低直接 diff 两个 rsp 文件一眼就能看出错位起点。5.3 speed.c 给出的优化目标speed.c 通常对 keypair、enc、dec 分别计时。NTRU-397 这类小维度参数下enc 和 dec 应该在几万到几十万周期量级具体看乘法实现keypair 因为有求逆运算会显著更慢。优化时先跑一遍得到基线再替换 MUL_OBJ 重新编译对比 dec 周期变化。如果换了乘法实现后 KAT 也变了那不是性能优化是引入了 bug先别管速度回到 6.1 的 KAT 回归排查。6. 换乘法实现后如何用最小代价自检 NTRU-397改一个乘法文件、换一个编译器版本或者换一台 CPU对 NTRU 实现来说都不算大改动但它足以让解密失败率从数学上可忽略变成实际报错。最小自检路径我推荐三步KAT 回归、系数余量断言、带统计的随机测试。6.1 把 KAT 的 rsp 当作唯一真值替换乘法实现之前先跑一次原始版本保存 rsp 基线./PQCgenKAT_kem sha256sum PQCkemKAT_*.rsp baseline.sha # 替换 poly_rq_mul_k2x4.c 为 poly_rq_mul_toom4_k2x2.c 后重新编译 ./PQCgenKAT_kem sha256sum -c baseline.sha如果哈希不一致优先检查两个位置一是插值后的环折叠顺序二是中心化取模的边界方向。分治实现在这两个环节最容易写反而且是那种“10 次里有 1 次错”的隐蔽 bug普通自测很难触发。6.2 在解密端加一行系数范围断言运行时开销几乎可以忽略的检查是在 owcpa_dec 里记录中心化后的最大系数与 q/2 比较看余量还有多少。int max_coef 0; for (int i 0; i NTRU_N; i) { int32_t v center(fc[i]); /* 中心化到 (-q/2, q/2] */ if (abs(v) max_coef) max_coef abs(v); dec[i] mod3(v); } if (max_coef q / 4) printf(dec margin warning: %d/%d\n, max_coef, q / 2);这个打印值直接反映当前参数离解密失败边界有多远。如果 max_coef 长时间接近 q/2先检查随机多项式 r 的采样重量是不是被翻倍了而不是急着调 q。重量翻倍会让 r·g 的系数上界线性上升是这类警告最常见的触发原因。6.3 把两份对象文件放同一张基准表里比最后把两种乘法的速度结果并列记录而不是先后记两个数。清掉构建目录分别用 k2x4 和 toom4_k2x2 各构建一次跑 5 次 speed 取中位数对比 dec 周期。如果两个版本差距在 2% 以内固定用代码可读性更好的那版长期维护只有差距超过 10% 时才值得为“快版”多维护一套乘法代码。用数据而不是第一印象选实现改完代码顺手把 rsp 哈希留在提交信息里下次任何人动到乘法层都能直接跑回归确认没有破坏正确性。本文还有配套的精品资源点击获取