2. SM4算法数学基础：有限域GF(2⁸)与S盒设计原理

SM4算法的核心运算，说白了就是围绕着两个数学工具转：一个是有限域GF(2⁸)，另一个是S盒。前者是字节运算的“战场”，后者是混淆数据的“心脏”。我最早接触SM4时，也觉得有限域这东西有点抽象。但一次在嵌入式设备上调试SM4实现，发现查表效率死活上不去……后来才意识到，搞懂GF(2⁸)的乘法本质，是写好查表优化的前提。

嗯，这一章我带着你，把这两个基础啃透。不追求数学证明，咱们讲透“它是什么”、“为什么这么设计”、“实战中怎么用”。

2.1 有限域GF(2⁸)：SM4的字节运算世界

你想想看，SM4处理的数据单位是字节，也就是8个比特。这8个比特能表示0~255，一共256个值。但问题是，普通的整数加法、乘法在密码学里不够用——因为一旦结果超出255，就需要模运算，而模一个合数（比如256）会导致很多运算不可逆。

那怎么办呢？密码学家们的方案是：使用有限域GF(2⁸)。它本质上是一个“特殊的算术系统”，里面的加法、乘法都是封闭的、可逆的，且结果永远在0~255之间。

2.1.1 什么是有限域？一句话讲清

有限域，就是元素个数有限，且能进行加、减、乘、除（除零以外）的数学系统。GF(2⁸)中的“2”表示域的特征值是2，“8”表示域中元素的二进制长度是8位。

• 域的特征为2：意味着加法就是按位异或（XOR）。没有进位，没有借位。举个例子：0x57 + 0x83 = 0xD4，等价于01010111 XOR 10000011 = 11010100。
• 元素个数为256：因为2⁸ = 256，每个字节正好对应一个域元素。

2.1.2 GF(2⁸)的乘法：比加法麻烦多了

加法是异或，很直观。但乘法就需要一个“生成法则”。GF(2⁸)的乘法是多项式乘法——你可以把每个字节看作一个系数为0或1的7次多项式。

举个例子：0x57（二进制01010111）对应多项式：x⁶ + x⁴ + x² + x + 1。0x83（10000011）对应：x⁷ + x + 1。

两数相乘，就是把这两个多项式乘开，得到结果。但这样乘出来的多项式次数可能超过7，怎么办呢？需要模一个不可约多项式。SM4中用的就是这个不可约多项式：

m(x) = x⁸ + x⁴ + x³ + x + 1   // 对应的十六进制是0x11B

这个多项式不可约，意味着它不能分解成两个更低次多项式的乘积。GF(2⁸)的所有非零元素都可以用这个多项式作为模数来生成。

2.1.3 特征多项式与乘法核心表

为了让你快速上手，这里我把GF(2⁸)常用的几个多项式和用途整理成了一个表格：

GF(2⁸)常用多项式对照

多项式（十六进制）	不可约？	在SM4中的用途	备注
0x11B	✅ 是	S盒乘法逆元计算	SM4标准指定，必须使用
0x1C3	✅ 是	某些非标实现中用于运算	SM4不推荐，仅供研究
0x1A9	✅ 是	加密库底层替换测试	改了会不兼容，别乱试
0x11D	❌ 否	不能用于SM4	会导致运算不封闭

2.2 S盒设计原理：非线性混淆的核心

S盒是SM4中唯一引入非线性的地方。如果没有S盒，整个SM4就是一组线性变换，攻击者用线性分析就能把密钥直接还原出来。所以，你想想看，S盒的设计质量直接决定了SM4的安全性。

2.2.1 SM4 S盒的构造步骤

SM4的S盒是一个8位输入、8位输出的置换，一共有256个映射值。构造它需要两个步骤：

1. 求乘法逆元：在GF(2⁸)中，对每个字节（除了0x00，其逆元定义为自身）计算其乘法逆元。这一步引入了极强的代数结构。
2. 仿射变换：对逆元结果应用一个仿射变换，公式如下：
   b' = b ⊕ (b << 1) ⊕ (b << 2) ⊕ (b << 3) ⊕ (b << 4) ⊕ 0xD3。
   这个变换打乱了逆元的分布，增加了代数复杂度。

为什么要有仿射变换这一步？因为仅靠乘法逆元构造的S盒，存在代数结构上的“可预测性”——攻击者可以用插值攻击绕过。加上仿射变换后，这个缺陷就被掩盖了。

2.2.2 SM4 S盒的完整生成代码

以下是我自己验证过的SM4 S盒生成代码。你可以直接用来生成完整的S盒256字节数组：

#include <stdint.h>

uint8_t gf256_inv(uint8_t a) {
    // 利用费马小定理：a^254 = a^(-1) in GF(2^8)
    uint8_t result = a;
    for (int i = 0; i < 6; i++) {
        result = gf256_mul(result, result);  // 平方运算
        result = gf256_mul(result, a);       // 乘以a
    } // 最终得到 a^254
    return result;
}

uint8_t sm4_affine(uint8_t x) {
    uint8_t y = x ^ (x << 1) ^ (x << 2) ^ (x << 3) ^ (x << 4);
    return y ^ 0xD3;
}

// 生成完整的SM4 S盒
void generate_sm4_sbox(uint8_t sbox[256]) {
    for (uint16_t i = 0; i < 256; i++) {
        uint8_t inv = (i == 0) ? 0 : gf256_inv((uint8_t)i);
        sbox[i] = sm4_affine(inv);
    }
}

2.2.3 S盒的密码学特性：为什么它这么强？

SM4的S盒不是随便生成的。它经过了一系列的密码学测试，确保以下三大特性：

• 非线性度：S盒输出与输入的线性关系尽量弱。SM4的S盒非线性度达到112（理论最大值120左右），意味着线性逼近攻击的成功率极低。
• 差分均匀性：给定一个输入差分，输出差分的分布尽量均匀。SM4的S盒差分均匀性为16/256，和AES的S盒处于同一水平。
• 代数次数：S盒的代数表达次数为7次（几乎达到8次的代数上界），使得插值攻击难以实现。

2.3 从GF(2⁸)到S盒：一张图看明白核心逻辑

有限域和S盒的关系，可以用下面这张图来梳理。它展示了从字节输入到S盒输出的完整路径：

2.4 合规视角下必须记住的细节

因为是做合规教程，我得额外提几个在审计和标准化测试中常遇到的细节点：

• S盒必须与标准完全一致：SM4标准文档（GM/T 0002-2012）附录中给出了完整的256字节S盒。任何自定义S盒都意味着算法不再是SM4。
• GF(2⁸)乘法实现必须使用0x11B：我曾经见过一个实现用了多项式0x1C3，理由是它“看起来更随机”——结果加解密正确，但换到另一个标准库就完全对不上了。这就是典型的“不兼容实现”。
• S盒查表速度与安全性：在软件实现中，通常用256字节的查表代替实时求逆和仿射变换。但要注意查表可能引入缓存时间侧信道攻击。在合规高安全场景下（比如金融加密机），建议用恒定时间查找或使用位片实现。