數據加密標準（英語：Data Encryption Standard，縮寫為 DES）是一種對稱密鑰加密塊密碼演算法，1976年被美國聯邦政府的國家標準局確定為聯邦資料處理標準（FIPS），隨後在國際上廣泛流傳開來。它基於使用56位密鑰的對稱算法。這個算法因為包含一些機密設計元素，相對短的密鑰長度以及懷疑內含美國國家安全局（NSA）的後門而在開始時有爭議，DES因此受到了強烈的學院派式的審查，並以此推動了現代的塊密碼及其密碼分析的發展。
DES現在已經不是一種安全的加密方法，主要因為它使用的56位密鑰過短。1999年1月，distributed.net與電子前哨基金會合作，在22小時15分鐘內即公開破解了一個DES密鑰。也有一些分析報告提出了該算法的理論上的弱點，雖然在實際中難以應用。為了提供實用所需的安全性，可以使用DES的衍生算法3DES來進行加密，雖然3DES也存在理論上的攻擊方法。DES標準和3DES標準已逐漸被高級加密標準（AES）所取代。另外，DES已經不再作為國家標準科技協會（前國家標準局）的一個標準。
在某些文獻中，作為算法的DES被稱為DEA（Data Encryption Algorithm，數據加密算法），以與作為標準的DES區分開來。在發音時，DES可以作為縮寫按字母拼出來(/ˌdiːˌiːˈɛs/)，或作為一個詞念成/ˈdɛz/。
DES的歷史
DES最初出現在1970年代早期。1972年，在一個對美國政府的計算機安全需求的研究得出結果後，NBS（國家標準局，現在的NIST）開始徵集用於加密政府內非機密敏感信息的加密標準[3]。因此1973年5月15日，在諮詢了美國國家安全局（NSA）之後，NBS向公眾徵集可以滿足嚴格設計標準的加密算法。然而，沒有一個提案可以滿足這些要求。因此在，1974年8月27日，NBS開始了第二次徵集。這一次，IBM提交了一種在1973-1974年間發展的算法，這份提案被有限度的接受了。這種算法是基於早先霍斯特·費斯妥（Horst Fiestel）提出的Lucifer算法的。費斯妥，沃爾特·塔克曼（Walter Tuchman），道·科柏密斯（Don Coppersmith），艾倫·康海姆（Alan Konheim），卡爾·梅爾（Carl Meyer），邁克·馬加什（Mike Matyas），羅伊·阿德勒（Roy Adler），埃德娜·格羅斯曼（Edna Grossman），比爾·諾茲（Bill Notz），林恩·史密斯（Lynn Smith）以及布萊恩特·塔克曼等人參與了IBM在算法設計和分析方面的工作。
1975年3月17日，被選中的DES在「聯邦公報」上公布並徵集公眾意見。次年，NBS舉行了兩個開放式研討會以討論該標準。不同團體提出了一些意見，其中公開密鑰加密先驅馬丁·赫爾曼和惠特菲爾德·迪菲認為密鑰長度過短以及神奇的「S盒」是NSA的不當干涉的結果。這項論點指出，算法被情報部門秘密的削弱了，使得他們—而不是別人—可以簡單的讀取加密信息[4]。S盒的設計者之一，艾倫·康海姆指出：「我們將S盒發給了華盛頓，而他們發回來的S盒變得完全不同了。」[5][6]因此，美國參議院情報特別委員會審查了NSA的行為以判斷是否存在不當行為。在1978年出版的一份公開的總結中，該委員會寫道：
在DES的開發中，NSA使IBM確信縮短後的密鑰長度也可以滿足需求，間接的幫助了S盒結構的開發，並確認最終的DES算法可以在他們所知範圍內沒有任何統計學的或數學的弱點。[7]
然而，也有人提到了：
NSA沒有以任何方式干涉算法的設計。IBM發明和設計了該算法，做出了一切相關決定，並一致同意密鑰長度超出了所有DES涉及的商業應用的需要。[8]
DES小組的另一個成員，沃爾特·塔克曼說：「完全在IBM內，由我們IBM人，發展了DES算法。NSA沒有干涉任何設計問題！[9]」相反，一本解密了的NSA關於加密歷史的書則寫道：
1973年NBS向私人工業徵集數據加密標準。第一份投標方案令人失望，因此NSA開始研究它自己的算法。此後，負責研究和工程的主任霍華德·羅森布拉姆（Howard Rosenblum）發現IBM的沃爾特·塔克曼正在研究修改Lucifer以適應一般應用。NSA為塔克曼發放了一份許可，讓他與情報部門一起研究Lucifer的改進方案。[10]
以及：
NSA與IBM緊密合作以增強算法針對除了暴力破解以外的攻擊方式，並增強被稱為S盒的置換表的強度。同時，很矛盾的，NSA試圖說服IBM將密鑰長度從64位削減到48位，而最終他們達成了妥協，使用56位的密鑰長度。[11]
由於艾力·畢漢姆（Eli Biham）和阿迪·薩莫爾（Adi Shamir）獨立發現和公開了差分密碼分析，一種破解塊密碼的通用方法，針對S盒中隱藏的弱點的懷疑在1990年平靜了下來。DES的S盒的設計使得該算法對這種攻擊方法的抵抗能力大大強於隨機的S盒，該事實強烈的支持了IBM在1970年代就已經知道了其中的技術背景的說法。這的確是事實—1994年，科柏密斯公開了一些原創的S盒的設計準則[12][13]。據史蒂文·列維（Steven Levy）說，IBM的沃森研究院（Watson）在1974年發現了差分密碼攻擊，而NSA要求保持技術秘密[14]。科柏密斯解釋IBM的保密決定說：「那是因為差分密碼攻擊是一種強有力的針對許多算法的工具，因此有人認為公開這樣的信息可能對國家安全產生不利影響。」列維引用沃爾特·塔克曼的話說：「他們讓我們將我們所有的文件可靠的封存起來...我們的確對每一份文件進行編號，並將它們放在保險箱裡，因為這些文件被認為是美國政府機密。他們說這樣做，所以我照做了。[14]」
雖然仍有一些批評，DES在1976年11月被確定為聯邦標準，並在1977年1月15日作為FIPS PUB 46發布[15]，被授權用於所有非機密資料。它在1988年（修訂為FIPS-46-1），1993年（FIPS-46-2）和1999年（FIPS-46-3），後者被規定為3DES（見下文）。2002年5月26日，DES終於在公開競爭中被高級加密標準（AES）所取代。2005年5月26日，FIPS 46-3被官方的拒絕了，但NIST確認3DES在2030年以前均可用於敏感政府信息的加密[16]。
DES算法也定義在了ANSI X3.92[17]，以及ISO/IEC 18033-3中[18]（作為TDEA的一部分）。
1994年發表了另一種理論攻擊方法，線性密碼分析，但1998年的一次蠻力攻擊顯示DES可以被實用的破解，顯示了替代算法的迫切需求。晚些時候的文章更詳細的探討了這些密碼分析的方法。
DES的導入被認為是密碼學的學術研究的催化劑，尤其是對塊密碼的密碼分析。NIST對DES的回顧中提到：
DES可以被稱為對加密算法的非軍用研究和發展的開始。1970年代除了為軍隊或情報組織工作的以外，只有很少的密碼學者，對密碼學的學術研究也很少。現在則有許多活躍的學術性的密碼學者，善於密碼學方面編程的數學部分，以及商業信息安全公司和顧問。一整代的密碼學者都拼命分析（或者說，破解）DES算法。用密碼學家布魯斯·施奈爾的話說：「DES在促進密碼學界的發展上做的比其它的一切都多。現在有一種算法供學者們分析了。[19]」在1970和1980年代，密碼學中關於DES的公開文獻所占的比例令人大吃一驚，而且DES是用來對每一種對稱密鑰算法進行比較的標準對象[20]。
| 日期 | 年份 | 事件 |
|---|---|---|
| 5月15日 | 1973 | NBS第一次徵集加密算法標準 |
| 8月27日 | 1974 | NBS第二次徵集加密算法標準 |
| 3月17日 | 1975 | DES在「聯邦公報」上發布並徵集意見 |
| 8月 | 1976 | DES的第一次研討會 |
| 9月 | 1976 | 第二次研討會，討論DES的數學基礎 |
| 11月 | 1976 | DES被確認為標準 |
| 1月15日 | 1977 | DES被作為FIPS標準FIPS PUB 46發布 |
| 1983 | DES第一次延長標準期限 | |
| 1986 | HBO開始使用一個基於DES的電視衛星加密系統，Videocipher II | |
| 1月22日 | 1988 | DES第二次延長標準期限，稱為FIPS 46-1，取代FIPS PUB 46 |
| 7月 | 1990 | 畢漢姆和薩莫爾重新發現了差分密碼分析，並將之應用到了一個15位的類DES密碼系統 |
| 1992 | 畢漢姆和薩莫爾發布了第一個複雜性小於暴力破解的理論攻擊方法：差分密碼分析。然而，這種方法仍然需要不現實的247選擇明文。 | |
| 12月30日 | 1993 | DES作為FIPS 46-2第三次延長標準期限[21] |
| 1994 | 試驗了第一個實驗性的DES密碼分析，線性密碼分析[22][23] | |
| 6月 | 1997 | DESCHAL計劃第一次公開破解了DES加密的信息 |
| 7月 | 1998 | EFF的DES破解機（Deep Crack）在56小時內破解了DES密鑰 |
| 1月 | 1999 | Deep Crack和distributed.net合作在22小時15分鐘內破解了一個DES密鑰 |
| 10月25日 | 1999 | DES作為FIPS46-3第四次延長標準期限，其中規定優先使用3DES，而普通DES只允許在遺留的系統中應用[24] |
| 11月26日 | 2001 | AES作為FIPS 197發布 |
| 5月26日 | 2002 | AES標準開始生效 |
| 7月26日 | 2004 | 「聯邦公報」發布了FIPS 46-3以及一系列相關標準被駁回的信息[25] |
| 5月19日 | 2005 | NIST拒絕了FIPS 46-3標準[26] |
| 4月 | 2006 | 德國魯爾大學和基爾大學基於FPGA的價值$10,000的並行計算機COPACOBANA在9天內破解了DES[27]在一年內，軟件改進將平均時間降低到了6.4天。 |
| 11月 | 2008 | COPACOBANA的下一代，RIVYERA將平均破解時間降低到了一天內 |
替代算法
安全性方面的考慮使得研究者在1980年代晚期和1990年代早期提出了一系列替代的塊密碼設計，包括RC5，Blowfish，IDEA，NewDES，SAFER，CAST5和FEAL。這些設計的大多數保持了DES的64位的塊大小，可以作為DES的直接替代方案，雖然這些方案通常使用64位或128位的密鑰。蘇聯導入了GOST 28147-89算法，該算法的塊大小為64位，而密鑰長度為256位，並在晚些時候的俄羅斯得到了應用[28]。
2000年代，DES逐漸被3DES替代。3DES相當於用兩個（2TDES）或三個（3TDES）不同的密鑰對數據進行三次DES加密。2010年代，3DES逐漸被更安全的高級加密標準（AES）替代。
2000年10月，在歷時接近5年的徵集和選拔之後，NIST選擇了高級加密標準（AES）替代DES和3DES[29]。2001年2月28日，聯邦公報發表了AES標準，以此開始了其標準化進程[30]，並於2001年11月26日成為FIPS PUB 197標準。AES算法在提交的時候稱為Rijndael。選拔中其它進入決賽的算法包括RC6，Serpent，MARS和Twofish[31]。
算法描述
為簡明起見，下文中的敘述省略的各變換和置換的細節，可以在DES補充材料中找到對應的查找表。
DES是一種典型的塊密碼—一種將固定長度的明文通過一系列複雜的操作變成同樣長度的密文的算法。對DES而言，塊長度為64位。同時，DES使用密鑰來自定義變換過程，因此算法認為只有持有加密所用的密鑰的用戶才能解密密文。密鑰表面上是64位的，然而只有其中的56位被實際用於算法，其餘8位可以被用於奇偶校驗，並在算法中被丟棄。因此，DES的有效密鑰長度僅為56位。
與其它塊密碼相似，DES單單它自身並不構成加密的實用手段，而必須以某種工作模式進行實際操作。FIPS-81確定了DES使用的幾種模式[32]。FIPS-74包括了更多關於DES使用的討論[33]。
算法的整體結構如圖1所示：有16個相同的處理過程，稱為「回次」（round），並在首尾各有一次置換，稱為IP與FP（或稱IP-1，FP為IP的反函數（即IP「撤銷」FP的操作，反之亦然）。IP和FP幾乎沒有密碼學上的重要性，為了在1970年代中期的硬件上簡化輸入輸出數據庫的過程而被顯式的包括在標準中。
在主處理回次前，數據塊被分成兩個32位的半塊，並被分別處理；這種交叉的方式被稱為費斯妥結構。費斯妥結構保證了加密和解密過程足夠相似—唯一的區別在於子密鑰在解密時是以反向的順序應用的，而剩餘部分均相同。這樣的設計大大簡化了算法的實現，尤其是硬件實現，因為沒有區分加密和解密算法的需要。
圖中的⊕符號代表異或（XOR）操作。「F函數」將數據半塊與某個子密鑰進行處理。然後，一個F函數的輸出與另一個半塊異或之後，再與原本的半塊組合併交換順序，進入下一個回次的處理。在最後一個回次完成時，兩個半塊需要交換順序，這是費斯妥結構的一個特點，以保證加解密的過程相似。
圖2中顯示了費斯妥函數（F函數）的過程。其每次對半塊（32位）進行操作，並包括四個步驟：
- 擴張—用擴張置換（圖中的E）將32位的半塊擴展到48位，其輸出包括8個6位的塊，每塊包含4位對應的輸入位，加上兩個鄰接的塊中緊鄰的位。
- 與密鑰混合—用異或操作將擴張的結果和一個子密鑰進行混合。16個48位的子密鑰—每個用於一個回次的F變換—是利用密鑰調度從主密鑰生成的（見下文）。
- S盒—在與子密鑰混合之後，塊被分成8個6位的塊，然後使用「S盒」，或稱「置換盒」進行處理。8個S盒的每一個都使用以查找表方式提供的非線性的變換將它的6個輸入位變成4個輸出位。S盒提供了DES的核心安全性—如果沒有S盒，密碼會是線性的，很容易破解。
- 置換—最後，S盒的32個輸出位利用固定的置換，「P置換」進行重組。這個設計是為了將每個S盒的4位輸出在下一回次的擴張後，使用4個不同的S盒進行處理。
圖3顯示了加密過程中的密鑰調度—產生子密鑰的算法。首先，使用選擇置換1（PC-1）從64位輸入密鑰中選出56位的密鑰—剩下的8位要麼直接丟棄，要麼作為奇偶校驗位。然後，56位分成兩個28位的半密鑰；每個半密鑰接下來都被分別處理。在接下來的回次中，兩個半密鑰都被左移1或2位（由回次數決定），然後通過選擇置換2（PC-2）產生48位的子密鑰—每個半密鑰24位。移位（圖中由<<標示）表明每個子密鑰中使用了不同的位，每個位大致在16個子密鑰中的14個出現。
解密過程中，除了子密鑰輸出的順序相反外，密鑰調度的過程與加密完全相同。
安全與密碼分析
雖然已發表的針對DES的密碼分析的研究文章多於所有其它的塊密碼，到目前為止，最實用的攻擊方法仍然是暴力攻擊。已知DES有一些次要的可能導致加密強度降低的密碼學特性，同時有3種理論攻擊的理論複雜性小於暴力破解，但由於需要過於龐大而通常不現實的已知明文或選擇明文數量，故實用價值微乎其微。
對於一切密碼而言，最基本的攻擊方法是暴力破解法—依次嘗試所有可能的密鑰。密鑰長度決定了可能的密鑰數量，因此也決定了這種方法的可行性。對於DES，即使在它成為標準之前就有一些關於其密鑰長度的適當性的問題，而且也正是它的密鑰長度，而不是理論密碼分析迫使它被後續算法所替代。在設計時，在與包括NSA在內的外部顧問討論後，密鑰長度被從128位減少到了56位以適應在單芯片上實現算法[34]。
在學術上，曾有數個DES破解機被提出。1977年，迪菲和海爾曼提出了一部造價約2千萬美元的破解機，可以在一天內找到一個DES密鑰。1993年，邁克爾·維納設計了一部造價約1百萬美元的破解機，大約可以在7小時內找到一個密鑰。然而，這些早期的設計並沒有被實現，至少沒有公開的實現。在1990年代晚期，DES開始受到實用的攻擊。1997年，RSA安全贊助了一系列的競賽，獎勵第一個成功破解以DES加密的信息的隊伍1萬美元，洛克·韋爾謝什（Rocke Verser），馬特·柯廷（Matt Curtin）和賈斯廷·多爾斯基（Justin Dolske）領導的DESCHALL計劃獲勝，該計劃使用了數千台連接到互聯網的計算機的閒置計算能力。1998年，電子前哨基金會（EFF，一個信息人權組織）製造了一台DES破解機，造價約$250,000。該破解機可以用稍多於2天的時間暴力破解一個密鑰，它顯示了迅速破解DES的可能性。EFF的動力來自於向大眾顯示DES不僅在理論上，也在實用上是可破解的：
許多人在親眼見到一個事實前不會相信它。向他們顯示一台實際的機器可以在數天內破解DES是讓某些人相信他們不能依賴DES的安全性的唯一方法。
下一個確認的DES破解機是2006年由德國的魯爾大學與基爾大學的工作組建造的COPACOBANA。與EFF的不同，COPACOBANA由商業上可獲得的，可重配置的FPGA組成。120片並行的XILINX Spartan3-1000型FPGA分為20個DIMM模塊，每個模塊包括6個FPGA。使用可重配置的FPGA使得這種設備也可以用於其它密碼的破解。另外一個關於COPACOBANA的有趣事實是它的成本。一台COPACOBANA的造價大約是$10,000，是EFF設備的25分之一，這充分說明了數字電路的持續進步。考慮到通貨膨脹因素，同樣價格的設備的性能在8年間大約提到了30倍。2007年，COPACOBANA的兩個項目參與者組建的SciEngines公司改進了COPACOBANA，並發展了它的下一代。2008年，他們的COPACOBANA RIVYERA將破解DES的時間減少到了1天以內，使用128片Spartan-3 5000型FPGA。目前SciEngines的RIVYEAR保持着使用暴力破解法破解DES的紀錄[35]。
有三種已知方法可以以小於暴力破解的複雜性破解DES的全部16回次：差分密碼分析（DC），線性密碼分析（LC），以及戴維斯攻擊。然而，這些攻擊都是理論性的，難以用於實踐；它們有時被歸結於認證的弱點。
- 差分密碼分析在1980年代晚期由艾力·畢漢姆和阿迪·薩莫爾重新發現[36][37]；1970年代IBM和NSA便發現了這種方法，但沒有公開。為了破解全部16回次，差分密碼分析需要247組選擇明文。DES被設計為對DC具有抵抗性。
- 線性密碼分析由松井充（Mitsuru Matsui）發現，需要243組已知明文[38]；該方法已被實現[22]，是第一種公開的實驗性的針對DES的密碼分析。沒有證據顯示DES的設計可以抵抗這種攻擊方法。一般概念上的LC—「多線性密碼分析」—在1994年由Kaliski和Robshaw所建議[39]，並由比留科夫等人於2004年所改進[40]。線性密碼分析的選擇明文變種是一種類似的減少數據複雜性的方法[2]。帕斯卡爾·朱諾德（Pascal Junod）在2001年進行了一些確定線性密碼分析的實際時間複雜性的實驗，結果顯示它比預期的要快，需要約239–241次操作[1]。
- 改進的戴維斯攻擊：線性和差分密碼分析是針對很多算法的通用技術，而戴維斯攻擊是一種針對DES的特別技術，在1980年代由唐納德·戴維斯（Donald Davies）首先提出，並於1997年為畢漢姆和亞歷克斯·比留科夫（Alex Biryukov）所改進[41][42]。其最有效的攻擊形式需要250已知明文，計算複雜性亦為250，成功率為51%。
也有一些其它的針對削減了回次的密碼版本，即少於16回次的DES版本。這些攻擊顯示了多少回次是安全所需的，以及完整版本擁有多少「安全餘量」。差分線性密碼分析於1994年為蘭福德（Langford）和海爾曼所提出，是一種組合了差分和線性密碼分析的方法[43]。一種增強的差分線性密碼分析版本可以利用215.8組已知明文可以以229.2的時間複雜性破解9回次的DES[44]。
DES有補碼特性，即
- 其中是的補碼，是以為密鑰的加密函數，和分別表示明文和密文。這樣的性質表明暴力破解的工作量在選擇明文攻擊下可以減少一半。
DES有四個所謂的弱密鑰。若使用弱密鑰，加密和解密有相同的效果（參見對合)：
- 或
也有6對半弱密鑰。若使用某個半弱密鑰進行加密，則相當於使用其對應的半弱密鑰進行解密：
- 或，
在實現中可以輕易的避開弱密鑰和半弱密鑰，可以顯式的測試密鑰，或簡單的隨機選擇密鑰：剛好選到弱或半弱密鑰的可能性幾乎沒有。這些密鑰事實上並不比其它的密鑰弱，因為他們沒有給攻擊以任何可利用的好處。
DES也被證明不是群，或更精確的，集合（對於所有可能的密鑰）在複合函數之下不是一個群，也不「近似」於一個群[45]。這有時是一個開放式的問題，而且若是這種情況，破解DES是可能的，且類似於3DES的加密模式不能增加其安全性。
DES的最大密碼學安全性被限制在了約64位，除非獨立選擇每個回次的子密鑰而不是從密鑰中生成，這樣做可以將允許768位的安全性。
參考文獻
外部連結
參見
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
