超级清晰的DES算法详解

一. DES算法介绍
1. 对称加密算法
通信的双方同时掌握一个密钥,加密解密都是由一个密钥完成的(加密密钥等于解密密钥)。
双方通信前共同拟定一个密钥,不对第三方公开。
不具有个体原子性,一个密钥被共享,泄露几率会大大增加。
2. 非对称加密算法
在非对称加密中,不再只有一个密钥Key了。
在非对称加密算法中,密钥被分解为一对,一个称为公开密钥,另一个称为私有密钥。
对于公钥,可以通过非保密方式向他人公开,而私钥则由解密方保密,不对别人公开。
3. 对称加密算法的应用
DES算法是对称加密算法的代表,虽然现在已经很好实现,但是对于研究其改进的方法,有很重大的影响。
在DES算法中由于大部分原始数据较长,首先需要将数据切成64位的明文分组,所以DES算法也叫做分组加密算法,由于分完组后是一块,所以又叫块加密。
在DES算法中使用的密钥位64位,其中有效的密钥长度其实只有56位(分成8块每块长为8位,每隔8位设置左后一位为校验位,采用就奇偶校验法)。
在DES算法中加密的明文较长,需要对DES加密进行16轮的函数循环迭代。
当n个64位明文数据块都经过DES加密处理后,所得到的n个64位密文数据块串在一起就是密文。
二. DES算法过程
DES 加密算法大致分为 4 个步骤:
- 初始置换
- 生成子密钥
- 迭代过程
- 逆置换
这是整体的流程
这里注意一下,我们默认明文和密钥都是64位的,至于怎么变成64位,我们这里不讲
1. 初始置换
初始置换是将原始明文经过IP置换表处理。
IP置换表:
置换过程:
比如我们的明文为:010101101101110111110101011011100110111011100011001001101011001
把这个64位明文排成一个 8 * 8 的矩阵
然后我们要通过IP置换表来进行置换,这个置换就是根据位置来的。
比如我看IP置换表的一个58,就代表要替换为明文矩阵中的第58个元素。
同理,置换表中的50,替换为明文矩阵中的第50个元素,即50替换为0
这样置换后我们就可以得到一个新的矩阵M’
这样我们就得到了一个转置矩阵M’
然后我们取M’的前32位位L0,后32位为R0
得到:
- L0(32位):11111111101110000111011001010111
- R0(32位):00000000111111110000011010000011
2. 生成子密钥
(1) 大体过程
DES 加密共执行16次迭代,每次迭代过程的数据长度为48位,因此需要16个48位的子密钥来进行加密,生成子密钥的过程如下:
(2) 涉及到的表
这里有涉及了几个表:
选择置换1 (PC-1)
选择置换2 (PC-2)
循环左移查表
以上就是我们需要的一些表,分别是选择置换1 (PC-1),选择置换2 (PC-2),循环左移查表
(3) 密钥置换与移位
下面开始生成子密钥
我们得到了64位的密钥K,K = 0001001100110100010101110111100110011011101111001101111111110001
我们把它变成 8 * 8 的矩阵,然后对照选择置换1 (PC-1)表进行置换,置换的规则和初始置换的规则一样,然后就可以得到一个新的矩阵,严格来说是两个,一个左C0矩阵,28位,一个右D0矩阵,28位。
这里注意,密钥的长度为64bit,但是我们置换的时候能够发现,置换后左右两个矩阵其实是56位,因为有8位是进行奇偶校验的,对于密钥来说没啥用,所以结果是64bit置换成为56bit的密钥,分左右C0和D0后,这两就是28位的数据
置换后得到:
- K’(56位):11110000110011001010101011110101010101100110011110001111
- C0(28位):1111000011001100101010101111
- D0(28位):0101010101100110011110001111
这样我们就得到了C0和D0,接下来准备进行第一轮移位
我们根据循环左移查表,第一轮是向左移一位,我们拿C0进行演示
同理对D0进行移位,这样我们就得到第一轮移位的结果C1和D1
- C1(28位):1110000110011001010101011111
- D1(28位):1010101011001100111100011110
将C1和D1合并后,经过PC-2表置换得到子密钥K1
- K1:11100001100110010101010111111010101011001100111100011110
然后我们根据选择置换2 (PC-2) 表对K1进行置换,置换规则和上面的一样,可以得到K1的置换结果K1’
注意PC-2这个表除了第9,18,22,25,35,38,43,54位。即K1’只有48个数
- K1’(48位):000110110000001011101111111111000111000001110010
接下来就是第二轮移位,查看移位表,发现第二轮是左移1位,我们对C1和D1进行移位,得到C2和D2
- C2(28位):1100001100110010101010111111
- C2(28位):0101010110011001111000111101
把这俩合并得到56位的K2
- K2(56位): 11000011001100101010101111110101010110011001111000111101
然后再通过PC-2表进行置换,得到K2’
- K2’(48位):011110011010111011011001110110111100100111100101
然后还是一样,进行第三轮,通过移位表对C2和D2进行移位,得到C3和D3,然后C3和D3放一起得到58位的K3,然后K3通过PC-2表进行置换,得到48位的K3’,然后进行第四轮……
C3(28位) = 0000110011001010101011111111
D3(28位) = 0101011001100111100011110101
K3(56位) = 00001100110010101010111111110101011001100111100011110101
K3’(48位) = 010101011111110010001010010000101100111110011001
C4(28位) = 0011001100101010101111111100
D4(28位) = 0101100110011110001111010101
K4(56位) = 00110011001010101011111111000101100110011110001111010101
K4’(48位) = 011100101010110111010110110110110011010100011101
C5(28位) = 1100110010101010111111110000
D5(28位) = 0110011001111000111101010101
K5(56位) = 11001100101010101111111100000110011001111000111101010101
K5’(48位) = 011111001110110000000111111010110101001110101000
C6(28位) = 0011001010101011111111000011
D6(28位) = 1001100111100011110101010101
K6(56位) = 00110010101010111111110000111001100111100011110101010101
K6’(48位) = 011000111010010100111110010100000111101100101111
C7(28位) = 1100101010101111111100001100
D7(28位) = 0110011110001111010101010110
K7(56位) = 11001010101011111111000011000110011110001111010101010110
K7’(48位) = 111011001000010010110111111101100001100010111100
C8(28位) = 0010101010111111110000110011
D8(28位) = 1001111000111101010101011001
K8(56位) = 00101010101111111100001100111001111000111101010101011001
K8’(48位) = 111101111000101000111010110000010011101111111011
C9(28位) = 0101010101111111100001100110
D9(28位) = 0011110001111010101010110011
K9(56位) = 01010101011111111000011001100011110001111010101010110011
K9’(48位) = 111000001101101111101011111011011110011110000001
C10(28位) = 0101010111111110000110011001
D10(28位) = 1111000111101010101011001100
K10(56位) = 01010101111111100001100110011111000111101010101011001100
K10’(48位) = 101100011111001101000111101110100100011001001111
C11(28位) = 0101011111111000011001100101
D11(28位) = 1100011110101010101100110011
K11(56位) = 01010111111110000110011001011100011110101010101100110011
K11’(48位) = 001000010101111111010011110111101101001110000110
C12(28位) = 0101111111100001100110010101
D12(28位) = 0001111010101010110011001111
K12(56位) = 01011111111000011001100101010001111010101010110011001111
K12’(48位) = 011101010111000111110101100101000110011111101001
C13(28位) = 0111111110000110011001010101
D13(28位) = 0111101010101011001100111100
K13(56位) = 01111111100001100110010101010111101010101011001100111100
K13’(48位) = 100101111100010111010001111110101011101001000001
C14(28位) = 1111111000011001100101010101
D14(28位) = 1110101010101100110011110001
K14(48位) = 11111110000110011001010101011110101010101100110011110001
K14’(48位) = 010111110100001110110111111100101110011100111010
C15(28位) = 1111100001100110010101010111
D15(28位) = 1010101010110011001111000111
K15(48位) = 11111000011001100101010101111010101010110011001111000111
K15’(48位) = 101111111001000110001101001111010011111100001010
C16(28位) = 1111000011001100101010101111
D16(28位) = 0101010101100110011110001111
K16(48位) = 11110000110011001010101011110101010101100110011110001111
K16’(48位) = 110010110011110110001011000011100001011111110101
这样我们就得到了 从K1’到K16’ 这16个子密钥了
3. 迭代过程
设Li(32位)和Ri(32位)为第i次迭代结果的左半部分与右半部分,子密钥Ki为第i轮的48位加密密钥。定义运算规则:
Li = Ri-1;
Ri = Li ⊕ f(Ri-1, Ki);
这个L和R在上面初始替换的最后出现过,分别是L0和R0,他们是64位明文矩阵M,经过IP转置表转置得到的新矩阵M’,再分组,前32位是L0,后32位是R0.
整个迭代过程如下图:
看不懂没关系,下面一点一点来
(1) 扩展置换E
右半部分 Ri 的位数为32位,而密钥长度 Ki 为48位,为了能够保证 Ri 与 Ki 可以进行异或运算需要对 Ri 位数进行扩展,用于扩展置换表E如下:
扩展置换表E:
例如我们之前得到的L0和R0:
- L0(32位):11111111101110000111011001010111
- R0(32位):00000000111111110000011010000011
我们通过扩展置换表E把R0进行扩展,得到E(R0)
- E(R0)(48位):100000000001011111111110100000001101010000000110
将 E(R0)(48位)与K1(48位)作异或运算(相同为0,不同为1)
得到:
- E(R0)^K1(48位) = 100110110001010100010001011111001010010001110100
(2) S盒替代
代替运算由8个不同的代替盒(S盒)完成。每个S盒有6位输入,4位输出。即将48位的E(R0)^K1输入,分为8个组,一组6个,第一组进入S1盒进行计算,第二组进入S2,第三组进入S3,一次类推,然后每个盒子最后会得出4位的结果,将8个盒子的结果拼在一起,就是32位输出
代替运算流程如下:
代替运算流程:

