DES详解

DES(Data Encryption Standard)是一种对称加密算法。之前我仅对DES的基本使用方式有了解，但对具体的加解密细节没有深入研究。这里，便是阅读相关资料后，对DES加密细节的记录笔记。

DES概述

DES是20世纪70年代初，由IBM设计的一种对称加密算法。DES使用56位的密钥，块长度为64位。当然，今天看来，这个密钥过于短了。

整个DES加密过程，可以大致分为以下几个阶段：

对输入的块进行初始置换(Initial Permutaion)，得到premuted input
使用密钥，对premuted input进行16轮变换，得到preoutput
最后，对preoutput进行最终置换，得到加密结果

初始置换

加密开始时，对输入的长度为64位的明文，进行初始置换 \(IP\)。其置换方式如下图中 \(8\times 8\) 的表格所示：

58	50	42	34	26	18	10	2
60	52	44	36	28	20	12	4
62	54	46	38	30	22	14	6
64	56	48	40	32	24	16	8
57	49	41	33	25	17	9	1
59	51	43	35	27	19	11	3
61	53	45	37	29	21	13	5
63	55	47	39	31	23	15	7

即：置换结果的各位，依次为输入的第58, 50, 42, …, 15, 7位。

这一阶段完成之后，得到的结果记为premuted input，作为下一阶段的输入。

加密

得到了premuted input之后，便是整个加密的主要过程了。在这个阶段，会进行16轮的变换。

记第 \(i\) 轮的输入为 \(L_iR_i\)，其中 \(L_i\) 是输入的前32位，\(R_i\) 是输入的后32位。那么每一轮计算的方式如下：

\[\begin{align} L_i &= R_{i-1}\\ R_i &= L_{i-1}\oplus f(R_{i-1}, K_i) \end{align}\]

其中：

\(i\) 取值从1到16
\(\oplus\) 是异或操作(XOR)
\(K_i\) 长度为48位，由密钥 \(KEY\) 计算得到，每轮根据Key Schedule进行更新
\(f\) 是加密函数(Cipher Function)，其输入为32位和48位的两个值，输出结果的长度为32位

当这16轮计算完成之后，将结果拼接得到 \(R_{16}L_{16}\)。将其记为preoutput，长度为64位，作为最后置换的输入。

在进行解密时，同样需要进行16轮计算。具体地，由于置换的方法是固定的，在已知密钥的情况下，可以计算出16轮用到的全部 \(K_i\)（具体计算方法见下文）。那么，解密需要做的，就是由 \(L_{16}\) 和 \(R_{16}\)，计算得到 \(L_0\) 和 \(R_0\)。

这个计算过程，可以由加密时的计算公式倒推而得。例如，由

\[\begin{align} L_{16} &= R_{15}\\ R_{16} &= L_{15}\oplus f(R_{15}, K_{16}) \end{align}\]

可知

\[\begin{align} R_{15} &= L_{16}\\ L_{15} &= R_{16}\oplus f(L_{16}, K_{16}) \end{align}\]

从而 \(L_{15}\) 和 \(R_{15}\) 可以计算得到。使用同样的方法，一步步可将全部 \(L_i\) 和 \(R_i\) 求得，进而完成解密。

Key Schedule

在这16轮计算中，每一轮的 \(K_i\) 是根据Key Schedule进行计算的，将该计算方法记为 \(KS\)。这一过程中涉及以下3种操作：

Permutated Choice 1(\(PC1\))：将长度为64位的输入，置换得到两个长度为28位的输出
Permutated Choice 2(\(PC2\))：将长度为56位的输入，置换得到长度为48位的输出
Left Shifts(\(LS\))：对输入进行位运算，向左循环移位

下面，将具体介绍 \(KS\) 的计算过程。

首先，将64位的密钥 \(KEY\) 使用 \(PC1\) 进行置换，得到两个长度为28位的结果，分别记为 \(C_0\) 和 \(D_0\)。用于计算这两者的置换分别如下：

57	49	41	33	25	17	9
1	58	50	42	34	26	18
10	2	59	51	43	35	27
19	11	3	60	52	44	36

63	55	47	39	31	23	15
7	62	54	46	38	30	22
14	6	61	53	45	37	29
21	13	5	28	20	12	4

可以看到，输入的64位中，只有56位被使用了，第8, 16, 24, 32, 40, 48, 56, 64位没有被使用。实际上，这就是DES的实际密钥长度为56位的原因：未被使用的8位，被用作56位密钥的奇偶校验。

