数据加密标准

**資料加密標準**（英語：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）開始徵集用於加密政府內非機密敏感資訊的加密標準。因此 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 的不當干涉的結果。這項論點指出，演算法被情報部門秘密的削弱了，使得他們 — 而不是別人 — 可以簡單的讀取加密資訊。S 盒的設計者之一，艾倫・康海姆指出：「我們將 S 盒發給了華盛頓，而他們發回來的 S 盒變得完全不同了。」因此，美國參議院情報特別委員會審查了 NSA 的行為以判斷是否存在不當行為。在 1978 年出版的一份公開的總結中，該委員會寫道：

> 在 DES 的開發中，NSA 使 IBM 確信縮短後的金鑰長度也可以滿足需求，間接的幫助了 S 盒結構的開發，並確認最終的 DES 演算法可以在他們所知範圍內沒有任何統計學的或數學的弱點。
> 
> 

然而，也有人提到了：

> NSA 沒有以任何方式干涉演算法的設計。IBM 發明和設計了該演算法，做出了一切相關決定，並一致同意金鑰長度超出了所有 DES 涉及的商業應用的需要。
> 
> 

DES 小組的另一個成員，沃爾特・塔克曼說：「完全在 IBM 內，由我們 IBM 人，發展了 DES 演算法。NSA 沒有干涉任何設計問題！」相反，一本解密了的 NSA 關於加密歷史的書則寫道：

> 1973 年 NBS 向私人工業徵集資料加密標準。第一份投標方案令人失望，因此 NSA 開始研究它自己的演算法。此後，負責研究和工程的主任霍華德・羅森布拉姆（Howard Rosenblum）發現 IBM 的沃爾特・塔克曼正在研究修改 Lucifer 以適應一般應用。NSA 為塔克曼發放了一份許可，讓他與情報部門一起研究 Lucifer 的改進方案。
> 
> 

以及：

> NSA 與 IBM 緊密合作以增強演算法針對除了暴力破解以外的攻擊方式，並增強被稱為 S 盒的置換表的強度。同時，很矛盾的，NSA 試圖說服 IBM 將金鑰長度從 64 位元削減到 48 位元，而最終他們達成了妥協，使用 56 位的金鑰長度。
> 
> 

由於艾力・畢漢姆（Eli Biham）和阿迪・薩莫爾（Adi Shamir）獨立發現和公開了差分密碼分析，一種破解塊密碼的通用方法，針對 S 盒中隱藏的弱點的懷疑在 1990 年平靜了下來。DES 的 S 盒的設計使得該演算法對這種攻擊方法的抵抗能力大大強於隨機的 S 盒，該事實強烈的支援了 IBM 在 1970 年代就已經知道了其中的技術背景的說法。這的確是事實 —1994 年，科柏密斯公開了一些原創的 S 盒的設計準則。據史蒂文・列維（Steven Levy）說，IBM 的華生研究院（Watson）在 1974 年發現了差分密碼攻擊，而 NSA 要求保持技術秘密。科柏密斯解釋 IBM 的保密決定說：「那是因為差分密碼攻擊是一種強有力的針對許多演算法的工具，因此有人認為公開這樣的資訊可能對國家安全產生不利影響。」列維參照沃爾特・塔克曼的話說：「他們讓我們將我們所有的檔案可靠的封存起來... 我們的確對每一份檔案進行編號，並將它們放在保險箱裡，因為這些檔案被認為是美國政府機密。他們說這樣做，所以我照做了。」

### 作為標準的演算法

雖然仍有一些批評，DES 在 1976 年 11 月被確定為聯邦標準，並在 1977 年 1 月 15 日作為 **FIPS PUB 46** 發布，被授權用於所有非機密資料。它在 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 年以前均可用於敏感政府資訊的加密。

DES 演算法也定義在了 ANSI X3.92，以及 ISO/IEC 18033-3 中（作為 TDEA 的一部分）。

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 相當於用兩個（2TDES）或三個（3TDES）不同的金鑰對資料進行三次 DES 加密。2010 年代，3DES 逐漸被更安全的高級加密標準（AES）替代。

