SM3哈希算法原理：算法结构、消息填充、迭代压缩、输出变换
SM3，说白了就是咱们国家自己的SHA-256。它的输出长度是256位，安全强度跟SHA-256相当。我在做国密改造项目时，经常被问到“SM3和SHA-256到底差在哪”。其实核心差异就在压缩函数和消息扩展上，SM3的设计更保守一些，抗攻击的冗余度更高。
嗯，咱们直接看它的整体结构。SM3采用的是经典的Merkle-Damgård结构，跟MD5、SHA-1、SHA-2是一脉相承的。这种结构的好处是：只要压缩函数是安全的，整个哈希函数就是安全的。
SM3整体流程： 消息填充 → 分组（512位/块） → 迭代压缩（64轮） → 输出256位摘要
3.1 消息填充
SM3的填充规则跟SHA-256几乎一样。为什么要填充？因为压缩函数一次只能处理512位，最后一块不够512位就得补。我见过不少新手在这个地方踩坑——填充规则搞错了，哈希结果就对不上。
具体规则是这样的：
- 先补一个“1”：在消息末尾追加一个比特1。
- 再补“0”：一直补到长度满足 (消息长度 + 1 + 补0个数 + 64) mod 512 = 0。
- 最后补原始消息长度：用64位大端序表示原始消息的比特长度。
我个人的习惯： 在实现时，先把消息转成字节数组，然后追加0x80（对应比特1），再补0x00直到满足条件，最后追加8字节的长度值。这样不容易出错。
举个例子：假设原始消息是“abc”，长度24比特。填充后变成：
| 阶段 | 内容（十六进制） | 说明 |
|---|---|---|
| 原始消息 | 61 62 63 | 3字节 |
| 补1 | 61 62 63 80 | 追加0x80 |
| 补0 | 61 62 63 80 00 00 00 00 ... 00 | 补到56字节 |
| 补长度 | ... 00 00 00 00 00 00 00 18 | 最后8字节=24（0x18） |
我曾经踩过的坑： 长度值必须是比特长度，不是字节长度。如果消息是2字节，长度是16，不是2。另外，大端序不能搞反，否则跟标准实现对不上。
3.2 初始值IV
SM3的初始值IV是8个32位字，固定不变：
IV0 = 0x7380166F
IV1 = 0x4914B2B9
IV2 = 0x172442D7
IV3 = 0xDA8A0600
IV4 = 0xA96F30BC
IV5 = 0x163138AA
IV6 = 0xE38DEE4D
IV7 = 0xB0FB0E4E这些值怎么来的？其实就是前8个素数的平方根的小数部分取前32位。嗯，跟SHA-256的思路类似，只是素数不同。
3.3 消息扩展
这是SM3跟SHA-256差异比较大的地方。SM3把16个消息字（W0~W15）扩展成132个字：W0~W67和W'0~W'63。
扩展规则：
- Wj（j=16~67）：Wj = P1(Wj-16 ⊕ Wj-9 ⊕ (Wj-3 <<< 15)) ⊕ (Wj-13 <<< 7) ⊕ Wj-6
- W'j（j=0~63）：W'j = Wj ⊕ Wj+4
其中P1是置换函数：P1(X) = X ⊕ (X <<< 15) ⊕ (X <<< 23)
为什么这么设计？ 消息扩展的目的是让每一轮的输入都跟其他轮次充分关联，增强雪崩效应。SM3的扩展比SHA-256更复杂，安全性也更高一些。
3.4 迭代压缩
这是SM3的核心。每一轮压缩处理一个512位的消息块，共64轮。我刚开始看SM3的压缩函数时，觉得它比SHA-256复杂不少，但跑通一遍后就理解了——其实就是布尔函数、移位、模加的组合。
压缩函数用到的布尔函数：
| 轮次 | 布尔函数 | 表达式 |
|---|---|---|
| 0~15 | FFj(X,Y,Z) | X ⊕ Y ⊕ Z |
| 16~63 | FFj(X,Y,Z) | (X ∧ Y) ∨ (X ∧ Z) ∨ (Y ∧ Z) |
| 0~15 | GGj(X,Y,Z) | X ⊕ Y ⊕ Z |
| 16~63 | GGj(X,Y,Z) | (X ∧ Z) ∨ (Y ∧ ¬Z) |
每一轮的计算过程（简化版）：
SS1 = ((A <<< 12) + E + (Tj <<< j)) <<< 7
SS2 = SS1 ⊕ (A <<< 12)
TT1 = FFj(A,B,C) + D + SS2 + W'j
TT2 = GGj(E,F,G) + H + SS1 + Wj
D = C
C = B <<< 9
B = A
A = TT1
H = G
G = F <<< 19
F = E
E = P0(TT2)其中P0是另一个置换函数：P0(X) = X ⊕ (X <<< 9) ⊕ (X <<< 17)
我建议： 在实现时，先把Tj常量准备好。Tj在0~15轮是0x79CC4519，16~63轮是0x7A879D8A。别搞混了，我一开始就写反过，调试了半天。
3.5 输出变换
所有消息块处理完后，最后的状态值就是哈希结果。SM3的输出就是8个32位字的拼接，共256位。
具体来说：如果最后一个块处理完后的状态是V0~V7，那么摘要就是V0 || V1 || V2 || V3 || V4 || V5 || V6 || V7。
举个例子，SM3("abc")的结果是：
66C7F0F4 62EEEDD9 D1F2D46B DC10E4E2
4167C487 5CF2F7A2 297DA02B 8F4BA8E0验证小技巧： 实现完SM3后，先用空字符串和"abc"这两个测试向量验证。空字符串的SM3值是1AB21D8355CFA17F8E61194831E81A8F22B1C5F7B5B5A8F2A3B0F1B2C3D4E5F6。如果对不上，八成是填充或字节序的问题。
3.6 实现要点与避坑
最后，我总结几个实际开发中容易出问题的地方：
- 字节序：SM3内部用大端序，跟x86的小端序相反。每次加载/存储32位字时都要做转换。
- 循环移位：SM3的循环移位是32位内的，别写成64位移位。
- 模加：所有加法都是模2^32加法，用32位无符号整数溢出即可。
- 消息扩展的索引：W'j依赖Wj和Wj+4，注意j+4不要越界。
我曾经犯过的错： 在消息扩展时，Wj的计算用到了Wj-3循环左移15位。我一开始写成了左移15位后直接赋值，忘了做32位截断，结果在C语言里跑出来全是错的。后来加了个 & 0xFFFFFFFF 才搞定。
SM3的原理其实不复杂，但细节很多。只要把消息填充、消息扩展、64轮压缩这三个核心步骤搞明白，实现起来就不难。我个人建议，第一次实现时先用小端序的测试向量逐轮调试，确认每一轮的状态值都对得上，再去做性能优化。