d 加密解密介绍 – wiki基地

数字安全的基石：深入理解数据加密标准 (DES) 加密与解密

在数字信息的洪流中，安全与隐私是永恒的命题。为了保护敏感数据不被窃取或篡改，密码学应运而生，并不断发展。在现代密码学的历史长河中，数据加密标准（Data Encryption Standard，简称 DES）无疑是一个里程碑式的存在。它曾在数十年间被广泛应用于金融、政府和商业领域，构成了数字安全的重要基石。尽管由于计算能力的飞速发展，DES 本身已不再被视为安全的选择，但对其原理的深入理解，对于学习对称加密、块密码以及现代密码学的发展具有不可估量的价值。

本文将带您深入探讨 DES 算法的每一个细节，从其历史背景、基本概念，到其精妙的加密和解密过程，再到其优点、缺点以及最终的命运。

第一部分：历史背景与基本概念

1.1 DES 的诞生：时代的呼唤

在 20 世纪 70 年代初期，随着计算机技术的普及和数据交换需求的增加，美国急需一个标准化的、可靠的数据加密算法，以保护政府部门和商业机构的非机密敏感信息。在此背景下，美国国家标准局（National Bureau of Standards，NBS，现更名为 NIST）于 1973 年发起了公开招标，寻求一种强有力的加密算法。

IBM 公司提交的基于 Lucifer 算法的方案最终脱颖而出。在与美国国家安全局（NSA）合作进行了一系列的修改和评估后（这些修改曾引发一些争议，主要是关于密钥长度和 S 盒的设计，但最终研究表明这些修改可能增强了算法的抗攻击能力），该算法于 1977 年被正式采纳为联邦信息处理标准（FIPS PUB 46），命名为数据加密标准（Data Encryption Standard, DES）。

DES 的出现，结束了之前加密方法分散、私有且缺乏统一标准的局面，极大地推动了对称加密算法的研究和应用。它成为了后续许多加密算法设计的参照和基石。

1.2 DES 的基本属性：对称、块密码、Feistel 结构

要理解 DES 如何工作，首先需要掌握几个核心概念：

对称密钥算法 (Symmetric-key Algorithm): DES 是一种对称密钥算法。这意味着加密和解密使用相同的密钥。这与非对称密钥算法（如 RSA）不同，后者使用一对公钥和私钥。对称加密的优点是速度快，适合处理大量数据；缺点是通信双方必须通过安全渠道预先共享密钥。
块密码 (Block Cipher): DES 是一种块密码。它不像流密码那样逐位或逐字节处理数据，而是将明文分成固定大小的数据块，然后对每个数据块进行独立的加密。DES 的块大小为 64 位（8 字节）。这意味着无论输入多长的明文，都会被切分成 64 位的块进行处理，如果最后一个块不足 64 位，通常需要进行填充（Padding）。
密钥长度 (Key Length): DES 的密钥长度是 64 位。然而，其中每第 8 位用于奇偶校验（Parity Check），并不用于加密运算。因此，DES 的实际有效密钥长度是 56 位。这个长度在当时被认为是足够的，但后来成为了 DES 被破解的主要原因。
Feistel 结构 (Feistel Structure): DES 的核心是一个迭代的 Feistel 结构。这种结构由 Horst Feistel 在 IBM 的 Lucifer 项目中提出。Feistel 结构的一个显著优点是，无论轮函数（Round Function）f 是如何设计的，解密过程与加密过程几乎完全相同，只需将轮密钥的顺序颠倒。这大大简化了硬件和软件的实现。Feistel 结构将输入的数据块分成左右两个部分，在每一轮中，使用轮密钥对其中一部分进行处理，然后将结果与另一部分进行异或，最后交换左右两部分（除了最后一轮）。DES 采用的是 16 轮 Feistel 结构。

第二部分：DES 加密过程详解

DES 加密过程是一个复杂的多步骤流程，对一个 64 位的明文块执行一系列置换（Permutation）和代换（Substitution）操作。这个过程重复 16 次（16 轮）。下面我们一步步剖析 DES 的加密流程：

