Back to notebook

对称密码：Feistel 网络、DES、AES 与分组密码工作模式

This post is not yet available in English. Showing the original version.
Notes 密码学 zh-CN
Table of Contents
Table of Contents

本篇系统解析对称密码体制中的核心支柱——分组密码（Block Cipher）。内容涵盖分组密码的设计哲学（混淆与扩散）、经典 Feistel 架构及其可逆性证明、DES 算法细节、AES 的有限域代数基础与四大轮变换，以及主流工作模式的安全性分析与双重加密的中间相遇攻击。

一、分组密码设计哲学：扩散、混淆与乘积密码

在固定密钥 KK 下，分组密码将固定长度的 nn 比特明文块确定性地映射为相同长度的 nn 比特密文块。在数学上，它构成定义在集合 {0,1}n\{0, 1\}^n 上的可逆置换（Permutation）。

香农（Claude Shannon）指出现代分组密码设计的两大核心准则：

  1. 混淆（Confusion）：
    使密文与密钥之间的统计关系尽可能复杂化、非线性化，从而挫败统计分析与代数求解。在算法中通常由非线性代换盒（S-Box）提供。
  2. 扩散（Diffusion）：
    使单个明文比特或密钥比特的微小变化，能够迅速扩散波及至输出密文的每一个比特中（雪崩效应 Avalanche Effect）。在算法中通常由线性置换盒（P-Box）或线性矩阵乘法（如 AES 的 MixColumns）实现。

单纯的固定位置置换（如 DES 的初始置换 IP）属于公开的布线排列，不增加任何熵，也不消除代数线性相关性；密码学强度的本质源于非线性代换（S 盒）与线性扩散（P 盒/行移位/列混淆）在多轮迭代中的交替复合（Substitution-Permutation Network, SPN）。

二、Feistel 密码结构与全局可逆性代数证明

Feistel 网络是构建对称分组密码的最经典范式（为 DES、Blowfish 等算法所采用）。其将输入的 2w2w 比特数据块平分为左右两半 (Li−1,Ri−1)(L_{i-1}, R_{i-1})。

2.1 轮函数推进方程

第 ii 轮（i=1,2,…,ri = 1, 2, \dots, r）的加密计算公式为：

Li=Ri−1,Ri=Li−1⊕f(Ri−1,Ki).L_i = R_{i-1},\qquad R_i = L_{i-1} \oplus f(R_{i-1}, K_i).

在解密端，给定第 ii 轮的输出 (Li,Ri)(L_i, R_i)，其逆向还原计算为：

Ri−1=Li,Li−1=Ri⊕f(Li,Ki).R_{i-1} = L_i,\qquad L_{i-1} = R_i \oplus f(L_i, K_i). 
flowchart TD
    subgraph 加密单轮计算
    L_in["左半部分 L_(i-1)"] --> XOR["⊕ 按位异或"] --> R_out["新右半部分 R_i"]
    R_in["右半部分 R_(i-1)"] --> L_out["新左半部分 L_i (直接直通复制)"]
    R_in --> F["轮函数 f(R_(i-1), K_i)"] --> XOR
    end

2.2 为什么轮函数 ff 无需具备可逆性？

[!IMPORTANT]
Feistel 网络可逆性的严格代数证明：
观察解密过程：由于正向加密时 Ri−1R_{i-1} 被原封不动地直通赋值给了 LiL_i（即 Li=Ri−1L_i = R_{i-1}），因此在解密端，输入 LiL_i 自然包含了计算轮函数 ff 所需的完整输入数据。
将 Ri=Li−1⊕f(Ri−1,Ki)R_i = L_{i-1} \oplus f(R_{i-1}, K_i) 代入解密式：
Li−1=Ri⊕f(Li,Ki)=(Li−1⊕f(Ri−1,Ki))⊕f(Ri−1,Ki)=Li−1⊕0=Li−1.L_{i-1} = R_i \oplus f(L_i, K_i) = \big(L_{i-1} \oplus f(R_{i-1}, K_i)\big) \oplus f(R_{i-1}, K_i) = L_{i-1} \oplus 0 = L_{i-1}.
利用异或运算的结合律与自反性（A⊕B⊕B=AA \oplus B \oplus B = A），轮函数的输出项被自身精确抵消，无损恢复出 Li−1L_{i-1}。

结论：无论轮函数 ff 内部多么复杂（包含剧烈的非线性压缩、不可逆查表或降维），整个 Feistel 网络恒保证在数学上严格可逆。解密算法可完全复用加密硬件架构，仅需将子密钥序列倒序施加（Kr,Kr−1,…,K1K_r, K_{r-1}, \ldots, K_1）。

三、DES 算法数据流推演与位追踪

数据加密标准（DES, Data Encryption Standard）采用 16 轮 Feistel 网络。

