3448 字
17 分钟
DES 与 Feistel 网络:理解经典分组密码的轮函数设计

DES(Data Encryption Standard,数据加密标准)是学习分组密码结构时最经典的例子之一。它并不再适合保护今天的新系统:DES 的有效密钥只有 56 位,已经可以被现代设备通过穷举搜索攻破。但它的结构非常适合用来理解一个重要问题:一个分组密码如何把明文和密钥加工成密文,以及为什么一个看起来并不复杂的轮函数,经过多轮组合后能够产生较强的混淆和扩散效果。

本文重点关注两件事:

  • Feistel 网络如何组织左右两半数据,使轮函数可以不要求可逆;
  • DES 的轮函数 F(R, K) 如何通过 E 盒扩展、异或、S 盒非线性代换和 P 置换,把 32 位输入变成 32 位输出。

一、先看 DES 的整体结构#

DES 每次处理一个 64 位分组,输入是一块 64 位明文,输出是一块 64 位密文。它先对明文做初始置换 IP,再进行 16 轮 Feistel 处理,最后做逆初始置换 IP⁻¹。

DES 加密的全局流程:初始置换、16 轮处理和逆初始置换

上图把 DES 的全局控制流画了出来。可以先忽略每一轮内部的细节,把整个过程记成:

64 位明文
→ 初始置换 IP
→ 分为 L₀ 和 R₀(各 32 位)
→ 进行 16 轮 Feistel 变换
→ 交换最后一轮的左右部分
→ 逆初始置换 IP⁻¹
→ 64 位密文

需要注意,IP 和 IP⁻¹ 主要是固定的比特重排,并不是把数据“加密”了。它们本身不提供复杂的非线性,也不是 DES 安全性的核心。真正产生混淆和扩散效果的,是 16 轮中反复执行的轮函数、S 盒和左右交换。

二、DES 的参数速览#

参数取值含义
分组长度64 bit每次处理 64 位明文或密文
标称密钥长度64 bit其中 8 位用于奇偶校验
有效密钥长度56 bit真正参与密钥调度的密钥位数
Feistel 轮数16每轮使用一个 48 位子密钥
左、右半部各 32 bitIP 之后拆出的两半数据
E 盒输出48 bit将右半部扩展后与子密钥异或
S 盒输出32 bit8 个 S 盒各输出 4 位
P 盒输出32 bit对 S 盒结果再次置换,制造扩散

DES 的密钥输入通常写作 64 位,但每 8 位中有 1 位是奇偶校验位,因此有效密钥只有 56 位。之后密钥还会被分割、循环左移并经过选择置换,生成 K₁ 到 K₁₆ 共 16 个 48 位轮密钥。

三、Feistel 网络:DES 的骨架#

初始置换完成后,64 位数据被分为两个 32 位部分:

IP(X)=(L0,R0)IP(X) = (L_0, R_0)

第 ii 轮的计算规则是:

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

这里:

  • Li−1L_{i-1} 是上一轮的左半部;
  • Ri−1R_{i-1} 是上一轮的右半部;
  • KiK_i 是第 ii 轮的 48 位子密钥;
  • FF 是轮函数,输入 32 位右半部和 48 位子密钥,输出 32 位结果;
  • ⊕\oplus 是按位异或。

这组公式可以用一句话概括:上一轮的右半部直接成为这一轮的左半部;上一轮的左半部与轮函数结果异或后,成为这一轮的右半部。

为什么轮函数不需要可逆#

这是 Feistel 网络最值得理解的设计。轮函数 F 可以包含压缩、查表甚至不可逆的操作,但整个网络仍然可以解密。

由加密过程可得:

Ri−1=LiR_{i-1} = L_i

代入另一条公式:

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

因此,已知 (Li,Ri)(L_i, R_i) 和 KiK_i,就能恢复 (Li−1,Ri−1)(L_{i-1}, R_{i-1})。解密时按相反顺序使用子密钥即可,轮函数本身不必单独求逆。

Feistel 网络的核心优势

轮函数可以专注于提供非线性和扩散,不必为了可逆性额外设计一个复杂的逆函数。这也是 Feistel 结构长期影响分组密码设计的原因之一。

四、轮函数 F 的完整流程#

DES 的轮函数可以写成:

32 位 R
→ E 盒扩展为 48 位
→ 与 48 位子密钥 Kᵢ 异或
→ 分成 8 组,每组 6 位
→ 分别进入 8 个 S 盒,每组变成 4 位
→ 拼接成 32 位
→ P 盒置换
→ 输出 32 位 F(R, Kᵢ)

DES 单轮内部的轮函数:E 盒、异或、S 盒和直通 P 盒