输入：一个 64 位的明文块 M，一个 64 位的密钥 K (其中 56 位有效)。
输出：一个 64 位的密文块 C。

2.1 初始置换 (Initial Permutation, IP)

加密过程的第一步是对 64 位的明文块进行一个固定的初始置换 IP。这个置换是根据一个预定义的置换表进行的，它改变了明文位的原始位置。例如，明文的第 58 位会被移动到第 1 位，第 50 位移动到第 2 位，依此类推。

IP 置换表 (部分示例，实际是完整的64位映射)： 58 50 42 34 26 18 10 02 60 52 44 36 28 20 12 04 ... 01 09 17 25 33 41 49 57 03 11 19 27 35 43 51 59
(表中数字表示明文的原始位索引，其位置表示置换后的位索引。例如，明文第58位移到输出的第1位，明文第50位移到输出的第2位)

初始置换 IP 本身对算法的加密强度没有贡献，其主要目的是为了方便硬件实现，可能也为了打乱明文的模式，使其在后续的轮处理中更快地扩散开。

经过 IP 置换后，得到一个 64 位的中间结果 IP(M)。这个 64 位结果被分成左右两个 32 位的半块：左半部分 L0 和右半部分 R0。

IP(M) = (L0, R0)

2.2 16 轮 Feistel 迭代

DES 的核心是这 16 轮相同的处理过程。每一轮的输入是前一轮输出的左半部分 L_{i-1} 和右半部分 R_{i-1}，以及本轮使用的轮密钥 K_i。每一轮的计算如下：

L_i = R_{i-1}
R_i = L_{i-1} XOR f(R_{i-1}, K_i)

其中，i 表示轮数，从 1 到 16。f 是 DES 的轮函数（Round Function），它接受 32 位的输入（前一轮的右半部分 R_{i-1}）和 48 位的轮密钥 K_i，输出一个 32 位的结果。

下面详细分解轮函数 f(R_{i-1}, K_i) 的步骤：

2.2.1 扩展置换 (Expansion Permutation, E-box)

轮函数的第一个步骤是对 32 位的输入 R_{i-1} 进行扩展置换 E，将其扩展到 48 位。这个置换的规则是固定的：它将 32 位输入中的某些位重复，以产生 48 位输出。

例如，32 位输入被分成 8 个 4 位的小组。扩展置换会将每个小组的两侧位与相邻小组的位重复。具体来说，每个 4 位小组的第一个位是前一个小组的最后一个位，最后一个位是下一个小组的第一个位。这样，每个 4 位小组就变成了 6 位，总共 8 * 6 = 48 位。

E-box 扩展表 (部分示例，实际是完整的32位->48位映射): 32 01 02 03 04 05 04 05 06 07 08 09 ... 28 29 30 31 32 01
(表中数字表示32位输入的原始位索引。例如，输出的第1位是输入的第32位，输出的第2位是输入的第1位，依此类推)

这个扩展操作的目的是为了使 32 位的 R_{i-1} 能够与 48 位的轮密钥进行异或运算，同时也增加了后续 S 盒输入的位数，有助于提高扩散性。

经过扩展置换后，得到一个 48 位的结果 E(R_{i-1})。

2.2.2 与轮密钥异或 (XOR with Round Key)

接下来，将 48 位的 E(R_{i-1}) 与本轮使用的 48 位轮密钥 K_i 进行逐位异或（XOR）运算。

Temp = E(R_{i-1}) XOR K_i

这是一个简单的线性运算，但它是引入密钥的地方，使得加密依赖于密钥。

2.2.3 S 盒代换 (Substitution Boxes, S-boxes)

这是 DES 轮函数中最核心、最重要的非线性部分，也是 DES 加密强度所在。DES 共有 8 个 S 盒（记作 S1, S2, …, S8）。

将 48 位的结果 Temp 分成 8 个 6 位的块。每个 6 位的块输入到一个对应的 S 盒中。例如，第一个 6 位块输入到 S1 盒，第二个输入到 S2 盒，以此类推，第八个输入到 S8 盒。

