◆艾奇昆

?

DES算法解析

◆艾奇昆

（遼寧省信息中心 遼寧 110002）

從技術(shù)層面上說，密碼學(xué)始終是信息安全的一個核心技術(shù)，而對稱密碼體制中的DES算法一直以來都作為數(shù)據(jù)加密的標(biāo)準(zhǔn)，本文主要介紹DES算法流程的基本原理及加密過程，旨在用最通俗易懂的方式對該算法進行闡述，使廣大愛好者對DES算法能有更深入的了解。

DES；密鑰；異或

0 引言

DES（Data Encryption Standard）算法是世界上最常用的加密算法。在很長時間內(nèi)，許多人心目中“密碼生成”與DES一直是個同義詞。目前網(wǎng)絡(luò)上有許多介紹DES算法的文章，也有許多博客則直接給出晦澀難懂的源碼，缺乏解讀，讓人誤解；事實上，DES算法并不復(fù)雜，只是流程繁多而已。本文旨在用最通俗易懂的方式對該算法進行闡述，使廣大密碼學(xué)愛好者對DES算法流程能有更深入的了解。

1 DES歷史

DES全稱為Data Encryption Standard，即數(shù)據(jù)加密標(biāo)準(zhǔn)，是一種使用密鑰加密的算法，1973年5月，美國國家標(biāo)準(zhǔn)局下發(fā)了紅頭文件，征求加密算法來保護傳輸過程中的數(shù)據(jù)。國家標(biāo)準(zhǔn)局等了很久一直沒有人投標(biāo)，一直到1974年8月6日，IBM才拿出了自己開發(fā)的一套代號LUCIFER的標(biāo)準(zhǔn)。美國安全局評估后，在1977年7月15日采用了LUCIFER的一個變種作為數(shù)據(jù)加密標(biāo)準(zhǔn)DES。

DES很快被非數(shù)字媒體采用，比如電話線中的信號加密。在那些年里，國際香料組織IFF曾用DES來加密那些用電話線傳輸?shù)拿孛芘浞?。同時，作為政府之后第二大急需加密的銀行業(yè)也將DES作為廣泛應(yīng)用的標(biāo)準(zhǔn)。

2 DES算法工作原理

DES是一個基于組塊的加密算法，這意味著無論輸入還是輸出都是64位長度的。也就是說DES產(chǎn)生了一種最多264種的變換方法。每個64位的區(qū)塊被分為2個32位的部分，左半部分L和右半部分R（這種分割只在特定的操作中進行）。雖然DES算法輸入是64位長度，但是它的密鑰長度卻是56位。比如，取明文M = 0123456789ABCDEF這里的M是16進制的，將M寫成二進制（4位二進制數(shù)對應(yīng)1位十六進制數(shù)），我們得到一個64位的區(qū)塊：

M = 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111

L = 0000 0001 0010 0011 0100 0101 0110 0111

R = 1000 1001 1010 1011 1100 1101 1110 1111

DES使用56位的密鑰操作這個64位的區(qū)塊。密鑰實際上也是儲存為64位的，但每間隔的第8位都沒有被用上（也就是第8，16，24，32，40，48，56，和64位都沒有被用上）。但是，我們?nèi)匀辉诮酉聛淼倪\算中將密鑰標(biāo)記為從1到64位的64個比特。不過，你也許會看到，剛剛提到的這8個在創(chuàng)建子密鑰的時候會被忽略掉。

舉個例子，取十六進制密鑰K為：K = 133457799BBCDFF1

我們可以得到它的二進制形式（1為0001，3為0011.依次類推，并且將每八位寫成一組）：

2.1 創(chuàng)建48位子密鑰

這個64位的密鑰首先根據(jù)如下規(guī)定的PC-1表格（位數(shù)排列表）進行變換：

PC-1表