这张图描述的是单独一轮中的 F(R, K),它和上一张全局图是互补关系:全局图告诉我们 16 轮如何串起来,轮函数图则展开其中一轮究竟做了什么。

1. E 盒扩展:32 位为什么变成 48 位#

E 盒(Expansion Permutation)接收右半部 R 的 32 位,输出 48 位。它不是数学意义上的加密盒,而是一张固定的比特选择表:部分输入位会被复制,部分相邻位会被放到同一个 6 位分组的边界位置。

把 32 位的 R 写成 8 个 4 位小组:

R = [b₁ b₂ b₃ b₄] [b₅ b₆ b₇ b₈] ... [b₂₉ b₃₀ b₃₁ b₃₂]

E 盒会把每个 4 位小组扩展为 6 位。中间某个小组的直观形式是:

原始局部数据: a b c d
扩展后形式: 前一组末位 a b c d 后一组首位

在 DES 的标准 E 表中,32 个输入位经过固定选择后变成 48 位;因此并不是增加了新的信息,而是重复利用部分位并改变排列。这样的设计有两个直接作用:

  1. 让每个 6 位 S 盒输入同时包含当前局部位和相邻位置的边界位,使相邻区域产生联系;
  2. 把右半部扩展到和子密钥相同的 48 位,便于直接进行异或。

E 盒的结果记作 E(R),接下来执行:

E(R)⊕KiE(R) \oplus K_i

这里的异或是逐位进行的:相同为 0,不同为 1。例如:

101100
⊕ 011010
= 110110

这个步骤把数据与本轮密钥结合起来。即使 R 相同,只要子密钥不同,送入 S 盒的结果也会不同。

2. S 盒:真正引入非线性的地方#

S 盒(Substitution Box)是 DES 轮函数中最关键的非线性组件。E 盒和 P 盒都主要是固定重排,而 S 盒不是简单搬移比特,而是按照预先设计的查找表,把 6 位输入映射成 4 位输出。

DES 一共有 8 个 S 盒:S₁ 到 S₈。48 位异或结果被切分为 8 组,每组 6 位。每个 S 盒的操作步骤完全相同,但使用的查找表不同。

对某个 6 位输入 b₁b₂b₃b₄b₅b₆:

第一步:用首尾两位确定行#

取第 1 位和第 6 位组成行号:

row=(b1b6)2row = (b_1b_6)_2

两位可以表示 00、01、10、11,所以行号范围是 0 到 3。

第二步:用中间四位确定列#

取第 2 到第 5 位组成列号:

column=(b2b3b4b5)2column = (b_2b_3b_4b_5)_2

四位可以表示 0 到 15,因此每个 S 盒本质上是一张 4 行 × 16 列的表,共 64 个表项。

第三步:查表得到 4 位输出#

把行号和列号送入对应的 S 盒查表,得到一个 0 到 15 之间的数,再写成 4 位二进制。8 个 S 盒各输出 4 位,最后重新拼接为 32 位:

6×8=48 bit→S-boxes4×8=32 bit6 \times 8 = 48 \text{ bit} \quad\xrightarrow{S\text{-boxes}}\quad 4 \times 8 = 32 \text{ bit}

举一个不依赖具体 S 盒表项的操作例子。假设某组输入是:

011011

那么:

  • 首尾两位是 01,行号为 1;
  • 中间四位是 1101,列号为 13;
  • 在对应的 S 盒第 1 行、第 13 列查找;
  • 将查到的数编码成 4 位输出。

这里的表项必须使用 DES 标准规定的固定表,不能临时选择。S 盒的设计决定了非线性的具体性质,也决定了差分分析、线性分析等攻击面对的结构。

为什么 S 盒不能只是重新排列

如果 S 盒只是交换或复制输入位,那么整个轮函数仍接近线性变换,攻击者可以更容易地建立输入、输出和密钥之间的关系。S 盒通过查表完成非线性代换,让这种关系变得复杂;经过多轮后,局部输入变化会影响大量输出位。

3. P 盒置换:把局部变化扩散出去#

8 个 S 盒输出的 32 位结果会进入 P 盒(Straight Permutation,直通置换)。P 盒仍然是一张固定置换表,它不改变比特数量,只是把 32 个位置重新排列。

P 盒的作用不是再增加非线性,而是扩散:某个 S 盒输出的 4 位,会被重新分散到下一轮不同位置。下一轮经过 E 盒后,这些位置又会和相邻区域组合,最终让一个输入比特的影响逐步传播到整个分组。

部件输入与输出主要作用
E 盒32 → 48 bit扩展、复制边界位、连接相邻区域
异或48 bit 与 48 bit混合本轮子密钥
S 盒48 → 32 bit查表代换,引入非线性
P 盒32 → 32 bit重排结果,促进跨区域扩散