2000 年 10 月，在歷時接近 5 年的徵集和選拔之後，NIST 選擇了進階加密標準（AES）替代 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 個相同的處理過程，稱為「回次」（_round_），並在首尾各有一次置換，稱為 **IP** 與 **FP**（或稱 **IP-1，FP 為 IP 的反函式（即 IP「復原」FP 的操作，反之亦然）。IP 和 FP 幾乎沒有密碼學上的重要性，為了在 1970 年代中期的硬體上簡化輸入輸出資料庫的過程而被顯式的包括在標準中。**

在主處理回次前，資料塊被分成兩個 32 位元的半塊，並被分別處理；這種交叉的方式被稱為費斯妥結構。費斯妥結構保證了加密和解密過程足夠相似 — 唯一的區別在於子金鑰在解密時是以反向的順序應用的，而剩餘部分均相同。這樣的設計大大簡化了演算法的實現，尤其是硬體實現，因為沒有區分加密和解密演算法的需要。

圖中的⊕符號代表互斥或（XOR）操作。「F 函式」將資料半塊與某個子金鑰進行處理。然後，一個 F 函式的輸出與另一個半塊互斥或之後，再與原本的半塊組合併交換順序，進入下一個回次的處理。在最後一個回次完成時，兩個半塊需要交換順序，這是費斯妥結構的一個特點，以保證加解密的過程相似。

### 費斯妥函式（F 函式）

圖 2 中顯示了費斯妥函式（F 函式）的過程。其每次對半塊（32 位元）進行操作，並包括四個步驟：

1. **擴張** — 用擴張置換（圖中的 **E**）將 32 位元的半塊擴充到 48 位元，其輸出包括 8 個 6 位的塊，每塊包含 4 位元對應的輸入位，加上兩個鄰接的塊中緊鄰的位。
2. **與金鑰混合** — 用互斥或操作將擴張的結果和一個**子金鑰**進行混合。16 個 48 位元的子金鑰 — 每個用於一個回次的 F 變換 — 是利用金鑰排程從主金鑰生成的（見下文）。
3. **S 盒** — 在與子金鑰混合之後，塊被分成 8 個 6 位的塊，然後使用「S 盒」，或稱「置換盒」進行處理。8 個 S 盒的每一個都使用以尋找表方式提供的非線性的變換將它的 6 個輸入位變成 4 個輸出位。S 盒提供了 DES 的核心安全性 — 如果沒有 S 盒，密碼會是線性的，很容易破解。
4. **置換** — 最後，S 盒的 32 個輸出位利用固定的置換，「P 置換」進行重組。這個設計是為了將每個 S 盒的 4 位元輸出在下一回次的擴張後，使用 4 個不同的 S 盒進行處理。

S 盒，P 置換和 E 擴張各自滿足了克勞德・香農在 1940 年代提出的實用密碼所需的必要條件，「混淆與擴散」。

### 金鑰排程

圖 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 位以適應在單晶片上實現演算法。

在學術上，曾有數個 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 的紀錄。

### 快於暴力攻擊的攻擊方法

有三種已知方法可以以小於暴力破解的複雜性破解 DES 的全部 16 回次：差分密碼分析（DC），線性密碼分析（LC），以及戴維斯攻擊。然而，這些攻擊都是理論性的，難以用於實踐；它們有時被歸結於認證的弱點。

