DES算法

DES（Data Encryption Standard，数据加密标准）是一种经典的对称分组密码算法

它的核心是Feistel 网络结构，加密过程包括初始置换、16 轮迭代、子密钥生成、逆初始置换等关键步骤。

DES 处理的明文和密文均为64 位分组，使用的密钥为64 位（但实际参与加密的有效密钥长度为 56 位，剩余 8 位为奇偶校验位）。加密流程可概括为 5 个核心步骤：

  1. 明文经过初始置换（IP）；
  2. 生成 16 个子密钥（K₁~K₁₆）；
  3. 对初始置换后的结果进行16 轮 Feistel 迭代；
  4. 迭代结束后交换左右两部分；
  5. 经过逆初始置换（IP⁻¹） 得到密文。

但是有个巨大的问题，56位的密钥对于现代计算机来说简直脆的像个巧克力蛋筒，早在1998年就被暴力破解。目前DES已经被AES(高级加密标准)取代。

（缅怀）

一、初始置换(IP,Initial Permutation)

IP置换的目的是将64位明文的位进行重排列

我们来看标准IP置换表：

输出位范围(n) 对应输入明文的位（IP [n]）
1~16 58, 50, 42, 34, 26, 18, 10, 2, 60, 52, 44, 36, 28, 20, 12, 4
17~32 62, 54, 46, 38, 30, 22, 14, 6, 64, 56, 48, 40, 32, 24, 16, 8
33~48 57, 49, 41, 33, 25, 17, 9, 1, 59, 51, 43, 35, 27, 19, 11, 3
49~64 61, 53, 45, 37, 29, 21, 13, 5, 63, 55, 47, 39, 31, 23, 15, 7

应当注意！！DES中我们认为索引n是从1开始的

也就是说我们输出的第1位其实是明文的第58位这样子

在重排列之后，我们会把64位的输出结果分割成左右两部分，左 32 位记为L0L_0，右 32 位记为R0R_0

二、生成 16 个子密钥(K₁~K₁₆)

DES 的原始密钥为 64 位，但其中8 位是奇偶校验位（用于验证密钥完整性，不参与加密运算），实际参与子密钥生成的是56 位有效密钥。64 位密钥中，校验位的位置是第 8、16、24、32、40、48、56、64 位（位索引从 1 开始）。

子密钥生成可分为 3 个阶段：

  1. 密钥预处理：通过 PC-1 置换从 64 位密钥中提取 56 位有效密钥，并分为左右两部分；
  2. 16 轮循环左移：对左右两部分分别进行循环左移（移位位数随轮次变化）；
  3. 置换选择（PC-2）：从左移后的 56 位中筛选 48 位，生成每轮子密钥。

1.密钥预处理(PC-1置换)

这一步的目的是剔除 8 位校验位，得到 56 位有效密钥，并将其分为左右两个 28 位部分（C₀和 D₀）。

这一步使用PC-1置换表：

左 28 位（C₀）对应原始密钥位 右 28 位（D₀）对应原始密钥位
57, 49, 41, 33, 25, 17, 9, 63, 55, 47, 39, 31, 23, 15,
1, 58, 50, 42, 34, 26, 18, 7, 62, 54, 46, 38, 30, 22,
10, 2, 59, 51, 43, 35, 27, 14, 6, 61, 53, 45, 37, 29,
19, 11, 3, 60, 52, 44, 36 21, 13, 5, 28, 20, 12, 4

和IP置换表比较像，应该不用赘述

2.16轮循环左移(LS)

对每轮 i（1≤i≤16），Cᵢ₋₁和 Dᵢ₋₁（上一轮的左右 28 位）分别进行循环左移

DES循环左移操作也很有意思，它的移动的位数是根据轮次决定的

  • 第 1、2、9、16 轮：左移 1 位；
  • 其余轮次（3~8、10~15）：左移 2 位。

3.置换选择（PC-2 置换）生成子密钥

这一步是要从第i轮左移后的56位（Cᵢ+Dᵢ）中筛选 48 位，生成第 i 轮子密钥 Kᵢ

这一步使用PC-2置换表：

第 1 列 第 2 列 第 3 列 第 4 列 第 5 列 第 6 列
14 17 11 24 1 5
3 28 15 6 21 10
23 19 12 4 26 8
16 7 27 20 13 2
41 52 31 37 47 55
30 40 51 45 33 48
44 49 39 56 34 53
46 42 50 36 29 32

总结

64位初始密钥生成16个48位轮密钥

三、16轮Feistel迭代

Feistel结构是DES的核心，记轮函数F(Ri−1,Ki)F(R_{i-1},K_i)

这一函数也比较复杂，我们放在后面讲解

16 轮迭代的输入是 L₀和 R₀，每轮的变换规则为：
Li=Ri−1L_i=R_{i−1}
Ri=Li−1⊕F(Ri−1,Ki)R_i=L_{i−1}⊕F(R_{i−1},K_i)

轮函数F

轮函数 F 的作用是将 32 位的Ri−1R_{i−1}和 48 位的子密钥KiK_i转换为 32 位输出，过程分为 4 步：

① E 扩展：32 位→48 位

将 32 位的Ri−1R_{i−1}通过E 扩展表扩展为 48 位。扩展规则是：将 32 位分为 8 组（每组 4 位），每组通过重复组内的首位和末位扩展为 6 位，例如第 1 组 4 位b1b2b3b4b_1b_2b_3b_4扩展为b4b1b2b3b4b1b_4b_1b_2b_3b_4b_1。扩展后总位数为8×6=48位。

② 与子密钥异或

扩展后的 48 位结果与 48 位子密钥KiK_i进行异或运算，得到 48 位中间结果。

③ S 盒置换：48 位→32 位

将 48 位异或结果分为 8 组（每组 6 位），分别输入 8 个S 盒（S₁~S₈）。每个 S 盒是一个非线性置换表，将 6 位输入转换为 4 位输出：

  • 6 位输入的第 1 位和第 6 位组成 “行号”（2 位，对应 0~3）；
  • 中间 4 位组成 “列号”（4 位，对应 0~15）；
  • 查 S 盒表中 “行号 × 列号” 对应的数值，转换为 4 位二进制，即为该 S 盒的输出。
    8 个 S 盒共输出8×4=32位。

④ P 盒置换：32 位重排

32 位 S 盒输出经过P 盒置换表进行位重排（例如第 16 位→第 1 位，第 7 位→第 2 位等），最终得到轮函数 F 的 32 位输出。

四、迭代后交换与逆初始置换

16 轮迭代结束后，得到L16L_{16}（32 位）和R16R_{16}（32 位）。此时需将两部分合并为∗R16L16*R_{16}L_{16}（即交换左右顺序），再经过逆初始置换（IP⁻¹）——IP⁻¹ 是 IP 的逆过程，将位恢复到原始顺序，最终输出 64 位密文。

五、解密

DES 解密与加密流程完全相同，唯一区别是子密钥使用顺序相反。这一特性源于 Feistel 结构的对称性：加密时Ri=Li−1⊕F(Ri−1,Ki)R_i=L_{i−1}⊕F(R_{i−1},K_i)，解密时通过逆序子密钥可反向推导出明文。