整数安全 · 第五章

FNV-1a 哈希函数
数学原理与雪崩效应

同样是 uint32_t 乘法回绕——在 calloc 里是漏洞,在哈希函数里是设计。
区别只有一个:程序员是否知道它会发生。

哈希函数是什么

把哈希函数想象成一台搅拌机:放进去一杯橙汁,搅出固定颜色的液体;放进去同一杯橙汁加一滴墨水,搅出的颜色和之前完全不同——不是"稍微深一点",而是彻底变了。它有三条关键性质: 同样的材料每次搅出一样的颜色(确定性); 材料差一点点,颜色天翻地覆(雪崩效应); 看着颜色,你没办法反推原来放了什么(单向性)。安全场景下最重要的是第②条。

// 输入:任意长度的数据
// 输出:固定范围内的一个整数

"abc"0xE40C292C
"abd"0xE70C2DE5 ← 只差一个字符,输出完全不同
"hello"0x4F9F2CAB
任意长文件0 到 2³²-1 之间的一个数

安全场景下的核心要求:雪崩效应

如果输入差一点,输出也只差一点,攻击者可以:

猜测原始数据
微小的输出变化暴露了输入规律
构造哈希碰撞
两个不同输入得到相同输出
绕过完整性校验
篡改数据后哈希值不变
FNV-1a 的代码
uint32_t simple_hash(const char *data, size_t len) {
    uint32_t h = 2166136261u; // 0x811C9DC5,经数学分析选定的初始值
    for (size_t i = 0; i < len; i++) {
        h = (h * 16777619) ^ data[i];
        // 乘法结果超出 uint32_t 范围时自动回绕(mod 2³²)
        // 回绕是算法的一部分,不是 bug
    }
    return h;
}
初始值
2166136261
= 0x811C9DC5
乘数 P
16777619
= 0x01000193
输出范围
0 ~ 2³²-1
固定 32 位
乘法扩散:信息为什么会扩散到所有位
1

把 h 拆成高低两部分

取第一轮实际值,将 h 写成多项式形式:

h = 0x811C9DC5 = 2,166,136,261

h = A × 2¹⁶ + B

A = 0x811C = 33,052 (高16位)
B = 0x9DC5 = 40,389 (低16位)

验证:33,052 × 65,536 + 40,389 = 2,166,136,261 ✓
2

多项式展开,看信息去了哪里

h × P = (A × 2¹⁶ + B) × P
      = A × P × 2¹⁶ + B × P

第一项:A × P × 2¹⁶
A × P = 33,052 × 16,777,619 ≈ 2³¹
log₂(33,052 × 16,777,619) ≈ 31 → 最多需要 31 位表示
再 × 2¹⁶(左移16位)→ 31 + 16 = 47 位
从第0位左移16位起算 → 落在第 16~47 位区域

第二项:B × P
B × P = 40,389 × 16,777,619 = 677,361,634,191
log₂(677,361,634,191) ≈ 39.3 → 最多需要 40 位
从第0位起算 → 落在第 0~39 位区域
3

两项在第 16~39 位区域交叉相加

第一项占 16~47 位,第二项占 0~39 位,重叠区间是 第 16~39 位,两项在此叠加混合。

位 47~40
仅 A×P 贡献
位 39~16 ← 交叉区域
A×P 低位 + B×P 高位
位 15~0
仅 B×P 贡献

↑ 橙色区域(位 39~16):A(原高16位)和 B(原低16位)的信息在此交叉叠加,互相影响

4

uint32_t 自动回绕 = 截取低32位 = mod 2³²,三者完全等价

// 三种说法,同一件事:
① uint32_t 回绕:超出 2³² 的部分自动消失
② 截取低32位:丢弃高32位,保留低32位
③ mod 2³²:除以 2³²,取余数

完整64位结果:0x0080FFFF_4B5E4A37

高32位:0x0080FFFF ← 三种方式都丢弃这里
低32位:0x4B5E4A37 ← 三种方式都保留这里 = 下一轮的 h

// 低32位里包含什么?
= B 的贡献 + A 溢出进来的部分(高位"折叠"回低位)
= 低16位的信息 + 高16位的信息

原来 h 的高16位和低16位,现在都影响了结果的每一位
位 63~32
0x0080FFFF
回绕丢弃 / mod截掉
位 31~0
0x4B5E4A37
保留 = 余数 = 下一轮 h

"折叠"是直觉描述:高位的信息没有消失,而是通过加法进位的方式"压入"了低32位。 这正是 uint32_tuint64_t 更适合做哈希的原因——回绕强制把所有信息压缩进固定范围,同时保留了扩散效果。

低32位 = (A × P × 2¹⁶ + B × P) mod 2³²
         = 高16位的贡献 + 低16位的贡献
         → 每一位都受到原 h 所有位的影响
亲眼看到雪崩效应
输入 A 输入 B
HASH(A)
0xE40C292C
HASH(B)
0xE70C2DE5
位级对比(橙色 = 不同的位)
HASH(A)
HASH(B)
雪崩扩散度
同样的回绕,完全不同的结果
场景 回绕是否预期 类型是否正确 行为定义 后果
calloc 乘法漏洞
count × sizeof(element_t)
❌ 意外 ❌ 取决于实现 未定义 / 回绕 堆溢出 → RCE
FNV-1a 哈希
h × 16777619
✅ 设计需求 ✅ uint32_t 无符号 C 标准定义 mod 2³² 雪崩效应 → 安全哈希
核心结论

无符号整数的回绕是 C 标准定义的 mod 2ⁿ 运算,行为完全可预测,可以作为算法设计的基础。
有符号整数溢出是未定义行为,任何依赖它的算法都是错误的。
区别不在于回绕本身,在于:程序员是否知道它会发生,并选对了类型。

问问 Claude
⟡ Claude · 实时问答

关于 FNV-1a、哈希函数原理、整数安全,有任何问题都可以直接问。