SM3算法原理：消息填充、扩展与压缩函数

聊SM3之前，我先说个大实话。
很多人觉得哈希算法就是调个库，原理不重要。
我以前也这么想，直到有次线上反馈验签失败，我排查半天，最后发现是消息填充的长度写错了。
嗯，从那以后我再也不敢跳过原理部分了。

SM3算法说白了就干三件事：
填充 → 扩展 → 压缩。
咱们一个个讲透。

1. 消息填充

为什么必须填充？
SM3处理的基本单位是512位（64字节）。
如果原始消息不是512的整数倍，就得填充。
好比你处理文件，底层按块读，最后一块不满就得补齐。

填充规则其实只有三步：

1. 末尾补一个 '1' —— 二进制就是1bit。
2. 补 '0' 直到满足模512同余448 —— 注意是模512余448（即448 mod 512）。
3. 附加原始消息长度（64位大端表示） —— 长度单位是bit。

举个例子更容易理解。原始消息只有"abc"，共24位。
填充后总长度 = 24 + 1 + 423个0 + 64 = 512位，正好一个分组。

2. 消息扩展

填充后的每个512位分组，需要扩展才能进入压缩函数。
扩展分两步：

2.1 生成 W₀ ~ W₆₇

前16个字W₀~W₁₅直接取自分组（每字32位）。
后52个字W₁₆~W₆₇通过递推得到：

for j in range(16, 68):
    W[j] = P1(W[j-16] ^ W[j-9] ^ (ROTL(W[j-3], 15))) ^ 
           ROTL(W[j-13], 7) ^ W[j-6]

P1是一个置换函数：

def P1(X):
    return X ^ ROTL(X, 15) ^ ROTL(X, 23)

2.2 生成 W′₀ ~ W′₆₃

这个就简单了：

for j in range(64):
    W1[j] = W[j] ^ W[j+4]

扩展一共产生132个字（68+64），供64轮压缩使用。

3. 压缩函数

压缩函数是SM3最核心的部分。
它基于迭代结构，每一轮更新8个32位寄存器（A~H）。

3.1 初始值

3.2 64轮迭代

for j in range(64):
    SS1 = ROTL((ROTL(A, 12) + E + (Tj << (j % 32))), 7)
    SS2 = SS1 ^ ROTL(A, 12)
    TT1 = FFj(A, B, C) + D + SS2 + W1[j]
    TT2 = GGj(E, F, G) + H + SS1 + W[j]
    D = C
    C = ROTL(B, 9)
    B = A
    A = TT1
    H = G
    G = ROTL(F, 19)
    F = E
    E = P0(TT2)

其中FFj和GGj是布尔函数：

• 0~15轮：FFj = (A & B) | (A & C) | (B & C)，GGj = (A & B) | (~A & C)
• 16~63轮：FFj = (A & B) | (A & C) | (B & C)，GGj = (A & B) | (~A & C)

没错，你没看错。SM3的布尔函数在0~15轮和16~63轮是一样的。
这个细节我当年看了好几遍SM3标准才确认。

P0置换：

def P0(X):
    return X ^ ROTL(X, 9) ^ ROTL(X, 17)

3.3 迭代

处理完第一分组后，将寄存器值作为下一分组的初始状态：

V^{i+1} = V^i + (A||B||C||D||E||F||G||H)

加号是字加，不是拼接。
最后一个分组处理完，拼接A~H即得到256位杂凑值。

最后说一句。SM3的压缩函数设计得很精巧。

每一轮只有4次移位、2次置换、1次布尔和几个加法。
在硬件或嵌入式上实现，效率相当高。

嗯，原理就这些。下面对照SM3标准实现一遍，所有细节都会落到实处。