第3章 SM3算法数学基础：位运算、模运算、置换

说实话，刚开始看SM3的数学基础时，我觉得没啥特别的——不就是位运算和加法吗？后来在项目中做硬件加速实现时，才发现这些基础运算的细微差别直接影响性能。这一章，我把SM3里最核心的三种数学操作拆开揉碎跟你讲清楚。

3.1 位运算：SM3的“肌肉记忆”

SM3里大量使用位运算，因为它快。一个CPU时钟周期就能完成。我印象最深的是，当初在嵌入式芯片上移植SM3，一块8位的MCU，靠位运算就能跑出可接受的速率。

3.1.1 基本位运算

• 按位与（&）：常用于掩码，比如取一个字的低8位：x & 0xFF。
• 按位或（|）：设置特定位，如设置第7位：x | 0x80。
• 按位异或（^）：SM3中信息扩散的关键操作，下面会细讲。
• 按位非（~）：取反，常与掩码配合使用。
• 左移（<<）：低位补0，相当于乘以2^移位量。
• 右移（>>）：逻辑右移高位补0，算术右移高位补符号位——SM3里统一用逻辑右移。

3.1.2 循环移位（ROTL / ROTR）

SM3里最频繁的位运算就是循环移位。比如压缩函数里大量出现ROTL(x, n)——把x循环左移n位。为什么不用普通左移？因为普通左移会把高位移出去丢掉，而SM3需要这些位绕回来继续参与运算。

实现的写法很简单：

uint32_t ROTL(uint32_t x, uint32_t n) {
    return (x << n) | (x >> (32 - n));
}

你看，就一行。注意n必须<32，否则结果不可预测。

3.2 模运算：加法模2³²

SM3里所有的加法都是在“模2³²”的环下进行的。说白了，就是两个32位无符号整数相加，结果只取低32位，高位溢出直接丢掉。为什么？因为哈希算法的输出长度和中间变量都是32位的，我们不需要高位信息，只要结果在0～2³²-1之间即可。

我记得刚开始写Python版本时，直接用(a + b) & 0xFFFFFFFF取模，结果跟C实现一致。但要小心，Python的整数是无限精度的，如果你不用掩码，数字会无限增长，性能会崩掉。

3.3 置换：让数据“搅匀”

SM3的置换操作主要集中在消息扩展和压缩函数的P置换里。置换本质上就是重新排列位或字的位置，没有数学运算，就是“搬砖”。

3.3.1 消息扩展中的置换

SM3将512位的消息分组扩展为132个32位字（W₀～W₆₇和W′₀～W′₆₃）。扩展时大量使用对W的循环移位和异或。比如生成W′时：

W′[j] = W[j] ^ W[j+4]

是不是很简单？但正是这种“简单”的异或，配合循环移位，实现了雪崩效应——输入改一位，输出一大半都变。

3.3.2 压缩函数中的P置换

P置换是SM3里唯一真正的“字级别置换”。它作用于两个32位字，产生一个新字。公式是：

P₀(X) = X ^ (X << 9) ^ (X << 17)   // 用于64步循环的第一轮
P₁(X) = X ^ (X << 15) ^ (X << 23)  // 用于后续轮次

这里的左移是循环左移（ROTL）。你看，还是位运算。我经常跟团队说：SM3的本质就是把位运算玩到极致。

3.4 三种运算的相互关系

把上面三种运算串起来，就是SM3每一轮迭代的“心脏”：

1. 从扩展寄存器取出W和W′
2. 做模加法：SS1 = ROTL(ROTL(A,12) + E + ROTL(T',j), 7)
3. 做异或和循环移位：TT1 = FF(A,B,C) + D + SS2 + W'[j]
4. 执行P置换：GG(A,B,C) = P₀(A ^ B ^ C)

每一步都离不开位运算、模运算、置换三者的配合。我特别喜欢用一个比喻：位运算是肌肉，模运算是关节，置换是骨骼——三者协同才能让哈希算法跑起来。

3.5 用Python验证基础运算

纸上谈兵没意思，我们写几行Python直接感受一下。下面这段代码演示了SM3中最常用的几个操作：

def rotl(x, n):
    """循环左移 n 位 (n<32)"""
    return ((x << n) | (x >> (32 - n))) & 0xFFFFFFFF

def mod_add(a, b):
    """模 2³² 加法"""
    return (a + b) & 0xFFFFFFFF

def p0(x):
    """P₀ 置换"""
    x = x & 0xFFFFFFFF
    return x ^ rotl(x, 9) ^ rotl(x, 17)

def p1(x):
    """P₁ 置换"""
    x = x & 0xFFFFFFFF
    return x ^ rotl(x, 15) ^ rotl(x, 23)

# 测试
a = 0x12345678
b = 0x9ABCDEF0
print(f"mod_add: 0x{mod_add(a,b):08X}")  # 预期：0xA8F24568
print(f"P0(0x{rotl(a,4):08X}) = 0x{p0(rotl(a,4)):08X}")

跑一下看看结果。如果数字对不上，大概率是移位位数写错了。我当初写P₀时把17写成了11，结果卡了两天——后来才发现是常量抄错了。

3.6 常见误区总结