2. SM4算法的数学基础：有限域GF(2^8)、S盒构造原理、线性变换
咱们搞密码的，说到底就是在跟数学打交道。SM4看着是一堆查表和异或操作，但底子全是有限域、S盒和线性变换这三板斧。
我个人习惯，每次拿到一个分组算法，最先看的就是它的S盒。为什么？因为整个算法的非线性强度全看这张表。SM4的S盒基于有限域GF(2^8)构造，背后的代数结构一点也不含糊。
2.1 有限域GF(2^8)：密码世界的8位密码本
先聊聊有限域。说白了，域就是一个能进行加、减、乘、除运算的集合。GF(2^8)就是256个元素构成的域，每个元素可以看作是一个8位的字节。你想想看，我们处理数据的最小单位就是字节，这不正好对齐了嘛。
在GF(2^8)里，加法运算其实是按位异或（XOR）。这就是为什么你在SM4实现里看到大量的异或操作——那不是在奇怪地抠位，而是在做域加法。
域加法与普通加法的区别
普通加法：0x57 + 0x83 = 0xDA（进位了）
域加法：0x57 ⊕ 0x83 = 0xD4（不进位，按位异或）
乘法则麻烦得多。我记得第一次手算SM4里的乘法时，完全被绕晕了。GF(2^8)的乘法不是直接数值相乘，而是多项式乘法再模一个不可约多项式。SM4用的是这个不可约多项式：
m(x) = x⁸ + x⁴ + x³ + x + 1二进制表示就是 0x11B。这个多项式在密码学里非常常见，AES的有限域用的也是它。
这里有个关键点：乘法逆元。在GF(2^8)里，除了0以外，每个元素都有唯一的乘法逆元。这个性质是构造S盒的基石。我当初做SM4硬件实现时，逆元计算那块折腾了好几天，后面会讲到为什么。
| 运算类型 | 示例 | 结果 | 说明 |
|---|---|---|---|
| 加法 | 0x57 ⊕ 0x83 |
0xD4 | 按位异或，不进位 |
| 乘法 | 0x57 · 0x83 |
0xC1 | 多项式乘法模0x11B |
| 求逆元 | 0x57⁻¹ |
0xEF | 扩展欧几里得算法求得 |
实战小技巧：做乘法运算时，可以预计算一个256×256的乘法表，查表代替运算。代价是64KB的存储空间，很多嵌入式设备吃不消。我一般推荐用对数表法，只存两个256字节的表就够用。
2.2 S盒构造原理：非线性之魂
S盒是整个SM4算法里唯一一个非线性部件。没有它，整个算法就是一个线性变换，随便几下就能破解。S盒的构造分两步：先求乘法逆元，再做仿射变换。
第一步：求逆元
对输入字节a（0除外），在GF(2^8)上求它的乘法逆元a⁻¹。0的逆元规定为0。这一步是整个S盒的核心，也是计算最重的一块。
我在项目中曾遇到过一个问题：查表实现的S盒只有256字节，但是硬件实现求逆元时，面积和时序难以权衡。后来我用了复合域（Composite Field）映射的方法，把GF(2⁸)降级到GF( (2⁴)² )，运算从查表变成了逻辑门，面积降了将近一半。
第二步：仿射变换
拿到逆元之后，还不是最终的S盒输出。还需要做一个仿射变换：
b' = A · b ⊕ c其中A是一个8×8的矩阵，c是固定向量0xD3。这个变换的目的很单纯——破坏代数结构，防止有人直接逆推。
仿射变换的矩阵A长这样：
1 1 1 0 0 1 0 1
1 1 1 1 0 0 1 0
0 1 1 1 1 0 0 1
1 0 1 1 1 1 0 0
0 1 0 1 1 1 1 0
0 0 1 0 1 1 1 1
1 0 0 1 0 1 1 1
1 1 0 0 1 0 1 1整个S盒构造过程可以用一句话概括：输入字节 → 求GF(2⁸)逆元 → 仿射变换 → 输出字节。这段过程的实现，我建议初学者先写好查表版本，跑通了再去碰硬件实现。
注意：S盒的逆元步骤计算量极大。在软件中直接查256字节的表效率最高；在硬件中使用复合域求逆可以减少约40%的逻辑门数，但设计复杂度明显上升。
2.3 线性变换L与合成置换T
SM4在轮函数中用了一个合成置换T，它由非线性变换τ和线性变换L组合而成。
非线性变换τ
说白了就是四个并行的S盒查找。输入32位字，拆成4个字节，每个字节过一遍S盒，再拼回32位。这一步保证了算法的非线性强度。
输入：A = (a₀, a₁, a₂, a₃)
输出：B = (Sbox[a₀], Sbox[a₁], Sbox[a₂], Sbox[a₃])线性变换L
这才是SM4的精髓。L变换就是做循环移位和异或，说白了就是个扩散层：
L(B) = B ⊕ (B <<< 2) ⊕ (B <<< 10) ⊕ (B <<< 18) ⊕ (B <<< 24)在密钥扩展里用的L'稍有不同：
L'(B) = B ⊕ (B <<< 13) ⊕ (B <<< 23)为什么这样设计？我研究过一阵子。你看，这个变换保证了一个比特的变化，经过一轮后至少影响5个不同的比特位。这就是密码学里常说的“雪崩效应”。我曾经为了验证这个性质，写了个脚本测试全空间输入，结果确实如此。
合成置换T的整体流程
输入32位 → 拆4字节分别过S盒 → 4字节拼回32位 → 线性变换L（循环移位+异或） → 输出32位
说白了，T变换把非线性（S盒）和线性扩散（L）捆在一起，一次操作就把混淆和扩散全做了。这种组合在分组密码里非常经典。
嗯，这里要注意：密钥扩展里的L'和加密轮函数里的L是不一样的。设计目的是在密钥扩展里减少扩散，降低硬件面积。我最初没注意这个区别，写代码时统一用一个L，结果混淆出来的密钥和标准答案对不上，排查了半天才发现。
2.4 整体知识关系图
下面这张SVG图总结了这一章的核心逻辑，三者环环相扣：
从图中你能看明白：有限域是S盒的运算根基，S盒是合成置换T的非线性来源。三者层层递进，构成了SM4的核心密码学强度。我个人觉得，把这张图吃透了，SM4的数学骨架就算拿下了。