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

5.1 DES 的描述

DES 是一个分组加密算法，它以 64 位为分组对数据加密。64 位一组的明文从算法的一端输入，64 位的密文从另一端输出。DES 是一个对称算法：加密和解密用的是同一算法 (除密钥编排不同以外)。

密钥的长度为 56 位。(密钥通常表示为 64 位的数，但每个第 8 位都用作奇偶校验，可以忽略。) 密钥可以是任意的 56 位的数，且可在任意的时候改变。其中极少量的数被认为是弱密钥，但能容易地避开它们。所有的保密都依赖于密钥。

简单地说，算法只不过是加密的两个基本技术——混乱和扩散的组合。DES 基本组件分组是这些技术的一个组合 (先代替后置换)，它基于密钥作用于明文，这是众所周知的轮 (round)。DES 有 16 轮，这意味着要在明文分组上 16 次实施相同的组合技术 (见图 12-1)。

此算法只使用了标准算术和逻辑运算，而其作用的数也最多只有 64 位，因此用 20 世纪 70 年代末期的硬件技术很容易实现。算法的重复特性使得它可以非常理想地用在一个专用芯片中。最初的软件实现很粗陋，但现在已好多了。

图12-1 DES.jpg

5.1.1 算法概要

DES 对 64 位的明文分组进行操作。通过一个初始置换，将明文分组分成左半部分和右半部分，各 32 位长。然后进行 16 轮完全相同的运算，这些运算称为函数 f，在运算过程中数据与密钥结合。经过 16 轮后，左、右半部分合在一起经过一个末置换 (初始置换的逆置换)，这样该算法就完成了。

在每一轮中 (见图 12-2)，密钥位移位，然后再从密钥的 56 位中选出 48 位。通过一个扩展置换将数据的右半部分扩展成 48 位，并通过一个异或运算与 48 位密钥结合，通过 8 个 S 盒将这 48 位替代成新的 32 位数据，再将其转换一次。这四步运算构成了函数 f。然后，通过另一个异或运算，函数 f 的输出与左半部分结合，其结果即成为新的右半部分，原来的右半部分成为新的左半部分。将该运算重复 16 次，便实现了 DES 的 16 轮运算。

图12-2 一轮 DES.jpg

假设 $B_i$ 是第 i 次迭代的结果， $L_i$ 和 $R_i$ 是 $B_i$ 的左半部分和右半部分， $K_i$ 是第 i 轮的 48 位密钥，且 f 是实现代替、置换及密钥异或等运算的函数，那么每一轮就是：
$L_i = R_{i-1}$

$R_i = L_{i-1} \bigoplus f(R_{i-1}, K_i)$

5.1.2 初始置换

初始置换在第一轮运算之前执行，对输入分组实施如表 12-1 所示的变换。此表应从左向右、从上向下读。例如，初始置换把明文的第 58 位换到第 1 位的位置，把第 50 位换到第 2 位的位置，把第 42 位换到第 3 位的位置等。

表12-1 初始置换.jpg

初始置换和对应的末置换并不影响 DES 的安全性。(正如人们所说，它的主要目的是为了更容易地将明文和密文数据以字节大小放入 DES 芯片中。记住，DES 早于 16 位和 32 位微处理总线。) 因为这种位方式的置换用软件实现很困难 (虽然用硬件实现较容易)，所以 DES 的许多软件实现方式删去了初始置换和末置换。尽管这种新算法的安全性不比 DES 差，但它并未遵循 DES 标准，所以不应该叫做 DES。

5.1.3 密钥置换

开始，由于不考虑每个字节的第 8 位，所以 DES 的密钥由 64 位减至 56 位，如表 12-2 所示。每个字节的第 8 位可作为奇偶校验以确保密钥不发生错误。在 DES 的每一轮中，从 56 位密钥产生出不同的 48 位子密钥 (subkey)，这些子密钥 $K_i$ 由下面的方式确定。

表12-2 密钥置换.jpg

首先，56 位密钥被分成两部分，每部分 28 位。然后，根据轮数，这两部分分别循环左移 1 位或 2 位。表 12-3 给出了每轮移动的位数。

表12-3 每轮移动的位数.jpg

移动后，就从 56 位中选出 48 位。因为这个运算不仅置换了每位的顺序，同时也选择了子密钥，因而称为压缩置换 (compression permutation)。这个运算提供了一组 48 位的集。表 12-4 定义了压缩置换 (也称为置换选择)。例如，处在第 33 位的那一位在输出时移到了第 35 位的位置，而处在第 18 位的那一位被略去了。

表12-4 压缩置换.jpg

因为有移动运算，所以在每一个子密钥中使用了不同的密钥子集的位。虽然不是所有的位在子密钥中使用的次数均相同，但在 16 个子密钥中，每一位大约使用了其中 14 个子密钥。

5.1.4 扩展置换

这个运算将数据的右半部分 $R_i$ 从 32 位扩展到了 48 位。由于这个运算改变了位的次序，重复了某些位，所以称为扩展置换 (expansion permutation)。这个运算有两个方面的目的：它产生了与密钥同长度的数据以进行异或运算；它提供了更长的结果，使得在替代运算时能进行压缩。但是，以上的两个目的都不是它在密码学上的主要目的。由于输入的一位将影响两个替换，所以输出对输入的依赖性将传播得更快，这叫做雪崩效应 (avalanche effect)。故 DES 的设计着重于尽可能快地使得密文的每一位依赖明文和密钥的每一位。