64 位明文 ─── 初始置换 (IP) ───> L0 (32 bit) || R0 (32 bit)
                                                      │
R0 (32 bit) ─── E 扩展 ───> 48 bit ──⊕── K1 (48 bit) ──> 8 组 × 6 bit
                                                                 │
                                                       8 个非线性 S 盒 (6 bit -> 4 bit)
                                                                 │
                                                        32 bit ── P 置换 ──> f(R0, K1)
L1 = R0                                R1 = L0 ⊕ f(R0, K1)

3.1 S 盒查表规范与非线性性质

DES 包含 8 个互不相同的 S 盒（S1∼S8S_1 \sim S_8）。每个 S 盒输入 6 比特，输出 4 比特。
对于输入向量 b=(b1b2b3b4b5b6)2b = (b_1 b_2 b_3 b_4 b_5 b_6)_2：

非线性证明：以 S1S_1 为例，输入 0000002000000_2（第 0 行第 0 列）输出为 14（111021110_2）；输入 0000012000001_2（第 1 行第 0 列）输出为 0（000020000_2）。
S1(000000)⊕S1(000001)=11102≠S1(000000⊕000001)=S1(000001)=00002.S_1(000000) \oplus S_1(000001) = 1110_2 \ne S_1(000000 \oplus 000001) = S_1(000001) = 0000_2.
满足 S(x⊕y)≠S(x)⊕S(y)S(x \oplus y) \ne S(x) \oplus S(y)，由此从数学上确证其为强非线性映射。

3.2 密钥编排与雪崩效应（Avalanche Effect）

四、AES 数学代数基础：GF(28)\mathrm{GF}(2^8) 伽罗瓦域

高级加密标准（AES / Rijndael）摒弃了 Feistel 架构，采用代数结构更加严密的代换-置换网络（SPN）。AES 固定处理 128 比特分组，其所有运算均建立在有限域 GF(28)\mathrm{GF}(2^8) 之上。

在 GF(28)\mathrm{GF}(2^8) 中，每个 8 比特字节 (b7b6…b1b0)2(b_7 b_6 \dots b_1 b_0)_2 被严格解释为系数属于 GF(2)\mathrm{GF}(2)（即系数只有 0 或 1）的一元多项式：

b7x7+b6x6+b5x5+b4x4+b3x3+b2x2+b1x+b0.b_7 x^7 + b_6 x^6 + b_5 x^5 + b_4 x^4 + b_3 x^3 + b_2 x^2 + b_1 x + b_0.

例如字节 0x1B 对应二进制 00011011，其多项式形式为 x4+x3+x+1x^4 + x^3 + x + 1。

4.1 有限域加法：按位异或（模 2 加法）

在系数域 GF(2)\mathrm{GF}(2) 中，加法遵循无进位的模 2 加法，满足 1+1=01 + 1 = 0。因此，加法与减法在代数上完全等价，均表现为同次项系数按位异或：

(x3+x2+1)+(x2+x+1)=x3+(1⊕1)x2+x+(1⊕1)=x3+x.(x^3 + x^2 + 1) + (x^2 + x + 1) = x^3 + (1 \oplus 1)x^2 + x + (1 \oplus 1) = x^3 + x.

两个次数小于 8 的多项式相加，最高次数依然小于 8，绝不产生进位，因此有限域加法无需进行模约简。

4.2 有限域乘法与模不可约多项式

两个域元素相乘时，先按普通多项式展开相乘（同次项系数按模 2 累加），随后必须对 AES 规定的标准不可约多项式（Irreducible Polynomial）求同余余式：

P(x)=x8+x4+x3+x+1(十六进制记为 0x11B).P(x) = x^8 + x^4 + x^3 + x + 1\quad (\text{十六进制记为 } \texttt{0x11B}).

在同余意义下，x8≡x4+x3+x+1(modP(x))x^8 \equiv x^4 + x^3 + x + 1 \pmod{P(x)}。任何大于或等于 8 次的高次项均可通过该式代换降次。

手算实例：在 GF(24)\mathrm{GF}(2^4)（模 P(x)=x4+x+1P(x) = x^4 + x + 1）下计算 (x2+1)⋅(x3+x2+1)(x^2 + 1) \cdot (x^3 + x^2 + 1)：

  1. 普通多项式展开：x5+x4+x2+x3+x2+1=x5+x4+x3+1x^5 + x^4 + x^2 + x^3 + x^2 + 1 = x^5 + x^4 + x^3 + 1；
  2. 模约简降次：因 x4≡x+1x^4 \equiv x + 1，且 x5≡x2+xx^5 \equiv x^2 + x；
  3. 代入展开式：(x2+x)+(x+1)+x3+1=x3+x2+(1⊕1)x+(1⊕1)=x3+x2(x^2 + x) + (x + 1) + x^3 + 1 = x^3 + x^2 + (1\oplus 1)x + (1\oplus 1) = x^3 + x^2。

