資料加密標準

資料加密標準的後門而在開始時有爭議，DES因此受到了強烈的學院派式的審查，並以此推動了現代的塊密碼及其密碼分析的發展。DES現在已經不是一種安全的加密方法，主要因為它使用的56位金鑰過短。1999年1月，distributed.net與電子前哨基金會合作，在22小時15分鐘內即公開破解了一個DES金鑰。也有一些分析報告提出了該演算法的理論上的弱點，雖然在實際中難以應用。為了提供實用所需的安全性，可以使用DES的衍生演算法3DES來進行加密，雖然3DES也存在理論上的攻擊方法。DES標準和3DES標準已逐漸被高階加密標準的一個標準。在某些，作為演算法的DES被稱為DEA，以與作為標準的DES區分開來。在發音時，DES可以作為縮寫按字母拼出來()，或作為一個詞念成。DES的歷史.DES最初出現在1970年代早期。1972年，在一個對美國政府的計算機安全需求的研究得出結果後，NBS以及布萊恩特·塔克曼等人參與了IBM在演算法設計和分析方面的工作。美國國家安全域性在設計中的作用.1975年3月17日，被選中的DES在“聯邦公報”上公佈並徵集公眾意見。次年，NBS舉行了兩個開放式研討會以討論該標準。不同團體提出了一些意見，其中公開金鑰加密先驅馬丁·赫爾曼和惠特菲爾德·迪菲認為金鑰長度過短以及神奇的“S盒”是NSA的不當干涉的結果。這項論點指出，演算法被情報部門秘密的削弱了，使得他們—而不是別人—可以簡單的讀取加密資訊。S盒的設計者之一，艾倫·康海姆指出：“我們將S盒發給了華盛頓，而他們發回來的S盒變得完全不同了。”因此，美國參議院情報特別委員會審查了NSA的行為以判斷是否存在不當行為。在1978年出版的一份公開的總結中，該委員會寫道：在DES的開發中，NSA使IBM確信縮短後的金鑰長度也可以滿足需求，間接的幫助了S盒結構的開發，並確認最終的DES演算法可以在他們所知範圍內沒有任何統計學的或數學的弱點。然而，也有人提到了：NSA沒有以任何方式干涉演算法的設計。IBM發明和設計了該演算法，做出了一切相關決定，並一致同意金鑰長度超出了所有DES涉及的商業應用的需要。DES小組的另一個成員，沃爾特·塔克曼說：“完全在IBM內，由我們IBM人，發展了DES演算法。NSA沒有干涉任何設計問題！”相反，一本解密了的NSA關於加密歷史的書則寫道：1973年NBS向私人工業徵集資料加密標準。第一份投標方案令人失望，因此NSA開始研究它自己的演算法。此後，負責研究和工程的主任霍華德·羅森布拉姆發現IBM的沃爾特·塔克曼正在研究修改Lucifer以適應一般應用。NSA為塔克曼發放了一份許可，讓他與情報部門一起研究Lucifer的改進方案。以及：NSA與IBM緊密合作以增強演算法針對除了暴力破解以外的攻擊方式，並增強被稱為S盒的置換表的強度。同時，很矛盾的，NSA試圖說服IBM將金鑰長度從64位削減到48位，而最終他們達成了妥協，使用56位的金鑰長度。由於在1974年發現了差分密碼攻擊，而NSA要求保持技術秘密。科柏密斯解釋IBM的保密決定說：“那是因為差分密碼攻擊是一種強有力的針對許多演算法的工具，因此有人認為公開這樣的資訊可能對國家安全產生不利影響。”列維引用沃爾特·塔克曼的話說：“他們讓我們將我們所有的檔案可靠的封存起來...我們的確對每一份檔案進行編號，並將它們放在保險箱裡，因為這些檔案被認為是美國政府機密。他們說這樣做，所以我照做了。”作為標準的演算法.雖然仍有一些批評，DES在1976年11月被確定為聯邦標準，並在1977年1月15日作為FIPS PUB 46釋出，被授權用於所有非機密資料。它在1988年所取代。2005年5月26日，FIPS 46-3被官方的拒絕了，但NIST確認3DES在2030年以前均可用於敏感政府資訊的加密。DES演算法也定義在了ANSI X3.92，以及ISO/IEC 18033-3中。1994年發表了另一種理論攻擊方法，線性密碼分析，但1998年的一次蠻力攻擊顯示DES可以被實用的破解，顯示了替代演算法的迫切需求。晚些時候的文章更詳細的探討了這些密碼分析的方法。DES的匯入被認為是密碼學的學術研究的催化劑，尤其是對塊密碼的密碼分析。NIST對DES的回顧中提到：DES可以被稱為對加密演算法的非軍用研究和發展的開始。1970年代除了為軍隊或情報組織工作的以外，只有很少的密碼學者，對密碼學的學術研究也很少。現在則有許多活躍的學術性的密碼學者，善於密碼學方面程式設計的數學部分，以及商業資訊保安公司和顧問。一整代的密碼學者都拼命分析DES演算法。用密碼學家布魯斯·施奈爾的話說：“DES在促進密碼學界的發展上做的比其它的一切都多。現在有一種演算法供學者們分析了。”在1970和1980年代，密碼學中關於DES的公開佔的比例令人大吃一驚，而且DES是用來對每一種對稱金鑰演算法進行比較的標準物件。替代演算法.安全性方面的考慮使得研究者在1980年代晚期和1990年代早期提出了一系列替代的塊密碼設計，包括RC5，Blowfish，IDEA，NewDES，SAFER，CAST5和FEAL。這些設計的大多數保持了DES的64位的塊大小，可以作為DES的直接替代方案，雖然這些方案通常使用64位或128位的金鑰。蘇聯匯入了GOST 28147-89演算法，該演算法的塊大小為64位，而金鑰長度為256位，並在晚些時候的俄羅斯得到了應用。2000年代，DES逐漸被3DES替代。3DES相當於用兩個替代。2000年10月，在歷時接近5年的徵集和選拔之後，NIST選擇了高階加密標準替代DES和3DES。2001年2月28日，聯邦公報發表了AES標準，以此開始了其標準化程序，並於2001年11月26日成為FIPS PUB 197標準。AES演算法在提交的時候稱為Rijndael。選拔中其它進入決賽的演算法包括RC6，Serpent，MARS和Twofish。演算法描述.為簡明起見，下文中的敘述省略的各變換和置換的細節，可以在DES補充材料中找到對應的查詢表。DES是一種典型的塊密碼—一種將固定長度的明文透過一系列複雜的操作變成同樣長度的密文的演算法。對DES而言，塊長度為64位。同時，DES使用金鑰來自定義變換過程，因此演算法認為只有持有加密所用的金鑰的使用者才能解密密文。金鑰表面上是64位的，然而只有其中的56位被實際用於演算法，其餘8位可以被用於奇偶校驗，並在演算法中被丟棄。因此，DES的有效金鑰長度僅為56位。與其它塊密碼相似，DES單單它自身並不構成加密的實用手段，而必須以某種工作模式進行實際操作。FIPS-81確定了DES使用的幾種模式。FIPS-74包括了更多關於DES使用的討論。整體結構.演算法的整體結構如圖1所示：有16個相同的處理過程，稱為“回次”。IP和FP幾乎沒有密碼學上的重要性，為了在1970年代中期的硬體上簡化輸入輸出資料庫的過程而被顯式的包括在標準中。在主處理回次前，資料塊被分成兩個32位的半塊，並被分別處理；這種交叉的方式被稱為費斯妥結構。費斯妥結構保證了加密和解密過程足夠相似—唯一的區別在於子金鑰在解密時是以反向的順序應用的，而剩餘部分均相同。這樣的設計大大簡化了演算法的實現，尤其是硬體實現，因為沒有區分加密和解密演算法的需要。圖中的⊕符號代表異或操作。“F函式”將資料半塊與某個子金鑰進行處理。然後，一個F函式的輸出與另一個半塊異或之後，再與原本的半塊組合並交換順序，進入下一個回次的處理。在最後一個回次完成時，兩個半塊需要交換順序，這是費斯妥結構的一個特點，以保證加解密的過程相似。費斯妥函式.圖2中顯示了費斯妥函式進行操作，幷包括四個步驟：S盒，P置換和E擴張各自滿足了克勞德·夏農在1940年代提出的實用密碼所需的必要條件，“混淆與擴散”。金鑰排程.圖3顯示了加密過程中的金鑰排程—產生子金鑰的演算法。首先，使用選擇置換1表明每個子金鑰中使用了不同的位，每個位大致在16個子金鑰中的14個出現。解密過程中，除了子金鑰輸出的順序相反外，金鑰排程的過程與加密完全相同。安全與密碼分析.雖然已發表的針對DES的密碼分析的研究文章多於所有其它的塊密碼，到目前為止，最實用的攻擊方法仍然是暴力攻擊。已知DES有一些次要的可能導致加密強度降低的密碼學特性，同時有3種理論攻擊的理論複雜性小於暴力破解，但由於需要過於龐大而通常不現實的已知明文或選擇明文數量，故實用價值微乎其微。暴力破解.對於一切密碼而言，最基本的攻擊方法是暴力破解法—依次嘗試所有可能的金鑰。金鑰長度決定了可能的金鑰數量，因此也決定了這種方法的可行性。對於DES，即使在它成為標準之前就有一些關於其金鑰長度的適當性的問題，而且也正是它的金鑰長度，而不是理論密碼分析迫使它被後續演算法所替代。在設計時，在與包括NSA在內的外部顧問討論後，金鑰長度被從128位減少到了56位以適應在單晶片上實現演算法。在學術上，曾有數個DES破解機被提出。1977年，迪菲和海爾曼提出了一部造價約2千萬美元的破解機，可以在一天內找到一個DES金鑰。1993年，邁克爾·維納設計了一部造價約1百萬美元的破解機，大約可以在7小時內找到一個金鑰。然而，這些早期的設計並沒有被實現，至少沒有公開的實現。在1990年代晚期，DES開始受到實用的攻擊。1997年，RSA安全贊助了一系列的競賽，獎勵第一個成功破解以DES加密的資訊的隊伍1萬美元，洛克·韋爾謝什製造了一臺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的紀錄。快於暴力攻擊的攻擊方法.有三種已知方法可以以小於暴力破解的複雜性破解DES的全部16回次：差分密碼分析，以及戴維斯攻擊。然而，這些攻擊都是理論性的，難以用於實踐；它們有時被歸結於認證的弱點。也有一些其它的針對削減了回次的密碼版本，即少於16回次的DES版本。這些攻擊顯示了多少回次是安全所需的，以及完整版本擁有多少“安全餘量”。差分線性密碼分析於1994年為蘭福德和海爾曼所提出，是一種組合了差分和線性密碼分析的方法。一種增強的差分線性密碼分析版本可以利用215.8組已知明文可以以229.2的時間複雜性破解9回次的DES。次要的密碼學特性.DES有補碼特性，即formula_1其中formula_2是formula_3的補碼，formula_4是以formula_5為金鑰的加密函式，formula_6和formula_7分別表示明文和密文。這樣的性質表明暴力破解的工作量在選擇明文攻擊下可以減少一半。DES有四個所謂的弱金鑰。若使用弱金鑰，加密和解密有相同的效果（合)：formula_8或formula_9也有6對半弱金鑰。若使用某個半弱金鑰formula_10進行加密，則相當於使用其對應的半弱金鑰formula_11進行解密：formula_12或，formula_13在實現中可以輕易的避開弱金鑰和半弱金鑰，可以顯式的測試金鑰，或簡單的隨機選擇金鑰：剛好選到弱或半弱金鑰的可能性幾乎沒有。這些金鑰事實上並不比其它的金鑰弱，因為他們沒有給攻擊以任何可利用的好處。DES也被證明不是群，或更精確的，集合formula_14在複合函式之下不是一個群，也不“近似”於一個群。這有時是一個開放式的問題，而且若是這種情況，破解DES是可能的，且類似於3DES的加密模式不能增加其安全性。DES的最大密碼學安全性被限制在了約64位，除非獨立選擇每個回次的子金鑰而不是從金鑰中生成，這樣做可以將允許768位的安全性。[[Category:資料加密標準]]