* **差分密碼分析**在 1980 年代晚期由艾力・畢漢姆和阿迪・薩莫爾重新發現；1970 年代 IBM 和 NSA 便發現了這種方法，但沒有公開。為了破解全部 16 回次，差分密碼分析需要 247 組選擇明文。DES 被設計為對 DC 具有抵抗性。
* **線性密碼分析**由松井充（Mitsuru Matsui）發現，需要 243 組已知明文；該方法已被實現，是第一種公開的實驗性的針對 DES 的密碼分析。沒有證據顯示 DES 的設計可以抵抗這種攻擊方法。一般概念上的 LC—「多線性密碼分析」— 在 1994 年由 Kaliski 和 Robshaw 所建議，並由比留科夫等人於 2004 年所改進。線性密碼分析的選擇明文變種是一種類似的減少資料複雜性的方法。帕斯卡爾・朱諾德（Pascal Junod）在 2001 年進行了一些確定線性密碼分析的實際時間複雜性的實驗，結果顯示它比預期的要快，需要約 239–241 次操作。
* **改進的戴維斯攻擊**：線性和差分密碼分析是針對很多演算法的通用技術，而戴維斯攻擊是一種針對 DES 的特別技術，在 1980 年代由唐納德・戴維斯（Donald Davies）首先提出，並於 1997 年為畢漢姆和亞歷克斯・比留科夫（Alex Biryukov）所改進。其最有效的攻擊形式需要 250 已知明文，計算複雜性亦為 250，成功率為 51%。

也有一些其它的針對削減了回次的密碼版本，即少於 16 回次的 DES 版本。這些攻擊顯示了多少回次是安全所需的，以及完整版本擁有多少「安全餘量」。差分線性密碼分析於 1994 年為蘭福德（Langford）和海爾曼所提出，是一種組合了差分和線性密碼分析的方法。一種增強的差分線性密碼分析版本可以利用 215.8 組已知明文可以以 229.2 的時間複雜性破解 9 回次的 DES。

### 次要的密碼學特性

DES 有補數特性，即

　
: $E_{K}(P)=C\Leftrightarrow E_{\overline {K}}({\overline {P}})={\overline {C}}$ 其中 ${\overline {x}}$ 是 $x$ 的補數， $E_{K}$ 是以 $K$ 為金鑰的加密函式， $P$ 和 $C$ 分別表示明文和密文。這樣的性質表明暴力破解的工作量在選擇明文攻擊下可以減少一半。

DES 有四個所謂的弱金鑰。若使用弱金鑰，加密和解密有相同的效果（參見對合)：

　
: $E_{K}(E_{K}(P))=P$ 或 $E_{K}=D_{K}$

也有 6 對半弱金鑰。若使用某個半弱金鑰 $K_{1}$ 進行加密，則相當於使用其對應的半弱金鑰 $K_{2}$ 進行解密：

　
: $E_{K_{1}}(E_{K_{2}}(P))=P$ 或， $E_{K_{2}}=D_{K_{1}}$

在實現中可以輕易的避開弱金鑰和半弱金鑰，可以顯式的測試金鑰，或簡單的隨機選擇金鑰：剛好選到弱或半弱金鑰的可能性幾乎沒有。這些金鑰事實上並不比其它的金鑰弱，因為他們沒有給攻擊以任何可利用的好處。

DES 也被證明不是群，或更精確的，集合 $\{E_{K}\}$ （對於所有可能的金鑰 $K$ ）在複合函式之下不是一個群，也不「近似」於一個群。這有時是一個開放式的問題，而且若是這種情況，破解 DES 是可能的，且類似於 3DES 的加密模式不能增加其安全性。

DES 的最大密碼學安全性被限制在了約 64 位元，除非獨立選擇每個回次的子金鑰而不是從金鑰中生成，這樣做可以將允許 768 位元的安全性。

## 參考文獻

### 參照

### 來源

## 外部連結

* EFF 的 DES 破解器計劃
* 針對 DES 的密碼學提示
* John Savard 對 DES 的描述 DES
* 可以顯示中間值的基於 Javascript 的 DES 計算機 （頁面存檔備份，存於網際網路檔案館）
* COPACOBANA，魯爾大學和基爾大學的基於 FPGA 的價值 $10,000 的 DES 破解器
* RFC4772 : 使用 DES 的安全隱患 （頁面存檔備份，存於網際網路檔案館）
* 一份簡單的 DES/3DES 實現文件 （頁面存檔備份，存於網際網路檔案館）

## 參見

* 金鑰密碼學
* Skipjack 加密
* 布萊恩特・塔克曼
* 3DES