3. 对称加密算法（一）：DES算法原理、Feistel网络结构、子密钥生成
数据加密标准（Data Encryption Standard, DES）是密码学历史上最具影响力的对称分组密码算法之一。DES 由 IBM 在 1970 年代设计，1977 年被美国国家标准局（NIST）采纳为联邦信息处理标准。尽管如今 DES 因 56 位密钥过短而不再安全，但其核心设计——Feistel 网络结构——至今仍是许多现代密码算法（如 AES 候选算法、Blowfish、Twofish）的基石。理解 DES 是掌握对称密码学的必修课。
3.1 DES 算法概述
DES 是一种分组密码，其基本参数如下：
| 参数 | 值 | 说明 |
|---|---|---|
| 分组大小 | 64 位 | 每次加密/解密处理 8 字节数据 |
| 密钥长度 | 64 位（有效 56 位） | 每 8 位中最后一位为奇偶校验位，不参与加密运算 |
| 轮数 | 16 轮 | 每轮使用不同的 48 位子密钥 |
| 结构 | Feistel 网络 | 对称结构，加密和解密过程几乎相同 |
| 算法类型 | 对称分组密码 | 加密和解密使用相同密钥 |
3.2 Feistel 网络结构
Feistel 网络是 DES 的核心架构，由 Horst Feistel 在 IBM 的 Lucifer 密码中提出。其基本思想是将数据块分成左右两半，在每一轮中，右半部分通过轮函数处理后与左半部分异或，然后交换左右两半。这种结构的最大优点是加密和解密可以使用完全相同的算法结构，只需颠倒子密钥的使用顺序。
3.2.1 Feistel 网络单轮结构
单轮 Feistel 网络的操作步骤如下：
- 分割： 将 64 位输入数据块分为左半部分 Li-1（32 位）和右半部分 Ri-1（32 位）。
- 轮函数： 右半部分 Ri-1 与子密钥 Ki 一起输入轮函数 F。
- 异或： 轮函数输出 F(Ri-1, Ki) 与左半部分 Li-1 进行异或运算。
- 交换： 新的左半部分 Li = Ri-1，新的右半部分 Ri = Li-1 ⊕ F(Ri-1, Ki)。
数学表达式为：
Li = Ri-1
Ri = Li-1 ⊕ F(Ri-1, Ki)3.2.2 DES 的 Feistel 网络整体流程
下图展示了 DES 算法的整体 Feistel 网络结构，包括初始置换（IP）、16 轮迭代和逆初始置换（IP-1）。
3.3 DES 轮函数 F 详解
DES 的轮函数 F 是整个算法中唯一提供混淆和扩散的组件。它接收 32 位的右半部分数据和 48 位的子密钥，输出 32 位的结果。F 函数由四个步骤组成：扩展置换、与子密钥异或、S 盒替换、P 盒置换。
3.3.1 轮函数 F 的四个步骤
| 步骤 | 输入 | 输出 | 操作描述 |
|---|---|---|---|
| 1. 扩展置换 (E) | 32 位 Ri-1 | 48 位 | 将 32 位扩展为 48 位，某些位被重复使用，增加扩散性 |
| 2. 与子密钥异或 | 48 位扩展结果 + 48 位 Ki | 48 位 | 将扩展后的数据与子密钥进行异或运算，引入密钥依赖性 |
| 3. S 盒替换 | 48 位 | 32 位 | 8 个 S 盒（S1~S8），每个输入 6 位，输出 4 位，提供非线性 |
| 4. P 盒置换 | 32 位 | 32 位 | 对 S 盒输出进行位重排，增加位之间的扩散 |
3.3.2 S 盒：DES 的非线性核心
S 盒（Substitution Box）是 DES 中唯一提供非线性的组件，也是 DES 安全性的根本保障。如果没有 S 盒，整个 DES 将退化为一个线性变换，极易被破解。DES 使用 8 个不同的 S 盒，每个 S 盒是一个 4 行 × 16 列的查找表。
S 盒的输入是 6 位（b1b2b3b4b5b6），输出是 4 位：
- 行号： 由 b1b6 决定（0~3）
- 列号： 由 b2b3b4b5 决定（0~15）
- 输出： 查找表中对应行列的数值（0~15），转换为 4 位二进制
3.4 子密钥生成
DES 的 16 轮迭代需要 16 个 48 位的子密钥（K1 到 K16），这些子密钥从 56 位有效密钥中通过置换和循环移位生成。子密钥生成过程完全独立于数据，可以预先计算。
3.4.1 子密钥生成步骤
- 密钥初始置换 (PC-1)： 将 64 位密钥（含 8 位奇偶校验位）通过 PC-1 置换表，去除校验位并重排，得到 56 位密钥。
- 分割： 将 56 位密钥分为左半部分 C0（28 位）和右半部分 D0（28 位）。
- 循环左移： 对于第 i 轮（i=1~16），对 Ci-1 和 Di-1 分别进行循环左移。移位数由轮数决定：第 1、2、9、16 轮左移 1 位，其余轮左移 2 位。
- 压缩置换 (PC-2)： 将 56 位的 CiDi 通过 PC-2 置换表，压缩为 48 位的子密钥 Ki。
3.4.2 子密钥生成流程图
3.4.3 循环左移位数表
| 轮数 i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 左移位数 | 1 | 1 | 2 | 2 | 2 | 2 | 2 | 2 | 1 | 2 | 2 | 2 | 2 | 2 | 2 | 1 |
3.5 DES 加解密一致性
Feistel 网络最优雅的特性是加解密结构完全相同。解密时，只需将子密钥的使用顺序颠倒（即使用 K16, K15, ..., K1），并将密文输入到加密算法中，即可恢复明文。这一特性极大地降低了硬件实现的复杂度。
解密过程的数学推导：
加密：Li = Ri-1, Ri = Li-1 ⊕ F(Ri-1, Ki)
解密：Ri-1 = Li, Li-1 = Ri ⊕ F(Li, Ki)由于解密时子密钥逆序使用，且异或运算的自反性（A ⊕ B ⊕ B = A），解密过程能够完美还原原始明文。
3.6 DES 的安全性讨论
DES 的主要安全弱点包括：
- 密钥长度过短： 56 位密钥空间约为 7.2×1016，现代专用硬件（如 FPGA 集群或 ASIC）可以在数小时内完成穷举搜索。1998 年，电子前沿基金会（EFF）用 25 万美元的专用机器在 56 小时内破解了 DES。
- 互补性： DES 具有互补性质，即 E(K, P) 的补码等于 E(K 的补码, P 的补码)。这可以将穷举搜索的工作量减半。
- S 盒设计未公开： S 盒的设计标准至今未完全公开，虽然已知其能抵抗差分密码分析，但设计动机仍存在争议。
尽管如此，DES 在密码学发展史上具有里程碑意义。其 Feistel 网络结构、S 盒设计理念、以及子密钥生成机制，为后续密码算法的设计提供了宝贵的经验和理论基础。