图 12-3 显示了扩展置换，有时它也叫做 E 盒 (E-box)。对每个 4 位输入分组，第 1 位和第 4 位分别表示输出分组中的两位，而第 2 位和第 3 位分别表示输出分组中的一位。表 12-5 给出了哪位输出位对应于哪个输入位。例如，处于输入分组中第 3 位的位置位移到了输出分组中第 4 位的位置，而输入分组中第 21 位的位置位移到了输出分组中第 30 位和第 32 位的位置。

图12-3 扩展转换.jpg

表12-5 扩展置换.jpg

尽管输出分组大于输入分组，但每一个输入分组产生唯一的位输出分组。

5.1.5 S 盒代替

压缩后的密钥与扩展分组异或以后，将 48 位的结果送入进行代替运算。代替由 8 个代替盒 (substitution box)，或 S 盒 (S-box) 完成。每一个 S 盒都有 6 位输入、4 位输出。且这 8 个 S 盒是不同的。(DES 的这 8 个 S 盒占的存储空间为 256 字节。) 48 位的输入被分为 8 个 6 位的分组，每个分组对应一个 S 盒代替操作：分组 1 由 S 盒 1 操作，分组 2 由 S 盒 2 操作等。见图 12-4。

图12-4 S盒代替.jpg

每个 S 盒是一个 4 行、16 列的表。盒中的每一项都是一个 4 位的数。S 盒的 6 个位输入确定了其对应的输出在哪一行哪一列。表 12-6 列出了所有 8 个 S 盒。

表12-6 S盒.jpg

表12-6续 S盒.jpg

输入位以一种非常特殊的方式确定了 S 盒中的项。假定将 S 盒的 6 位输入标记为 $b_1、b_2、b_3、b_4、b_5、b_6、b_7、b_8$ 。 $b_1$ 和 $b_6$ 组合构成了一个 2 位的数，从 0 ~ 3，它对应于表中的一行。从 $b_2 \sim b_5$ 构成了一个 4 位的数，从 0 ~ 15，对应于表中的一列。

例如，假设第 6 个 S 盒的输入 (即异或函数的第 31 ~ 36 位) 为 110011。第 1 位和最后一位组合形成了 11，它对应着第 6 个 S 盒的第三行。中间的 4 位组合在一起形成了 1001，它对应着同一个 S 盒的第 9 列。S 盒 6 的第三行第 9 列的数是 14 (记住，行、列的记数均从 0 开始，而不是从 1 开始)，则值 1110 就代替了 110011。

当然，用软件实现 64 项的 S 盒更容易。仅需要花费一些精力重新组织 S 盒的每一项，这并不困难。(S 盒的设计必须非常仔细，不要仅仅改变查找的索引，而不重新编排 S 盒中的每一项。) 然而，S 盒的这种描述，使它的工作过程可视化了。每个 S 盒可看做一个 4 位输入的代替函数： $b_2 \sim b_5$ 直接输入，输出结果为 4 位。 $b_1$ 和 $b_6$ 位来自临近的分组，它们从特定 S 盒的四个代替函数中选择一个。

这是该算法的关键步骤。所有其他的运算都是线性的，易于分析。而 S 盒是非线性的，它比 DES 的其他任何一步都提供了更好的安全性。

这个代替过程的结果是 8 个 4 位的分组，它们重新合在一起形成了一个 32 位的分组。这个分组将进行下一步：P 盒转换。

5.1.6 P 盒置换

S 盒代替运算后的 32 位输出依照 P 盒 (P-box) 进行置换。该置换把每输入位映射到输出位，任一位不能映射两次，也不能被略去，这个置换叫做直接置换 (straight permutation)，或就叫做置换。表 12-7 给出了每位移至的位置。例如，第 21 位移到了第 4 位，同时第 4 位移到了第 31 位。

表12-7 P盒置换.jpg

最后，将 P 盒置换的结果与最初的 64 位分组的左半部分异或，然后左、右半部分交换，接着开始另一轮。

5.1.7 末置换

末置换是初始置换的逆过程，表 12-8 列出了该置换。注意 DES 在最后一轮后，左半部分和右半部分并未交换，而是将 $R_16$ 和 $L_16$ 并在一起形成一个分组作为末置换的输入。到此，不再做其他的事。其实交换左、右两部分并循环移动，仍将获得完全相同的结果。但这样做，就使该算法既能用作加密，又能用作解密。

表12-8 末置换.jpg

5.1.8 DES 解密

在经过所有的代替、置换、异或和循环移动之后，你或许认为解密算法与加密算法完全不同，并且也像加密算法一样有很强的混乱效果。恰恰相反，经过精心选择各种运算，获得了这样一个非常有用的性质：加密和解密可使用相同的算法。

DES 使得用相同的函数来加密或解密每个分组成为可能。两者的唯一不同是密钥的次序相反。这就是说，如果各轮的加密密钥分别是 $K_1、K_2、K_3、...、K_{16}$ ，那么解密密钥就是 $K_{16}、K_{15}、K_{14}、...、K_1$ 。为各轮产生密钥的算法也是循环的。密钥向右移动，每次移动的个数为 $0,1,2,2,2,2,2,2,1,2,2,2,2,2,2,1$ 。