S盒的计算规则:
例如:
若S1盒的输入为110111,第一位与最后一位构成11,对应1yyyy1行
中间4位为1011对应x1011x。
查找S-盒1表的值为14,则S-盒1的输出为14的二进制,即1110。
通过这种规则,8个S盒将输入的48位数据输出为32位数据。
按照S-盒的计算过程,将
E(R0)^K1(48位)= 100110110001010100010001011111001010010001110100,分组,然后通过S盒替换得到的S盒输出为:E(R0)^K1_S(32位) = 10001011110001000110001011101010。
(3) P盒置换
将S盒替代的输出结果作为P盒置换的输入。P盒置换表如下:
所以,E(R0)^K1_S经过P盒置换后得到 E(R0)^K1_P(32位) = 01001000101111110101010110000001
(4) 函数概念
我们把上面的所有过程,即扩展置换E、S盒替代、P盒置换的过程作为函数f。
我们刚才是通过置换R0得到E(R0),然后将E(R0)与K1异或运算,得到E(R0)^K1,通过S盒得到E(R0)^K1_S,然后通过P盒得到E(R0)^K1_P = 01001000101111110101010110000001,所以我们这个函数f就是:f(R0, K1) = 01001000101111110101010110000001
接下来进行运算规则:
- L1(32位)= R0 = 00000000111111110000011010000011
- R1(32位)= L0 ^ f(R0, K1) = 10110111000001110010001111010110
然后再将R1和K2代入f函数,然后得到f(R1, K2),之后得到R2和L2,之后一直运行f函数,直到f(R15, K16),然后L16 = R15,R16 = L15 ^ f(R15, K16),这样就得到了R16和L16
- L16(32位)= 00110000100001001101101100101000
- R16(32位)= 10110001011001010011000000011000
4. 逆置换
将初始置换进行16次的迭代,即进行16层的加密变换,得到L16和R16,将此作为输入块,进行逆置换得到最终的密文输出块。
逆置换是初始置换的逆运算。
从初始置换规则中可以看到,原始数据的第1位置换到了第40位,第2位置换到了第8位。则逆置换就是将第40位置换到第1位,第8位置换到第2位。以此类推,逆置换规则表如下
逆置换过程图:
我们得到了L16和R16,把他们拼起来,得到
- M’’ = 0011000010000100110110110010100010110001011001010011000000011000
然后我们把M’’通过IP逆转置表转置,就可以得到密文
- 密文 = 0101100000001000001100000000101111001101110101100001100001101000