SM3 算法原理：消息填充、迭代压缩、消息扩展

SM3 是我在国产密码项目里用得最多的哈希算法之一。它本质上是一个 Merkle-Damgård 结构的迭代哈希函数，核心就三步：消息填充、消息扩展、迭代压缩。我拆解过它的每一步，今天咱们就把它讲透。

1. 消息填充：把消息切成整齐的块

SM3 要求输入消息的长度必须为 512 位的整数倍。不够怎么办？填充。我遇到过不少新手直接在消息末尾加零，结果算出来的哈希值完全不对。嗯，这里要注意：填充规则是固定的。

1. 补 1 比特：在消息末尾追加一个二进制 1，即 0x80（当按字节处理时）。
2. 补 0 比特：继续填充 0，直到消息长度 mod 512 ≡ 448（即剩余 64 位留给长度域）。
3. 附加消息长度：将原始消息的比特长度（64 位无符号整数）以大端序拼接到末尾。总长度变成 512 的整数倍。

举个例子。假设原始消息是 "abc"（3 个字节，24 比特）。填充后：

• 先加 0x80 → 长度变 25 比特
• 再补 0 直至长度 ≡ 448 mod 512，即补 423 个 0 比特 → 总长度 448 比特
• 最后追加 64 位长度值 0x00000000 00000018（24 的十六进制）
• 最终得到 512 比特的完整块

def sm3_pad(message: bytes) -> bytes:
    # 原始消息长度（比特）
    ml = len(message) * 8
    # 补 0x80
    message += b'\x80'
    # 补 0 直到 (当前比特数 % 512) == 448
    while (len(message) * 8) % 512 != 448:
        message += b'\x00'
    # 附加 64 位大端长度
    message += ml.to_bytes(8, byteorder='big')
    return message

2. 迭代压缩：SM3 的灵魂循环

填充完的消息被分成 N 个 512 位的消息块。每个块依次进入压缩函数。压缩函数内部先对块做消息扩展，生成 132 个 32 位字，然后跑 64 轮迭代。

2.1 消息扩展是怎么干的？

把 512 位（16 个字）扩展到 132 个字。我建议你这样记：前 16 个字直接来自消息块，后面 52 个字通过异或、循环移位和置换算出来，最后 64 个字是前 68 个字两两组合的异或。

这里 P₁ 是 SM3 定义的置换函数，说白了就是让比特扩散得更均匀。我记得第一次手动验证扩展时，因为移位方向搞反导致后面 60 轮全错，查了我一整天。

2.2 迭代压缩的 64 轮怎么跑？

初始化 8 个 32 位寄存器：V₀ = 0x7380166f, V₁ = 0x4914b2b9, ..., V₇。每一轮用上一轮的输出、消息字 W[j]、W'[j] 和常量 T，经过逻辑函数更新这 8 个值。64 轮结束后，当前块的输出与上一块输出相加（模 2³²），作为下一块的初始值。

逻辑函数 FFj 和 GGj 在 j ≤ 15 和 j ≥ 16 时不一样——前 16 轮用异或和与运算，后 48 轮用多数函数。你想想看，这样设计的好处是让非线性度在不同阶段变化，抵抗密码分析。

3. 完整一步：消息填充 → 分组 → 迭代压缩 → 256 位摘要

1. 输入任意长度消息
2. 按规则填充，使长度是 512 的整数倍
3. 将填充后的消息划分为 512 位（64 字节）的块
4. 设置初始哈希值 H₀ = 8 个常数
5. 对每个块执行：
   5.1 消息扩展生成 W[0..67] 和 W'[0..63]
   5.2 64 轮迭代压缩，更新 8 个寄存器
   5.3 将寄存器值与当前 H 相加得到新的 H
6. 最终 H₀..H₇ 拼接成 256 位摘要

4. 对比一下：SM3 vs SHA-256

说白了，SM3 在结构上借鉴了 SHA-256 的设计思路，但修改了常量和置换函数，并且在扩展阶段生成了更多字（132 对比 64），增加了攻击者的分析难度。国密标准对 SM3 的安全性评估是：抗碰撞强度 128 bit，抗原像攻击强度 256 bit。

嗯，到这里 SM3 的核心原理你应该已经清楚了。下节我们会用 Python 实现一个完整的 SM3，从零开始手写消息扩展和压缩函数。到时候你会发现，代码写出来比看公式要直观得多。