对称加密算法：Data Encryption Standard

所谓对称加密算法，指的是加密和解密使用相同密钥的加密算法，而 Data Encryption Standard （数据加密标准），简称 DES，就是一种经典的对称加密算法。

DES 设计遵循 “香农准则”：

• 充分混乱：密钥、明文以及密文之间的依赖关系相当复杂。
• 充分扩散：密钥的每一位数字影响密文的许多位数字，明文的每一位数字也应影响密文的许多位数字。

DES 具有以下属性：

• 明文：M = { m1, m2, …, m64}，64bits 信息。
• 密文：C = { c1, c2, …, c64}，64bits 信息。
• 密钥：K = { k1, k2, …, k64}，64bits，8为奇偶校验位，有效位 56 bits。

作为一个经典的加密算法，DES 在数十年经久不衰，本文则希望通过自顶向下的方法，探讨一下 DES 算法的具体原理。

另附：实现代码

一、DES 流程概览

在 DES 算法中，明文会被分组成 64 位一组。而每一组依次进入算法加密，因此在此我们只讨论 64位一组的加密。

1.1 总流程图

忽略一部分细节，DES 整个流程可用下图表示：

这个图只是 DES 算法的大体过程，忽略了很大一部分技术细节，那些省略的细节也会在第二、三部分进行详细讲解。现在看不懂这个图也没有关系，后文将逐渐展开。看完第一部分，请回到这里，看看能否对 DES 算法过程有一个宏观认识。

1.2 IP 置换 （初始置换）

s1. 明文为 64bits 的信息，按下表所示进行重新排列，即新的第 1 位为原来的第 58 位，新的第 2 位为原来的第 50 位……原有信息被打乱，这个过程称之为 IP 置换。

IP 置换表：

s2. 将经过 IP 置换重排后的信息分割成左右两部分 L[0] (32bits)，R[0] (32bits)。

1.3 Feistel 迭代

IP 置换后的 L[0], L[1] 以及 64bits 的密钥 k 作为 Feistel 函数的输入，经过 16 次相同迭代，输出 L[16] (32bits) 和 R[16] (32bits)。

注：这部分细节将会在后续进行讲解。

1.4 IP 逆置换

将经过 Feistel 迭代的左右子串 L16，R16 按照 先右后左的 { R[16], L[16] } 顺序排列，经过 IP 置换的逆关系 IP逆 进行置换混淆，产生最后输出的密文。

IP 逆置换：

上面这三步就是整个 DES 算法的大体步骤。不过也正如同前面所说，这里省略了大量步骤，其中一个关键的步骤就是被一笔带过的 Feistel 迭代，下面也将会从这里开始讲起。

二、Feistel 轮函数详解

2.1 初始置换后的 16 次迭代

在 IP 置换（初始置换）后，经过重新排列混淆的 64bits 信息被分为左右两部分： L0(32bits), R0(32bits)，这时候，它们要经过 16 次迭代，具体迭代过程如下图：

• L[i]： 直接为上一层的 R[i - 1]

• R[i]： 略微复杂一些，它是上一层的 L[i - 1] 与 Feistel 函数返回值的异或。

• Feistel 函数： 接受两个参数：R[i - 1] 和 k[i] （后面详解），返回一个 32bits 的值。

2.2 Feistel 函数

• 参数：R[i - 1]: 32bits, k[i]: 48bits

• 返回：32bits

2.2.1 Feistel: 总流程

s1. 32bits 的 R[i - 1] 通过 E 扩展，变为 48bits 的 E(R[i - 1])。

s2. E(R[i - 1]) xor k[i]，结果为 48bits。

s3. 将上述 xor 操作得到的结果分为 8 份，每份就是 6bits。

s4. 让第 i 份通过 S(i)Box，将会从 6bits -> 4bits。

s5. 将 8 份 4bits 数据组合成 32bits 的数据。

s6. 将上一步得到的 32bits 数据经过 P置换，然后输出 32bits 数据。

如下图：

2.2.2 Feistel: E 扩展

Feistel 函数的一个步骤是：将 32bits 的 R[i - 1] 扩展成 48bits 的 E(R[i - 1])，这个过程不难理解。

首先，将 32bits 的 R[i - 1] 转化为 8 * 4 的矩阵。

现在，我们要扩展这个矩阵，使其扩展成 8 * 6 的矩阵，在首尾各增加一列：

利用原矩阵数据，依次循环向后扩展。

2.2.3 Feistel: S-Box

DES的核心是 S-Box，除此之外的计算是线性的。S-Box 作为该密码体制的非线性组件对安全性至关重要，但 S-Box 的设计原理至今未公布，是否存在隐藏陷门 ( Hidden Trapdoors ) 不得而知。

S-Box 的设计准则：

• S-Box 中的每一行是整数 0-15 的一个置换
• S-Box 不是它输入变量的线性或仿射函数
• S-Box 的输入端每改变1位至少要引起输出端改变 2 位
• S(X) 和 S(X + 001100) 至少有 2 位不同
• 对 6 位二进制串 X = x1x2x3x4x5x6，S(X) != S(X + {11x5x600})
• S-Box 的输入端保持任 1 位不变，则其它输入位的变化输出数字中 0 和 1 的总数近于相等。

S-Box 计算：

设S[i] 的6位输入为 { b1 b2 b3 b4 b5 b6 }

• 行号：r = ( b1 b6 )10

• 列号：c = ( b2 b3 b4 b5 )10

• 输出：(S[i])[r, c] 元素的值的二进制形式即为所要的 S[i] 的输出。

以 S1-Box 为例：

• 输入：{ b1 b2 b3 b4 b5 b6 } = 101100

• 行号：( b1 b6 )10 = (10)10 = 2

• 列号：( b2 b3 b4 b5 )10 = (0110)10 = 6

• 输出： S1[2, 6] = 2 = 0010

2.2.3 Feistel: P 置换

8 个 S-Box 最终会输出 8 组 4bits 的数据，将其合并为 32 bits，然后进行 P 置换，最后输出并参与 16 轮迭代。

P 置换表：

三、子密钥 k[i] 生成

在上述 Feistle 函数中，另一个参数就是 48bits 的 k[i]，而 k[i] 便是通过密钥 k 生成的。这部分的生成只与密钥 k 相关，不依赖明文密文，所以这一步完全可以在整个算法第一步完成。

用下图表示子密钥 k[i] 生成过程：

3.1 PC-1 置换

对 k 56bits 的非校验位进行 PC-1 置换混淆，得到左右各 28bits 两部分，记为 C[0], D[0]。

PC-1 置换表：

3.2 循环左移

从 i 开始，利用 C[i - 1], D[i - 1]，计算 C[i], D[i]。

• C[i] = LS[i] (C[i - 1]) 和D[i] = LS[i] (D[i - 1])
• i = 1, 2, 9, 16 时：LS[i] (A) 表示 A 循环左移 1bit。
• i = others 时：LS[i] (A) 表示 A 循环左移 2bits。

可以用下表表示：

3.3 PC-2 压缩置换

每一次循环，都拼接 C[i]D[i] 为 56bits 信息，进行 PC-2 压缩置换，压缩为 48bits，生成 k[i] 并输出。

PC-2 压缩置换表：

附：全部 S-Box

S1:

S2:

S3:

S4:

S5:

S6:

S7:

S8: