7.2 常量时间与性能优化

7.2 常量时间与性能优化

同一个 ML-KEM，参考实现与向量优化实现的吞吐能差一个数量级，而任何一处密钥相关分支都可能把安全清零。本节讲两件必须同时做到的事：快（数论变换、SIMD、压缩的快速算法）与稳（常量时间编码的红线清单），并给出主流库的生态对照。

承接 7.1 节：参数选定了，代码从哪来、怎么审。本节是第 6 章侧信道案例的工程续篇，也是 7.3 节真实流量迁移的前提——没有经过验收的实现不配上生产。

快从哪来：三台发动机

发动机一，数论变换（NTT）。第 4 章说过环乘是卷积折叠，朴素做法 N^2 次乘法；NTT 把系数域搬到"原根的世界"做点乘，复杂度降到 N \log N。N=256 时是 2048 次对 2560 次的差距不大，但 N=1024 及以上（签名场景）差距拉开到 10 倍以上。模数的选择在此兑现：3329 - 1 含 256 的因子，所以 256 点 NTT 原根存在——4.1 节那笔"怪数字账"的兑现处。发动机二，SIMD 向量化：AVX2/Neon 一条指令并行处理 8 到 16 个系数，蝴蝶运算、采样、压缩全都可以向量化，主流 AVX2 实现相对参考实现快 4 到 8 倍。发动机三，压缩的乘移化：把 \lfloor x \cdot 2^{d_u} / q \rceil 这类除法改写成乘常数加移位——这既是优化也是安全修复（6.3 节 KyberSlash 的坑正是它没做对）。

性能的量级感给三笔：桌面 AVX2 实现的 ML-KEM-768 封装与解封装在数万周期量级（约十几微秒）；Cortex-M4 级微控制器落在几十万周期量级，适合物联网端点；ML-DSA-44 签一份约在几十万到百万周期量级，验证更快。跨库跨机型差异很大，引用任何性能数字都要带口径——这是本章反复出现的纪律。

稳从哪来：常量时间红线清单

常量时间的定义一句话：程序的执行轨迹（分支走向、内存地址、指令选择）不依赖秘密数据。落到清单，五条红线：

红线一: 密钥相关的 if 与 switch —— 一律改算术掩码
        例: 条件交换 a,b 改为 mask = -(a^b 为真); a,b = b^mask&(a^b), a^mask&(a^b)
红线二: 以密钥为下标的查表 —— 换成无查表的算术路径（Kyber 已是纯算术，签名需自查）
红线三: 密钥相关的除法与取模 —— 改乘常数加移位（KyberSlash 的修复点）
红线四: 提前返回与早停循环 —— 签名的"作废重签"次数也要恒定
红线五: 编译器的优化越权 —— 关自动向量化于敏感循环，或用密码学专用后端
​

每条红线都有对应的机器审计工具（计时对比、源码污点分析、符号执行的常量时间验证器），大型库把它们挂进持续集成；前沿项目更进一步用形式化验证把实现与规约的等价性做成机器可查证明。开发者的务实姿势：首选经过审计的成熟库，自己写的实现只用于学习。学习时的正确打开方式也顺带交代：先读参考实现的密钥生成与解封装两段，对照第 4 章的迷你 Kyber 找到每个变量的对应物，再看优化层如何把同一段逻辑向量化——这条阅读路径能省掉一半的迷路时间，比直接硬啃优化代码高效得多。

NTT 的手感：十六点走一遍

把数论变换从名词变成手感，最小可行规模是 16 点。原理与快速傅里叶同构：把 256 点多项式按系数奇偶劈成两半，递归到单点，再合并——每一层做"蝴蝶"运算 c = a \pm \omega^k b（模 q）。256 点共八层、每层 128 只蝴蝶，总计 1024 次模乘加，对比朴素的 65536 次系数乘，加速 64 倍。Kyber 的优化实现把蝴蝶向量化（一条 AVX2 指令四只蝴蝶）、把旋转因子表预计算进缓存友好的排布，叠加起来就是"参考实现比优化实现慢一个数量级"的去向。动手党可以把四点 NTT 写在纸上：两层、四只蝴蝶、手算完全可行——做完这一遍，性能调优文档里的"层次排布""原根幂表"都不再是黑话。

性能验收还有一条容易被忽略的维度：内存与缓存的账。ML-KEM 的私钥 2400 字节（768 档）恰好横跨数个缓存行，频繁的密钥访问在多租户环境里会与邻居负载互相干扰；高吞吐网关通常把密钥驻留与握手运算做亲和性绑定，把缓存未命中从两位数百分比压到个位数——这是纯工程收益，不碰任何密码学假设，也是性能评审会上最先该问的一行。

库生态对照

选库两问：问维护主体（是否有持续审计与响应记录，6.3 节的补丁速度就是检验）；问验证深度（过没过已知答案测试与常量时间审计，有没有第三方报告）。7.3 节的迁移实战将直接从 TLS 栈的内置能力出发。

动手：一次最小验收

在集成前跑一组最小检查，命令式验证实现"像不像话"：

步骤一 已知答案测试: 导入官方测试向量，逐字节比对输出
步骤二 随机一致性: 生成百组随机密钥对，加解密全回路成功率必须为百分之百
步骤三 失败注入: 手工翻转密文一比特，解封装必须显式失败而非输出错误明文
步骤四 计时扫描: 固定明文翻转密钥比特重复计时，分布差异应不显著
步骤五 版本锁定: 记录库版本与编译参数，升级时回归全部四步
​

步骤四在家中只能做粗筛——Hertzbleed 式的泄漏要专业设备——但"粗筛也比不筛强"：KyberSlash 最初的复现脚本不过几十行。把验收做成流水线的一部分，而不是上线前的仪式。

要点速记：性能三发动机是 NTT、SIMD、压缩乘移化，参考与优化实现差一个数量级；常量时间五条红线每条都有真实事故背书；选库先问维护与审计记录，自研只用于学习；最小验收五步应进持续集成，粗筛早于上线。

参数与实现就绪，下一节把引擎装进协议：真实 TLS 流量里的混合密钥交换，逐字节拆给你看。