每个 S 盒都执行一个 6 位输入到 4 位输出的代换操作。这个代换不是线性的，而是通过一个预定义的查找表完成的。

对于每一个 6 位输入到 S 盒的块，其代换规则如下：
* 这 6 位的第一位和第六位组成一个 2 位的二进制数，用来确定 S 盒查找表的行索引（0到3）。
* 这 6 位的中间四位组成一个 4 位的二进制数，用来确定 S 盒查找表的列索引（0到15）。
* 根据行索引和列索引，在对应的 S 盒表中查找得到一个 4 位的输出值。

例如，如果一个 6 位输入是 101101，第一位和第六位是 11 (二进制)，即 3 (十进制)，表示查找表的第 3 行。中间四位是 0110 (二进制)，即 6 (十进制)，表示查找表的第 6 列。然后查找对应的 S 盒表中第 3 行第 6 列的值，将这个值转换为 4 位二进制数作为输出。

DES 的 8 个 S 盒的查找表是经过精心设计的（据称是 NSA 和 IBM 共同努力的结果），它们具有特定的密码学属性，例如抗差分密码分析和线性密码分析（尽管这些攻击方法是在 DES 发布后才被公开发现和完善的），它们是 DES 能够抵抗这些攻击的关键。S 盒的非线性特性是 DES 提供混淆（Confusion）能力的主要来源。

经过 8 个 S 盒的并行处理后，我们得到 8 个 4 位的输出块。将这 8 个 4 位块按顺序拼接起来，形成一个 32 位的结果。

2.2.4 置换 P (Permutation P)

轮函数的最后一个步骤是对 S 盒输出的 32 位结果进行一个固定的置换 P。这个置换是根据一个预定义的置换表进行的，它只是重新排列了 32 位的位置。

P 置换表 (部分示例，实际是完整的32位映射): 16 07 20 21 ... 25 03 28 15
(表中数字表示S盒输出的原始位索引，其位置表示置换后的位索引)

置换 P 的作用是提高扩散性（Diffusion），将 S 盒的输出混杂到下一轮的输入中，使得明文的每一位和密钥的每一位都尽可能快地影响到密文的每一位。

置换 P 的 32 位输出就是轮函数 f(R_{i-1}, K_i) 的最终结果。

2.3 轮计算的迭代完成

将轮函数 f 的 32 位输出与本轮的左半部分 L_{i-1} 进行异或运算：

R_i = L_{i-1} XOR f(R_{i-1}, K_i)

本轮的左半部分直接成为下一轮的右半部分：

L_i = R_{i-1}

这样就完成了一轮的计算，得到了 L_i 和 R_i。这个过程重复 16 次，从 (L0, R0) 迭代到 (L1, R1)，再到 (L2, R2)，…，直到 (L16, R16)。

2.4 最后一轮的特殊处理（无交换）

在完成第 16 轮计算后，通常 Feistel 结构的最后一轮会将左右部分交换，即 (R16, L16)。然而，DES 标准规定，在第 16 轮计算完成后，不进行左右部分的交换。所以，第 16 轮的输出就是 (L16, R16)。

2.5 最终置换 (Final Permutation, FP)

加密过程的最后一步是对第 16 轮的输出 (L16, R16) 拼接成的 64 位块进行一个固定的最终置换 FP。这个置换是初始置换 IP 的逆置换（Inverse Permutation）。这意味着 FP(IP(M)) = M 对于任意 64 位块 M 成立。

FP 置换表 (部分示例，实际是完整的64位映射): 40 08 48 16 56 24 64 32 39 07 47 15 55 23 63 31 ... 01 09 17 25 33 41 49 57 02 10 18 26 34 42 50 58
(表中数字表示第16轮输出的原始位索引，其位置表示置换后的位索引。例如，第16轮输出的第40位移到最终输出的第1位，第8位移到最终输出的第2位，依此类推)