最终可以写成:

F(R,Ki)=P(S(E(R)⊕Ki))F(R, K_i) = P\bigl(S(E(R) \oplus K_i)\bigr)

其中 S 表示 8 个 S 盒分别处理后再拼接。

五、子密钥是怎样生成的#

DES 的 64 位密钥并不会直接作为每一轮的密钥使用,而是经过密钥调度生成 16 个轮密钥。

64 位输入密钥
→ PC-1:去掉 8 个奇偶校验位
→ 得到 56 位
→ 分成 C₀、D₀(各 28 位)
→ 每轮循环左移
→ PC-2:选择并压缩为 48 位
→ 得到 K₁ ... K₁₆

具体来说,PC-1 将 64 位密钥置换并去掉校验位,得到 56 位,再分为两个 28 位部分 C 和 D。每轮对它们进行 1 位或 2 位的循环左移,然后拼接成 56 位,经 PC-2 选择出 48 位,作为当前轮的 Kᵢ。

所以,数据路径中的 E 盒是 32 → 48,密钥路径中的 PC-2 则是 56 → 48。二者输出长度相同,正好可以在轮函数入口处异或。

六、16 轮之后如何得到密文#

完成第 16 轮后得到 L₁₆ 和 R₁₆。DES 在应用逆初始置换之前会进行最后一次左右交换,形成:

R16L16R_{16}L_{16}

然后执行逆初始置换:

C=IP−1(R16∥L16)C = IP^{-1}(R_{16} \| L_{16})

其中 ‖ 表示拼接。这个“最后交换”经常是流程图中容易被忽略的一步,也是实现 DES 时容易出现偏差的地方。

七、DES 为什么既能加密又能解密#

Feistel 结构的解密过程与加密过程使用相同的轮函数,只改变子密钥顺序:

加密:K₁,K₂,...,K₁₆
解密:K₁₆,K₁₅,...,K₁

原因在于每轮的左右关系可以从后向前恢复,而不需要计算 F 的逆函数。对于 DES 来说,E 盒、S 盒和 P 盒在解密时仍然按同样的方式执行;改变的是送入轮函数的子密钥顺序。

八、混淆、扩散与雪崩效应#

DES 的安全结构可以从两个经典目标理解:

混淆#

混淆希望让密钥与密文之间的关系尽量复杂。DES 中最重要的混淆来源是 S 盒:它把输入按照非线性查找表映射到输出,阻止攻击者简单地用线性关系描述轮函数。

扩散#

扩散希望让一个输入比特的影响传播到越来越多的输出比特。E 盒复制边界位,P 盒重新分散 S 盒输出,下一轮又会把这些位置带入不同的 S 盒。16 轮迭代后,单个明文位或密钥位的变化会影响密文中的许多位置,这就是雪崩效应的直观来源。

E 盒、P 盒:让影响传播得更广(扩散)
S 盒 :让输入输出关系更难预测(混淆)
多轮 Feistel:反复叠加两种效果

九、DES 的安全性与今天的使用边界#

DES 的主要问题不是 Feistel 思想失效,而是密钥空间太小。它的有效密钥长度只有 56 位,现代计算能力已经足以对其进行实际的穷举搜索。三重 DES(3DES)曾通过多次执行 DES 延长安全寿命,但效率较低,块大小仍为 64 位,也已经不适合作为新系统的首选。

不要在新系统中使用 DES

DES 和 3DES 都不应作为新系统的加密算法。工程实践中应使用经过验证的现代认证加密方案,例如 AES-GCM 或 ChaCha20-Poly1305,并正确处理 nonce、密钥生命周期和完整性校验。

十、最后总结#

理解 DES,可以抓住下面这条主线:

  1. 64 位明文经过 IP 后分为 32 位的 L₀ 和 R₀;
  2. 每一轮把 R 送入轮函数 F,并与左半部异或;
  3. E 盒把 32 位扩展为 48 位,便于和 48 位子密钥异或;
  4. 8 个 S 盒把 48 位分成 8 组,每组 6 位查表得到 4 位,完成非线性压缩;
  5. P 盒重新排列 32 位结果,促进扩散;
  6. 16 轮使用不同子密钥反复处理,最后交换并执行 IP⁻¹;
  7. 解密使用同样的结构,只需逆序使用子密钥。

DES 今天已经不安全,但它仍然是理解“轮函数如何设计”“S 盒为什么重要”以及“不可逆的局部组件如何组成可逆的整体结构”的优秀教材。

DES 与 Feistel 网络:理解经典分组密码的轮函数设计
https://blog.xqcherry.top/posts/cryptography/des-feistel-network/
作者
xqcherry
发布于
2026-09-18
许可协议
CC BY-NC-SA 4.0