3. SM3 算法原理：消息填充、迭代压缩、哈希计算流程、与 SHA-256 对比及优化着眼点
SM3 是国家密码管理局发布的密码杂凑算法，输出 256 位摘要。说实话，它和 SHA-256 长得挺像，但细节上有很多“小动作”。我在做国密适配 SDK 时，发现不少人以为直接拿 SHA-256 替换就行，结果跑出的摘要对不上——坑就出在这些细节上。下面我把 SM3 的完整流程拆开讲一遍，顺便聊聊哪些地方能动手脚做性能优化。
3.1 消息填充：补位 + 补长度
SM3 处理的消息长度最大是 264 bits。填充规则很简单：先补一个 1，再补若干个 0，最后附上 64 位的原始长度（大端序）。目标是让总长度刚好是 512 的倍数。
填充步骤
- 末尾加一个二进制 1
- 加 k 个 0，直到长度满足
(L + 1 + k) ≡ 448 mod 512 - 加 64 位原始消息长度（bits）
举个例子：消息“abc”（24 bits）填充后，先加 1，再加 423 个 0（因为 24+1=25, 448-25=423），最后附上 0x00000000 00000018。这样就凑够一个完整的 512-bit 分组了。
我踩过的坑：曾经有个同事用的长度单位是字节，直接塞了 64-bit 的字节数进去。结果呢？SM3 要求的是位长度。填错之后整个摘要全乱套。
3.2 迭代压缩：消息扩展与轮函数
填充后的消息被切成 512-bit 的分组，每个分组经过 64 轮迭代。SM3 的压缩函数里有个“消息扩展”步骤，把 16 个 32-bit 字（W0~W15）扩展到 132 个字（W0~W67 和 W'0~W'63）。
扩展公式（我记这个公式时用了点小技巧）：
W[j] = P1(W[j-16] ⊕ W[j-9] ⊕ ROTL15(W[j-3])) ⊕ ROTL7(W[j-13]) ⊕ W[j-6]
W'[j] = W[j] ⊕ W[j+4]这里 ROTLx 表示循环左移 x 位。P1 是 SM3 独有的置换函数：P1(X) = X ⊕ ROTL15(X) ⊕ ROTL23(X)。每轮用到两个字 W[j] 和 W'[j]。你看，这些移位常数和 SHA-256 完全不一样。
压缩过程的轮函数叫 CF。64 轮里，每轮更新 8 个 32-bit 寄存器 A~H。具体的布尔函数我就不全贴了，核心是 FF 和 GG 两个函数，每 16 轮换一次逻辑。个人习惯是把它们写成 constexpr 表，编译期就能展开。
3.3 哈希计算流程总览
- 初始化 8 个 32-bit 寄存器：
IV = 0x7380166F, 0x4914B2B9, 0x172442D7, 0xDA8A0600, 0xA96F30BC, 0x163138AA, 0xE38DEE4D, 0xB0FB0E4E - 对每个 512-bit 分组执行消息扩展 + 迭代压缩，输出新的 256-bit 状态
- 处理完所有分组后，拼接 A~H 寄存器值（大端序）得到最终的哈希值
SM3 的整个流程，说白了就是“把消息切成块，每块用压缩函数搅一遍，然后累加状态”。这个框架和大多数 Merkle-Damgård 结构的哈希一样，但内部轮函数和移位常数是国密自己的。
3.4 SM3 与 SHA-256 对比
两者都是 256-bit 输出，都是 64 轮迭代，但内部细节差异明显。我把主要区别列在下面这张表里——嗯，当年我调试国密适配时，就是卡在这些数字上。
| 维度 | SM3 | SHA-256 |
|---|---|---|
| 初始值 IV | 8 个特定常数（见上） | 另有 8 个常数 |
| 消息扩展函数 | P1(X)=X⊕ROTL15(X)⊕ROTL23(X) | σ0(X)=ROTR7(X)⊕ROTR18(X)⊕SHR3(X) |
| 布尔函数 (0-15轮) | FF = X⊕Y⊕Z , GG = X⊕Y⊕Z | Ch=(X∧Y)⊕(¬X∧Z) , Maj=(X∧Y)⊕(X∧Z)⊕(Y∧Z) |
| 布尔函数 (16-63轮) | FF = (X∧Y)∨(X∧Z)∨(Y∧Z) , GG = (X∧Z)∨(Y∧¬Z) | 同上（不切换） |
| 移位常数 | 每轮用固定 Tj (前16轮 0x79CC4519, 后48轮 0x7A879D8A) | 每轮用固定 Kj (前64个质数立方小数部分) |
| 循环移位 | 大量使用 ROTL7, ROTL15, ROTL23 等 | 使用 ROTR 和 SHR |
经验之谈：SM3 的 FF/GG 函数在 16 轮后切换逻辑，很多移植 SHA-256 的代码直接用了 SHA-256 的布尔函数。我曾在一个项目中查了两天，才发现是这里错了。SM3 的 FF 后期用的是 (X∧Y)∨(X∧Z)∨(Y∧Z)，和 SHA-256 的 Maj 一样；但 GG 不一样，后期是 (X∧Z)∨(Y∧¬Z)。千万别混用。
3.5 优化着眼点
了解了原理，咱们就能从几个地方下手提速。我当年优化 SM3 SDK 时主要关注这几个点：
- 消息扩展的预计算：既然每个分组的 W[j] 扩展只依赖前 16 个字和之前算出的值，完全可以把扩展结果提前算好存入内存。128 个字（128*4=512字节）的代价远小于每轮都算一遍。
- 循环展开：64 轮迭代里，每轮的指令模式非常固定。手动展开 4 轮或 8 轮可以减少分支开销。我在 ARM Cortex-A72 上测试，展开 8 轮能带来约 15% 的提升。
- 利用 SIMD 指令：SM3 的移位操作（ROTL7、ROTL15、ROTL23）可以用 NEON/SSE 的向量移位指令一次处理多个字。不过要注意字节序——SM3 是大端运算，x86 平台上需要先用
bswap转换。 - 常数表的缓存友好：将 T[0..63] 压缩成两个 32-bit 值循环复用（前 16 轮和后 48 轮各一个），可以减少查表次数和缓存压力。我自己习惯把 T_j 做成
__m128i广播常量。 - 寄存器重命名：A~H 的更新顺序是交错依赖的，合理排列赋值顺序可以减少数据冒险。比如处理最后 16 轮时，可以提前加载下一组的 W'[j]。
一个值得注意的细节：SM3 的压缩函数末尾有一个“修正”操作：ABCDEFGH ← ABCDEFGH ⊕ V_j（V_j 是上一轮的寄存器状态）。这相当于把原始状态加了进去。很多低功耗芯片上，这个加法路径是关键的瓶颈，可以考虑用 ADD 替换 XOR 吗？不行——我试过，结果就不对了。所以千万别自作聪明改动这个结构。
总的来说，SM3 的优化既要吃透算法细节，又要摸清硬件特性。如果能吃透消息扩展的预计算和循环展开，大部分场景下性能就能翻倍。如果你在做国密适配 SDK，强烈建议先对着 SM3 标准文档逐行检查代码，尤其是布尔函数和移位常数——我当年就在这儿交了学费。