4. 逐字节异或：常数时间比较的经典实现——异或累加法
好了，前面我们聊了那么多理论，现在该上手写真正的代码了。
这一章要讲的，是常数时间比较里最经典、最常用的实现方式——异或累加法。说白了，就是把两个字节数组逐字节做异或，然后把所有结果累加（或按位或）起来，最后检查累加值是不是零。
为什么异或能用来做比较？因为 a XOR b 只有在 a 和 b 完全相等时才等于 0。你想想看，只要有一个字节不同，异或结果就不是 0，累加和自然也不是 0。这个逻辑简单到令人发指，但恰恰是这种简单，保证了它能在常数时间内完成。
4.1 核心原理：异或的数学性质
先复习一下异或的几个基本性质：
- 自反性：
a XOR a = 0—— 自己跟自己异或，结果一定是 0。 - 交换律：
a XOR b = b XOR a—— 顺序不影响结果。 - 结合律：
(a XOR b) XOR c = a XOR (b XOR c)—— 可以任意分组。
基于这些性质，我们可以推导出：如果两个数组 A 和 B 长度相同，且每个对应字节都相等，那么 A[0] XOR B[0] 到 A[n-1] XOR B[n-1] 全部为 0，累加结果自然也是 0。只要有一个字节不同，累加结果就非零。
核心结论：异或累加法的正确性完全依赖于异或的自反性。这是整个算法的数学根基。
4.2 经典实现：C 语言版本
我个人习惯用 C 语言来写这类底层函数，因为 C 能精确控制内存访问和指令执行。下面这个实现，是我在多个项目中反复打磨过的版本。
#include <stdint.h>
#include <stddef.h>
/* 常数时间比较：逐字节异或累加法 */
int constant_time_compare(const uint8_t *a, const uint8_t *b, size_t len) {
uint8_t result = 0;
size_t i;
for (i = 0; i < len; i++) {
result |= a[i] ^ b[i];
}
/* 返回 0 表示相等，返回非 0 表示不等 */
return (int)result;
}
嗯，这里要注意几个关键点：
- 使用
uint8_t：确保每个字节都是无符号 8 位整数，避免符号扩展带来的意外。 - 使用
|=累加：按位或操作不会溢出，而且能保留所有差异信息。如果用+=，理论上可能溢出（虽然实际中很少发生），但|=更安全。 - 循环次数固定：循环执行
len次，不提前退出。这是常数时间的关键。
小技巧：如果你需要返回布尔值（0/1），可以用 !!result 来归一化。但注意，!! 在某些编译器上可能被优化成条件分支，所以最好保持原样返回，让调用方自己判断。
4.3 为什么用 |= 而不是 +=？
这个问题我经常被问到。其实两种方式在大多数情况下都能工作，但 |= 有几个明显的优势：
| 特性 | |=（按位或） |
+=（加法） |
|---|---|---|
| 溢出风险 | 无溢出 | 可能溢出（uint8_t 范围 0-255） |
| 信息保留 | 保留所有差异位 | 可能因溢出丢失信息 |
| 编译器优化 | 通常映射到简单 OR 指令 | 可能被优化成条件分支 |
| 可读性 | 意图明确：累积差异 | 容易误解为计数 |
我在项目中遇到过一个问题：用 += 实现时，某个编译器把加法优化成了 SIMD 指令，结果因为对齐问题导致段错误。换成 |= 后，编译器生成了更保守的代码，问题就解决了。所以我现在一律用 |=。
4.4 避坑指南：常见错误
我曾经在代码审查中看到过不少新手犯的错误，这里列几个典型的：
- 提前退出：在循环里加
if (result != 0) break;—— 这直接破坏了常数时间性质。 - 使用
memcmp：标准库的memcmp通常不是常数时间实现的，它会在找到第一个不同字节时立即返回。 - 类型错误：用
int或char存储异或结果，可能导致符号扩展或未定义行为。 - 长度不一致：如果两个数组长度不同，直接比较会出问题。我一般会先比较长度，如果长度不同直接返回不等。
警告：永远不要假设编译器会保留你的常数时间意图。某些激进优化（如循环展开、向量化）可能改变执行路径。建议在关键代码处加 volatile 或使用编译器屏障来防止优化。
4.5 知识体系：异或累加法的核心逻辑
下面这张图，把整个算法的流程和关键决策点都画出来了。我建议你仔细看看，尤其是「累加方式」那个分支——选错了，常数时间性质就可能打折扣。
4.6 扩展：处理长度不一致的情况
实际应用中，两个数组的长度可能不同。这时候直接逐字节比较会出问题。我的做法是：
int constant_time_compare_safe(const uint8_t *a, size_t len_a,
const uint8_t *b, size_t len_b) {
/* 先比较长度，结果存入 result */
uint8_t result = (len_a != len_b);
/* 取较小长度进行逐字节比较 */
size_t min_len = (len_a < len_b) ? len_a : len_b;
size_t i;
for (i = 0; i < min_len; i++) {
result |= a[i] ^ b[i];
}
/* 如果长度不同，result 已经非零；如果长度相同，result 反映字节差异 */
return (int)result;
}
这里有个细节：result = (len_a != len_b) 这个赋值本身是常数时间的——它只是一个比较指令，没有分支。但要注意，某些编译器可能把 != 编译成条件跳转，所以最好用位运算来替代：result = (len_a ^ len_b) != 0 或者直接用 result = (len_a ^ len_b) >> 8 之类的技巧。不过说实话，在大多数现代编译器上，直接写 != 是安全的。
个人经验：我在一个密码学库中看到过一种更激进的写法——把长度也当作字节数组的一部分来比较。具体做法是把 len_a 和 len_b 拆成 4 个字节，然后跟数据字节一起异或累加。这样连长度比较都融入循环里了，进一步减少了侧信道信息泄露。
4.7 性能考量：真的「常数时间」吗？
你可能会问：这个循环执行 len 次，时间跟长度成正比，怎么能叫常数时间？
嗯，这里要澄清一下：常数时间比较中的「常数」，指的是对于给定的输入长度，执行时间不随数据内容变化。也就是说，无论两个数组是相等还是不等，无论第一个字节就不同还是最后一个字节才不同，循环都执行同样的次数。这才是我们关心的——防止攻击者通过时间差异推断出比较结果。
至于长度本身，它通常是公开信息（比如密码哈希值的长度是固定的），所以长度带来的时间变化不构成安全风险。
| 场景 | 普通比较 | 常数时间比较 |
|---|---|---|
| 第一个字节不同 | 1 次循环后返回 | len 次循环后返回 |
| 最后一个字节不同 | len 次循环后返回 | len 次循环后返回 |
| 完全相等 | len 次循环后返回 | len 次循环后返回 |
看到了吧？普通比较的时间会随数据变化，而常数时间比较的时间只取决于长度。这就是我们想要的效果。
4.8 小结
异或累加法是常数时间比较的基石。它简单、可靠、容易验证。我个人在写安全相关的代码时，几乎都用这个模式。记住几个要点：
- 用
|=而不是+= - 循环次数固定，不提前退出
- 注意类型安全，用
uint8_t - 长度不一致时要额外处理