DES背景

DES 全称 Data Encryption Standard（数据加密标准）。DES 最初出现在 1970 年代早期。1972 年，在一个对美国政府的计算机安全需求的研究得出结果后，NBS（国家标准局，现在的NIST）开始征集用于加密政府内非机密敏感信息的加密标准。因此 1973 年 5 月 15 日，在咨询了美国国家安全局（NSA）之后，NBS向公众征集可以满足严格设计标准的加密算法。然而，没有一个提案可以满足这些要求。因此在，1974 年 8 月 27 日，NBS开始了第二次征集。这一次，IBM提交了一种在 1973-1974 年间发展的算法，这份提案被有限度的接受了。这种算法是基于早先霍斯特·费斯妥（Horst Fiestel）提出的Lucifer算法的。

注意在某些文献中，作为算法的DES称为数据加密算法（Data Encryption Algorithm, DEA），已与作为标准的DES区分开来。

DES功能

给定一个 64 位的明文和一个 64 位的密钥，输出一个 64 位的密文。这个密文可以用相同的密钥解密。所谓 64 位的密钥，其实里面只有 54 位在起作用。剩余的位当作奇偶校验位。虽然 DES 一次只能加密 8 个字节，但我们只需要把明文划分成每 8 个字节一组的块，就可以实现任意长度明文的加密。如果明文长度不是 8 个字节的倍数，则需要填充，目前填充方式主要是 PKCS7 / PKCS5。

DES加密原理

下来主要分析 8 个字节的加解密过程，下图是 DES 算法框架。

des_img01.png

密钥调度

所谓密钥调度，就是从 1 把 64 位的主钥匙，得到 16 把 48 位的子钥匙，然后把这些子钥匙用于迭代加密。

1. 使用选择置换1（PC-1）从64位输入密钥中选出 56 位的密钥，剩下的 8 位要么直接丢弃，要么作为奇偶校验位，然后把 56 位分成两个 28 位的半密钥。
2. 把两个半密钥都向左移 1 或 2 位（移位逻辑类似循环数组，具体移多少由回次数决定，见下表）。
3. 合并两个半密钥，通过置换2（PC-2）产生 48 位的子密钥。
4. 重复第 2 步和第 3 步 16 次，这样就得到了 16 把 48 位的子密钥。

流程图

des_img02.png

选择置换1(PC-1)：输入的64位数据中只用到了56位，剩余的8位可以用于奇偶校验，也可以直接丢弃。

image.png

des_img05.png

左移回次表：全部移动完移动次数恰好是 28 次，最后一次移动完又回到初始状态。

image.png

选择置换2(PC-2)：从56位的密钥调度状态中置换出48位的子密钥。

image.png

des_img06.png

轮函数（F函数）

轮函数（F函数）是整个算法的核心，以一个 48 位子密钥加密 32 位数据信息。

1. 将 32 位数据进行扩展置换，生成 48 位的数据。
2. 将置换后的 48 位结果与输入的 48 位子密钥进行异或运算，得到 48 位的运算结果。
3. 将 48 位运算结果分成 8 组，每组 6 位数据，按照组号对应相应的 S 盒，进行 8 个 S 盒置换，生成 8 个 4 位的数据。
4. 将这 8 个 4 位数据合并，得到一个 32 位数据。
5. 将 32 位进行 P 置换就得到最后的 32 位处理结果。

流程图

des_img04.png

扩张函数 (E函数)：输入中的某些位在输出中被用到了不止一次，例如输入的第 5 位出现在输出的第 6 和 8 位。因此，输入 32 位被扩张到了 48 位。这样也会带来雪崩效益，输入数据中当有 1 为发生变化时，有 50% 的概率使得 2 位输出位发生变化。

image.png

des_img07.png

置换盒 (S盒)：每个 S 盒将 6 位输入变为 4 位输出。给定输入后，输出行由外侧两位确定，列由内侧的 4 位确定。

例如，在 S2 盒中输入 “011011”。在输入的外侧位为 “01”（十进制的 1），内侧位为 “1101”（十进制的 13），因此在 S2 中的对应输出为 “1001”（十进制的 9），即第 2 行，第 14 列。

des_img08.png

S 盒作为 DES 算法中唯一的非线性器件，是加密的关键所在，然而，多年来，一直未有人将 S 盒的设计准则公开。从已有的关于 S 盒的推理不难看出有如下几条准则。

