2、SM3的数学基础与设计原理

做哈希算法，说白了就是玩数学。SM3 本质上是一堆布尔运算、移位、加法和非线性函数的组合。我刚开始啃国标文档时，满眼的 FF、GG、移位量，差点劝退。后来调了一次代码，才发现这些运算其实很规整，甚至有点可爱。

2.1 核心数学构件

SM3 的运算全部基于 字（Word），一个字 = 32 位。你看下面这几个基本操作，全是位级别的：

运算	符号	说明
按位异或	⊕	相同为 0，不同为 1
按位与	∧	全 1 才 1
按位或	∨	有 1 就 1
按位取反	¬	每位翻转
模 2³² 加法	+	加法后取低 32 位，溢出不管
循环左移	«‹‹k	向左移 k 位，移出的补到右边

你想想看，这些运算在硬件上都能用门电路直接实现，速度极快。我个人习惯在写代码时把循环左移封装成一个宏或函数，避免手算出错。

2.2 非线性函数 FF 和 GG

SM3 在每轮压缩中用到了两个非线性函数。为什么叫“非线性”？因为它们的输出不能写成输入的线性组合。这两个函数让算法更难被破解。

• FF(X, Y, Z)：每轮前 16 步和后 48 步不一样
• 前 16 步（j=0..15）：FFj = X ⊕ Y ⊕ Z
• 后 48 步（j=16..63）：FFj = (X ∧ Y) ∨ (X ∧ Z) ∨ (Y ∧ Z) —— 多数投票函数
• GG(X, Y, Z)：同样分两段
• 前 16 步：GGj = X ⊕ Y ⊕ Z
• 后 48 步：GGj = (X ∧ Y) ∨ (¬X ∧ Z) —— 选择函数

你看，前半段就是简单的异或，后半段变成了有逻辑选择性的函数。这样设计的好处是：早期快速扩散，后期增强雪崩效应。我记得第一次在 C 语言里实现 FF 时，对着国标公式看了半天才明白“多数投票”到底是在干什么——其实就是三个输入中哪个值出现次数多，结果就取哪个。

2.3 置换函数 P₀ 和 P₁

置换函数就是对字内的位重新排列。SM3 定义了两种：

P₀(X) = X ⊕ (X «‹‹ 9) ⊕ (X «‹‹ 17)
P₁(X) = X ⊕ (X «‹‹ 15) ⊕ (X «‹‹ 23)

这里的位移量 9、17、15、23 不是随便选的。我个人测试过，这些数值能让 1 比特的输入变化在 3 轮内扩散到整个状态，嗯，这就是密码学里常说的“雪崩效应”。

2.4 消息扩展：从 16 个字到 132 个字

SM3 每轮处理 512 位（16 个字）的分组。但压缩函数需要运行 64 轮，每一轮要用到一个 32 位的消息字。所以需要不断产生新字。

1. 前 16 个字：W₀ ~ W₁₅ 直接取自输入分组。
2. 后 48 个字：Wⱼ = P₁(Wⱼ₋₁₆ ⊕ Wⱼ₋₉ ⊕ (Wⱼ₋₃ «‹‹ 15)) ⊕ (Wⱼ₋₁₃ «‹‹ 7) ⊕ Wⱼ₋₆
3. 还有一个额外的 W'ⱼ = Wⱼ ⊕ Wⱼ₊₄ 用于每轮的第二步更新。

说白了，这是用一个线性反馈移位寄存器（LFSR）风格的递推公式。你想想看，64 轮每轮两个消息字，一共需要 128 个，加上初始 16 个，总共 132 个。SM3 官方文档里把这 132 个字都展开列了出来，但实际代码里都是用循环算出来的。

2.5 压缩函数：64 轮迭代

SM3 的压缩函数接收 8 个状态字（A~H，每个 32 位）和两个消息字 Wⱼ、W'ⱼ，输出新的 8 个状态字。每轮干了这些事：

SS1 = ((A «‹‹ 12) + E + (Tⱼ «‹‹ j)) «‹‹ 7
SS2 = SS1 ⊕ (A «‹‹ 12)
TT1 = FFⱼ(A, B, C) + D + SS2 + W'ⱼ
TT2 = GGⱼ(E, F, G) + H + SS1 + Wⱼ
D = C
C = B «‹‹ 9
B = A
A = TT1
H = G
G = F «‹‹ 19
F = E
E = P₀(TT2)

注意 Tⱼ 是常量：前 16 轮 Tⱼ = 0x79cc4519，后 48 轮 Tⱼ = 0x7a879d8a。这两个数是 SM3 算法设计时精心挑选的——它们能保证每轮轮常量有足够的随机性。

2.6 设计思想：为什么这么拼凑？

SM3 的整体结构属于 Merkle-Damgård（MD）结构。消息先分组（512 位一组），每组经过压缩函数更新状态，最后输出 256 位摘要。这种结构保证了如果压缩函数是抗碰撞的，那么整个哈希函数也是抗碰撞的。

SM3 的设计还借鉴了 SHA-2 的一些思路，但做了改进：

• 它用了双消息字（W 和 W'），每轮更新两个中间变量，扩散速度更快。
• 状态寄存器之间的移位量不完全对称，打破了一些代数结构。
• 常量 Tⱼ 随轮数变化，让每轮使用的参数不同。

嗯，我当年做密码学课程设计时，尝试过把 SM3 的轮数从 64 减到 32，结果碰撞概率明显上升。这说明 64 轮是经过安全折中的——太多影响性能，太少不安全。

图中的每个蓝色/红色/绿色节点都对应了 SM3 的一个关键数学模块。紫色节点代表初始向量 IV（固定值 0x7380166f 等 8 个常数）。整个流程就像一道流水线：分组进来，先扩展出 132 个字，再与状态一起跑 64 轮，最后得到 256 位的摘要。

2.7 小结

SM3 的数学基础并不复杂——基本都是你大学数字逻辑课上学过的布尔代数。把复杂的安全性建立在简单的位运算上，这正是现代密码学的魅力。我个人觉得，理解了消息扩展和压缩函数这两块，整个 SM3 就算抓住七成了。剩下的就是严格按照轮常量、移位量去编码。多跑几个官方测试向量，很快就能上手。