4. 后量子密码常数时间实现原则

后量子密码（PQC）算法在数学结构上与传统公钥算法差异很大，但其实现层面的侧信道风险来源并没有改变：只要程序的控制流、内存访问地址或执行指令序列与秘密数据相关，攻击者就可能通过时间、缓存、功耗或电磁等旁路恢复秘密。常数时间实现的目标不是让程序“跑得一样快”，而是让可被观测的行为不依赖秘密。本节围绕分支、内存访问、指令选择和编译器优化四条主线，说明秘密相关行为如何产生，并给出一套可落地的编码规范。

一、分支：控制流泄漏的第一来源

最典型的问题是“秘密相关的条件跳转”。例如在 Kyber 的 NTT 或多项式采样中，若写成 if (coeff >= Q) coeff -= Q;，则是否执行减法取决于 coeff，而 coeff 往往由秘密多项式决定。攻击者通过大量计时样本，可以统计出该分支被执行的频率，进而推断秘密分布。类似地，if (bit == 1) ... else ... 在密钥生成、解封装失败判断、拒绝采样中都很常见。

常数时间原则要求：用算术或位运算替代条件跳转。例如模约减可写成掩码形式：

// 非常数时间
if (a >= Q) a -= Q;

// 常数时间：掩码选择
uint32_t mask = -(uint32_t)(a >= Q);   // 全 0 或全 1
a -= Q & mask;

这里 a >= Q 的比较结果被转换为 0/1，再取负得到全 0 或全 1 掩码，减法是否生效由掩码决定，但指令序列固定。注意：比较本身在多数平台上编译为 setcc 等无分支指令，但若编译器把 a >= Q 优化回分支，则前功尽弃，因此必须结合编译器约束一起考虑。

二、内存访问：缓存与地址依赖

即使没有分支，若数组下标与秘密相关，也会通过缓存行、页表或预取行为泄漏。典型场景包括：S 盒查表、按秘密索引的置换表、以及 Kyber/Dilithium 中按系数值访问的预计算表。攻击者利用 Prime+Probe 或 Flush+Reload 可以判断某个缓存行是否被访问，从而缩小秘密候选范围。

常数时间实现要求：访问地址与秘密无关。常见做法有三类：

• 全表扫描：无论秘密为何，都遍历整张表，用掩码选出目标项。代价是 O(n) 而非 O(1)，但地址序列固定。
• 位切片/算术化：把查表替换为等价的布尔或算术运算，彻底消除数据相关地址。
• 固定置换：若必须使用置换，则让置换顺序与秘密无关，秘密只影响被置换的数据内容。

以“按秘密索引取 256 字节表”为例，常数时间写法如下：

uint8_t ct_lookup(const uint8_t table[256], uint8_t idx) {
    uint8_t r = 0;
    for (int i = 0; i < 256; i++) {
        uint8_t m = (uint8_t)-(i == idx);  // 全 0 或全 1
        r |= table[i] & m;
    }
    return r;
}

该函数对每个 i 都读取 table[i]，地址序列与 idx 无关。实际工程中若表较大，可结合缓存行对齐与预取策略，但核心仍是“地址不依赖秘密”。

三、指令选择：乘法、除法与可变延迟指令

不同指令的延迟可能不同。整数乘法、除法、取模在部分架构上延迟随操作数变化；浮点运算、sqrt、div 尤其危险。PQC 中大量使用模乘、模逆和 NTT 蝶形运算，若直接使用 % 或 /，可能引入数据相关延迟。

常数时间原则要求：优先使用固定延迟指令，避免可变延迟指令。例如模逆可用费马小定理的固定指数幂实现，或使用常数时间扩展欧几里得；模约减用 Barrett/Montgomery 归约替代除法。对于必须使用的除法，应确认目标平台指令延迟是否恒定，必要时用乘法加移位模拟。

四、编译器优化：最容易被忽视的破坏者

即使源码写得“看起来常数时间”，编译器仍可能把掩码选择优化回分支，或把全表扫描优化成提前退出。常见破坏包括：-O3 下的循环展开与向量化改变访问顺序、if 被识别为可预测分支、以及 memcmp 被替换为提前返回的实现。

应对策略是：使用 volatile 阻止过度优化、使用编译器屏障、在关键函数上关闭特定优化，或使用经过审计的常数时间原语库。工程上建议对关键函数做反汇编检查，确认没有秘密相关跳转和地址计算。

五、常数时间编码规范（可执行清单）

把上述原则固化为编码规范，才能在团队协作和长期维护中保持一致性。以下清单可直接用于代码评审：

六、一个可复现的验证思路

规范落地后需要验证。常用方法是 dudect 类统计检验：对同一函数输入固定秘密与随机秘密两组数据，采集大量执行时间样本，用 Welch t 检验判断两组分布是否可区分。若 |t| 值长期低于阈值（如 4.5），说明未发现显著时间依赖；若显著，则回到反汇编定位秘密相关跳转或地址计算。示例流程如下：

# 示例：dudect 风格检验（伪代码）
for i in range(N):
    cls = random_bit()
    t0 = rdtsc()
    ct_function(secret if cls else fixed)
    t1 = rdtsc()
    samples[cls].append(t1 - t0)
t = welch_t_test(samples[0], samples[1])
assert abs(t) < 4.5   # 未发现显著时间泄漏

需要强调：通过统计检验不等于绝对安全，它只能排除已观测到的时间依赖；缓存、功耗和电磁仍需结合平台特性单独评估。常数时间实现是一项持续工程，而不是一次性的代码改写。

综上，PQC 常数时间实现的核心是让控制流、内存地址和指令延迟三者都与秘密解耦。分支用掩码消除，内存用全表扫描或算术化替代，指令选择固定延迟路径，编译器用屏障和审计约束。把这四条原则写成规范并配合统计验证，才能在实际部署中真正降低侧信道风险。