目录
一、DES简介
二、DES算法入参
三、DES加密算法步骤解析
1. IP置换(M -> M0)
2. 密钥K控制的16轮运算(M0,K1~K16 -> M16)
2.1. 子密钥Kn的计算
——2.1.1 PC-1置换
——2.1.2 循环左移运算
——2.1.3 PC-2置换
2.2. 轮运算
——2.2.1 扩展置换E
——2.2.2 异或Kn
——2.2.3 S盒转换
——2.2.4 P盒置换
——2.2.5 异或运算
——2.2.6 2-16轮运算
3. 交换左右32位(M16 -> M16')
4. IP-1逆置换(M16' -> M')
一、DES简介
DES算法为密码体制中的对称密码体制,又被称为美国数据加密标准,是1972年美国IBM公司研制的对称密码体制加密算法。加密和解密使用相同的密钥。
明文按64位进行分组,密钥长64位,密钥事实上是56位参与DES运算(第8、16、24、32、40、48、56、64位是校验位, 使得每个密钥都有奇数个1),分组后的明文组和56位的密钥按位替代或交换的方法形成密文组的加密方法。
二、DES算法入参
- data:要加密数据/被解密的数据,8字节64位。不足64位补足64位。
- key:密钥,64位中56位参与DES运算(第8、16、24、32、40、48、56、64位是校验位, 使得每个密钥都有奇数个1)。
- mode:加密 or 解密。
三、DES加密算法步骤解析
加密步骤:
- 64位明文M
- —— 1.(IP置换)
- —— 2.(密钥K控制的16轮迭代运算)
- —— 3.(交换左右32位)
- —— 4.(IP-1逆置换)
- 64位密文M'
其中56位密钥K会被处理,最终输出16个48位子密钥参与到16轮迭代运算中。
// 明文M(16进制和2进制)64位
M = 0123456789ABCDEF
M = 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
// 密钥K(16进制和2进制)64位
K = 133457799BBCDFF1
K = 00010011 00110100 01010111 01111001 10011011 10111100 11011111 11110001
// 去除校验位的密钥 56位
K = 00010011 00110100 01010111 01111001 10011011 10111100 11011111 11110001
1. IP置换(M -> M0)
描述:64位明文M,经过IP置换获得M0。
IP置换表如下所示:
IP置换表 |
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 |
这里的 IP 置换是将 64 bit 明文 M 的位重新排序,得到新的数据 M0。例如将 M 的 58 位放在第 1 位,将 M 的 50 位放在第 2 位,以此类推,M 的第 7 位 放到第 64 位 ,得到置换后的 M0。
M = 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
M0 = IP(M)
= 1100 1100 0000 0000 1100 1100 1111 1111 1111 0000 1010 1010 1111 0000 1010 1010
2. 密钥K控制的16轮运算(M0,K1~K16 -> M16)
描述:轮运算的输入为M0、K1-K16;输出为M16。
- 第1轮运算,输入M0、K1,得到M1。
- 第2轮运算,输入M1、K2,得到M2。
- 第16轮运算,输入M15、K16,最终得到M16。
可以分为两步进行,先根据K计算子密钥K1~K16,再根据M0以及K1~K16,计算16轮运算结果M16。
2.1. 子密钥Kn的计算
描述:先将64位密钥去除8个奇偶校验位,得到实际使用的56位密钥K(56bit),再经过运算得到子密钥K1~K16(48bit)。
- 首先对K(56bit)进行PC-1置换,得到新K(56bit)。
- K(56bit)分为左右28bit C0和D0,分别进行循环左移运算得到C1和D1;之后将数据C1 D1合并,再进行PC-2置换,得到K1。
- 在C1和D1的基础上进行第二次循环左移运算,之后将数据合并,再进行PC-2置换,得到K2。
- 以此类推,得到 K16。
①:PC-1置换,内容详见2.1.1
②:循环左移表R(n),内容详见2.1.2
③:PC-2置换,内容详见2.1.3
——2.1.1 PC-1置换
PC-1置换表如下所示:
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 |
PC-1置换也是位置换,将原K的57位放在第一位,将K的第4位放在最后一位。
密钥 64位
K = 00010011 00110100 01010111 01111001 10011011 10111100 11011111 11110001
56位原密钥(去除校验位)
K = 00010011 00110100 01010111 01111001 10011011 10111100 11011111 11110001
新密钥
PC-1(K) = 1111000 0110011 0010101 0101111 0101010 1011001 1001111 0001111
将新密钥分为左右两组
C0 = 1111000 0110011 0010101 0101111
D0 = 0101010 1011001 1001111 0001111
——2.1.2 循环左移运算
循环左移表R(n)如下所示,n表示第几次循环左移,循环左移是会将左移后的数字补在末尾。
循环左移表 |
轮数 n |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
位数 R(n) |
1 |
1 |
2 |
2 |
2 |
2 |
2 |
2 |
1 |
2 |
2 |
2 |
2 |
2 |
2 |
1 |
可以看出第一轮循环左移1位(补在末尾),即C1=C0<<1,第二轮C2=C1<<1,以此类推
C0 = 1111000011001100101010101111
C1 = C0<<1 = 1110000110011001010101011111
C2 = C1<<1 = 1100001100110010101010111111
C3 = C2<<2 = 0000110011001010101011111111
得到 C0-C16,D0-D16
C0 = 1111000011001100101010101111
D0 = 0101010101100110011110001111
C1 = 1110000110011001010101011111
D1 = 1010101011001100111100011110
C2 = 1100001100110010101010111111
D2 = 0101010110011001111000111101
C3 = 0000110011001010101011111111
D3 = 0101011001100111100011110101
C4 = 0011001100101010101111111100
D4 = 0101100110011110001111010101
C5 = 1100110010101010111111110000
D5 = 0110011001111000111101010101
C6 = 0011001010101011111111000011
D6 = 1001100111100011110101010101
C7 = 1100101010101111111100001100
D7 = 0110011110001111010101010110
C8 = 0010101010111111110000110011
D8 = 1001111000111101010101011001
C9 = 0101010101111111100001100110
D9 = 0011110001111010101010110011
C10 = 0101010111111110000110011001
D10 = 1111000111101010101011001100
C11 = 0101011111111000011001100101
D11 = 1100011110101010101100110011
C12 = 0101111111100001100110010101
D12 = 0001111010101010110011001111
C13 = 0111111110000110011001010101
D13 = 0111101010101011001100111100
C14 = 1111111000011001100101010101
D14 = 1110101010101100110011110001
C15 = 1111100001100110010101010111
D15 = 1010101010110011001111000111
C16 = 1111000011001100101010101111
D16 = 0101010101100110011110001111
——2.1.3 PC-2置换
PC-2置换表如下所示:
PC-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 |
这步,根据 Cn和 Dn 获取 Kn(K1-K16),第n轮的新秘钥Kn 的第1位来自组合子秘钥CnDn的第14位,第2位来自第17位,依次类推,新秘钥的第48位来自组合秘钥的第32位。
C1D1 = 1110000 1100110 0101010 1011111 1010101 0110011 0011110 0011110
K1 = PC-2(C1D1)
= 000110 110000 001011 101111 111111 000111 000001 110010
依次计算
K2 = 011110 011010 111011 011001 110110 111100 100111 100101
K3 = 010101 011111 110010 001010 010000 101100 111110 011001
K4 = 011100 101010 110111 010110 110110 110011 010100 011101
K5 = 011111 001110 110000 000111 111010 110101 001110 101000
K6 = 011000 111010 010100 111110 010100 000111 101100 101111
K7 = 111011 001000 010010 110111 111101 100001 100010 111100
K8 = 111101 111000 101000 111010 110000 010011 101111 111011
K9 = 111000 001101 101111 101011 111011 011110 011110 000001
K10 = 101100 011111 001101 000111 101110 100100 011001 001111
K11 = 001000 010101 111111 010011 110111 101101 001110 000110
K12 = 011101 010111 000111 110101 100101 000110 011111 101001
K13 = 100101 111100 010111 010001 111110 101011 101001 000001
K14 = 010111 110100 001110 110111 111100 101110 011100 111010
K15 = 101111 111001 000110 001101 001111 010011 111100 001010
K16 = 110010 110011 110110 001011 000011 100001 011111 110101
2.2. 轮运算
根据M0(L0R0)以及K1~K16,计算16轮运算结果M16(L16R16)。
64bit M0 拆为左右32bit,分别写作L0和R0。第1轮运算如下所示,第2-16轮运算带入上一轮运算结果。
第n轮运算结果为:Mn = LnRn
所以可得计算公式:
将经过IP置换的明文分为左右两组
M0 = IP(M)
= 1100 1100 0000 0000 1100 1100 1111 1111 1111 0000 1010 1010 1111 0000 1010 1010
L0 = 1100 1100 0000 0000 1100 1100 1111 1111
R0 = 1111 0000 1010 1010 1111 0000 1010 1010
——2.2.1 扩展置换E
扩展置换E如下所示:
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 |
这样,R0`= E(R0), Rn`=E(Rn-1)
R0`= E(R0) = 011110 100001 010101 010101 011110 100001 010101 010101
——2.2.2 异或Kn
48bit数据 异或 48bit子密钥, Rn`` = Kn 异或 E(Rn-1)
K1 = 000110 110000 001011 101111 111111 000111 000001 110010
R0`` = K1+E(R0) = 011000 010001 011110 111010 100001 100110 010100 100111
——2.2.3 S盒转换
对上述结果进行S盒转换(48bit --> 32bit), Rn``` = S( Rn`` ) = S( Kn 异或 E(Rn-1) )
R0``` = S(R0``) = S( K1+E(R0) )
将 R0`` 分为8个6bit的块,分别进行S盒转换(共有8个S盒)
R0``` = S(011000 010001 011110 111010 100001 100110 010100 100111)
= S(B1 B2 B3 B4 B5 B6 B7 B8 )
= S1(B1)S2(B2)S3(B3)S4(B4)S5(B5)S6(B6)S7(B7)S8(B8)
R0``` = S(R0``)
= S1(B1-0)S2(B2-0)S3(B3-0)S4(B4-0)S5(B5-0)S6(B6-0)S7(B7-0)S8(B8-0)
R1``` = S(R1``)
= S1(B1-1)S2(B2-1)S3(B3-1)S4(B4-1)S5(B5-1)S6(B6-1)S7(B7-1)S8(B8-1)
...
R15``` = S(R15``)
= S1(B1-15)S2(B2-15)S3(B3-15)S4(B4-15)S5(B5-15)S6(B6-15)S7(B7-15)S8(B8-15)
其中 B1-0、B1-15 中的0和16表示 1-16 轮,0表示第1轮,15表示第16轮
B1-0, 第 1轮 R0`` 拆开的6bit
B1-16,第16轮 R15`` 拆开的6bit
S盒如下所示:48bit 转 32bit
如果S1是定义在这张表上的函数,B是一个6位的块,那么计算S1(B) 的方法是:B的第一位和最后一位组合起来的二进制数决定一个介于0和3之间的十进制数(或者二进制00到11之间)。设这个数为i。B的中间4位二进制数代表一个介于0到15之间的十进制数(二进制0000到1111)。设这个数为j。查表找到第i行第j列的那个数,这是一个介于0和15之间的数,并且它是能由一个唯一的4位区块表示的。这个区块就是函数S1 输入B得到的输出S1(B)。比如,对输入B = 011011 ,第一位是0,最后一位是1,决定了行号是01,也就是十进制的1 。中间4位是1101,也就是十进制的13,所以列号是13。查表第1行第13列我们得到数字5。这决定了输出;5是二进制0101,所以输出就是0101。也即S1(011011) = 0101。
同理,定义这8个函数S1,…,S8的表格如下所示:
S1 |
14 |
4 |
13 |
1 |
2 |
15 |
11 |
8 |
3 |
10 |
6 |
12 |
5 |
9 |
0 |
7 |
0 |
15 |
7 |
4 |
14 |
2 |
13 |
1 |
10 |
6 |
12 |
11 |
9 |
5 |
3 |
8 |
4 |
1 |
14 |
8 |
13 |
6 |
2 |
11 |
15 |
12 |
9 |
7 |
3 |
10 |
5 |
0 |
15 |
12 |
8 |
2 |
4 |
9 |
1 |
7 |
5 |
11 |
3 |
14 |
10 |
0 |
6 |
13 |
S2 |
15 |
1 |
8 |
14 |
6 |
11 |
3 |
4 |
9 |
7 |
2 |
13 |
12 |
0 |
5 |
10 |
3 |
13 |
4 |
7 |
15 |
2 |
8 |
14 |
12 |
0 |
1 |
10 |
6 |
9 |
11 |
5 |
0 |
14 |
7 |
11 |
10 |
4 |
13 |
1 |
5 |
8 |
12 |
6 |
9 |
3 |
2 |
15 |
13 |
8 |
10 |
1 |
3 |
15 |
4 |
2 |
11 |
6 |
7 |
12 |
0 |
5 |
14 |
9 |
S3 |
10 |
0 |
9 |
14 |
6 |
3 |
15 |
5 |
1 |
13 |
12 |
7 |
11 |
4 |
2 |
8 |
13 |
7 |
0 |
9 |
3 |
4 |
6 |
10 |
2 |
8 |
5 |
14 |
12 |
11 |
15 |
1 |
13 |
6 |
4 |
9 |
8 |
15 |
3 |
0 |
11 |
1 |
2 |
12 |
5 |
10 |
14 |
7 |
1 |
10 |
13 |
0 |
6 |
9 |
8 |
7 |
4 |
15 |
14 |
3 |
11 |
5 |
2 |
12 |
S4 |
7 |
13 |
14 |
3 |
0 |
6 |
9 |
10 |
1 |
2 |
8 |
5 |
11 |
12 |
4 |
15 |
13 |
8 |
11 |
5 |
6 |
15 |
0 |
3 |
4 |
7 |
2 |
12 |
1 |
10 |
14 |
9 |
10 |
6 |
9 |
0 |
12 |
11 |
7 |
13 |
15 |
1 |
3 |
14 |
5 |
2 |
8 |
4 |
3 |
15 |
0 |
6 |
10 |
1 |
13 |
8 |
9 |
4 |
5 |
11 |
12 |
7 |
2 |
14 |
S5 |
2 |
12 |
4 |
1 |
7 |
10 |
11 |
6 |
8 |
5 |
3 |
15 |
13 |
0 |
14 |
9 |
14 |
11 |
2 |
12 |
4 |
7 |
13 |
1 |
5 |
0 |
15 |
10 |
3 |
9 |
8 |
6 |
4 |
2 |
1 |
11 |
10 |
13 |
7 |
8 |
15 |
9 |
12 |
5 |
6 |
3 |
0 |
14 |
11 |
8 |
12 |
7 |
1 |
14 |
2 |
13 |
6 |
15 |
0 |
9 |
10 |
4 |
5 |
3 |
S6 |
12 |
1 |
10 |
15 |
9 |
2 |
6 |
8 |
0 |
13 |
3 |
4 |
14 |
7 |
5 |
11 |
10 |
15 |
4 |
2 |
7 |
12 |
9 |
5 |
6 |
1 |
13 |
14 |
0 |
11 |
3 |
8 |
9 |
14 |
15 |
5 |
2 |
8 |
12 |
3 |
7 |
0 |
4 |
10 |
1 |
13 |
11 |
6 |
4 |
3 |
2 |
12 |
9 |
5 |
15 |
10 |
11 |
14 |
1 |
7 |
6 |
0 |
8 |
13 |
S7 |
4 |
11 |
2 |
14 |
15 |
0 |
8 |
13 |
3 |
12 |
9 |
7 |
5 |
10 |
6 |
1 |
13 |
0 |
11 |
7 |
4 |
9 |
1 |
10 |
14 |
3 |
5 |
12 |
2 |
15 |
8 |
6 |
1 |
4 |
11 |
13 |
12 |
3 |
7 |
14 |
10 |
15 |
6 |
8 |
0 |
5 |
9 |
2 |
6 |
11 |
13 |
8 |
1 |
4 |
10 |
7 |
9 |
5 |
0 |
15 |
14 |
2 |
3 |
12 |
S8 |
13 |
2 |
8 |
4 |
6 |
15 |
11 |
1 |
10 |
9 |
3 |
14 |
5 |
0 |
12 |
7 |
1 |
15 |
13 |
8 |
10 |
3 |
7 |
4 |
12 |
5 |
6 |
11 |
0 |
14 |
9 |
2 |
7 |
11 |
4 |
1 |
9 |
12 |
14 |
2 |
0 |
6 |
10 |
13 |
15 |
3 |
5 |
8 |
2 |
1 |
14 |
7 |
4 |
10 |
8 |
13 |
15 |
12 |
9 |
0 |
3 |
5 |
6 |
11 |
所以第一轮的S和输出就是
将 R0`` 分为8个6bit的块,分别进行S盒转换(共有8个S盒)
R0``` = S(R0``)
= S(011000 010001 011110 111010 100001 100110 010100 100111)
= S(B1 B2 B3 B4 B5 B6 B7 B8 )
= S1(B1)S2(B2)S3(B3)S4(B4)S5(B5)S6(B6)S7(B7)S8(B8)
第一轮中:
R0``` = S(R0``)
= S1(B1-0)S2(B2-0)S3(B3-0)S4(B4-0)S5(B5-0)S6(B6-0)S7(B7-0)S8(B8-0)
= 0101 1100 1000 0010 1011 0101 1001 0111
——2.2.4 P盒置换
P盒如下所示,置换后产生 32bit 输出:Rn```` = P( Rn``` )
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 |
第一轮中:
R0``` = S(R0``)
= S1(B1-0)S2(B2-0)S3(B3-0)S4(B4-0)S5(B5-0)S6(B6-0)S7(B7-0)S8(B8-0)
R0``` = 0101 1100 1000 0010 1011 0101 1001 0111
R0```` = P(R0```)
= 1110 1111 0100 1010 0110 0101 0100 0100
——2.2.5 异或运算
R1 = R0```` 异或 L0, Rn= (Rn-1```` 异或 Ln-1)
L0 = 1100 1100 0000 0000 1100 1100 1111 1111
R0```` = 0010 0011 0100 1010 1010 1001 1011 1011
R1 = L0 异或 R0````
= 1100 1100 0000 0000 1100 1100 1111 1111
(异或)+ 0010 0011 0100 1010 1010 1001 1011 1011
= 1110 1111 0100 1010 0110 0101 0100 0100
即 R1 = 1110 1111 0100 1010 0110 0101 0100 0100
L1=R0, Ln = Rn-1
L1 = R0
= 1111 0000 1010 1010 1111 0000 1010 1010
——2.2.6 2-16轮运算
直到2.2.6,才进行完第一次轮运算,按照公式
Ln = Rn-1 ;Rn= (Rn-1```` 异或 Ln-1);
L2 = R1,R2 = L1 异或 P(S(E(R1)异或K2))。
可以依次计算,得到 L16 R16,即 M16:
L16 = 0100 0011 0100 0010 0011 0010 0011 0100
R16 = 0000 1010 0100 1100 1101 1001 1001 0101
M16 = L16R16
3. 交换左右32位(M16 -> M16')
描述:将16轮运算结果 M16 进行左右32bit交换。
(L16)(R16) -> (R16)(L16)
L16 = 0100 0011 0100 0010 0011 0010 0011 0100
R16 = 0000 1010 0100 1100 1101 1001 1001 0101
M16 = L16R16
M16` = R16L16 = 00001010 01001100 11011001 10010101 01000011 01000010 00110010 00110100
4. IP-1逆置换(M16' -> M')
描述:将M16'进行IP-1逆置换,得到最终加密数据M',M'也是64bit。
IP-1表如下所示:
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 |
IP-1 置换同理,将 M16` 的第40位作为第1位,将 M16` 的第25位作为最后一位。
M' = IP-1 (M16')
M16` = R16L16 = 00001010 01001100 11011001 10010101 01000011 01000010 00110010 00110100
M' = IP-1 (M16')
= 10000101 11101000 00010011 01010100 00001111 00001010 10110100 00000101
再转换为16进制:
M' = 85E813540F0AB405