最终置换 FP 的输出就是 64 位的密文块 C。

C = FP((L16, R16))

至此，一个 64 位明文块的 DES 加密过程就完成了。

第三部分：DES 密钥生成过程详解

DES 加密算法的安全性高度依赖于密钥。DES 使用一个 64 位的输入密钥，但如前所述，其中只有 56 位用于生成轮密钥。从这 56 位主密钥中，通过一系列置换和循环移位操作，生成 16 个 48 位的轮密钥（K1, K2, …, K16），每一轮 Feistel 迭代使用一个不同的轮密钥。

DES 密钥生成过程如下：

输入：一个 64 位的输入密钥 K。
输出：16 个 48 位的轮密钥 K1, K2, ..., K16。

3.1 去除奇偶校验位和初始置换 (Permuted Choice 1, PC-1)

首先，输入 64 位密钥 K。DES 的密钥生成过程会忽略每字节的最后一位（即第 8, 16, …, 64 位），这些位通常用于奇偶校验。然后对剩余的 56 位进行一个固定的置换 PC-1。这个置换将 56 位重新排列，并将其分成两个独立的 28 位半块：C0 和 D0。

PC-1 置换表 (部分示例，实际是完整的56位映射): 57 49 41 33 25 17 09 ... 08 16 24 32 40 48 56
(表中数字表示64位输入密钥的原始位索引，奇偶校验位(8, 16, …, 64)被跳过。前28位构成了C0，后28位构成了D0)

3.2 循环左移 (Left Shift)

为了生成后续的轮密钥，在每一轮（从 i=1 到 16），对前一轮得到的 C_{i-1} 和 D_{i-1} 分别进行循环左移操作，得到 C_i 和 D_i。左移的位数不是固定的，而是根据轮数 i 来确定的。

轮数 (i)	左移位数
1	1
2	1
3	2
4	2
5	2
6	2
7	2
8	2
9	1
10	2
11	2
12	2
13	2
14	2
15	2
16	1

注意，在第 1, 2, 9, 16 轮，左移 1 位；在其他轮（3-8, 10-15），左移 2 位。移位操作是循环的，即被移出左端的位会从右端重新进入。

3.3 置换选择 2 (Permuted Choice 2, PC-2)

在每一轮计算出 C_i 和 D_i 后（它们都是 28 位），将它们拼接成一个 56 位的块 (C_i, D_i)。然后对这个 56 位块进行置换 PC-2，从其中选择并排列 48 位，形成本轮使用的轮密钥 K_i。

PC-2 置换表 (部分示例，实际是完整的56位->48位映射): 14 17 11 24 01 05 ... 39 47 55 38 46 63
(表中数字表示56位输入(C_i, D_i)的原始位索引。PC-2从56位中选择了48位并重新排列)

这个过程重复 16 次，每一轮都使用前一轮的 C 和 D 进行左移，然后通过 PC-2 生成本轮的轮密钥 K_i。这样就生成了从 K1 到 K16 的 16 个不同的轮密钥。

第四部分：DES 解密过程详解

DES 采用 Feistel 结构的一个主要优势在于其解密过程与加密过程几乎相同。这是因为 Feistel 结构的每一轮都是可逆的。

如果我们有加密过程的输出 (L_i, R_i)，我们可以通过以下计算回到前一轮的输入 (L_{i-1}, R_{i-1})：

已知 L_i = R_{i-1} 和 R_i = L_{i-1} XOR f(R_{i-1}, K_i)

将第一个等式代入第二个等式中的 R_{i-1}：
R_i = L_{i-1} XOR f(L_i, K_i)

为了得到 L_{i-1}，我们将等式两边与 f(L_i, K_i) 进行异或：
R_i XOR f(L_i, K_i) = L_{i-1} XOR f(L_i, K_i) XOR f(L_i, K_i)
R_i XOR f(L_i, K_i) = L_{i-1}

所以，我们可以通过 L_{i-1} = R_i XOR f(L_i, K_i) 恢复左半部分，并通过 R_{i-1} = L_i 恢复右半部分。

