2. SM4算法原理：核心结构剖析

说实话，SM4算法的设计思路非常经典。它采用了一个我在很多项目中都非常喜欢的结构——Feistel网络。为什么说喜欢？因为它的加解密真的太对称了，你几乎可以复用同一套代码，只是轮密钥的顺序反一下就行。

2.1 基本结构：Feistel网络

SM4的分组长度是128位，密钥长度也是128位。这意味着每次处理的数据块是16个字节，密钥也是16个字节。它的核心结构是Feistel网络，把明文分成左右两半，每轮只处理一半，然后交叉。

具体来说，它把128位数据看作4个32位的字：(X₀, X₁, X₂, X₃)。每一轮操作只更新X₀，其余三个字直接移动位置。我一共跑32轮，最终输出密文。

你们可以想象一下这个数据流：

• 输入：X₀, X₁, X₂, X₃ (每个32位)
• 第i轮：用X₁, X₂, X₃和一个轮密钥rkᵢ去更新X₀
• 更新后：新的X₀ = X₀ ⊕ F(X₁, X₂, X₃, rkᵢ)
• 然后整体左移：(X₁, X₂, X₃, 新的X₀)

这种结构的最大优点就是实现简单，而且加解密可以共用同一个硬件或软件模块。我在优化SM4的吞吐量时，Feistel结构的对称性帮了大忙——我只需要优化一轮，整个加解密流程就都受益了。

2.2 轮函数：从32位到32位的变换

轮函数是整个SM4的发动机。它的输入是三个32位字和一个32位轮密钥，输出是一个32位的结果。轮函数可以分解为三步：异或、S盒替换、线性变换。

咱们一步步拆解：

1. 第一步：异或 —— 把X₁, X₂, X₃和rkᵢ这4个32位数做异或：
   B = X₁ ⊕ X₂ ⊕ X₃ ⊕ rkᵢ
   结果B还是一个32位数。
2. 第二步：S盒替换 —— 把B分成4个字节，每个字节通过一个固定的8×8的S盒，输出一个新的字节。
3. 第三步：线性变换L —— 把S盒输出的32位结果做一次循环移位和异或的组合。

嗯，这里要注意。轮函数中的线性变换L和密钥扩展中的线性变换L'是两回事，它们的结构略有不同。轮函数中的L变换是完整的，而密钥扩展中的L'是简化的。

2.3 S盒：非线性变换

S盒是SM4中唯一的非线性部件。它的作用是打破线性关系，让密码变得难以分析。我当年第一次看SM4的S盒时，觉得这东西就是一张256个字节的查表。

// SM4 S盒，16×16的二维表
static const unsigned char SM4_S[256] = {
    0xD6,0x90,0xE9,0xFE,0xCC,0xE1,0x3D,0xB7,0x16,0xB6,0x14,0xC2,0x28,0xFB,0x2C,0x05,
    0x2B,0x67,0x9A,0x76,0x2A,0xBE,0x04,0xC3,0xAA,0x44,0x13,0x26,0x49,0x86,0x06,0x99,
    0x9C,0x42,0x50,0xF4,0x91,0xEF,0x98,0x7A,0x33,0x54,0x0B,0x43,0xED,0xCF,0xAC,0x62,
    0xE4,0xB3,0x1C,0xA9,0xC9,0x08,0xE8,0x95,0x80,0xDF,0x94,0xFA,0x75,0x8F,0x3F,0xA6,
    0x47,0x07,0xA7,0xFC,0xF3,0x73,0x17,0xBA,0x83,0x59,0x3C,0x19,0xE6,0x85,0x4F,0xA8,
    0x68,0x6B,0x81,0xB2,0x71,0x64,0xDA,0x8B,0xF8,0xEB,0x0F,0x4B,0x70,0x56,0x9D,0x35,
    0x1E,0x24,0x0E,0x5E,0x63,0x58,0xD1,0xA2,0x25,0x22,0x7C,0x3B,0x01,0x21,0x78,0x87,
    0xD4,0x00,0x46,0x57,0x9F,0xD3,0x27,0x52,0x4C,0x36,0x02,0xE7,0xA0,0xC4,0xC8,0x9E,
    0xEA,0xBF,0x8A,0xD2,0x40,0xC7,0x38,0xB5,0xA3,0xF7,0xF2,0xCE,0xF9,0x61,0x15,0xA1,
    0xE0,0xAE,0x5D,0xA4,0x9B,0x34,0x1A,0x55,0xAD,0x93,0x32,0x30,0xF5,0x8C,0xB1,0xE3,
    0x1D,0xF6,0xE2,0x2E,0x82,0x66,0xCA,0x60,0xC0,0x29,0x23,0xAB,0x0D,0x53,0x4E,0x6F,
    0xD5,0xDB,0x37,0x45,0xDE,0xFD,0x8E,0x2F,0x03,0xFF,0x6A,0x72,0x6D,0x6C,0x5B,0x51,
    0x8D,0x1B,0xAF,0x92,0xBB,0xDD,0xBC,0x7F,0x11,0xD9,0x5C,0x41,0x1F,0x10,0x5A,0xD8,
    0x0A,0xC1,0x31,0x88,0xA5,0xCD,0x7B,0xBD,0x2D,0x74,0xD0,0x12,0xB8,0xE5,0xB4,0xB0,
    0x89,0x69,0x97,0x4A,0x0C,0x96,0x77,0x7E,0x65,0xB9,0xF1,0x09,0xC5,0x6E,0xC6,0x84,
    0x18,0xF0,0x7D,0xEC,0x3A,0xDC,0x4D,0x20,0x79,0xEE,0x5F,0x3E,0xD7,0xCB,0x39,0x48
};

