DES算法詳細(xì)介紹

1、精選文檔1973年5月15日，美國國家標(biāo)準(zhǔn)局（現(xiàn)在美國國家標(biāo)準(zhǔn)技術(shù)研究所（NIST）在聯(lián)邦注冊(cè)報(bào)上發(fā)表一則啟事，公開征集用來保護(hù)傳輸和靜止存儲(chǔ)中的計(jì)算機(jī)數(shù)據(jù)的密碼算法，這一舉措最終導(dǎo)致了數(shù)據(jù)加密標(biāo)準(zhǔn)DES的出現(xiàn)。DES采用分組乘積密碼體制，它是由IBM開發(fā)，是對(duì)早期被稱為Lucifer 密碼體制的改進(jìn)。DES在1975年3月17日首次在聯(lián)邦記錄中公布，而且聲明對(duì)比算法征求意見。到1977年2月15日擬議中的DES被采納為“非密級(jí)”應(yīng)用的一個(gè)聯(lián)邦標(biāo)準(zhǔn)。最初預(yù)期DES作為一個(gè)標(biāo)準(zhǔn)只能使用1015年，然而，出于種種原因，可能是DES還沒有受到嚴(yán)重的威脅，事實(shí)證明了DES要長壽得多。在其被采用后，大約

2、每隔5年被評(píng)審一次。DES的最后一次評(píng)審是在1999年1月。但是，隨著計(jì)算機(jī)計(jì)算能力的提高，由于DES的密鑰過短，僅有56位，對(duì)DES的成功攻擊也屢見報(bào)端。例如：1999年1月，RSA數(shù)據(jù)安全公司宣布：該公司所發(fā)起的對(duì)56位DES的攻擊已經(jīng)由一個(gè)稱為電子邊境基金（EFF）的組織，通過互聯(lián)網(wǎng)上的100000臺(tái)計(jì)算機(jī)合作在22小時(shí)15分鐘內(nèi)完成。在這種情況下，對(duì)于替代DES的要求日益增多。最終，NIST于1997年發(fā)布公告，征集新的數(shù)據(jù)加密標(biāo)準(zhǔn)作為聯(lián)邦信息處理標(biāo)準(zhǔn)以代替DES。新的數(shù)據(jù)加密標(biāo)準(zhǔn)稱為AES，關(guān)于AES的討論將放在后面的4.5節(jié)。盡管如此，DES的出現(xiàn)是現(xiàn)代密碼學(xué)歷史上非常重要的事件。

3、它對(duì)于我們分析掌握分組密碼的基本理論與設(shè)計(jì)原理仍然具有重要的意義。4.1.1 DES算法描述DES是一個(gè)16輪的Feistel型結(jié)構(gòu)密碼，它的分組長度為64比特，用一個(gè)56比特的密鑰來加密一個(gè)64比特的明文串，輸出一個(gè)64比特的密文串。其中，使用密鑰為64比特，實(shí)用56比特，另8位用作奇偶校驗(yàn)。加密的過程是先對(duì)64位明文分組進(jìn)行初始置換，然后分左、右兩部分分別經(jīng)過16輪迭代，然后再進(jìn)行循環(huán)移位與變換，最后進(jìn)行逆變換得出密文。加密與解密使用相同的密鑰，因而它屬于對(duì)稱密碼體制。圖4-3給出了DES過程框圖。假設(shè)輸入的明文數(shù)據(jù)是64比特。首先經(jīng)過初始置換IP后把其左半部分32比特記為L0，右半部分3