具体地：

使用第一张表置换得到 \(C_0\)，其各位依次为 \(KEY\) 的第57, 49, 41, …, 44, 36位
使用第二张表置换得到 \(D_0\)，其各位依次为 \(KEY\) 的第63, 55, 47, …, 12, 4位

接下来，在每一轮计算 \(K_i\) 时，使用如下公式：

\[\begin{align} C_i &= LS_i(C_{i-1})\\ D_i &= LS_i(D_{i-1})\\ K_i &= PC2(C_iD_i) \end{align}\]

其中 \(LS_i\) 即为向左循环移位操作，具体每轮移位的位数由下表确定：

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

将得到的 \(C_i\) 与 \(D_i\) 拼接，得到长度为56位的块，再使用置换 \(PC2\) 得到长度为48位的块，作为这一轮的 \(K_i\)。置换 \(PC2\) 的方式可见下面的表格：

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

综上，DES的Key Schedule过程，可见Wiki上的这张图所示：

Cipher Function

回顾之前提到的每轮计算方式：

\[\begin{align} L_i &= R_{i-1}\\ R_i &= L_{i-1}\oplus f(R_{i-1}, K_i) \end{align}\]

现在，我们由 \(KS\) 知道了每轮的 \(K_i\) 的值。接下来，就需要了解加密函数 \(f\) 是如何工作的。其大致流程如下图所示：

其中涉及3种操作：

扩张置换\(E\)：输入长度为32位，输出长度为48位
Substitution-Box(\(S_i\))：输入长度为6位，输出长度为4位
置换 \(P\)：输入长度为32位，输出长度为32位

下面，是具体计算过程。

首先，\(f\) 的第一个参数，即32位的 \(R_{i-1}\)，经过 \(E\) 的变换，得到48位的结果。变换 \(E\) 由如下表格确定：

32	1	2	3	4	5
4	5	6	7	8	9
8	9	10	11	12	13
12	13	14	15	16	17
16	17	18	19	20	21
20	21	22	23	24	25
24	25	26	27	28	29
28	29	30	31	32	1

具体地，经过 \(E\) 的变换，结果中的各位，依次为输入的第32, 1, 2, …, 32, 1位。可以看到，输入的有些位，在输出中重复出现了。所以输出的位数，由输入时的32，增加到了48。

接下来，得到的这48位的块，与函数 \(f\) 的参数 \(K_i\) 进行 \(\oplus\) 操作，即异或操作，得到的结果仍然是48位的。将其每6位编为一组，记为：

\[B_1B_2\cdots B_8\]

然后，对每一个 \(B_i\)，使用对应的sbox进行变换，并将结果继续拼接起来。

sbox将6位的输入，变换为4位的输出，那么其具体计算方式是什么呢？以 \(S_1\) 为例，其内容如下：

S1	x0000x	x0001x	x0010x	x0011x	x0100x	x0101x	x0110x	x0111x	x1000x	x1001x	x1010x	x1011x	x1100x	x1101x	x1110x	x1111x
0yyyy0	14	4	13	1	2	15	11	8	3	10	6	12	5	9	0	7
0yyyy1	0	15	7	4	14	2	13	1	10	6	12	11	9	5	3	8
1yyyy0	4	1	14	8	13	6	2	11	15	12	9	7	3	10	5	0
1yyyy1	15	12	8	2	4	9	1	7	5	11	3	14	10	0	6	13

对于长度为6位的输入，根据其第1, 6位确定所在行，再根据其第2至5位确定所在列，找到对应的值，即为sbox的输出结果。

例如，对于 \(S_1\)，如果输入是 011011，那么其变换的结果是在第2行，倒数第3列，值为5=0101。所以：

\[S_1(011011) = 0101\]

剩下7个sbox的内容，可见Wiki。对于这8个 \(B_i\)，通过 \(S_i\) 全部计算完成后再拼接，得到长度为32位的结果：

\[S_1(B_1)S_2(B_2)\cdots S_8(B_8)\]

最后，再对这32位使用 \(P\) 进行置换。\(P\) 的定义如下：

16	7	20	21	29	12	28	17
1	15	23	26	5	18	31	10
2	8	24	14	32	27	3	9
19	13	30	6	22	11	4	25

于是，加密函数 \(f\) 的最终返回值，为：

\[P\Big(S_1(B_1)S_2(B_2)\cdots S_8(B_8)\Big)\]