具體的變換規(guī)則為：將密鑰K轉(zhuǎn)換成的二進制數(shù)，按照位數(shù)對應(yīng)的PC-1表格順序重新排列，既第一個元素為57，那么原密鑰的第57位變換為新密鑰K+的第1位。同理，原密鑰的第49位變換為新密鑰的第2位……原密鑰的第4位變換為新密鑰的最后一位。注意原密鑰中只有56位會進入新密鑰，上表也只有56個元素。具體變換過程如下：

這樣就得到了56位的新密鑰，然后，將這個密鑰拆分為左右兩部分，C0和 D0，每半邊都有28位。如下所示：

C0= 1111000 0110011 0010101 0101111

D0= 0101010 1011001 1001111 0001111

對相同定義的C0和D0，我們現(xiàn)在創(chuàng)建16個塊Cn和 Dn，1<=n<=16。每一對Cn和Dn都是由前一對Cn-1和 Dn-1移位而來。具體說來，對于n = 1，2，…，16，在前一輪移位的結(jié)果上，使用如下表格進行二進制數(shù)的左移操作。左移操作的具體過程是指將除第一位外的所有位往左移一位，并將第一位移動至最后一位。

例如：對于CandD是CandD移位而來的，具體來說，通過2次左移位；CandD則是由CandD通過1次左移得到的。通過以上操作，我們就可以得到如下的CandD排列表：

C= 1111000011001100101010101111

D= 0101010101100110011110001111

C= 1110000110011001010101011111

D= 1010101011001100111100011110

C= 1100001100110010101010111111

D= 0101010110011001111000111101

C= 0000110011001010101011111111

D= 0101011001100111100011110101

C= 0011001100101010101111111100

D= 0101100110011110001111010101

C= 1100110010101010111111110000

D= 0110011001111000111101010101

C= 0011001010101011111111000011

D= 1001100111100011110101010101

C= 1100101010101111111100001100

D= 0110011110001111010101010110

C= 0010101010111111110000110011

D= 1001111000111101010101011001

C= 0101010101111111100001100110

D= 0011110001111010101010110011

C= 0101010111111110000110011001

D= 1111000111101010101011001100

C= 0101011111111000011001100101

D= 1100011110101010101100110011

C= 0101111111100001100110010101

D= 0001111010101010110011001111

C= 0111111110000110011001010101

D= 0111101010101011001100111100

C= 1111111000011001100101010101

D= 1110101010101100110011110001

C= 1111100001100110010101010111

D= 1010101010110011001111000111

C= 1111000011001100101010101111

D= 0101010101100110011110001111

接下來，我們還需要按照表PC-2將變換得到Cn和 Dn轉(zhuǎn)變成新密鑰Kn（1<=<=16）：

PC-2表

原來每對子密鑰有56位，但按照PC-2表變成僅僅使用其中的48位。于是，第n輪的新密鑰Kn 的第1位來自組合子密鑰CnDn的第14位，第2位來自第17位，依次類推，知道新密鑰的第48位來自組合密鑰的第32位，比如，對于第1輪的組合密鑰C1D1= 1110000 1100110 0101010 1011111 1010101 0110011 0011110 0011110通過PC-2表變換后：

得到：

K1=000110 110000 001011 101111 111111 000111 000001 110010，按照以上的組合規(guī)律，依次組合得到：

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 加密每個數(shù)據(jù)的64位區(qū)塊

對于明文數(shù)據(jù)M，我們還要計算一個初始變換IP（）。IP是重新變換數(shù)據(jù)M的每一位產(chǎn)生的。產(chǎn)生過程由以下IP表決定：

這里M的第58位是1，變成了IP的第1位。M的第50位是1，變成了IP的第2位。M的第7位是0，變成了IP的最后一位。例如對于明文M=0123456789ABCDEF，經(jīng)過如下變換后結(jié)果IP為：

IP = 1100 1100 0000 0000 1100 1100 1111 1111 1111 0000 1010 1010 1111 0000 1010 1010，接著將變換得到的IP分為32位的左半邊L0和32位的右半邊R0，對于上例，我們得到：

