算法还原之DES
一 DES原理介绍
可以参考下面这篇文章，讲解的很详细：
https://blog.csdn.net/Demonslzh/article/details/129129493
DES算法采用分组密码，将明文分成64位一组，密钥长度为56位。其基本原理是通过一系列的置换、替换和异或运算，利用密钥对数据进行加密和解密。
- DES为对称加密算法
- DES还是一种分组加密算法，算法每次处理固定长度的数据段，称之为分组
- DES算法过程的关键是从给定的初始密钥中得到16个子密钥的函数
- 要加密一组明文，每个子密钥按照顺序(1-16)以一系列的位操作施加于数据上，每个子密钥一次，一共重复16次
- DES算法的分组大小是64位，因此，如果需要加密的明文长度不足64位，需要进行填充；如果明文长度超过64位，则需要使用分组模式进行分组加密。
- 虽然DES算法的分组大小是64位，但是由于DES算法的密钥长度只有56位。
子密钥k的生成
DES算法采用了每轮子密钥生成的方式来增加密钥的复杂性和安全性。每轮子密钥都是由主密钥（64位）通过密钥调度算法（Key Schedule Algorithm）生成的。DES算法的密钥调度算法可以将64位的主密钥分成16个子密钥，每个子密钥48位，用于每轮加密中与输入数据进行异或运算。
通过子密钥生成的流程图来看下整个过程。
1、将64位主密钥经过置换选择1（Permuted Choice 1简写为PC-1）后输出了56位，将其分为左右两个28位的数据块，分别记为C0和D0。同上面我们讲过的置换规则一样，PC-1置换函数也是一个固定的置换表。
从PC-1的置换表中可以看到，舍弃掉的8位数据是原始数据中每8位数据的最后一位，也就是我们所熟知的奇偶检验位。这8位被丢弃是因为它们对于密钥的安全性没有贡献，而且能够使DES算法的计算速度更快。
【举例】
假设我们输入的64位初始密钥对应字符串 “12345678”
则K(64) = 0011000100110010001100110011010000110101001101100011011100111000
这块对初始的k进行变换：
- 第一位为第57位：0
- 第二位为第49位：0
- 第三位为第41位：1
- ……
2、对C0和D0进行循环左移操作。循环左移完成后生成C1和D1。因此，在16个轮次的计算当中会得到16个32位的数据块C1-C16和D1-D16。在DES中循环左移也有固定的规则。
对于i=1，2，…，16，对于Ci和Di，若i为1，2，9或16，则循环左移一位，否则循环左移两位。
3、对于C1，D1，将它们经过置换选择2(Permuted Choice 2 简写位PC-2）后，得到48位的子密钥K1，用于每轮加密中与输入数据进行异或运算。PC-2置换的输入是由PC-1置换生成的56位的密钥，而它的输出是48位的子密钥。PC-2置换将56位的密钥重新排列，丢弃了8位并选取了其中的48位作为子密钥。PC-2的置换规则如下：
即PC-2置换表的第一行表示选择了输入密钥中的第14、17、11、24、1和5位，并将它们作为输出子密钥的前6位。以此类推…
4、至此，经过PC-2后的结果就是我们当前轮次的子密钥K1了。在整个DES加密过程中会生成16个48位子密钥K1-K16，分别用于DES算法中的16轮加密过程，从而保证每轮加密所使用的密钥都是不同的，增加了破解的难度。
DES加密流程
当输入了一条64位的数据之后，DES将通过以下步骤进行加密。在第4部分中，我们对每个流程进行详解。
1、初始置换（IP置换）：将输入的64位明文块进行置换和重新排列，生成新的64位数据块。
2、加密轮次：DES加密算法共有16个轮次，每个轮次都包括四个步骤：
- 将64位数据块分为左右两个32位块。
- 右侧32位块作为输入，经过扩展、异或、置换等操作生成一个48位的数据块。这个48位的数据块被称为“轮密钥”，它是根据加密算法的主密钥生成的子密钥。
- 将左侧32位块和轮密钥进行异或运算，结果作为新的右侧32位块。
- 将右侧32位块与原来的左侧32位块进行连接，生成一个新的64位数据块，作为下一轮的输入。
3、末置换（FP置换）：在最后一个轮次完成后，将经过加密的数据块进行置换和重新排列，得到加密后的64位密文。
DES算法步骤详解
初始置换(Initial Permutation，IP置换)
IP置换是将输入的64位明文块进行置换和重新排列，生成新的64位数据块。
目的:增加加密的混乱程度，使明文中的每一位都能够对后面的加密过程产生影响，提高加密强度。
我们将把64位的顺序按下表中规定的顺序放置，图中的数字是在64位明文中每个比特的索引位置。注意，在DES中，这个置放规则是固定的。
即将原来位于第58个位置的数据放在第1个位置，原来位于第50个位置的元素放在第2个位置，第42个放在第3个，34->4以此类推…
初始置换的逆置换（Final Permutation，FP置换）是将加密后的数据块进行置换和重新排列，得到最终的加密结果，与初始置换相对应。
加密轮次
初始置换完成后，明文被划分成了相同长度（32位）的左右两部分，记作L0,R0。接下来就会进行16个轮次的加密了。
我们从单独一个轮次来看。首先把目光聚焦在R0这里。
右半部分R0会作为下一轮次的左半部分L1的输入。其次，R0会补位到48位和本轮次生成的48位K0(马上讲K0的生成)输入到F轮函数中去。F函数的输出结果为32位，结果F(R0,K0)会和L0进行异或运算作为下一轮次右半部分R1的输入。
以此类推，重复16轮运算。所以，上面描述的过程可以用以下公式表述。
F轮函数
扩展运算：扩展R到48位
将32位的R0右半部分进行扩展，得到一个48位的数据块。同样的，数据拓展也是根据一个固定的置换表。红框中就是我们要补位的数据。
由此可见，扩展过程的每一位都是根据上述的置换表从输入的32位数据块中提取出来的。原始数据的第32位被补充到了新增列的第一个，第5位被补充到了第二个新增列的第一个，以此类推…
子密钥生成
参考上面第一部分：子密钥K的生成
当前轮次的子密钥与拓展的48位R进行异或运算
当前轮次的子密钥Ki与拓展的48位Ri进行异或运算。运算结果会作为接下来S盒替换的输入
S盒替换（Substitution Box substitution）
S盒替换（Substitution Box substitution）是一种在密码学中广泛使用的加密技术。它是将明文中的一组比特映射到密文中的一组比特的过程，用于增强密码的安全性。DES中S盒替换用于将上一轮异或运算的48位结果映射到32位输出中去。
同样的，S盒也是一种置换表。在DES的每一轮计算中S盒都是不一样的。这里我以第一轮计算中的S盒为例。从上图中我们看到，S盒内部有8个S块，记作S1-S8。每个S块都会接收6位字符作为输入并输出四位字符。这里我们以第一个S盒S1为例。他是一个4*16的置换表。
例如输入101010到S1中。S1会将这六位的第一位和第六位拿出来10作为S1的行，中间四位0101拿出来作为S1的列。我们转换成十进制，此时映射到这个S盒的位置就是(2,5)对应S盒的第3行第6列（索引都从0开始数）。
所以这个输入的结果是6，将6转化为二进制110，S盒的输出是4位，所以得S(101010)=0110
因此，可以看到S盒其实是一种非线性的加密技术，它能够抵御许多传统的密码分析攻击，如差分攻击和线性攻击。
P盒替换
P盒替换将S盒替换的32位输出作为输入，经过上述固定的替换表进行替换后即为最后F轮函数的结果。
该结果F(R0,K0)与L0进行异或运算得到下一轮的右半部分R1
逆置换
在经过16轮次计算后，DES会对最后的结果进行最后一次置换。即为最后的输出结果。
二 DES算法优缺点
【优点】
安全性高：DES算法使用密钥进行加密和解密，相同的明文使用不同的密钥加密后得到的密文是不同的。密钥越长，加密的安全性就越高。
算法简单：DES算法的加密和解密过程非简单，基于对称加密，使用相同的key进行加解密。
适用广泛：DES算法是最早也是最广泛使用的加密算法之一，被广泛应用于电子商务、电子邮件、虚拟私人网络等领域，具有广泛的适用性和可移植性。
【缺点】
密钥长度较短：DES算法使用56位密钥，虽然在当时足够安全，但在当前计算机的处理能力下，已经不足以保证加密的安全性，易受到暴力破解攻击。
无法抵抗差分密码分析攻击：DES算法无法抵抗差分密码分析攻击，这种攻击可以通过比较相同明文的密文，分析加密算法的行为并推断出密钥。
比较慢：由于DES算法是一种分组密码算法，需要对64位的明文进行加密，加密速度比较慢，不适用于对大量数据进行实时加密和解密。
三 DES算法实现
Python
from Crypto.cipher import DES |
C实现
https://github.com/dhuertas/DES/blob/master/des.c