4.3 xtime 算法（乘 xx 运算）

在底层硬件与软件中，乘以 xx 对应于字节的逻辑左移 1 位：

unsigned char xtime(unsigned char b) {
    return (b << 1) ^ ((b & 0x80) ? 0x1B : 0x00);
}

五、AES 轮变换机制与状态矩阵

AES 将 128 比特（16 字节）的输入数据映射为一个以列优先（Column-major）排列的 4×44 \times 4 字节状态矩阵（State Matrix）：

State=[s0,0s0,1s0,2s0,3s1,0s1,1s1,2s1,3s2,0s2,1s2,2s2,3s3,0s3,1s3,2s3,3].\text{State} = \begin{bmatrix} s_{0,0} & s_{0,1} & s_{0,2} & s_{0,3} \\ s_{1,0} & s_{1,1} & s_{1,2} & s_{1,3} \\ s_{2,0} & s_{2,1} & s_{2,2} & s_{2,3} \\ s_{3,0} & s_{3,1} & s_{3,2} & s_{3,3} \end{bmatrix}.

根据密钥长度（128、192、256 比特），算法分别执行 10、12、14 轮。除首轮初始轮密钥加与最终轮外，每一轮标准迭代包含四个级联变换：

flowchart LR
    State["输入状态矩阵"] --> Sub["1. SubBytes<br>(字节代换，非线性S盒)"]
    Sub --> Shift["2. ShiftRows<br>(行移位，行置换打散)"]
    Shift --> Mix["3. MixColumns<br>(列混淆，有限域矩阵扩散)"]
    Mix --> Add["4. AddRoundKey<br>(轮密钥加，异或子密钥)"]
  1. 字节代换（SubBytes）：
    • 作用于状态矩阵的每一个独立字节；
    • 映射规则：求输入字节在有限域 GF(28)\mathrm{GF}(2^8) 上的乘法逆元（规定 0 的逆元为自身），随后施加一次定义在 GF(2)\mathrm{GF}(2) 上的仿射变换，并异或常数 0x63。这是全算法唯一的非线性组件。
  2. 行移位（ShiftRows）：
    • 作用于状态矩阵的各行，执行循环左移操作：
      • 第 0 行：循环左移 0 字节（不移动）；
      • 第 1 行：循环左移 1 字节；
      • 第 2 行：循环左移 2 字节；
      • 第 3 行：循环左移 3 字节。
    • 作用：打破列内相关性，实现跨列解构。
  3. 列混淆（MixColumns）：
    • 将状态矩阵的每一列与一个固定的最大距离可分（MDS）矩阵在有限域 GF(28)\mathrm{GF}(2^8) 上做矩阵相乘：
      [s0,j′s1,j′s2,j′s3,j′]=[02030101010203010101020303010102][s0,js1,js2,js3,j].\begin{bmatrix} s'_{0,j} \\ s'_{1,j} \\ s'_{2,j} \\ s'_{3,j} \end{bmatrix} = \begin{bmatrix} 02 & 03 & 01 & 01 \\ 01 & 02 & 03 & 01 \\ 01 & 01 & 02 & 03 \\ 03 & 01 & 01 & 02 \end{bmatrix} \begin{bmatrix} s_{0,j} \\ s_{1,j} \\ s_{2,j} \\ s_{3,j} \end{bmatrix}.
    • 作用：提供极强的线性扩散性能，单字节变化可在单轮内扩散到整列全部 4 个字节。
  4. 轮密钥加（AddRoundKey）：
    • 将当前状态矩阵与当前轮导出的 128 比特子密钥进行按位异或。

[!NOTE]
结构对称性设计：AES 的最终轮强制省略了 MixColumns（列混淆）变换。该设计使得解密算法的逆向变换结构能够与加密过程保持高度的形式对称，降低了芯片与硬件的门电路实现开销。

六、分组密码工作模式（Modes of Operation）

底层分组密码只能对固定大小的块（如 128 比特）进行变换。工作模式定义了如何安全地处理任意长度的明文流。