IP = 1100 1100 0000 0000 1100 1100 1111 11111111 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

接著我們還需執(zhí)行16輪迭代，對1<=<=16，使用一個函數(shù)f。函數(shù)f輸入兩個區(qū)塊：一個32位的數(shù)據(jù)區(qū)塊和一個48位的密鑰區(qū)塊K，輸出一個32位的區(qū)塊。定義+表示異或（XOR）。那么讓n從1循環(huán)到16，我們計算：

LR

RLRK

這樣我們就得到最終區(qū)塊，也就是n=16的L16R16。具體說這個過程就是，我們拿前一個迭代的結(jié)果的右邊32位作為當(dāng)前迭代的左邊32位。對于當(dāng)前迭代的右邊32位，將它和上一個迭代的f函數(shù)的輸出執(zhí)行異或（XOR）運算。剩下的就是f函數(shù)是如何工作的了。為了計算f，我們首先拓展每個Rn-1，將其從32位拓展到48位。這是通過使用一張表來重復(fù)Rn-1中的一些位來實現(xiàn)的。我們稱這個過程為函數(shù)E。也就是說函數(shù)E（Rn-1）輸入32位輸出48位。

定義E為函數(shù)E的輸出，將其寫成8組，每組6位。這些比特是通過選擇輸入的某些位來產(chǎn)生的，具體選擇順序按下表實現(xiàn)：

也就是說E（Rn-1）開頭的三個比特分別來自Rn-1的第32、1和2位。E（Rn-1）末尾的2個比特分別來自Rn-1的第32位和第1位。比如，給定R0，我們可以計算出E（R0），具體過程如下：

接著在f函數(shù)中，我們對輸出E（Rn-1）和密鑰執(zhí)行XOR運算：Kn+E（Rn-1），二進制數(shù)的XOR（⊕）運算規(guī)則為：兩個二進制數(shù)進行異或運算，相同的則為0，不同的則為1，比如，對K1，E（R0），我們有：

到這里我們還沒有完成f函數(shù)的運算，我們僅僅使用一張表將Rn-1從32位拓展為48位，并且對這個結(jié)果和密鑰Kn執(zhí)行了異或運算。我們現(xiàn)在有了48位的結(jié)果，或者說8組6比特數(shù)據(jù)。我們現(xiàn)在還要對每組的6比特執(zhí)行一些特殊的操作：我們將它作為一張被稱為“S盒”的表格的地址。每組6比特都將給我們一個位于不同S盒中的地址。在那個地址里存放著一個4比特的數(shù)字。這個4比特的數(shù)字將會替換掉原來的6個比特。最終結(jié)果就是，8組6比特的數(shù)據(jù)被轉(zhuǎn)換為8組4比特（一共32位）的數(shù)據(jù)。將上一步的48位的結(jié)果寫成如下形式：Kn+E（Rn-1）B1B2B3B4B5B6B7B8每個B都是一個6比特的分組，我們現(xiàn)在計算S1（B1）S2（B2）S3（B3）S4（B4）S5（B5）S6（B6）S7（B7）S8（B8），其中，SB指的是第i個S盒的輸出。為了計算每個函數(shù)SSS，取一個6位的區(qū)塊作為輸入，輸出一個4位的區(qū)塊。例如決定S的表格如下：

如果S是定義在這張表上的函數(shù)，B是一個6位的塊，那么計算S的方法是：B的第一位和最后一位組合起來的二進制數(shù)決定一個介于0和3之間的十進制數(shù)（或者二進制00到11之間）。設(shè)這個數(shù)為i。B的中間4位二進制數(shù)代表一個介于0到15之間的十進制數(shù)（二進制0000到1111）。設(shè)這個數(shù)為j。查表找到第i行第j列的那個數(shù)，這是一個介于0和15之間的數(shù)，并且它是能由一個唯一的4位區(qū)塊表示的。這個區(qū)塊就是函數(shù)S輸入得到的輸出S。比如，對輸入第一位是0，最后一位是1，決定了行號是01，也就是十進制的1 。中間4位是1101，也就是十進制的13，所以列號是13。查表第1行第13列我們得到數(shù)字5。這決定了輸出；5是二進制0101，所以輸出就是0101。也即S（011011）= 0101，同理，定義其余函數(shù)SS的表格如下所示：

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

