DES算法詳細(xì)介紹

-.z.1973年5月15日，美國國家標(biāo)準(zhǔn)局〔現(xiàn)在美國國家標(biāo)準(zhǔn)技術(shù)研究所〔NIST〕在聯(lián)邦注冊報(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密碼體制的改良。DES在1975年3月17日首次在聯(lián)邦記錄中公布，而且聲明比照算法征求意見。到1977年2月15日擬議中的DES被采納為"非〞應(yīng)用的一個(gè)聯(lián)邦標(biāo)準(zhǔn)。最初預(yù)期DES作為一個(gè)標(biāo)準(zhǔn)只能使用10~15年，然而，出于種種原因，可能是DES還沒有受到嚴(yán)重的威脅，事實(shí)證明了DES要長壽得多。在其被采用后，大約每隔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é)歷史上非常重要的事件。它對(duì)于我們分析掌握分組密碼的根本理論與設(shè)計(jì)原理仍然具有重要的意義。DES算法描述DES是一個(gè)16輪的Feistel型構(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，右半局部32比特記為R0，即成了置換后的輸入；然后把R0與密鑰產(chǎn)生器產(chǎn)生的子密鑰k1進(jìn)展運(yùn)算，其結(jié)果計(jì)為f(R0,k1);再與L0進(jìn)展摸2加得到L0eq\o\ac(○,+)f(R0,k1),把R0記為L1放在左邊，而把L0eq\o\ac(○,+)f(R0,k1)記為R1放在右邊，從而完成了第一輪迭代運(yùn)算。在此根底上，重復(fù)上述的迭代過程，一直迭代至第16輪。所得的第16輪迭代結(jié)果左右不交換，即L15eq\o\ac(○,+)f(R15,k16)記為R16,放在左邊，而R15記為L16放在右邊，成為預(yù)輸出，最后經(jīng)過初始置換的逆置換IP-1運(yùn)算后得到密文。下面詳細(xì)介紹DES加密過程中的根本運(yùn)算：DES中的初始置換IP與初始逆置換IP-1表4-1給出了初始置換IP與初始逆置換IP-1。對(duì)于要加密的明文串64比特，初始置換IP把原來輸入的第58位置換為第1位，原輸入的第50位置換為第2位，……,把原輸入的第7位置換為第64位，即最后一位。同樣的初始置換是以預(yù)輸出作為它的輸入，該置換的輸出以預(yù)輸出塊的第40位作為它的第1位，……,而以25位作為它的最后一位。圖4-3DES框圖表4-1初始置換IP與初始逆置換〔2〕密碼函數(shù)f函數(shù)f:{0,1}32{0,1}48{0,1}32的輸入是一個(gè)32比特串(當(dāng)前狀態(tài)的右半部)和子密鑰。密鑰編排方案由16個(gè)48比特的子密鑰組成，這些子密鑰由56比特的種子密鑰k導(dǎo)出。每個(gè)ki都是由k置換選擇而來〔子密鑰的產(chǎn)生過程將在后面詳細(xì)說明〕。圖4-4給出了函數(shù)f的示意圖。它主要包含一個(gè)應(yīng)用S盒的替代以及其后跟隨的一個(gè)固定置換P。密碼函數(shù)f是整個(gè)加密的關(guān)鍵局部，它包含了如下四種功能：擴(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-4DES的f函數(shù)模2加法模2加功能就是將E(R)的各個(gè)位與密鑰k的各位逐位作模2加，以得到輸出bi,具體運(yùn)算如下：表4-2E比特選擇表3212345456789891011121312131415161716171819202120212223242524252627282928293031321S盒運(yùn)算在密碼函數(shù)f(R,k)中有8個(gè)S盒，稱為8個(gè)不同的選擇函數(shù)，分別用表示，參見表4-3。每個(gè)S盒都是將6位作為輸入，得到一個(gè)4位塊作為輸出。以S1為例，假設(shè)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位塊代表，則該塊就是輸入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)=置換函數(shù)P置換函數(shù)P是通過輸入塊的位，從32位輸入中得到32位的輸出。置換函數(shù)P由表4-4給出。由該表確定的函數(shù)P的輸出P(C)，是通過C的第16位為P(C)的第1位，取第7位為P(C)的第2位，……,取第25為P(C)的第32位。表4-3S-盒表4-4置換函數(shù)P現(xiàn)在我們就令為8個(gè)不同的選擇函數(shù)，P為置換函數(shù)，E為擴(kuò)展函數(shù)。為了計(jì)算f(R,k)，先規(guī)定每個(gè)為6位塊，且=keq\o\ac(○,+)E(R),于是有f(R,k)=因此，在f(R,k)的計(jì)算中將keq\o\ac(○,+)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中，每一輪迭代都使用了一個(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所示。注意到，在置換選擇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)的輸入。然后，以CiDi作為另外一個(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,則，解