SM4分组密码算法的Feistel结构解密正确性证明

题目描述
SM4算法是中国国家商用密码标准中的一种分组密码算法，其采用非平衡Feistel网络结构，分组长度为128位，密钥长度也为128位，共进行32轮迭代。题目要求：详细证明SM4算法采用的非平衡Feistel结构在解密过程中，只要按照与加密相反的次序使用轮密钥，就能正确恢复出原始明文。请循序渐进地解释每一轮加解密的状态变化，直至完成整个证明。

解题过程

SM4的加解密过程都使用相同的轮函数F，但解密时轮密钥的使用顺序与加密相反。证明的核心在于展示，当从最后一轮加密状态开始，用逆序的轮密钥进行同样轮函数的运算，可以一步一步回到初始状态。

1. SM4的非平衡Feistel结构回顾
SM4将128位的输入分组分为4个32位的字：(X_0, X_1, X_2, X_3)。
加密时，对于 i = 0, 1, ..., 31，轮运算为：

X_{i+4} = F(X_i, X_{i+1}, X_{i+2}, X_{i+3}, rk_i)

其中 rk_i 是第 i 轮的轮密钥。轮函数 F 定义为：

F(A, B, C, D, rk) = A ⊕ T(B ⊕ C ⊕ D ⊕ rk)

这里 T 是一个可逆变换，由非线性变换 τ（4个并行的8进8出S盒）和线性变换 L 复合而成，即 T(·) = L(τ(·))。
由于 T 是双射（一一对应），其逆变换 T^{-1} 存在。

一轮操作可以看作是将状态寄存器 (X_i, X_{i+1}, X_{i+2}, X_{i+3}) 左移一字，并填入新计算出的 X_{i+4}。加密完成32轮后，输出为 (X_32, X_33, X_34, X_35)。最后的输出经过一个反序变换：(Y_0, Y_1, Y_2, Y_3) = (X_35, X_34, X_33, X_32) 作为密文。

2. 解密过程的设定
解密时，输入是密文 (Y_0, Y_1, Y_2, Y_3)。我们首先将其反序，得到解密过程的初始状态：

D_0 = Y_3 = X_32
D_1 = Y_2 = X_33
D_2 = Y_1 = X_34
D_3 = Y_0 = X_35

解密过程同样进行32轮迭代，使用相同的轮函数F，但轮密钥使用顺序为 rk_31, rk_30, ..., rk_0。解密轮运算记为：

D_{i+4} = F(D_i, D_{i+1}, D_{i+2}, D_{i+3}, rk_{31-i})

其中 i = 0, 1, ..., 31。解密完成后输出 (D_32, D_33, D_34, D_35)，并期望它等于加密前的明文 (X_0, X_1, X_2, X_3)。

3. 证明思路：数学归纳法
我们将证明：对于所有 j = 0, 1, ..., 36，有等式

D_j = X_{35-j}   （关键关系式）

当 j = 0,1,2,3 时，根据解密初始状态设定，显然成立：

D_0 = X_32 = X_{35-3}? 这里需要小心下标。实际上，我们需验证 D_0 = X_{35} 吗？不，根据设定 D_0 = X_32，而 X_{35-0}=X_35，不相等。所以我们需要调整假设。

实际上，观察加解密的对称性，正确的对应关系是：解密过程的第 i 轮状态 (D_i, D_{i+1}, D_{i+2}, D_{i+3}) 应该等于加密过程中第 (32-i) 轮状态的某个顺序反转。更精确的，我们直接验证一轮的可逆性。

4. 单轮的可逆性推导
考虑加密的第 r 轮（r 从0开始）：
已知加密状态 (X_r, X_{r+1}, X_{r+2}, X_{r+3})，计算

X_{r+4} = F(X_r, X_{r+1}, X_{r+2}, X_{r+3}, rk_r) = X_r ⊕ T(X_{r+1} ⊕ X_{r+2} ⊕ X_{r+3} ⊕ rk_r)

加密后状态变为 (X_{r+1}, X_{r+2}, X_{r+3}, X_{r+4})。

现在假设我们从加密后的状态开始解密，即设：

D_0 = X_{r+3}
D_1 = X_{r+2}
D_2 = X_{r+1}
D_3 = X_{r+4}

注意这里顺序是反的：(D_0, D_1, D_2, D_3) = (X_{r+3}, X_{r+2}, X_{r+1}, X_{r+4})。如果我们用解密密钥 rk_r（注意解密时对应这一轮的密钥正是 rk_r，因为顺序相反，这里假设这是解密的第某轮对应的加密密钥）计算下一状态：

D_4 = F(D_0, D_1, D_2, D_3, rk_r)
    = D_0 ⊕ T(D_1 ⊕ D_2 ⊕ D_3 ⊕ rk_r)
    = X_{r+3} ⊕ T( X_{r+2} ⊕ X_{r+1} ⊕ X_{r+4} ⊕ rk_r )

但 X_{r+4} = X_r ⊕ T(X_{r+1} ⊕ X_{r+2} ⊕ X_{r+3} ⊕ rk_r)，代入得：

D_4 = X_{r+3} ⊕ T( X_{r+2} ⊕ X_{r+1} ⊕ [X_r ⊕ T(X_{r+1} ⊕ X_{r+2} ⊕ X_{r+3} ⊕ rk_r)] ⊕ rk_r )
    = X_{r+3} ⊕ T( X_{r+1} ⊕ X_{r+2} ⊕ X_r ⊕ T(X_{r+1} ⊕ X_{r+2} ⊕ X_{r+3} ⊕ rk_r) ⊕ rk_r )

由于 T 是线性变换 L 和非线性 τ 的复合，且 L 是线性，τ 是双射，整个 T 是双射。注意到变量 U = X_{r+1} ⊕ X_{r+2} ⊕ X_{r+3} ⊕ rk_r，则 T(U) = L(τ(U))。那么：

