本文主要介紹了DES算法的步驟,包括IP置換、密鑰置換、E擴展置換、S盒代替、P盒置換和末置換。
DES算法為密碼體制中的對稱密碼體制,又被稱為美國數據加密標准。
DES是一個分組加密算法,典型的DES以64位為分組對數據加密,加密和解密用的是同一個算法。
密鑰長64位,密鑰事實上是56位參與DES運算(第8、16、24、32、40、48、56、64位是校驗位,使得每個密鑰都有奇數個1),分組後的明文組和56位的密鑰按位替代或交換的方法形成密文組。
DES算法的主要流程如下圖所示,本文按照流程依次介紹每個模塊。
IP置換目的是將輸入的64位數據塊按位重新組合,並把輸出分為L0、R0兩部分,每部分各長32位。
置換規則如下表所示:
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
表中的數字代表原數據中此位置的數據在新數據中的位置,即原數據塊的第1位放到新數據的第58位,第2位放到第50位,……依此類推,第64位放到第7位。置換後的數據分為L0和R0兩部分,L0為新數據的左32位,R0為新數據的右32位。
設轉換前的數據位D1D2D3…D64,則IP置換後的結果為L0=D58D50…D8,R0=D57D49…D7。0x0000 0080 0000 0002轉換後的結果為0x0002 0000 0000 0001,且L0=0x0002 0000,R0=0x0000 0001。置換步驟如下:
原數據第33位為1,置換表第33位為64,因此將1放到新數據的第64位;原數據第63位為1,置換表第63位為7,因此將1放到新數據的第7位;其余值為0的位按此置換。要注意一點,位數是從左邊開始數的,即最0x0000 0080 0000 0002最左邊的位為1,最右邊的位為64。
不考慮每個字節的第8位,DES的密鑰由64位減至56位,每個字節的第8位作為奇偶校驗位。產生的56位密鑰由下表生成(注意表中沒有8,16,24,32,40,48,56和64這8位):
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
在DES的每一輪中,從56位密鑰產生出不同的48位子密鑰,確定這些子密鑰的方式如下:
1).將56位的密鑰分成兩部分,每部分28位。
2).根據輪數,這兩部分分別循環左移1位或2位。每輪移動的位數如下表:
輪數
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
位數
1
1
2
2
2
2
2
2
1
2
2
2
2
2
2
1
移動後,從56位中選出48位。這個過程中,既置換了每位的順序,又選擇了子密鑰,因此稱為壓縮置換。壓縮置換規則如下表(注意表中沒有9,18,22,25,35,38,43和54這8位):
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
置換方法同上,此處省略。
擴展置置換目標是IP置換後獲得的右半部分R0,將32位輸入擴展為48位(分為4位×8組)輸出。
擴展置換目的有兩個:生成與密鑰相同長度的數據以進行異或運算;提供更��的結果,在後續的替代運算中可以進行壓縮。
擴展置換原理如下表:
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
表中的數字代表位,兩列黃色數據是擴展的數據,可以看出,擴展的數據是從相鄰兩組分別取靠近的一位,4位變為6位。靠近32位的位為1,靠近1位的位為32。表中第二行的4取自上組中的末位,9取自下組中的首位。
我們舉個例子看一下(雖然擴展置換針對的是上步IP置換中的R0,但為便於觀察擴展,這裡不取R0舉例):
輸入數據0x1081 1001,轉換為二進制就是0001 0000 1000 0001B,按照上表擴展得下表
1
0
0
0
1
0
1
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
1
0
1
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
表中的黃色數據是從臨近的上下組取得的,二進制為1000 1010 0001 0100 0000 0010 1000 1010 0000 0000 0000 0010B,轉換為十六進制0x8A14 028A 0002。
擴展置換之後,右半部分數據R0變為48位,與密鑰置換得到的輪密鑰進行異或。
壓縮後的密鑰與擴展分組異或以後得到48位的數據,將這個數據送人S盒,進行替代運算。替代由8個不同的S盒完成,每個S盒有6位輸入4位輸出。48位輸入分為8個6位的分組,一個分組對應一個S盒,對應的S盒對各組進行代替操作。
一個S盒就是一個4行16列的表,盒中的每一項都是一個4位的數。S盒的6個輸入確定了其對應的輸出在哪一行哪一列,輸入的高低兩位做為行數H,中間四位做為列數L,在S-BOX中查找第H行L列對應的數據(<32)。
8個S盒如下:
S盒1
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
S盒2
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
S盒3
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
S盒4
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
19
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
S盒5
2
12
4
1
7
10
11
6
5
8
3
15
13
0
14
9
14
11
2
12
4
7
13
1
5
0
15
13
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
S盒6
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
S盒7
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
S盒8
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盒8的輸入為110011,第1位和第6位組合為11,對應於S盒8的第3行;第2位到第5位為1001,對應於S盒8的第9列。S盒8的第3行第9列的數字為12,因此用1100來代替110011。注意,S盒的行列計數都是從0開始。
代替過程產生8個4位的分組,組合在一起形成32位數據。
S盒代替時DES算法的關鍵步驟,所有的其他的運算都是線性的,易於分析,而S盒是非線性的,相比於其他步驟,提供了更好安全性。
S盒代替運算的32位輸出按照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
9
13
30
6
22
11
4
25
表中的數字代表原數據中此位置的數據在新數據中的位置,即原數據塊的第16位放到新數據的第1位,第7位放到第2位,……依此類推,第25位放到第32位。
例如0x10A1 0001進行P盒置換後變為0x8000 0886。
0x10A1 0001表現為表的形式(第一位位於左上角)原來為
0
0
0
1
0
0
0
0
1
0
1
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
經P盒變換後為
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
1
1
0
即1000 0000 0000 0000 0000 1000 1000 0110B,十六進制為0x8000 0886。
最後,P盒置換的結果與最初的64位分組左半部分L0異或,然後左、右半部分交換,接著開始另一輪。
末置換是初始置換的逆過程,DES最後一輪後,左、右兩半部分並未進行交換,而是兩部分合並形成一個分組做為末置換的輸入。末置換規則如下表:
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
置換方法同上,此處省略。
經過以上步驟,就可以得到密文了。