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

2、被評審一次。DES的最后一次評審是在1999年1月。但是，隨著計算機計算能力的提高，由于DES的密鑰過短，僅有56位，對DES的成功攻擊也屢見報端。例如：1999年1月，RSA數據安全公司宣布：該公司所發起的對56位DES的攻擊已經由一個稱為電子邊境基金（EFF）的組織，通過互聯網上的100000臺計算機合作在22小時15分鐘內完成。在這種情況下，對于替代DES的要求日益增多。最終，NIST于1997年發布公告，征集新的數據加密標準作為聯邦信息處理標準以代替DES。新的數據加密標準稱為AES，關于AES的討論將放在后面的4.5節。盡管如此，DES的出現是現代密碼學歷史上非常重要的事件。它對于我

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

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

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

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

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

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

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

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

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