例如：對于第一輪，我們得到這8個S盒的輸出：

K+（R）= 011000 010001 011110 111010 100001 100110 010100 100111

SBSBSBSBSBSBSBSB= 0101 1100 1000 0010 1011 0101 1001 0111

函數(shù)f的最后一步就是對S盒的輸出進行一個變換來產(chǎn)生最終值：=（SBSB…SB）。

變換P由如下表格定義：

P輸入32位數(shù)據(jù)，通過變換產(chǎn)生32位輸出，比如，對于8個S盒的輸出：

SBSBSBSBSBSBSBSB= 0101 1100 1000 0010 1011 0101 1001 0111具體變換過程如下：

圖5 變換過程圖

最終，我們得到= 0010 0011 0100 1010 1010 1001 1011 1011，那么，R=L+RK，即再執(zhí)行異或+（XOR）操作：

1100 1100 0000 0000 1100 1100 1111 1111 + 0010 0011 0100 1010 1010 1001 1011 1011 = 1110 1111 0100 1010 0110 0101 0100 0100

在下一輪迭代中，我們的L=R，這就是我們剛剛計算的結(jié)果。之后我們必須計算R=L RK，一直完成16個迭代。在第16個迭代之后，我們有了區(qū)塊LandR。接著我們逆轉(zhuǎn)兩個區(qū)塊的順序得到一個64位的區(qū)塊：RL然后對其執(zhí)行一個最終的變換IP，其定義如下表所示：

也就是說，該變換的輸出的第1位是輸入的第40位，第2位是輸入的第8位，一直到將輸入的第25位作為輸出的最后一位，比如，如果我們使用了上述方法得到了第16輪的左右兩個區(qū)塊：

L16= 0100 0011 0100 0010 0011 0010 0011 0100

R16= 0000 1010 0100 1100 1101 1001 1001 0101

我們將這兩個區(qū)塊調(diào)換位置，然后執(zhí)行最終變換：R16L16= 00001010 01001100 11011001 10010101 01000011 01000010 00110010 00110100，再按照IP-1執(zhí)行最終的變換，具體變換過程如下：

寫成16進制得到：85E813540F0AB405，這就是明文M = 0123456789ABCDEF的加密密文C = 85E813540F0AB405，至此整個DES加密過程結(jié)束。

3 結(jié)束語

最后再補充3DES加密算法的相關(guān)知識，它是DES加密算法的一種模式，它使用3條64位的密鑰對數(shù)據(jù)進行三次加密。3DES是DES的一個更安全的變形。它是以DES為基本模塊，通過組合分組方法設(shè)計出的更為安全的分組加密算法。

目前，在中國尤其是金卡工程的全面啟動，DES算法在POS、ATM、磁卡及智能卡（IC卡）、加油站、高速公路收費站等領(lǐng)域被廣泛應(yīng)用，以此來實現(xiàn)關(guān)鍵數(shù)據(jù)的保密。信用卡持卡人的PIN的加密傳輸，IC卡與POS間的雙向認證、金融交易數(shù)據(jù)包的MAC校驗等，均用到DES算法。

[1]（美）帕爾，（美）佩爾茨爾著，馬小婷譯.深入淺出密碼學(xué)—常用加密技術(shù)原理與應(yīng)用[M].北京：清華大學(xué)出版社，2012.

[2]羅守山等編著.密碼學(xué)與信息安全技術(shù)[M].北京：北京郵電大學(xué)出版社，2009.

[3]張文政，陳克非，趙偉.密碼學(xué)的基本理論與技術(shù)[M].北京：國防工業(yè)出版社，2015.