4、2比特記為R0，即成了置換后的輸入；然后把R0與密鑰產(chǎn)生器產(chǎn)生的子密鑰k1進(jìn)行運(yùn)算，其結(jié)果計(jì)為f (R0,k1);再與L0進(jìn)行摸2加得到L0f (R0 , k1), 把R0記為L1放在左邊，而把L0f (R0 , k1)記為R1放在右邊，從而完成了第一輪迭代運(yùn)算。在此基礎(chǔ)上，重復(fù)上述的迭代過程，一直迭代至第16輪。所得的第16輪迭代結(jié)果左右不交換，即L15f (R15 , k16)記為R16,放在左邊，而R15記為L16放在右邊，成為預(yù)輸出，最后經(jīng)過初始置換的逆置換IP-1運(yùn)算后得到密文。下面詳細(xì)介紹DES加密過程中的基本運(yùn)算：（1） DES中的初始置換IP與初始逆置換IP-1 表4-1給出了

5、初始置換IP與初始逆置換IP-1。對(duì)于要加密的明文串64比特，初始置換IP把原來輸入的第58位置換為第1位，原輸入的第50位置換為第2位，,把原輸入的第7位置換為第64位，即最后一位。同樣的初始置換是以預(yù)輸出作為它的輸入，該置換的輸出以預(yù)輸出塊的第40位作為它的第1位，,而以25位作為它的最后一位。圖4-3 DES框圖表 4-1初始置換IP與初始逆置換 （2）密碼函數(shù)f函數(shù)f:0 , 132 ´ 0 , 148®0 , 132的輸入是一個(gè)32比特串(當(dāng)前狀態(tài)的右半部)和子密鑰。密鑰編排方案由16個(gè)48比特的子密鑰組成，這些子密鑰由56比特的種子密鑰k導(dǎo)出。每個(gè)ki都是由k置

6、換選擇而來（子密鑰的產(chǎn)生過程將在后面詳細(xì)說明）。圖4-4給出了函數(shù)f的示意圖。它主要包含一個(gè)應(yīng)用S盒的替代以及其后跟隨的一個(gè)固定置換P。密碼函數(shù)f是整個(gè)加密的關(guān)鍵部分，它包含了如下四種功能：i) 擴(kuò)展函數(shù)E擴(kuò)展函數(shù)E的功能就是將一個(gè)32位的輸入塊擴(kuò)展為48位的輸出塊，而這48位的輸出塊再分成8個(gè)6位的塊。它是按照表4-2依次選擇它所輸入中的位而取得的。從表4-2可知，E(R)的前面3位是R的32，1，2位置上的值，而E(R)的最后2位是R的32，1位的值。 圖4-4 DES 的 f 函數(shù)ii) 模2加法 模2加功能就是將E(R) 的各個(gè)位與密鑰k的各位逐位作模2加，以得到輸出bi , 具體運(yùn)算

7、如下：表4-2 E 比特選擇表3212345456789891011121312131415161716171819202120212223242524252627282928293031321iii) S盒運(yùn)算在密碼函數(shù)f (R , k)中有8個(gè)S盒，稱為8個(gè)不同的選擇函數(shù)，分別用表示，參見表4-3。每個(gè)S盒都是將6位作為輸入，得到一個(gè)4位塊作為輸出。以S1為例，若B是6位的一個(gè)塊，則S1(B)計(jì)算如下：B的第一和最后一位表示從0到3之間的二進(jìn)制數(shù)，令該數(shù)為i ；而B的中間4位表示從0到15之間的二進(jìn)制數(shù)，令該數(shù)為j；在該表S1中查第i行j列的數(shù)，它是從0到15之間的一個(gè)數(shù)，且唯一地由4位塊

8、代表，則該塊就是輸入B的S1的輸出S1(B)例如對(duì)于輸入為101000而言，行是10，即第2行。而列是由0100確定，即第5列，S1盒的第2行與第5列的交叉處即為B，因而輸出為1101，因此1101就是S 盒S1在輸入為101000時(shí)的輸出。在f ( R , k )的計(jì)算中，它將由模2加運(yùn)算得到的按每6個(gè)一組共分為8組，順序記為它們分別經(jīng)過8個(gè)選擇函數(shù) Si運(yùn)算變成即S1(B1)S2(B2)S8(B8) = iv) 置換函數(shù)P置換函數(shù)P是通過輸入塊的位，從32位輸入中得到32位的輸出。置換函數(shù)P由表4-4給出。由該表確定的函數(shù)P的輸出P(C)，是通過C的第16位為P(C)的第1位，取第7位為P