最终置换

经过了漫长的加密，即将得到最终的DES加密结果。再次回顾之前的内容，进行了16轮加密计算后，我们得到了 \(L_{16}\) 和 \(R_{16}\)。将其交换之后，进行最终置换

\[FP(R_{16}L_{16})\]

此置换为初始置换的逆 \(IP^{-1}\)，其内容如下：

40	8	48	16	56	24	64	32
39	7	47	15	55	23	63	31
38	6	46	14	54	22	62	30
37	5	45	13	53	21	61	29
36	4	44	12	52	20	60	28
35	3	43	11	51	19	59	27
34	2	42	10	50	18	58	26
33	1	41	9	49	17	57	25

即：DES最终加密结果的各位，依次为 \(R_{16}L_{16}\) 的第40, 8, 48, …, 57, 25位。

以上便是整个DES的加密流程，其大致示意图如下：

当然，这只是对一个块进行加密，实际使用中，还涉及到工作模式如ECB等。由于相关资料较多，这里就不赘述了。

安全性

自从DES加密算法被采取为标准之后，对DES安全性的分析和研究便一直在进行。而DES设计过程中NSA的参与，更是催生出了“DES算法中存在NSA的后门”这种论点。质疑者认为，过短的密钥长度，以及神器的sbox的选取，都有可能是NSA为了便于破解DES而故意设计的。

sbox

抛开密钥长度不论，sbox是DES加密中非常重要的一环，其直接影响到了整个加密的安全性。这是因为sbox是加密过程中唯一的非线性部分。由于sbox的设计准则迟迟没有被公开，所以有些人怀疑sbox的设计上存在缺陷，可以被NSA利用来破解DES。

事实上，一直到DES被公布后约20年，对sbox的设计的质疑才慢慢停歇。而这与微分密码分析(Differential cryptanalysis)的公开有关。这种破解方法，是由Eli Biham和Adi Shamir(RSA算法的发明者之一)在80年代晚期，才逐渐研究并公开的。于是，人们尝试将这种破解方法试用在70年代发明的DES上，却发现sbox的设计可以有效抵御Differential cryptanalysis。

这难道是巧合？当然不是。时间到了1994，终于真相大白。曾经参与过DES设计的IBM研究人员，Don Coppersmith，发布了一篇论文The Data Encryption Standard (DES) and its strength against attacks。在这篇论文中，Coppersmith提到，在当时设计DES时，他们就已经知道了Differential cryptanalysis这种攻击方法。于是在设计sbox时，就考虑到了对其防御。

那么，既然IBM，当然也有NSA，早在近20年前就知道了这种攻击方法，为什么不公开呢？这就值得回味了。根据Coppersmith那篇论文中的解释，Differential cryptanalysis是一种非常强大的攻击方法，对于许多加密方式都有效。一旦他们将其公开，就会对美帝的国家安全造成危害。当然，直到90年代被公开之前，Differential cryptanalysis应该就是NSA的”黑科技“了，不知道他们利用其破解了多少信息。

同时，在Coppersmith的论文中，也第一次公开了sbox的一些设计准则。例如：sbox不能接近线性；只相差1位的输入，经过sbox变换后，相差至少2位，等等。详细内容可见Coppersmith的论文。

3DES

仅仅56位的密钥长度，是DES另一个被人诟病的地方。为此，Triple Data Encryption Algorithm(TDES或3DES)被提出。3DES实际上是使用3个56位的密钥 \(K1\), \(K2\), \(K3\)，进行了3次DES。具体地，加密过程如下：

\[C=E_{K3}\Big(D_{K2}\big(E_{K1}(P)\big)\Big)\]

其中，\(P\) 是输入的明文，\(C\) 是输出的密文，\(E_{K}\) 指用 \(K\) 进行DES加密，\(D_K\) 指用 \(K\) 进行解密。

知道了3DES的加密过程，那么解密便是其逆过程，具体如下：

\[P=D_{K1}\Big(E_{K2}\big(D_{K3}(C)\big)\Big)\]

而3DES用到的密钥 \((K1, K2, K3)\)，可以有以下3种选择：

\(K1\), \(K2\), \(K3\) 互相独立
\(K1\) 和 \(K2\) 互相独立，\(K3=K1\)
3个密钥全部相同

第一种选择中，虽然3个密钥是互相独立的，但由于Meet-in-the-middle_attack，其有效安全性仅有112位。

参考文献