观察这个逆过程的计算：
左半部分变成前一轮的右半部分：R_{i-1} = L_i
右半部分变成前一轮的左半部分：L_{i-1} = R_i XOR f(L_i, K_i)

对比加密过程第 i 轮的计算：
L_i = R_{i-1}
R_i = L_{i-1} XOR f(R_{i-1}, K_i)

如果我们从密文 (L16, R16) 开始解密（记住，加密最后一轮没有交换），将其看作是解密过程的第一轮输入。将加密过程的 (L_i, R_i) 对应解密过程的 (R'_i, L'_i)，并使用密钥 K_{17-i}。

密文是 (L16, R16)。
解密第一轮 (i=16) 输入是 (L'_0, R'_0) = (L16, R16)。
解密第一轮计算：
L'_1 = R'_0 = R16
R'_1 = L'_0 XOR f(R'_0, K_{16}) = L16 XOR f(R16, K16)

回看加密过程第 16 轮的计算：
L16 = R15
R16 = L15 XOR f(R15, K16)

所以，解密第一轮的输出是 (R16, L16 XOR f(R16, K16))。
根据加密过程，R16 = L15 XOR f(R15, K16)，所以 L15 = R16 XOR f(R15, K16)。同时 R15 = L16。
解密第一轮的输出 (R16, L16 XOR f(R16, K16)) 实际上就是 (L15, R15)！

这证明了，如果我们将加密生成的 16 个轮密钥 K1, K2, ..., K16 以逆序 K16, K15, ..., K1 应用于加密的 16 轮 Feistel 结构的输出，就可以恢复原始的输入。

因此，DES 解密过程与加密过程完全相同，只是：

对密文块首先应用初始置换 IP (这实际上是加密过程最终置换 FP 的逆置换)。注意，FP 是 IP 的逆置换，所以应用 FP 的逆就是 IP。
然后进行 16 轮 Feistel 迭代，但使用轮密钥的顺序是 K16, K15, …, K1。
在完成 16 轮迭代后（同样，最后一轮不交换左右半部分），得到 (L0', R0') (理论上应该是 (L0, R0) 的逆置换，但因为 Feistel 结构的性质，最终会恢复到 (L0, R0))。
最后，对 16 轮迭代的输出应用最终置换 FP (这实际上是加密过程初始置换 IP 的逆置换)。

总结来说，DES 解密过程是：

密文 C -> 初始置换 IP -> 16 轮 Feistel (使用轮密钥 K16 到 K1) -> 最终置换 FP -> 明文 M。

由于 FP 是 IP 的逆置换，而 Feistel 结构在逆序使用密钥时是自逆的（加密 16轮 + 解密 16轮 = 原始输入），所以整个流程是正确的。

第五部分：DES 的优点与缺点

5.1 DES 的优点

标准化： 作为第一个广泛采用的加密标准，它为对称加密算法的设计和实现提供了统一的范本。
强大的 Feistel 结构： Feistel 结构使得加密和解密过程高度相似，简化了实现，特别是硬件实现。
精妙的 S 盒设计： S 盒是 DES 非线性的来源，精心设计的 S 盒在当时有效地抵抗了已知的密码分析方法（尽管更强大的攻击方法后来被发现）。
广泛的应用基础： 在其全盛时期，DES 在金融（尤其是在 ATM 系统中）、政府和商业通信中得到了广泛应用，推动了加密技术的发展和普及。

5.2 DES 的缺点与为何被淘汰

尽管 DES 在其时代是先进的，但随着技术的发展，其缺点逐渐暴露，并最终导致其被淘汰：

密钥长度太短： 56 位的有效密钥长度是 DES 最致命的弱点。随着计算能力的飞速提升，特别是专用硬件（如 DES Cracker）的出现，通过穷举搜索（Brute Force Attack）所有可能的 2^56 个密钥变得可行。1999 年，EFF 的 DES Cracker 仅用不到 24 小时就破解了一个 DES 密文。
差分密码分析 (Differential Cryptanalysis): 这是由 Eli Biham 和 Adi Shamir 在 20 世纪 80 年代末公开发表的一种强大的攻击方法。它分析明文对密文差异的影响。尽管 DES 的 S 盒被设计成对这种攻击具有一定的抵抗力，但如果 S 盒设计不当，差分密码分析会非常有效。据称 NSA 在 DES 设计时已经了解这种攻击方法。
线性密码分析 (Linear Cryptanalysis): 这是由 Mitsuru Matsui 在 20 世纪 90 年代初提出的一种攻击方法。它利用明文、密文和密钥之间的线性近似关系来恢复密钥位。同样，DES 的 S 盒设计对这种攻击也有一定的抵抗力，但仍需大量明密文对。
弱密钥和半弱密钥： 存在一些特殊的 DES 密钥（弱密钥有 4 个，半弱密钥有 6 对共 12 个），它们在密钥生成过程中会产生相同或重复的轮密钥，从而导致加密和解密过程具有特殊的不安全性（例如，使用弱密钥加密两次会恢复原始明文）。尽管这些密钥数量很少，很容易避免，但它们揭示了密钥调度算法的一些理论弱点。

第六部分：DES 的进化与终结

认识到 DES 56 位密钥长度的不足，密码学家们开始寻找增强 DES 或设计新的算法。

三重 DES (Triple DES, 3DES 或 TDES): 为了延长 DES 的生命周期，人们提出了使用多个 DES 密钥对数据进行三次 DES 操作的方法。最常见的是 EDE (Encrypt-Decrypt-Encrypt) 模式：C = E_K3(D_K2(E_K1(M)))，其中 K1, K2, K3 是三个独立的 DES 密钥（总密钥长度 168 位，实际有效 112 位），或者使用两个密钥 (K1=K3) 使得有效密钥长度为 112 位。3DES 显著提高了密钥长度，使其能够抵抗暴力破解，在 DES 被认为不安全后，3DES 成为了许多应用（如支付系统）的首选，并沿用了很长时间。然而，3DES 的处理速度比 DES 慢三倍，而且其块大小仍然是 64 位，在某些模式下（如 CBC）处理大量数据时效率不高，并且仍然存在一些理论上的攻击方法（如中间相遇攻击，但需要大量的计算资源和数据）。
高级加密标准 (Advanced Encryption Standard, AES): 随着计算能力的进一步提高和对更高效、更安全算法的需求，NIST 再次公开招标，最终于 2001 年选择了 Rijndael 算法作为新的高级加密标准（AES，FIPS PUB 197）。AES 是一个全新的块密码算法，其块大小为 128 位，支持 128、192 或 256 位的密钥长度，并且其设计基于一个完全不同的结构（替换-置换网络，SPN），比 DES 更快、更安全。AES 的出现标志着 DES 及其变种 3DES 正式退出了主流加密应用的舞台。

第七部分：总结与历史意义

数据加密标准 (DES) 作为历史上第一个被广泛采用的对称块密码标准，在密码学发展史上留下了浓墨重彩的一笔。它引入并验证了 Feistel 结构和精心设计的 S 盒等关键概念，促进了对称加密算法的研究和标准化进程。

虽然 DES 本身因为密钥长度的限制而不再安全，不应再用于保护敏感数据，但对其工作原理、设计思想及其被破解过程的研究，仍然是学习现代密码学不可或缺的一部分。DES 的兴衰历程，生动地展示了计算能力、密码分析技术与加密算法之间的动态对抗关系，强调了密钥长度和算法设计在保障数据安全中的重要性。它为 3DES 的过渡性应用铺平了道路，并最终被更强大、更灵活的 AES 所取代，完成了其历史使命。

理解 DES 的内部机制，就像是窥探了数字安全历史的一扇重要窗户，它不仅让我们了解过去如何保护信息，更启发我们思考未来如何构建更坚固的加密防线。尽管 DES 已远去，但它作为数字安全基石的贡献，将永远铭刻在密码学的史册上。