# 1 简介
## 1.1 历史
DES(Data Encryption Standard)是由IBM公司在**1974年提出**的加密算法，在**1977年被NIST定位数据加密标准**。随后的很多年里，DES都是最流行的对称密码算法，尤其是在金融领域更是如此，直到90年代随着对DES研究的深入和算力的发展，DES变得不再那么安全，但1994年NIST仍然公布了DES在未来地5年将继续作为数据加密标准，到1999年，NIST宣布DES将只在法律系统中使用并推出了它的改进版3DES，即使用两个或三个不同的密钥重复三次DES的操作。直到**2001年，AES（Adanced Encryption Standard）的提出，DES逐渐退出了历史舞台**。
这里简单提一句，DES的不安全性主要源自于它的**密钥过短**，只有64位，所以其改进版3DES到今天依然活跃在很多加密系统中。
## 1.2 结构
DES使用了典型的Feistel结构（见[维基百科]([https://zh.wikipedia.org/zh-hans/%E8%B4%B9%E6%96%AF%E5%A6%A5%E5%AF%86%E7%A0%81](https://zh.wikipedia.org/zh-hans/费斯妥密码)))，只在开始时添加了一个初始置换和结束时添加了一个逆初始置换。
结构图表示如下：
首先解释一下上图，DES共有16轮，对于每个输入的分组（64bit），首先会进行一次初始置换($IP$)，初始置换后即进行16轮的加密，种子密钥会为每一轮加密操作生成一个48bit的轮密钥，具体的生成过程以及为什么是48bit后边会有相应的解释。
对每一轮来说，输入的数据都被分为左右两部分，各32bit。每一轮的右半部分成为下一轮的左半部分，而左半部分同经过一系列操作的右半部分异或成为新的右半部分（除16轮）。
16轮加密结束后，会首先进行一次左右部分的互换，再进行一次逆初始置换($IP^{-1}$)就得到了64bit的密文分组，下面我们来详细介绍每一轮操作具体发生了什么，以及轮密钥是如何生成的。
# 2 算法描述
## 2.1 $IP,IP^{-1}$
讲内部结构之前先介绍一下初始置换和逆初始置换的具体操作：
其实都是很简单的根据表换位置的操作，首先是初始置换：
| 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位放到第二位，以此类推，
相应的，逆初始置换就是把要输出的密文按照表进行置换（我想设置它的原因应该是为了对称地解密）：
| 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 |
## 2.2 轮加密
对每轮操作来说，都是只需要对输入数据的右半部分的32bit进行操作。每轮加密的内部结构可以用下图来表示：
- **扩张**：将32bit的右半部分拓张为48bit的值，从下表可以看出，实际上就是以4bit为一组，把原本左右相邻的bit复制一次，扩张为6*8=48bit
| 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 |
- **轮密钥加**：将拓展置换生成的48bit与轮密钥异或，轮密钥同样是48bit的，轮密钥如何生成将在下一部分解释
- **S盒替换**：S盒是DES中最核心的部分，有了S盒DES才具有了非线性的性质，安全性得到保障。S盒将输入的48bit转化位32bit的输出，它的实现细节可以简述为：S盒共8个，每个S盒可以看作一个4*16的矩阵，将输入每6bit一组输入对应的S盒，输入的第0、5bit组合起来决定行数，中间4bit组合起来决定列数，S盒也是DES中最有争议的一部分，因为它的设计原则并未公开，被怀疑装有后门，具体的S盒是这样规定的：
| 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 |
| S2 | | | | | | | | | | | | | | | | |
| | x0000x | x0001x | x0010x | x0011x | x0100x | x0101x | x0110x | x0111x | x1000x | x1001x | x1010x | x1011x | x1100x | x1101x | x1110x | x1111x |
| 0yyyy0 | 15 | 1 | 8 | 14 | 6 | 11 | 3 | 4 | 9 | 7 | 2 | 13 | 12 | 0 | 5 | 10 |
| 0yyyy1 | 3 | 13 | 4 | 7 | 15 | 2 | 8 | 14 | 12 | 0 | 1 | 10 | 6 | 9 | 11 | 5 |
| 1yyyy0 | 0 | 14 | 7 | 11 | 10 | 4 | 13 | 1 | 5 | 8 | 12 | 6 | 9 | 3 | 2 | 15 |
| 1yyyy1 | 13 | 8 | 10 | 1 | 3 | 15 | 4 | 2 | 11 | 6 | 7 | 12 | 0 | 5 | 14 | 9 |
| S3 | | | | | | | | | | | | | | | | |
| | x0000x | x0001x | x0010x | x0011x | x0100x | x0101x | x0110x | x0111x | x1000x | x1001x | x1010x | x1011x | x1100x | x1101x | x1110x | x1111x |
| 0yyyy0 | 10 | 0 | 9 | 14 | 6 | 3 | 15 | 5 | 1 | 13 | 12 | 7 | 11 | 4 | 2 | 8 |
| 0yyyy1 | 13 | 7 | 0 | 9 | 3 | 4 | 6 | 10 | 2 | 8 | 5 | 14 | 12 | 11 | 15 | 1 |
| 1yyyy0 | 13 | 6 | 4 | 9 | 8 | 15 | 3 | 0 | 11 | 1 | 2 | 12 | 5 | 10 | 14 | 7 |
| 1yyyy1 | 1 | 10 | 13 | 0 | 6 | 9 | 8 | 7 | 4 | 15 | 14 | 3 | 11 | 5 | 2 | 12 |
| S4 | | | | | | | | | | | | | | | | |
| | x0000x | x0001x | x0010x | x0011x | x0100x | x0101x | x0110x | x0111x | x1000x | x1001x | x1010x | x1011x | x1100x | x1101x | x1110x | x1111x |
| 0yyyy0 | 7 | 13 | 14 | 3 | 0 | 6 | 9 | 10 | 1 | 2 | 8 | 5 | 11 | 12 | 4 | 15 |
| 0yyyy1 | 13 | 8 | 11 | 5 | 6 | 15 | 0 | 3 | 4 | 7 | 2 | 12 | 1 | 10 | 14 | 9 |
| 1yyyy0 | 10 | 6 | 9 | 0 | 12 | 11 | 7 | 13 | 15 | 1 | 3 | 14 | 5 | 2 | 8 | 4 |
| 1yyyy1 | 3 | 15 | 0 | 6 | 10 | 1 | 13 | 8 | 9 | 4 | 5 | 11 | 12 | 7 | 2 | 14 |
| S5 | | | | | | | | | | | | | | | | |
| | x0000x | x0001x | x0010x | x0011x | x0100x | x0101x | x0110x | x0111x | x1000x | x1001x | x1010x | x1011x | x1100x | x1101x | x1110x | x1111x |
| 0yyyy0 | 2 | 12 | 4 | 1 | 7 | 10 | 11 | 6 | 8 | 5 | 3 | 15 | 13 | 0 | 14 | 9 |
| 0yyyy1 | 14 | 11 | 2 | 12 | 4 | 7 | 13 | 1 | 5 | 0 | 15 | 10 | 3 | 9 | 8 | 6 |
| 1yyyy0 | 4 | 2 | 1 | 11 | 10 | 13 | 7 | 8 | 15 | 9 | 12 | 5 | 6 | 3 | 0 | 14 |
| 1yyyy1 | 11 | 8 | 12 | 7 | 1 | 14 | 2 | 13 | 6 | 15 | 0 | 9 | 10 | 4 | 5 | 3 |
| S6 | | | | | | | | | | | | | | | | |
| | x0000x | x0001x | x0010x | x0011x | x0100x | x0101x | x0110x | x0111x | x1000x | x1001x | x1010x | x1011x | x1100x | x1101x | x1110x | x1111x |
| 0yyyy0 | 12 | 1 | 10 | 15 | 9 | 2 | 6 | 8 | 0 | 13 | 3 | 4 | 14 | 7 | 5 | 11 |
| 0yyyy1 | 10 | 15 | 4 | 2 | 7 | 12 | 9 | 5 | 6 | 1 | 13 | 14 | 0 | 11 | 3 | 8 |
| 1yyyy0 | 9 | 14 | 15 | 5 | 2 | 8 | 12 | 3 | 7 | 0 | 4 | 10 | 1 | 13 | 11 | 6 |
| 1yyyy1 | 4 | 3 | 2 | 12 | 9 | 5 | 15 | 10 | 11 | 14 | 1 | 7 | 6 | 0 | 8 | 13 |
| S7 | | | | | | | | | | | | | | | | |
| | x0000x | x0001x | x0010x | x0011x | x0100x | x0101x | x0110x | x0111x | x1000x | x1001x | x1010x | x1011x | x1100x | x1101x | x1110x | x1111x |
| 0yyyy0 | 4 | 11 | 2 | 14 | 15 | 0 | 8 | 13 | 3 | 12 | 9 | 7 | 5 | 10 | 6 | 1 |
| 0yyyy1 | 13 | 0 | 11 | 7 | 4 | 9 | 1 | 10 | 14 | 3 | 5 | 12 | 2 | 15 | 8 | 6 |
| 1yyyy0 | 1 | 4 | 11 | 13 | 12 | 3 | 7 | 14 | 10 | 15 | 6 | 8 | 0 | 5 | 9 | 2 |
| 1yyyy1 | 6 | 11 | 13 | 8 | 1 | 4 | 10 | 7 | 9 | 5 | 0 | 15 | 14 | 2 | 3 | 12 |
| S8 | | | | | | | | | | | | | | | | |
| | x0000x | x0001x | x0010x | x0011x | x0100x | x0101x | x0110x | x0111x | x1000x | x1001x | x1010x | x1011x | x1100x | x1101x | x1110x | x1111x |
| 0yyyy0 | 13 | 2 | 8 | 4 | 6 | 15 | 11 | 1 | 10 | 9 | 3 | 14 | 5 | 0 | 12 | 7 |
| 0yyyy1 | 1 | 15 | 13 | 8 | 10 | 3 | 7 | 4 | 12 | 5 | 6 | 11 | 0 | 14 | 9 | 2 |
| 1yyyy0 | 7 | 11 | 4 | 1 | 9 | 12 | 14 | 2 | 0 | 6 | 10 | 13 | 15 | 3 | 5 | 8 |
| 1yyyy1 | 2 | 1 | 14 | 7 | 4 | 10 | 8 | 13 | 15 | 12 | 9 | 0 | 3 | 5 | 6 | 11 |
例如“**0**1101**1**”的输入的外侧位为“**01**”，内侧位为“1101”，即第2行，第14列。因此在S5中的对应输出为“1001”（十进制的9）
- **P置换**：P置换将S盒输出的32位数据重新排列
| 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 |
置换后输出的数据同本轮的左半部分异或成为新的右半部分，随即作为输入进入下一轮。
# 3 轮密钥生成
上面提到，参与轮密钥加的轮密钥有48bit，但种子密钥是有64bit的，生成轮密钥主要要经过以下几步：
## 3.1 选择置换（PC-1）
在输入的种子密钥中，有8bit是不用于加密的，通常用于校验或者直接舍弃掉，PC-1就是打乱顺序的同时舍弃掉这些比特，观察下表，首先可以注意到表中是没有8、16、24这些比特的；此外，PC-1结束后密钥被分为左右两部分，如下表所示：
| 左 | | | | | | |
| :--: | :--: | :--: | :--: | :--: | :--: | :--: |
| 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 |
# 3.2 循环移位
对每一轮操作，密钥的左右两部分会同时进行循环左移，每一轮循环左移的位数规定如下：
| 回次 | 左移位数 |
| :--: | :------: |
| 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 |
## 3.3 压缩置换（PC-2）
每一次循环左移结束后，根据下表选出48bit作为轮密钥，所以选择置换2又被称为压缩置换：
| 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 |
这样，每一轮都能得到一个单独的轮密钥用于轮密钥加的操作。
解密时，只需要将轮密钥序列反序使用即可
# 4 解密操作
开头说过，DES时典型的Feistel结构，在直到密钥的情况下很容易就能实现对称解密。
最开始学习的时候，收AES的影响，我以为是每个操作都会有一个逆操作，相应的S盒也有一个逆S盒，但在我代码实现时我发现这是错误的，不像AES是基于有限域上的操作，DES的S盒是没有逆操作的，这时我才明白，原来只需要一样的步骤，只需要改变轮密钥的顺序就能实现解密操作，所以说，学习知识时还是要仔细思考，不能浅尝辄止！
# 参考资料
1. 维基百科[DES](https://zh.wikipedia.org/wiki/資料加密標準)
2. [DES描述 NIST](http://csrc.nist.gov/publications/fips/fips46-3/fips46-3.pdf)
3. 密码编码学与网络安全原理与实践（英文版）第七版
