SM4 分组密码算法推导
SM4是一种分组密码算法，其分组长度和密钥长度均为128位。它采用32轮迭代的非平衡Feistel结构。
1. 初始设定
明文分组长度为128位，密钥长度为128位。首先，将128位的输入明文 $P$ 分为4个32位的字 $(X_0, X_1, X_2, X_3)$。
$$ P = (X_0, X_1, X_2, X_3) \quad \text{其中 } X_i \in \{0,1\}^{32} $$
加密过程共进行 $i=0, 1, \dots, 31$ 共32轮迭代。
2. 轮函数 F
SM4的精髓在于其轮函数 $F$。每一轮的输入为4个32位的字 $(X_i, X_{i+1}, X_{i+2}, X_{i+3})$ 和一个32位的轮密钥 $rk_i$。
$$ X_{i+4} = F(X_i, X_{i+1}, X_{i+2}, X_{i+3}, rk_i) $$
这个函数具体定义为：
$$ X_{i+4} = X_i \oplus T(X_{i+1} \oplus X_{i+2} \oplus X_{i+3} \oplus rk_i) $$
3. T 变换
轮函数中的核心是合成变换 $T$，$T$ 是一个可逆的32位输入到32位输出的变换，由一个非线性变换 $\tau$ 和一个线性变换 $L$ 复合而成。
$$ T(A) = L(\tau(A)) $$
- 非线性变换 $\tau$:
这个变换将一个32位的字 $A$ 分为4个8位的字节 $(a_0, a_1, a_2, a_3)$，然后分别对每个字节进行S盒（S-box）代换，最后将结果合并成一个32位的字 $B$。
$$ A = (a_0, a_1, a_2, a_3) \quad \text{其中 } a_j \in \{0,1\}^8 $$
$$ B = \tau(A) = (Sbox(a_0), Sbox(a_1), Sbox(a_2), Sbox(a_3)) $$
S盒是一个预定义的8位输入到8位输出的非线性置换表，提供了抗击差分分析和线性分析的能力。
- 线性变换 $L$:
这个变换对32位的输入 $B$ 进行线性混合，以增强扩散性。它通过异或和循环移位操作实现。
$$ L(B) = B \oplus (B \lll 2) \oplus (B \lll 10) \oplus (B \lll 18) \oplus (B \lll 24) $$
其中 $\lll k$ 表示循环左移 $k$ 位。
4. 输出
经过32轮迭代后，得到 $(X_{32}, X_{33}, X_{34}, X_{35})$。最后将这4个字进行一次反序变换 $R$，得到密文输出 $C$。
$$ C = R(X_{32}, X_{33}, X_{34}, X_{35}) = (X_{35}, X_{34}, X_{33}, X_{32}) $$
5. 密钥扩展
SM4的128位主密钥 $MK$ 也被分为4个32位的字 $(MK_0, MK_1, MK_2, MK_3)$。轮密钥 $rk_i$ 由主密钥通过一个类似的迭代过程生成，同样也使用了S盒。
与AES的不同之处
SM4和AES（高级加密标准）虽然都是128位分组的对称密码算法，但它们的内部结构和设计哲学有显著不同。
| 特性 | SM4 (GM/T 0002-2012) | AES (Rijndael) |
|---|---|---|
| 核心结构 | Feistel 网络 | SPN (Substitution-Permutation Network) |
| 分组长度 | 128 位 | 128 位 |
| 密钥长度 | 128 位 | 128, 192, 或 256 位 |
| 迭代轮数 | 32 轮 | 10, 12, 或 14 轮 (取决于密钥长度) |
| 加密/解密 | 结构相同，仅轮密钥顺序相反 | 解密是加密的逆过程，需要逆向操作（如InvMixColumns） |
1. 结构差异 (Feistel vs. SPN)
- SM4 (Feistel网络):
Feistel结构将数据块分成两半（在SM4中是分成4个字，但本质上是非平衡Feistel），在每一轮中，一块数据通过一个轮函数 $F$ 进行处理，其结果与另一块数据进行异或。这种结构的一个巨大优势是加解密过程非常相似，解密时只需按相反的顺序使用轮密钥即可，这在硬件实现上可以节省资源。
- AES (SPN网络):
SPN结构在每一轮中都对整个数据块进行操作。AES的一轮由四个阶段组成：
SubBytes: 类似于SM4的S盒变换，进行非线性替换。
$$ S'_{i,j} = \text{S-box}(S_{i,j}) $$
ShiftRows: 对状态矩阵的行进行循环移位，实现置换。
$$ S'_{i,j} = S_{i, (j + \text{shift}(i, N_b)) \pmod{N_b}} $$
MixColumns: 对状态矩阵的列进行线性混合，提供扩散。
$$ S'_j = \text{MixColumns}(S_j) $$
AddRoundKey: 将轮密钥与状态矩阵异或。
$$ S' = S \oplus \text{RoundKey} $$
AES的每一轮操作都作用于整个128位的状态，扩散速度更快。但解密时需要实现InvSubBytes, InvShiftRows, InvMixColumns等逆运算。
2. S盒设计
SM4和AES都使用了S盒来实现非线性替换。 两者都基于有限域 $GF(2^8)$ 上的求逆运算，但SM4的S盒在求逆后还进行了不同的仿射变换，因此两个S盒是不同的。
Python 可视化SM4的线性变换L
SM4中的线性变换 $L$ 是一个很好的可视化对象，因为它只涉及到位操作。下面的Python代码将演示一个32位的字如何经过 $L$ 变换。
# -*- coding: utf-8 -*-
def rol(x, n):
"""
Performs a 32-bit left circular shift (rotate left).
Args:
x (int): The 32-bit integer to rotate.
n (int): The number of bits to rotate by.
Returns:
int: The rotated 32-bit integer.
"""
return ((x << n) & 0xFFFFFFFF) | (x >> (32 - n))
def L_transform(B):
"""
Applies the linear transformation L of the SM4 algorithm.
L(B) = B ^ rol(B, 2) ^ rol(B, 10) ^ rol(B, 18) ^ rol(B, 24)
Args:
B (int): A 32-bit integer.
Returns:
int: The result of the L transformation.
"""
return B ^ rol(B, 2) ^ rol(B, 10) ^ rol(B, 18) ^ rol(B, 24)
def visualize_L_transform(input_hex):
"""
Visualizes the L transformation step-by-step.
Args:
input_hex (str): A 32-bit hex string (e.g., "01234567").
"""
B = int(input_hex, 16)
term1 = B
term2 = rol(B, 2)
term3 = rol(B, 10)
term4 = rol(B, 18)
term5 = rol(B, 24)
result = term1 ^ term2 ^ term3 ^ term4 ^ term5
print(f"SM4 线性变换 L 的可视化过程")
print("-" * 40)
print(f"输入 B (Hex): 0x{input_hex}")
print(f"输入 B (Bin): {B:032b}\n")
print("计算 L(B) = B ⊕ (B <<< 2) ⊕ (B <<< 10) ⊕ (B <<< 18) ⊕ (B <<< 24)\n")
print(f" B = {term1:032b}")
print(f" (B <<< 2) = {term2:032b}")
print(f" (B <<< 10) = {term3:032b}")
print(f" (B <<< 18) = {term4:032b}")
print(f" (B <<< 24) = {term5:032b}")
print("------------------------------------------ (XOR all terms)")
print(f" L(B) (Bin) = {result:032b}")
print(f" L(B) (Hex) = 0x{result:08x}")
print("-" * 40)
# 使用一个示例输入来运行可视化
# 这个值是 SM4 官方标准文档附录中的一个中间值
example_input = "657E5274"
visualize_L_transform(example_input)SM4 线性变换 L 的可视化过程
输入 B (Hex): 0x657E5274
输入 B (Bin): 01100101011111100101001001110100计算 L(B) = B ⊕ (B <<< 2) ⊕ (B <<< 10) ⊕ (B <<< 18) ⊕ (B <<< 24)
B = 01100101011111100101001001110100(B <<< 2) = 10010101111110010100100111010001
(B <<< 10) = 11111001010010011101000110010101
(B <<< 18) = 01001001110100011001010111111001
(B <<< 24) = 01110100011001010111111001010010------------------------------------------ (XOR all terms)
L(B) (Bin) = 00110100011110100010000110011011
L(B) (Hex) = 0x347a219b
作者：GARFIELDTOM
邮箱：coolerxde@gt.ac.cn