参数 = X_{r+1} ⊕ X_{r+2} ⊕ X_r ⊕ T(U) ⊕ rk_r
     = (X_{r+1} ⊕ X_{r+2} ⊕ X_{r+3} ⊕ rk_r) ⊕ X_r ⊕ T(U) ⊕ X_{r+3}   （因为加了又减X_{r+3}）
     = U ⊕ X_r ⊕ T(U) ⊕ X_{r+3}

于是：

D_4 = X_{r+3} ⊕ T( U ⊕ X_r ⊕ T(U) ⊕ X_{r+3} )

这看起来复杂。实际上更简洁的方法是：在非平衡Feistel中，解密时用相同轮函数但反向密钥顺序，是因为加密时 X_{r+4} 依赖于 X_r 和 T(···)，而解密时可以从 X_{r+4} 和 X_{r+1}, X_{r+2}, X_{r+3} 恢复出 X_r。

5. 直接构造解密正确性
我们从加密最后的状态开始：
加密第31轮后，状态为 (X_31, X_32, X_33, X_34)，第32轮（最后一轮，r=31）使用 rk_31 计算：

X_35 = F(X_31, X_32, X_33, X_34, rk_31) = X_31 ⊕ T(X_32 ⊕ X_33 ⊕ X_34 ⊕ rk_31)

加密最终输出密文为 (X_35, X_34, X_33, X_32)。

解密初始状态设为：

D_0 = X_35
D_1 = X_34
D_2 = X_33
D_3 = X_32

解密第一轮（i=0）使用 rk_31（因为解密轮密钥顺序为 rk_31, rk_30, ...）：

D_4 = F(D_0, D_1, D_2, D_3, rk_31)
    = D_0 ⊕ T(D_1 ⊕ D_2 ⊕ D_3 ⊕ rk_31)
    = X_35 ⊕ T(X_34 ⊕ X_33 ⊕ X_32 ⊕ rk_31)

但由加密最后一轮可知：

X_35 = X_31 ⊕ T(X_32 ⊕ X_33 ⊕ X_34 ⊕ rk_31)

且 T 的输入中，X_34 ⊕ X_33 ⊕ X_32 = X_32 ⊕ X_33 ⊕ X_34（异或交换律），所以

D_4 = [X_31 ⊕ T(X_32 ⊕ X_33 ⊕ X_34 ⊕ rk_31)] ⊕ T(X_32 ⊕ X_33 ⊕ X_34 ⊕ rk_31)
    = X_31

于是解密第一轮后，状态变为 (D_1, D_2, D_3, D_4) = (X_34, X_33, X_32, X_31)，这恰好是加密第31轮的状态 (X_34, X_33, X_32, X_31) 吗？注意加密第31轮后状态是 (X_31, X_32, X_33, X_34)，顺序不同。但解密这一步后得到的状态顺序是 (X_34, X_33, X_32, X_31)，实际上是加密第30轮输出状态的某个反序？我们需要继续。

6. 一般性推导
观察发现，加密中状态是4字的滑动窗口，每轮左移一字。解密时，我们实际上在逆向滑动。可以归纳证明：解密第 i 轮（i 从0开始）开始时的状态为

(D_i, D_{i+1}, D_{i+2}, D_{i+3}) = (X_{35-i}, X_{34-i}, X_{33-i}, X_{32-i})

用数学归纳法：

• 基始：i=0 时，(D_0, D_1, D_2, D_3) = (X_35, X_34, X_33, X_32)，成立。
• 归纳：假设对某个 i 成立，解密使用轮密钥 rk_{31-i} 计算：

D_{i+4} = F(D_i, D_{i+1}, D_{i+2}, D_{i+3}, rk_{31-i})
       = X_{35-i} ⊕ T( X_{34-i} ⊕ X_{33-i} ⊕ X_{32-i} ⊕ rk_{31-i} )

由加密过程，在第 (31-i) 轮（加密轮数从0到31）有：

X_{35-i} = X_{31-i} ⊕ T( X_{32-i} ⊕ X_{33-i} ⊕ X_{34-i} ⊕ rk_{31-i} )

注意加密中 T 的输入顺序是 X_{32-i} ⊕ X_{33-i} ⊕ X_{34-i}，与我们解密中的 X_{34-i} ⊕ X_{33-i} ⊕ X_{32-i} 相同（异或交换律）。因此：

D_{i+4} = [X_{31-i} ⊕ T(···)] ⊕ T(···) = X_{31-i}

于是：

(D_{i+1}, D_{i+2}, D_{i+3}, D_{i+4}) = (X_{34-i}, X_{33-i}, X_{32-i}, X_{31-i})

这正是 (X_{35-(i+1)}, X_{34-(i+1)}, X_{33-(i+1)}, X_{32-(i+1)})，归纳假设对 i+1 成立。

7. 解密最终结果
当 i=31 时，解密完成后状态为：

(D_32, D_33, D_34, D_35) = (X_{35-32}, X_{34-32}, X_{33-32}, X_{32-32}) = (X_3, X_2, X_1, X_0)

但SM4解密输出前有一个反序变换（与加密最后的反序对应），即输出为 (D_35, D_34, D_33, D_32) = (X_0, X_1, X_2, X_3)，这正是原始的明文。证明完成。

总结
SM4的非平衡Feistel结构中，轮函数F在加密和解密中完全相同，只需将轮密钥序逆序，即可正确解密。核心在于每轮解密计算出的新字正是加密过程中对应轮次被替换掉的旧字，从而状态逐轮反向回溯到初始明文。整个证明利用了轮函数F中异或与可逆变换T的性质，以及归纳法清晰地展示了状态对应关系。