9、(C)的第2位，,取第25為P(C)的第32位。表 4-3 S-盒表4-4 置換函數(shù)P現(xiàn)在我們就令為8個(gè)不同的選擇函數(shù)，P為置換函數(shù)，E為擴(kuò)展函數(shù)。為了計(jì)算f ( R , k )，先規(guī)定每個(gè)為6位塊，且= kE (R),于是有f ( R , k ) = 因此，在f ( R , k )的計(jì)算中將k E(R)分成8個(gè)塊，即每塊6位（即Bi）,然后每個(gè)Bi取作Si的一個(gè)輸入就得到每個(gè)都為4位的8個(gè)塊Si(Bi) ( i = 1 , 2 , , 8)的輸出，再將此8塊連接成32位的整塊。這個(gè)整塊就構(gòu)成了P的輸出，經(jīng)P置換，即為f ( R , k )的輸出。（3）子（輪）密鑰的生成過程在DES中，每一輪

10、迭代都使用了一個(gè)輪密鑰。輪密鑰是從用戶輸入的密鑰k（64位）產(chǎn)生的。實(shí)用密鑰是56位，另8位是奇偶校驗(yàn)位：輸出密鑰k的第8 , 16 , ,64位為奇偶校驗(yàn)位（每一字節(jié)的最后一位），這些位的值使得每個(gè)字節(jié)恰好包含了奇數(shù)個(gè)1，這樣如果輸入密鑰中某個(gè)字節(jié)中存在一個(gè)錯(cuò)誤，奇偶校驗(yàn)可以幫助查到這些錯(cuò)誤。圖4-5 給出了子密鑰的生成示意圖，具體的子密鑰生成過程描述如下：1）輸入的密鑰k先經(jīng)過一個(gè)置換（稱為“置換選擇1”）進(jìn)行重排。置換結(jié)果（56位）被當(dāng)成兩個(gè)28比特的量C0與D0 ,其中C0是置換結(jié)果的前28位，而D0是置換結(jié)果的后28位。圖4-5 子密鑰的生成置換選擇1如表4-5所示。注意到，在置換選

11、擇1中不出現(xiàn)第8，16，24，32，40，48，6，4位，因此實(shí)際64位的密鑰k在經(jīng)過置換選擇1后，奇偶校驗(yàn)位被刪除掉而僅保留下有效的56位密鑰。置換選擇1與初始置換IP的含義類似。例如，置換結(jié)果C0的第7位是輸入密鑰k的第9位，而置換結(jié)果D0的第10位是輸入密鑰的第54位。表4-5置換選擇12）在計(jì)算第i輪迭代所需要的子密鑰時(shí)，首先對(duì)Ci - 1與Di - 1進(jìn)行循環(huán)左移，分別得到Ci與Di。循環(huán)的次數(shù)取決于i的值：如果i = 1，2，9和16，循環(huán)左移的次數(shù)是1；否則循環(huán)左移的次數(shù)等于2。這些經(jīng)過移位的值將作為下一個(gè)循環(huán)的輸入。然后，以Ci Di作為另外一個(gè)由DES算法固定的置換選擇（稱為“置換選擇2”）的輸入，所得到的置換結(jié)果即為第i輪迭代所需要的子密鑰ki。表4-6 置換選擇2表4-6給出了置換選擇2，它表示從56比特（即Ci與Di ）選擇出48位進(jìn)行輸出。前面說過，DES的解密過程與加密過程共用了同樣的計(jì)算過程。兩者的不同之處僅在于解密時(shí)子密鑰ki的使用順序與加密時(shí)相反。如果加密的子密鑰k1，k2,k16, 那么，解密時(shí)子密鑰