1. S 盒的每一行是整数0，1，2，…，15 的一个置换。
2. 每个 S 盒均为 6 位输入，4 位输出。
3. S 盒的输出都不是其输入的简单线性或仿射函数。
4. 改变 S 盒的 1 位输入，至少要引起 2 位的输出变化。

P置换：P置换将32位的半块数据重新排列。

image.png

des_img09.png

加密过程

1. 输入的明文（长度为64的布尔数组）做一个置换（IP置换），得到64位的数组。
2. 把得到的数组拆成左、右两半边。每边是32位长度。
3. 每一轮迭代，都是接收一组 L, R，返回 L', R' ，作为下一轮迭代的 L, R。迭代过程如下：

L' = R;
R' = L^(F(k[i], R))

4. 利用之前得到的 16 个子密钥，执行步骤 3 一共 16 次。
5. 将最终的 R 与 L 拼接，再做一次置换(FP置换)，即得到密文。

des_img03.png

IP置换

image.png

des_img10.png

FP置换：FP（亦被称为IP-1）是IP的逆过程。

image.png

des_img11.png

DES解码原理

对称加解密的基本数学原理是：一个数进行两次异或运算就能恢复，S ^ e ^ e = S。

比如：

10 ^ 6（二进制：1010 ^ 110）= 12（二进制：1100）
12 ^ 6（二进制：1100 ^ 110）= 10（二进制：1010）

DES 算法中解码只要处理好 F 函数的恢复即可，其他就是简单的查表置换即可

L' = R;
R' = L^(F(k[i], R))

最后一轮 F 函数形成密文是 L[16] 和 R[16]。

L[16] = R[15];
R[16] = L[15] ^ F(k[16], R[15])

我只要能从 L[16] 和 R[16] 得到 L[15] 和 R[15] 即可。由于 L[16] = R[15] 所以，只要获取 L[15] 即可。

再由于 R[16] = L[15] ^ F(k[16], R[15])，其中 k[16] 和 R[15] 都是已经知道的，所以

L[15] = L[15] ^ F(k[16], R[15]) ^ F(k[16], R[15]) = R[16] ^ F(k[16], R[15])

同理，根据 L[15] 和 R[15] 可以退出 L[14] 和 R[14]，以此类推可以推出 L[1] 和 R[1]。

小结：解码过程其实就是把密钥逆序一下，然后就是跑 16 轮 F 函数。

关于3DES

三重数据加密算法（英语：Triple Data Encryption Algorithm，缩写为TDEA，Triple DEA），或称3DES（Triple DES），是一种对称密钥加密块密码，相当于是对每个数据块应用三次DES算法。由于计算机运算能力的增强，原版DES由于密钥长度过低容易被暴力破解；3DES即是设计用来提供一种相对简单的方法，即通过增加DES的密钥长度来避免类似的攻击，而不是设计一种全新的块密码算法。

注意：有3个独立密钥的3DES的密钥安全性为168位，但由于中途相遇攻击（知道明文和密文），它的有效安全性仅为112位。

算法实现

3DES使用“密钥包”，其包含3个DES密钥，K1，K2和K3，均为56位（除去奇偶校验位）。

密文 = E_k3(D_k2(E_k1(明文)))

而解密则为其反过程：

明文 = D_k3(E_k2(D_k1(密文)))

1、为什么是3DES，而不是2DES？

原因：中途相遇攻击（知道明文和密文），通过空间换时间的策略，安全度降为和DES一样。

具体做法：

第一步：枚举全部加密密钥对明文加密，生成有序集合S1，时间复杂度 O(2^56)

第二步：枚举全部解码密钥对密文解码，生成有序集合S2，时间复杂度 O(2^56)

第三步：通过双指针在有序集合S1和S2中找到相同的元素，时间复杂度 O(2^57)

于是总的时间复杂度就是 O(2^56) + O(2^56) + O(2^57) = O(2^58)

2、为什么是E_k3(D_k2(E_k1(明文)))，而不是E_k3(E_k2(E_k1(明文)))？

原因：允许3DES用户通过重复密钥来解密由旧的单个DES用户加密的数据。

参考资料

• [原创]密码学基础：DES加密算法
• DES算法原理及实现
• 维基百科-DES
• 维基百科-DES补充材料
• 维基百科-3DES
• 基于S盒优化的轻量级加密算法设计