模式名称核心加密代数关系解密代数关系安全性特征与适用场景
ECB（电子密码本模式）Ci=EK(Pi)C_i = E_K(P_i)Pi=DK(Ci)P_i = D_K(C_i)严重不安全。相同的明文块必然产生相同的密文块，完全泄露数据分布模式（如 ECB 企鹅图）；易受块重排与替换攻击。在任何工程协议中均被禁用
CBC（密文分组链接模式）Ci=EK(Pi⊕Ci−1)C_i = E_K(P_i \oplus C_{i-1})
（其中 C0=IVC_0 = IV）		Pi=DK(Ci)⊕Ci−1P_i = D_K(C_i) \oplus C_{i-1}密文具备链式扩散性。必须配备随机且不可预测的初始向量 IVIV；密文单比特损坏将彻底摧毁当前明文块，并使下一明文块对应比特翻转；加密串行不可并行，解密可并行
OFB（输出反馈模式）Zi=EK(Zi−1), Z0=IVZ_i = E_K(Z_{i-1}),\ Z_0=IV
Ci=Pi⊕ZiC_i = P_i \oplus Z_i		Pi=Ci⊕ZiP_i = C_i \oplus Z_i同步序列密码。密钥流 ZiZ_i 完全独立于明文和密文；IV 绝不可复用；密文单比特传输错误仅影响明文对应单比特，无错误传播
CFB（密文反馈模式）Ci=Pi⊕EK(Ci−1)C_i = P_i \oplus E_K(C_{i-1})Pi=Ci⊕EK(Ci−1)P_i = C_i \oplus E_K(C_{i-1})自同步序列密码。将分组密码转化为自同步流密码，解密端仅调用底层加密函数 EKE_K
CTR（计数器模式）Ci=Pi⊕EK(Nonce∥i)C_i = P_i \oplus E_K(\text{Nonce} \parallel i)Pi=Ci⊕EK(Nonce∥i)P_i = C_i \oplus E_K(\text{Nonce} \parallel i)现代主流流模式。计数器块必须保证全网唯一；加解密均仅调用 EKE_K；支持完全的硬件多核并行处理与随机位置读写访问

七、复合加密结构与代数消去攻击

7.1 双重加密与中间相遇攻击（Meet-in-the-Middle Attack）

为了增加密钥长度，一种朴素构想是采用双重加密体制：

C=EK2(EK1(P)),C = E_{K_2}(E_{K_1}(P)),

其中 K1,K2K_1, K_2 均为 kk 比特密钥。直觉上密钥空间似乎达到了 22k2^{2k}。然而，Diffie 和 Hellman 提出的中间相遇攻击证明其计算安全强度仅为 O(2k)O(2^k)：

flowchart LR
    P["明文 P"] -->|尝试所有 2^k 个 K1| M1["中间值 X = E_K1(P)<br>(存入哈希查找表)"]
    C["密文 C"] -->|尝试所有 2^k 个 K2| M2["中间值 X' = D_K2(C)"]
    M1 <-->|"在表中匹配碰撞: X == X' !"| M2
  1. 预计算阶段：攻击者已知一对明密文 (P,C)(P, C)。枚举所有 2k2^k 个可能的 K1K_1，计算正向中间值 X=EK1(P)X = E_{K_1}(P)，并将映射 (X→K1)(X \to K_1) 存入内存哈希表中。耗时 O(2k)O(2^k)，空间 O(2k)O(2^k)；
  2. 碰撞匹配阶段：枚举所有 2k2^k 个可能的 K2K_2，反向计算候选中间值 X′=DK2(C)X' = D_{K_2}(C)，在哈希表中检索 X′X'。若命中，则 (K1,K2)(K_1, K_2) 即为一个候选有效密钥对。
  3. 误判滤除：针对命中的候选密钥对，引入第二组明密文对 (P′,C′)(P', C') 进行验证以排除伪密钥。

结论：双重加密的时间复杂度为 2k+2k=2k+12^k + 2^k = 2^{k+1}，并未提供预期的平方级安全增益。这一漏洞促成了三重数据加密标准（3DES）的诞生（C=EK3(DK2(EK1(P)))C = E_{K_3}(D_{K_2}(E_{K_1}(P)))）。

7.2 输出白化（Output Whitening）与线性掩码消去

考虑形如 DESA 的变体结构：C=DESK(P)⊕K1C = \mathrm{DES}_K(P) \oplus K_1，其中 KK 为 56 比特主密钥，K1K_1 为 64 比特外部白化掩码。

攻击者无需在 256+64=21202^{56 + 64} = 2^{120} 的空间内盲目穷举。只需获取两组明密文对 (P1,C1),(P2,C2)(P_1, C_1), (P_2, C_2)：

  1. 枚举 56 比特候选主密钥 K′K'，由第一对数据反算出唯一适配的掩码：
    K1′=C1⊕DESK′(P1);K'_1 = C_1 \oplus \mathrm{DES}_{K'}(P_1);
  2. 将该对 (K′,K1′)(K', K'_1) 代入第二组数据进行检验：检查是否满足：
    C2=?DESK′(P2)⊕K1′.C_2 \stackrel{?}{=} \mathrm{DES}_{K'}(P_2) \oplus K'_1.

结论：在线性层叠加未知的密钥掩码无法提升非线性主变换的密码分析复杂度。攻击的时间复杂度依然严格受控于主密钥空间 O(256)O(2^{56})。

0 / 2000
Loading comments...