简介NTRU-397加密算法实现包面向密码学学习者和安全开发人员基于NTRU公开密钥加密体制提供完整的C语言源码、头文件与Python辅助脚本覆盖参数生成、密钥生成、加密和解密四个核心环节。资源共500个文件压缩包整体仅274KB分布上以255个.c源文件、130个.h头文件、82个.py脚本为主另有makefile和makefile-nist构建脚本、sh工具及license说明便于直接用于课程设计、后量子密码研究或安全原型开发。已有316人学习下载。包内代码还包含PQCgenKAT_kem、owcpa、rng、speed等测试与性能评估程序可辅助验证NTRU-397多项式环运算的正确性帮助使用者快速理解算法参数设置与实现细节并为后续优化、移植或二次开发提供清晰的代码基线。1. NTRU-397把格密码压进一个 397 次多项式环NTRU 是少数几个“先有高效实现、后有完整安全论证”的公钥加密家族1996 年公开时演示代码已经能跑而基于格的安全归约又过了好几年才补上。像 ntru-master 这类仓库里常见的 NTRU-397参数核心就是把截断多项式环的次数 N 固定在 397397 是素数配合模 3 和模 2048 的双模运算可以在代数结构上避开一些简化格攻击。这篇文章要解决的问题很具体NTRU-397 到底在算什么、为什么解密偶尔会失败、参数怎么调才稳。我从代数定义开始用纯 Python 把密钥生成、加密、解密的最小闭环跑通再针对解密失败率做实验最后给出三个不依赖复杂工具的验证技巧。适合要做 PQC 方案评估的工程师、审计第三方密码库的研发以及想在课程设计里真正“动过手”的研究生。2. NTRU-397 的代数底座截断多项式环、双模数与中心提升2.1 环乘法为什么是循环卷积NTRU 所有计算都发生在商环 R Z[x]/(x^397 - 1) 里。所谓“截断”是指两个长度最多 397 的多项式相乘后凡是次数不低于 397 的项都按 x^397 1 折叠回 0 到 396 次。于是 R 中的乘法等价于一次被 397 索引的循环卷积(a·b)k Σ{ij≡k (mod 397)} a_i·b_j用程序实现时这比格的矩阵运算便宜得多只需要两层循环逐项累加再对下标取模。这里的代数现象是如果 N 是合数商环 R 会分裂出多个因子环攻击者可以把多项式表示分解到更小的子空间中降维而 N397 为素数时x^397-1 只分解为 Φ_1(x)·Φ_397(x)Φ_397 是不可约分圆多项式这让格攻击面对的子格更规则、更难简化。2.2 用 SageMath 检查 N397 下的可逆性密钥生成的第一步是找一个同时模 3、模 2048 都可逆的小多项式 f。直接对 2048 做多项式扩展欧几里得并不方便常见做法是先看它在模 2 的有限域上是否可逆——这只要在 GF(2)[x] 上做一次 xgcdN, Q 397, 2048 F2 GF(2) R2.x PolynomialRing(F2) def f_invertible_mod2(f_coeffs): # 只保留每个系数的奇偶性 f2 R2([int(c) 1 for c in f_coeffs]) g, _, _ R2.xgcd(f2, x^N - 1) return g 1这里 g 等于 1 说明 f 在 GF(2) 上可逆。因为模 2048 可逆一定蕴含模 2 可逆所以这一步可当作预筛选不过就直接换一组候选 f省得进到代价更贵的模 2048 逆元计算里。在继续之前先把 NTRU-397 这组演示参数的取值和行为看对参数表如下符号演示取值在 NTRU-397 里的作用N397多项式次数直接决定格维度和私钥大小p3明文模数消息系数来自{-1,0,1}q2048密文模数取 2 的幂以方便逆元提升df133私钥 f 中1和-1的数量约 N/3dg133多项式 g 中非零项数量dr133加密盲化多项式 r 中非零项数量df、dg、dr 取 N/3 附近是 NTRU 家族一直以来的构造习惯。它们并不独立df 越大解密容噪能力越好但私钥范数变大攻击者从公钥 h 恢复 f 的格攻击也更有利dr 越大盲化越强加密安全性更好但同样会把噪声顶到解密边界。后面第 4 章会专门讨论这种对冲。2.3 中心提升解密正确性的隐形支柱中心提升center-lift是 NTRU 里最容易被忽略、却最容易写错的一步。解密过程中我们算出的其实是“模 q 的多项式”但下一步要对每个系数取模 p。如果系数停在 0 到 q-1 的无符号区间里结果会系统性出错。看一个具体例子q2048某个系数的真实整数取值是 -2但它在模 q 下的表示是 2046。若直接对 2046 取模 3得到 0而正确流程是先中心提升为 -2再取模 3得到 1。加密侧的消息和盲化多项式都带负系数所以从第一轮乘法开始就必须用有符号表示处理中间值最后再统一% q。换句话说中心提升的作用是把 Z/qZ 的陪集映射到(-q/2, q/2]这段“最接近零”的范围内。只有这样之后“模 q 下的计算”和“整数上的计算”才能对上。它同时给出了解密正确性的一个直观判断标准只要 f·e 的每个系数的实际整数绝对值不超过 q/2中心提升就不会丢信息解密就不会出错。3. 用纯 Python 把 NTRU-397 的密钥生成和加解密跑通3.1 最小环运算集合下面的mul_ring实现 R Z[x]/(x^397-1) 里的乘法它不取模只做次数折叠。center_lift负责把模 Q 的结果还原成有符号整数。N, P, Q 397, 3, 2048 DF DG DR 133 def mul_ring(a, b): Z[x]/(x^N-1) 中的乘法不约模 c [0] * N for i, ai in enumerate(a): if ai 0: continue for j, bj in enumerate(b): c[(i j) % N] ai * bj return c def center_lift(v, qQ): 把模 q 的系数映射到 (-q/2, q/2] return [(x % q) - q if (x % q) q // 2 else x % q for x in v]参数说明mul_ring使用普通 list 而不是 numpy是为了让环结构直观可读外层 i 枚举 a 的项内层 j 枚举 b 的项目标下标是 (ij) 对 N 取模。N397 时这个两重循环足以支撑千轮测试要上生产环境再换成 Karatsuba 或 NTT 变体。3.2 用 Hensel 提升从模 2 走到模 2048再得公钥 hSage 里一条 xgcd 就能在多项式环上算逆元但工程里的常见做法是“先求模 2 逆再用牛顿迭代把精度翻倍”。一次迭代满足若当前 b 使 fb ≡ 1 (mod 2^k)则 b b(2-fb) 使 fb ≡ 1 (mod 2^{2k})。这个迭代每轮代价是两次环乘法N397、q2048 时只要 11 轮。下面的代码先给出 GF(2) 上的多项式除法与扩展欧几里得用整数位表示系数第 i 个 bit 就是 x^i 的系数。GF(2) 中加法等于异或所以除法可以直接用异或完成。def poly_divmod_f2_bits(a, b): GF(2)[x] 中的除法输入输出都是整数 if b 0: raise ZeroDivisionError(divide by zero polynomial) q, r 0, a db b.bit_length() while r and r.bit_length() db: shift r.bit_length() - db q ^ (1 shift) r ^ (b shift) return q, r def poly_xgcd_f2_bits(a, b): GF(2)[x] 上的扩展欧几里得返回 (gcd, s, t) r0, r1 a, b s0, s1, t0, t1 1, 0, 0, 1 while r1: q, r poly_divmod_f2_bits(r0, r1) r0, r1 r1, r s0, s1 s1, s0 ^ (q * s1) t0, t1 t1, t0 ^ (q * t1) return r0, s0, t0 def fold(v, NN): 在 GF(2) 环中按 x^N 1 折叠次数 mask (1 N) - 1 return (v mask) ^ (v N) def poly_inv_mod_q(a_list, NN, QQ): 求 a 在 (Z/qZ)[x]/(x^N-1) 中的逆元 bits 0 for i, c in enumerate(a_list): if c 1: bits | (1 i) g, inv_bits, _ poly_xgcd_f2_bits(bits, (1 N) | 1) if g ! 1: raise ValueError(f is not invertible mod 2) inv [(fold(inv_bits) i) 1 for i in range(N)] modulus 2 while modulus Q: modulus 1 a_mod [c % modulus for c in a_list] prod mul_ring(a_mod, inv) factor [(2 - p) % modulus for p in prod] inv [x % modulus for x in mul_ring(inv, factor)] return [x % Q for x in inv]逻辑说明poly_xgcd_f2_bits在 GF(2)[x] 中把 a 和 x^N1即 x^N-1做扩展欧几里得返回的 s 就是 a 的逆由于 x^N-1 可约这一步必须靠 xgcd 而不是简单的幂运算。poly_inv_mod_q里每一轮迭代都把modulus翻倍直到 2048先计算 a·inv 在商环中的值再用2 - prod做牛顿修正。中间所有系数都做过% modulus防止整数无限增长。有了逆元密钥生成就很直接了。为了让解密不需要额外算模 3 的逆这里采用经典构造 f 1 3Fimport random def random_trinary(npos, nneg, rngrandom): 生成恰好含 npos 个 1、nneg 个 -1 的三元多项式 coeffs [0] * N pos rng.sample(range(N), npos nneg) for idx in pos[:npos]: coeffs[idx] 1 for idx in pos[npos:]: coeffs[idx] -1 return coeffs def keygen(rngrandom): while True: F random_trinary(DF, DF, rng) f [(1 3 * c) % Q for c in F] try: finv poly_inv_mod_q(f) break except ValueError: pass g random_trinary(DG, DG, rng) h [(3 * c) % Q for c in mul_ring(finv, g)] return f, g, h参数说明f的每个系数形如“1 3c”c 取自{-1,0,1}所以 f ≡ 1 mod 3 永远成立解密时不需要再乘 f 模 p 的逆。h 3·f^{-1}·g mod q系数被压回 0 到 2047在 q 这个模数下h 的 1995 位左右信息就是公钥。3.3 加密、解密与闭环自测加密端选一个同样稀疏的三元多项式 r计算 e r·h m 后模 Q。消息 m 直接用系数在{-1,0,1}里的向量表示不做字节填充这样最小闭环里没有额外编码干扰。def encrypt(m, h, rngrandom): r random_trinary(DR, DR, rng) e mul_ring(r, h) return [(e[i] m[i]) % Q for i in range(N)] def decrypt(e, f): a center_lift(mul_ring(f, e)) return [c % P for c in a] def untrit(c): 把模3结果 {0,1,2} 映射回 {-1,0,1} return 0 if c 0 else (1 if c 1 else -1) # 200 轮随机消息自测 for _ in range(200): m [random.choice([-1, 0, 1]) for _ in range(N)] c encrypt(m, h) m2 [untrit(x) for x in decrypt(c, f)] assert m2 m, decryption failed代码逻辑解密端先算 f·e中心提升到有符号整数再对每个系数取模 3。因为 f ≡ 1 mod 3模 3 后直接就是 m 的系数untrit只是把 Python 取模得到的 2 还原成 -1。200 轮循环里只要有一轮失败断言就会立刻报错这比打印“OK”可靠得多。4. NTRU-397 解密失败率从哪来df、dr 与 q 的调参实验4.1 解密失败的唯一边界噪声超出 q/2把加密表达式代入解密过程会得到f·e f·(r·h m) 3·r·g f·m (mod q)等号右边是一个整数多项式解密能否成功取决于它的每个系数在经过中心提升后能否无歧义地映射回整数。唯一需要担心的就是某个系数的绝对值超过 q/2。一旦超过模 q 的表示和整数表示之间会差一个 q 的倍数而这个倍数对模 3 的结果没有确定的贡献解密就可能翻车。所以“解密失败”不是随机比特错误而是一个可预测的边界条件。用下面的函数可以观察每一轮的噪声余量def noise_margin(f, g, m, r, qQ): t1 mul_ring(r, g) # r*g t2 mul_ring(f, m) # f*m vals [3 * t1[i] t2[i] for i in range(N)] margin q // 2 - max(abs(v) for v in vals) return margin参数解读margin大于 0 表示该轮所有系数都在安全区小于 0 说明进入了失败风险区。注意这里t1里 g 有 2·dg 个非零项r有 2·dr 个非零项两者卷积后的单个系数最大可能达到 min(2dg, 2dr) 量级再乘 3才是噪声的主体。f·m的贡献相对小但 df 太大时同样会推高整体量级。4.2 调参表哪一头松了另一头就紧了实践里最常见的错误是把 df、dr 调到很小来提升性能结果解密失败率立刻可见。反过来盲目加大 df 又会放大私钥范数降低抵抗格攻击的安全余量。可以用参数表记住不同变量的作用方向参数调大后的影响调大后的代价df解密余量变大失败率下降私钥范数变大格攻击者更容易接近 fdg噪声项 3·r·g 变大失败率上升g 的熵变大对生成器要求更高dr盲化增强加密安全性上升噪声项 3·r·g 变大失败率上升q解密边界变宽失败率显著下降公钥、密文和所有中间结果都变大这四组关系里df 和 dr 的方向相反是最需要小心权衡的。我在实验里通常会固定 N、q然后扫描 df 和 dr从较小值开始每档跑上千轮看noise_margin是否出现过负值。NTRU-397 在 dfdr133、q2048 时相当稳如果 q 减到 1024噪声边界直接砍半大量随机消息就会开始暴露失败。4.3 在 KEM 层用 FO 变换收敛失败NTRU 设计上不可能把解密失败率压到完全为零因为要在安全余量和性能之间取平衡。标准做法不是在算法层消除失败而是在 KEM 层把失败显式暴露出来。Fujisaki-Okamoto 变换的思路是加密时用哈希函数把随机盲化多项式 r 绑定到消息 m 上解密后重新加密一次比对不相等就返回失败。def kem_encaps(pk, m): r hash_to_trinary(m, pk) # 确定性地生成 r c encrypt(m, pk, r) return c, kdf(m) def kem_decaps(sk, c, pk): m decrypt(c, sk) r hash_to_trinary(m, pk) c2 encrypt(m, pk, r) if c2 ! c: return None # 封装失败外部应重试或终止 return kdf(m)逻辑说明FO 变换的核心价值是把“解密失败”从内部错误变成协议层可见的拒绝。c2 ! c的判断必须逐系数比较不能只在哈希层面比较否则某些中间差错会被掩盖。NTRU 系列提交到标准化流程的构造里也普遍采用这个外壳所以自己实现时不要省掉这一层。5. 验证 NTRU-397 实现的三个实用排错技巧5.1 用公钥一致性检查定位密钥生成错误def check_key(f, g, h): lhs [x % Q for x in mul_ring(f, h)] rhs [(3 * c) % Q for c in g] return lhs rhs这个检查的原理来自 h 的定义f·h ≡ 3g mod q。如果密钥生成里混错了finv或g这一步会立刻暴露。注意mul_ring(f, h)返回的是未约模的整数系数先对 Q 取模再和 3g 比对。这一步比直接跑加密解密更快也更容易定位。5.2 用固定随机种子复现故障轮rng random.Random(20240117) f, g, h keygen(rng) m [rng.choice([-1, 0, 1]) for _ in range(N)] c encrypt(m, h, rng)把随机源从全局random换成random.Random(seed)之后任何一条失败消息都可以完整复现。出现解密失败时不要急着调参数先用这组种子把失败的 m 和当时的 r 存下来再看noise_margin是否真的接近边界。这比盲改 df 高效得多。5.3 用零消息探针快速判断参数是否可用加密一个全零消息时解密中间值只剩 3·r·g 这一项。此时判定条件简化为 max|3·(r·g)_k| q/2等价于 max|(r·g)_k| q/6。用零消息做筛选能在不构造真实业务消息的情况下快速判断一组参数是否“处于崩溃边缘”def zero_msg_probe(g, dr, rngrandom, qQ): r random_trinary(dr, dr, rng) n mul_ring(r, g) return max(abs(c) for c in n) q // 6zero_msg_probe返回 True 时说明仅加密盲化噪声就可能顶破边界。这个测试消耗极小特别适合在调整 q 或 dr 后做冒烟回归。它虽然严格于真实消息却能把最危险的参数组合先筛掉是我换新参数前必跑的一关。本文还有配套的精品资源点击获取