密码学专题 - 对称加密算法 - DES 算法

5.1 DES 算法

数据加密标准 (DES) 是应用最广泛的一种分组密码算法，但由于它仅仅 56 位的密钥长度和 64 位的分组长度严重地限制了算法的安全性，已经不适合今天的快速计算机和大量数据运算的情况了。随之取代它的是一种称为 3DES 的分组密码算法，它以某种特殊的顺序使用两个密钥执行三次 DES 加密，用第一个 56 位密钥执行 DES，然后用第二个 56 位密钥执行 DES 逆运算即解密函数，最后用第一个 56 位密钥进行加密。这种算法解决了位数过少的密钥带来的安全问题，但是并没有解决数据分组长度过短的问题。DES 已经不是现行标准下的快速加密方法。3DES 也只有 DES 执行速度的三分之一。可能在很多系统中会遇到 DES 算法，但是在新的设计中并不推荐使用 DES 或者 3DES。但是，DES 作为一个经典的设计本身就很值得研究。

图 3-1 给出了一个单轮的 DES。这是一个 DES 算法的具体流程图，在有关密码学文献中经常看到类似的图。每个盒执行一个特定的功能，线段表示所使用的值。有一些符号规定：异或运算有时也称为按位加法或者无进位加法，在图中显示为 $\bigoplus$ 运算符。有些图中还包含整数加法，用运算符 $田$ 表示。

一轮 DES 的结构.jpg

DES 算法有 64 位明文，首先将明文进行 IP 置换。然后将明文从中间分成左右两部分，分别是 32 位的 L 和 R。似乎很难理解为什么要将明文进行 IP 置换，从密码设计的角度来讲并没有增强算法的安全性，但是 DES 算法的确是这样定义的。在一轮加密结束后同样交换 L 和 R 的序列以得到 64 位的密文。

DES 算法有 16 轮加密，分别被编号为 1 至 16.每一轮使用一个 48 位的轮密钥 $K_i$ 。这 16 个轮密钥是从分组密码的 56 位密钥 K 中选择 48 位生成的，对于每一轮密钥，选择方式都是不同的。这个由主分组密码密钥生成轮密钥的算法称为子密钥生成器 (key schedule)。

如图 3-1 所示，虚线框之内的表示轮函数 F。轮函数通过一系列的运算改变 $(L, R)$ 的值。32 位的 R 值首先要经过扩展函数得到 48 位的输出。然后和轮密钥 $K_i$ 进行异或并将结果输入 S 盒。 S 盒 (S 表示替代，是 substituion 首字母) 是一个公开的查找表。48 位的输入被分成一些组，每组大小约为 4 ~ 6 位。S 盒将 48 位的向量通过非线性映射成为 32 位的向量。这 32 位经过位变换函数后与 L 异或得到新的 L，将此 L 和 R 的值互换，进入新一轮的加密。如此重复 16 轮就是一个完整的 DES 加密。

DES 算法的基本结构称为 Feistel 结构。这是一个巧妙的设计。每一轮通过 L 和 $F(K_i,R)$ 的异或生成新的 L，然后将 L 与 R 交换，该设计的巧妙之处在于解密函数可以使用相同的运算，只需要将 L 和 R 的值交换。所以在分析时，只需要分析加密函数或者解密函数中的一个。还有一点需要注意的是最后一轮计算后的输出结果不需要交换 L 和 R，因此除了轮密钥的顺序之外，加密和解密函数几乎相同。这种设计对于硬件实现是非常有好处的，因为可以使用相同的电路进行加密和解密的计算。

DES 加密算法的不同部分有不同的功能，这种设计简单的 Feistel 结构使得 L 和 R 两部分混合在一起。用密钥来进行异或主要是通过密钥和数据进行混合运算来打乱消息。S 盒提供非线性变换。如果没有以上这些部分，密码就可以表示成二进制加法，从而很容易遭受到基于线性代数的数学攻击。最后，S 盒、扩展函数、位变换函数的结合起到了扩散的作用。扩散是指输入 F 的任何一位发生变化都影响到输出密文的许多位。在接下来一轮的计算中就会影响到更多位。如果没有良好的扩散性能，明文微小的变化也只能导致密文的某些位发生变化，攻击者很容易检测出这些变化。

根据安全定义，DES 算法有很多特有的性质。比如，每一轮的轮密钥都是由分组密码的主密钥的某些位生成的。如果主密钥为 0，那么所有的轮密钥都是相同的，也都为 0。上面提到加密和解密的唯一区别就是轮密钥的顺序，因为所有轮密钥都是 0，所以所有的加密密钥和密钥密钥也都相同了。

DES 算法也有互补的性质：
$\overline{E} (\overline{K},\overline{P}) = \overline{E(K,P)}$

$K$ 为密钥， $P$ 为明文， $\overline{X}$ 是指 $X$ 的所有位取反后的值。如果使用取反的密钥加密取反后的明文值，那么所得到的密文是原密文的取反。

这是很容易理解的。试想在图 3-1 中如果将 $L$ 、 $R$ 和 $K_i$ 的所有位均取反会出现何种情况。取反输入经过扩展与取反的 $K_i$ 的进行异或，会得到和之前相同的输入，经过 $S$ 盒和位变换后输出还是与未取反时的输出相同。但是 $L$ 的值取反，所以异或后得到的取反结果作为新的 $R$ 值。因此得到结论：如果将 $L$ 和 $R$ 以及加密的密钥均取反，那么得到的输出值也是原来值的取反结果。

总之，DES 因为具备这些特殊性质，按照前面对分组密码安全的定义，可以排除 DES 是一个安全的分组密码。但是即使忽略这些性质，DES 的密钥长度也是远远不能保证安全性的。目前已经能够通过简单的穷举搜索破译出 DES 的密钥。

3DES 算法具有更长一些的密钥，但是它继承了 DES 算法的弱密钥和互补性质，其中每一项都不符合我们的标准。而且，也受到分组长度只有 64 位的限制，这使单个密钥加密的数据量受到限制。有些时候，由于一些原因不得不使用 3DES 算法，但是需要仔细使用，因为这个算法具有分组长度的限制，而且它并非是一个理想分组密码。

项目源代码

项目源代码会逐步上传到 Github，地址为 https://github.com/windstamp。

Contributor

Windstamp, https://github.com/windstamp

5.1 密码学专题 - 对称加密算法 - DES 算法

5.1 密码学专题 - 对称加密算法 - DES 算法

密码学专题 - 对称加密算法 - DES 算法

5.1 DES 算法

项目源代码

Contributor