第3章 SM4算法数学基础：有限域与S盒
讲SM4之前，我一直觉得有必要先把数学底子打扎实。你想想看，很多做接口开发的同事，上来就调包，加密解密也能跑通，但一旦遇到平台差异、字节序不对、轮数出错，马上就懵了。说白了，SM4的骨架就两个东西：有限域运算和S盒。这两个搞明白，后面看轮函数、密钥扩展就是顺水推舟的事。
我记得2018年有个项目，客户要求替换国际算法，全部改用国密。我当时在对接一个嵌入式设备，结果S盒查表总是对不上。排查到最后才发现——他们用的S盒查表顺序跟标准字节序差了半拍。从那以后我就养成了一个习惯：凡是涉及SM4的代码，第一件事就是确认S盒实现是不是按国标《GB/T 32907-2016》来的。
3.1 有限域 GF(2⁸) 的基本概念
SM4的S盒本质上是一个8比特输入、8比特输出的非线性替换表。这个替换并不是随便拍脑门设计的，它背后站着一个代数结构——有限域 GF(2⁸)。听起来高大上，其实就是在一个特定的“多项式世界”里做加减乘除。
GF(2⁸) 可以理解为所有8位二进制数的集合，但加法和乘法不是普通整数运算，而是基于一个不可约多项式定义的。SM4选用的不可约多项式是：
m(x) = x⁸ + x⁷ + x⁶ + x⁵ + x⁴ + x² + 1 // 十六进制 0x1F5加法：就是按位异或（XOR）。两个多项式相加，系数在 GF(2) 里，说白了就是二进制不带进位的加法。我自己在写测试向量的时候，最怕的就是把加法理解成普通整数相加，那结果就全歪了。
乘法：多项式相乘后，用 m(x) 取模。为什么要取模？因为乘出来的结果可能超过8位，必须“环回到”有限域里。这个操作在硬件实现时就是一堆异或门和移位寄存器，但在软件里我们一般不用实时做乘法——S盒是预计算好的。
我的小习惯：如果你只是调SM4接口，不需要手动算乘法。但如果你要自己验证S盒的代数性质（比如差分均匀性、非线性度），那就得熟悉 GF(2⁸) 的乘法表。很多开源库都提供 gf256_mul 函数，直接用就好。
3.2 S盒的构造过程
SM4的S盒，生成过程大致分两步：先在 GF(2⁸) 里求乘法逆元（0的逆元定义为0），再做一次仿射变换。
- 求逆：对每个字节
a ∈ [0x00, 0xFF]（0x00映射到自身），计算它在 GF(2⁸) 里的乘法逆元。说白了就是找一个数 b，使得 a × b ≡ 1 mod m(x)。 - 仿射变换：把逆元结果当成向量，乘上一个8×8的矩阵，再加一个常数向量。这个变换的目的是打散代数结构，防止攻击者通过代数方程直接破解。
仿射变换的矩阵和常数向量，国标里写得很清楚。我通常把S盒生成代码做成一个独立函数，方便调试和比对。
下面是一个简化的Python实现，生成SM4的S盒：
def sm4_sbox_generate():
# 不可约多项式 0x1F5，用整数表示
poly = 0x1F5
sbox = [0] * 256
# 第一步：求 GF(2⁸) 乘法逆元，0映射为0
inv = [0] * 256
for i in range(1, 256):
# 暴力搜索逆元（小域可以，正式实现用扩展欧几里得）
for j in range(1, 256):
if gf256_mul(i, j, poly) == 1:
inv[i] = j
break
# 第二步：仿射变换矩阵（按国标）
# 矩阵 C：行优先，共8行
C = [
[1,0,0,1,1,1,1,1],
[1,1,0,0,1,1,1,1],
[1,1,1,0,0,1,1,1],
[1,1,1,1,0,0,1,1],
[1,1,1,1,1,0,0,1],
[1,1,1,1,1,1,0,0],
[0,1,1,1,1,1,1,0],
[0,0,1,1,1,1,1,1]
]
# 常数向量 d = 0xD3 (二进制 11010011)
d = [1,1,0,1,0,0,1,1] # 低位在上？注意国标字节序
for i in range(256):
bits = [(inv[i] >> (7 - k)) & 1 for k in range(8)]
# 做矩阵乘法（模2加法）
result = [0]*8
for row in range(8):
s = 0
for col in range(8):
s ^= bits[col] & C[row][col]
result[row] = s ^ d[row]
# 从最高位到最低位组合成字节
sbox_byte = 0
for k in range(8):
sbox_byte = (sbox_byte << 1) | result[k]
sbox[i] = sbox_byte
return sbox避坑提醒：我曾经在实现仿射变换时，把矩阵的“行优先”和“列优先”搞反了，结果生成的S盒前几个值是对的，中间全乱套。后来对照国标附录A逐字节检查才发现。建议你生成完后，直接拿标准S盒的前几个值（如S[0x00]=0xD6, S[0x01]=0x90）做比对，一步到位。
3.3 S盒在轮函数中的作用
SM4的轮函数，第一步就是把32比特的输入拆成4个字节，每个字节过一遍S盒，再组成32比特。这就是非线性替换层，是抵抗线性分析和差分分析的核心。没有S盒，整个算法就是一堆线性操作，很容易被攻破。
S盒的代数性质决定了算法的安全边际。比如：
- 差分均匀性：S盒的最大差分概率越低越好，SM4的S盒最大差分概率为 2⁻⁶，属于优良水平。
- 非线性度：SM4的S盒非线性度是 112，比AES的S盒（非线性度112）一样，但代数表达式更复杂。
- 代数次数：S盒可表示为 GF(2) 上的高次多项式，次数为7，意味着代数攻击的计算复杂度很高。
我在一次安全测评中，需要向客户解释为什么SM4能够抵抗线性密码分析。实际上，S盒的高非线性度使得线性逼近的偏差很小，需要海量的明密文对才能攻破。客户听完就放心了。
3.4 有限域与S盒的关系总览
为了帮你梳理清楚这些概念，我画了一张结构图。它展示了从有限域到S盒的完整脉络，以及S盒在SM4伦函数里的位置。
3.5 章节小结——你需要记住的
| 核心概念 | SM4中的具体形式 | 我的建议 |
|---|---|---|
| 有限域 GF(2⁸) | 基于多项式 m(x)=0x1F5，加法=异或，乘法=多项式模乘 | 验证代码时用标准测试向量（如输入0x01×0x01应得0x01） |
| 乘法逆元 | 0→0，非零用扩展欧几里得或查表求得 | 预计算256字节逆元表，查表比实时算快10倍以上 |
| 仿射变换 | 8×8矩阵 + 常数 0xD3，逐位做异或 | 必须按国标确认字节序（最高位对应矩阵第一行第一列） |
| S盒 | 256字节替换表，非线性度112，差分均匀性2⁻⁶ | 实现完成后打印前16个值与标准对比，一步排查问题 |
实用技巧：我通常在 sm4_setup() 函数里把S盒从ROM加载到L1缓存，这样不会因为查表引起大的性能震荡。另外，如果你做的是硬件实现，记得把S盒综合成组合逻辑，别做成时钟门控——否则一个时钟周期出不来S盒结果，整个流水线就卡住了。
好，这章的内容到这里。SM4的S盒跟有限域绑在一起，理解了这些数学背景，后面看32轮迭代和密钥扩展时就不会觉得是黑盒了。如果你自己写一遍S盒生成代码，再跟标准值对一遍，那就算是彻底“内化”了。