S盒的输入是一个8位字节（0-255），输出也是一个8位字节。查表就是最直接、最高效的实现方式。我记得在早期的嵌入式项目中，有人尝试用逻辑门运算代替查表，结果速度慢了十几倍。

2.4 线性变换L：扩散的艺术

S盒输出之后，得到32位的中间结果。这时需要做线性变换L，让这32位的信息扩散到整个输出中。线性变换L的公式如下：

C = B ⊕ (B ≪ 2) ⊕ (B ≪ 10) ⊕ (B ≪ 18) ⊕ (B ≪ 24)

这里的B是S盒输出的32位结果，C是经过线性变换后的结果。每个≪表示循环左移。

这个变换的作用是什么？它让S盒输出的每一个比特，在2、10、18、24位之后的位置都留下痕迹。说白了，就是让雪崩效应更充分。我测试过，去掉线性变换后，SM4的密码强度会急剧下降。

2.5 密钥扩展算法：生成32轮密钥

SM4的主密钥是128位，但我们需要32轮的轮密钥，每轮一个32位。密钥扩展算法就是负责从主密钥派生这32个轮密钥。

密钥扩展的流程：

1. 把128位主密钥分成4个32位字：(MK₀, MK₁, MK₂, MK₃)
2. 用固定常数FK做异或，得到(K₀, K₁, K₂, K₃)：
   K₀ = MK₀ ⊕ FK₀
   K₁ = MK₁ ⊕ FK₁
   K₂ = MK₂ ⊕ FK₂
   K₃ = MK₃ ⊕ FK₃
3. 对i从0到31，用迭代公式生成轮密钥rkᵢ：
   rkᵢ = Kᵢ₊₄ = Kᵢ ⊕ T'(Kᵢ₊₁ ⊕ Kᵢ₊₂ ⊕ Kᵢ₊₃ ⊕ CKᵢ)

这里的T'变换与轮函数中的T变换非常相似，但有一个关键区别：T'中的线性变换是L'，而不是L。L'只是L的简化版：

L'(B) = B ⊕ (B ≪ 13) ⊕ (B ≪ 23)

FK和CK都是固定的常数。FK是系统参数，CK是32个轮常数。这些常数在国密标准文档中都能找到。

2.6 整体流程一览

我把SM4的加解密流程画成了一张图。从图上可以看出，加密和解密的过程几乎一样，只是轮密钥的使用顺序是相反的。

2.7 理论总结

SM4的算法设计本身就考虑到了软件实现的友好性。你想想看，它用的是基本的异或和移位操作，全是CPU擅长的指令。S盒虽然小，但查表访问模式对缓存还算友好。

组件	位宽	作用	实现难度
Feistel网络	128位分组	保证加解密对称	低
轮函数	32位输出	提供密码强度	中
S盒	8×8位	非线性变换	低（查表）
线性变换L	32位	扩散比特	低（移位+异或）
密钥扩展	128位→32×32位	生成轮密钥	中