Data Encryption Standardのソースを表示

{{Infobox Encryption method
|name={{lang|en|data encryption standard}}
|image=[[ファイル:Data Encryption Standard InfoBox Diagram.png|300px|center]]
|caption=DESのファイステル関数（F関数）
|designers=[[IBM]]
|publish date=1977年（標準化は1979年1月）
|derived from=[[Lucifer (暗号)|Lucifer]]
|derived to=[[トリプルDES]], [[GDES]], [[DES-X]], {{仮リンク|LOKI|label=LOKI89|en|LOKI}}, {{仮リンク|ICE (暗号)|label=ICE|en|ICE}}
|key size=56ビット
|block size=64ビット
|structure=均衡型[[Feistel構造]]
|rounds=16
|cryptanalysis=DESは今では[[総当り攻撃]]で解読可能であるため、安全ではない。2008年現在、最良の攻撃法は[[線形解読法]]で、2<sup>43</sup>の既知平文を必要とし、時間計算量は2<sup>39–43</sup>である(Junod, 2001)。選択平文を前提とすれば、データ計算量は4分の1に減じることができる(Knudsen and Mathiassen, 2000)。}}

{{lang|en|'''Data Encryption Standard'''}}（データ暗号化標準）、略して'''DES'''（{{要出典|デス、ディーイーエス|date=2017年1月}}）は、[[アメリカ合衆国]]の旧国家暗号規格、もしくはその[[規格]]で規格化されている[[共通鍵暗号]]である。[[ブロック暗号]]の一種であり、1976年[[アメリカ国立標準技術研究所|国立標準局]] (NBS) が[[アメリカ合衆国]]の公式[[Federal Information Processing Standards|連邦情報処理標準]] (FIPS) として採用し、その後国際的に広く使われた。56[[ビット]]の鍵を使った[[共通鍵暗号]]を基盤としている。その[[アルゴリズム]]は、機密設計要素、比較的短い鍵長、[[アメリカ国家安全保障局]] (NSA) が[[バックドア]]を設けたのではないかという疑いなどで、当初物議をかもしていた。結果としてDESは、現代の[[ブロック暗号]]とその[[暗号解読]]の理解に基づいて学究的に徹底した精査を受けた。

DESは今では多くの用途において[[安全]]ではないと見なされている。これは主に56ビットという鍵長が短すぎることに起因する。1999年1月、[[distributed.net]]と[[電子フロンティア財団]]は共同で、22時間15分でDESの鍵を破ったことを公表した。この[[暗号]]の理論上の弱さを示した解析結果もあるが、そのような弱さを実際に利用することが可能というわけではない。アルゴリズム自体は実用上安全であるとされ、[[トリプルDES]]という形で使われているが、[[暗号理論|理論]]的攻撃方法は存在する。近年、{{lang|en|[[Advanced Encryption Standard]]}} (AES)に取って代わられた。

なお、標準としてのDESとアルゴリズムを区別することがあり、アルゴリズムを {{lang|en|'''Data Encryption Algorithm'''}} ('''DEA''')と称することがある。

==DESが制定されるまでの経緯==
DESの起源は[[1970年代]]初めに遡る。1972年、アメリカ政府は[[コンピュータセキュリティ]]が重要であるという研究結果を得た。そこでNBS（National Bureau of Standard。合衆国標準局。現在の[[アメリカ国立標準技術研究所|NIST（アメリカ国立標準技術研究所）]]）が、政府全体で機密情報を暗号化するための標準規格が必要だと判断した<ref>{{cite conference|author=Walter Tuchman|title=A brief history of the data encryption standard|book-title=Internet besieged:countering cyberspace scofflaws|publisher=ACM Press/Addison-Wesley Publishing Co. New York, NY, USA|pages=275-280|year=1997}}</ref>。それに応じて1973年5月15日、[[アメリカ国家安全保障局|NSA]]と相談の上、NBSが厳しい[[設計]]基準を満たした暗号を公募した。しかし応募のいずれも条件を満たしていなかったため、1974年8月27日に2回目の公募を行った。今回は[[IBM]]の応募した案が条件を満たしていると思われた。それは、以前からあったアルゴリズムに基づき1973年から1974年に開発された[[ホルスト・ファイステル]]の[[Lucifer (暗号)|Lucifer]]暗号だった。IBMでこの暗号の設計と解析を行ったチームにはファイステルの他に、ウォルト・タックマン (Walt Tuchman)、ドン・コッパースミス (Don Coppersmith)、アラン・コンハイム (Alan Konheim)、カール・メイヤー (Carl Meyer)、マイク・マーチャーシュ (Mike Matyas)、ロイ・アドラー (Roy Adler)、エドナ・グロスマン (Edna Grossman)、ビル・ノッツ (Bill Notz)、リン・スミス (Lynn Smith)、ブライアント・タッカーマン (Bryant Tuckerman) らがいた。

Lucifer・DESはホルスト・ファイステルらの考えた[[Feistel構造]]と呼ばれる構造をなしている。この事は後の共通鍵暗号研究に多大な影響を与え、後に提案された多くの共通鍵暗号方式がFeistel構造に基づいて設計された。

===NSAの設計への関与===
1975年3月17日、規格案としてのDESが ''[[連邦官報|Federal Register]]'' に発表された。そしてコメントが募集され、翌年には2回ワークショップを開催してこの規格案について議論した。各所から様々な批判が寄せられた。中には[[公開鍵暗号]]の先駆者である[[マーティン・ヘルマン]]と[[ホイットフィールド・ディフィー]]の批判があり、鍵長が短いという点と謎めいた「[[Sボックス]]」がNSAによる不適切な干渉を意味しているのではないかと指摘した。それは、このアルゴリズムを諜報機関が密かに弱め、その諜報機関だけが暗号化されたメッセージを容易に解読できるようにしたのではないかという疑いが持たれたのである<ref>{{cite web|url=http://www.rsa.com/rsalabs/node.asp?id=2227|title=Has DES been broken?|author=RSA Laboratories|accessdate=2009-05-27}}</ref>。アラン・コンハイム（DES設計者の1人）はそれについて「我々はSボックスをワシントンに送った。戻ってきたものは送ったものとは全く異なっていた」と述べた<ref>{{cite book|last=Schneier|title=Applied Cryptography|edition=2nd|page=280}}</ref>。アメリカ合衆国上院諜報特別委員会がNSAの行為に不適切な干渉があったかどうかを調査した。調査結果の公開された要約には次のように書かれている。
:「DESの開発において、NSAは[[IBM]]に対して鍵長が短くても大丈夫だと納得させ、Sボックスの開発を間接的に支援し、最終的なDESアルゴリズムが統計学的にも数学的にも考えられる最高のものだと保証した」<ref>{{cite book|first=D.W.|last=Davies|coauthors=W.L. Price|title=Security for computer networks, 2nd ed.|publisher=John Wiley & Sons|year=1989}}</ref>
しかし、同時に次のようなことも判明している。
:「NSAはいかなる形でもアルゴリズムの設計を改変していない。[[IBM]]はこのアルゴリズムを発明・設計し、関連する設計上の意思決定は全てIBMが行い、鍵長もDESのあらゆる商用の用途にとって十分な長さとして決定した」<ref>{{cite journal|author=Robert Sugarman (editor)|title=On foiling computer crime|journal=IEEE Spectrum|date=July 1979|publisher=[[IEEE]]}}</ref>
DES設計チームのウォルト・タックマンは「我々はIBM内でIBMの人員だけでDESアルゴリズム全体を開発した。NSAに命じられて変更した部分は1つもない」と述べた<ref>{{cite journal|author=P. Kinnucan|title=Data Encryption Gurus:Tuchman and Meyer|journal=Cryptologia|volume=2|issue=4|date=October 1978|doi=10.1080/0161-117891853270|page=371}}</ref>。一方、機密解除されたNSAの暗号史に関する本には次のように書かれている。
:「1973年、NBSはDESを民間企業に求めた。最初の応募案は満足のいくものではなかったため、NSAは独自にアルゴリズムの研究を始めた。そして、工学研究部門の代表であるハワード・ローゼンブラムは、IBMのウォルト・タックマンがLuciferを汎用化する修正を行っていることに気づいた。NSAはタックマンに人物証明を与え、当局と共にLuciferを修正する作業を行わせた」<ref>{{cite journal|author=Thomas R. Johnson|title=American Cryptology during the Cold War, 1945-1989.Book III:Retrenchment and Reform, 1972-1980|journal=United States Cryptologic History|volume=5|issue=3}}</ref>
Sボックスに関する嫌疑の一部は1990年に鎮められることになった。同年、[[エリ・ビハム]]と[[アディ・シャミア]]（[[RSA暗号|RSA]]のS）が[[差分解読法]]を独自に発見して公表した。差分解読法はブロック暗号を破る汎用技法である。DESのSボックスは無作為に選ばれた場合よりもこの攻撃法にずっと抵抗力があり、IBMが1970年代にこの攻撃法を知っていたことを強く示唆していた。1994年、ドン・コッパースミスがSボックスの元々の設計基準について一部を公表したことで、それが裏付けられた<ref>{{cite book|last=Konheim|title=Computer Security and Cryptography|page=301}}</ref>。[[スティーブン・レビー]]によれば、IBMでは1974年に差分解読法を発見していたが、NSAがそれを秘密にするよう要請していたという<ref name=Levy>Levy, ''Crypto'', p. 55</ref>。コッパースミスはIBMの方針について「（差分解読法）は非常に強力なツールであり、様々な方式に応用でき、これを公にすると国家の安全に悪い影響を及ぼすことが懸念された」と述べている。レビーはタックマンの言葉として「彼らは我々のあらゆる文書に極秘というスタンプを押させようとした…それらは合衆国政府の機密と見なされたので、我々は実際にそれらに番号を振り、金庫に入れた。彼らがそうしろと言ったから、そうしたまでだ」と書いている<ref name=Levy/>。

===標準暗号としてのDES===
批判はあったがDESは1976年11月[[連邦規格]]として承認され、1977年1月15日には '''[[Federal Information Processing Standards|FIPS]] PUB 46''' として公表され、非機密政府通信での利用が承認された。さらに1981年に [[ANSI]]として制定され、民間標準規格にもなった。1983年、1988年（'''FIPS-46-1''' に更新）、1993年 ('''FIPS-46-2''')、1999年 ('''FIPS-46-3''') と再承認され、最後には[[トリプルDES]]が定められた。2002年5月26日、DESは公開のコンペティションで選ばれた [[Advanced Encryption Standard]] (AES) で置き換えられた。2005年5月19日、FIPS 46-3は公式に廃止となったが、[[アメリカ国立標準技術研究所|NIST]]は[[トリプルDES]]については政府の重要情報用に使うことを2030年まで承認している<ref name=SP800-67>{{cite web|url=http://nvlpubs.nist.gov/nistpubs/Legacy/SP/nistspecialpublication800-67r1.pdf|page=6|title=NIST Special Publication 800-67 ''Recommendation for the Triple Data Encryption Algorithm (TDEA) Block Cipher'', Version 1.1|accessdate=2016-10-09|publisher=[[アメリカ国立標準技術研究所|National Institute of Standards and Technology]]|language=English|format=PDF}}</ref>。

このアルゴリズムは ANSI X3.92<ref>[[ANSI|American National Standards Institute]], ANSI X3.92-1981 ''American National Standard, Data Encryption Algorithm''</ref>、NIST SP 800-67<ref name=SP800-67/>、ISO/IEC 18033-3<ref>{{cite web|url=http://www.iso.org/iso/iso_catalogue/catalogue_tc/catalogue_detail.htm?csnumber=37972|title=ISO/IEC 18033-3:2005 Information technology&nbsp;— Security techniques&nbsp;— Encryption algorithms&nbsp;— Part 3:Block ciphers|publisher=Iso.org|date=2008-10-15|accessdate=2009-06-02}}</ref> でも指定されている（[[トリプルDES|TDEA]]の要素として）。

もう1つの理論的攻撃法である線形解読法は1994年に公表された。1998年には[[総当り攻撃]]で実用的な時間でDESを破れることが実証され、アルゴリズムの更新の必要性が高まった。これら攻撃法については後の節で詳述する。

DESの登場は暗号研究、特に暗号解読法の研究を活発化させる触媒の役割を果たした。NISTは後にDESについて次のように述べている。
:DESは暗号アルゴリズムの非軍事的研究と開発を「ジャンプスタート」させたと言える。1970年代、[[暗号学者]]は[[軍隊]]や[[諜報機関]]以外にはほとんどおらず、暗号の学問的研究は限定的だった。今では多数の学者が暗号を研究し、数学関係の学科で暗号を教え、情報セキュリティ企業やコンサルタントが商売をしている。暗号解読者はDESアルゴリズムを解析することで経験を積んだ。暗号研究者[[ブルース・シュナイアー]]は「DESは暗号解読というフィールドを大いに活気付けた。今では研究すべきアルゴリズムのひとつだ」と述べている<ref>Bruce Schneier, Applied Cryptography, Protocols, Algorithms, and Source Code in C, Second edition, John Wiley and Sons, New York (1996) p. 267</ref>。1970年代から1980年代にかけて、暗号に関する多くの書籍がDESを扱っており、共通鍵暗号を比較する際の基準となっている<ref>William E. Burr, "Data Encryption Standard", in NIST's anthology "A Century of Excellence in Measurements, Standards, and Technology:A Chronicle of Selected NBS/NIST Publications, 1901–2000.  [http://nvl.nist.gov/pub/nistpubs/sp958-lide/html/250-253.html HTML] [http://nvl.nist.gov/pub/nistpubs/sp958-lide/250-253.pdf PDF]</ref>。

===年表===
{|class=wikitable
!日付
!出来事
|-
|nowrap|1973年5月15日
|NBSが標準暗号アルゴリズムの要求仕様を公開（1回目）。
|-
|nowrap|1974年8月27日
|NBSが標準暗号アルゴリズムの要求仕様を公開（2回目）。
|-
|nowrap|1975年3月17日
|コメントを求めるため、DESが {{lang|en|Federal Register}} で公表された。
|-
|nowrap|1976年8月
|DESに関する最初のワークショップ開催。
|-
|nowrap|1976年9月
|2回目のワークショップ。DESの数学的基盤について議論。
|-
|nowrap|1976年11月
|DESを標準として承認。
|-
|nowrap|1977年1月15日
|DESを {{lang|en|FIPS PUB}} 46 として公表。
|-
|nowrap|1983年
|DESについて、1回目の再承認を実施。
|-
|nowrap|1986年
|[[HBO]]がDESをベースとした衛星テレビ放送のスクランブリングシステム {{lang|en|Videocipher II}} を実用化。
|-
|nowrap|1988年1月22日
|DES について2回目の再承認を行い、{{lang|en|FIPS PUB}} 46 を置き換える {{lang|en|FIPS}} 46-1 を制定。
|-
|nowrap|1990年7月
|ビハムとシャミアが[[差分解読法]]を再発見し、DESに似た15ラウンドの暗号に適用。
|-
|nowrap|1992年
|ビハムとシャミアが総当り攻撃よりも計算量が少ない理論上の攻撃法（[[差分解読法]]）があることを発表。ただし、必要とする選択平文数は非現実的な2<sup>47</sup>だった。
|-
|nowrap|1993年12月30日
|DES について3回目の承認を行い、{{lang|en|FIPS}} 46-2 とした。
|-
|nowrap|1994年
|[[線形解読法]]を用いた[[暗号解読#解読法の分類|既知平文攻撃]]によって、DESの解読が初めて実際に行われた ([[松井充]])。平文と暗号文の組数は、2<sup>43</sup>だった。
|-
|nowrap|1997年6月
|{{仮リンク|DESCHALL|en|DESCHALL Project}}によりDESで暗号化されたメッセージの解読が行われ、初めて一般に公表。
|-
|nowrap|1998年7月
|[[電子フロンティア財団]]の{{仮リンク|DESクラッカー|en|EFF DES cracker}}が56時間でDESの鍵を破った。
|-
|nowrap|1999年1月
|{{lang|en|Deep Crack}} と {{lang|en|[[distributed.net]]}} が共同で22時間15分でDESの鍵を破った。
|-
|nowrap|1999年10月25日
|DESについて4回目の承認を行い FIPS 46-3としたが、[[トリプルDES]]の使用を推奨し、シングルDESは古いシステムでのみ使用することとした。
|-
|nowrap|2001年11月26日
|[[Advanced Encryption Standard|{{lang|en|Advanced Encryption Standard}} (AES) ]]を {{lang|en|FIPS}} 197として公表。
|-
|nowrap|2002年5月26日
|AES規格が発効。
|-
|nowrap|2004年7月26日
|{{lang|en|FIPS}} 46-3（および関連する規格群）の廃止が {{lang|en|Federal Register}} で提案された<ref>{{cite web|url=http://edocket.access.gpo.gov/2004/04-16894.htm|title=FR Doc 04-16894|publisher=Edocket.access.gpo.gov|date=|accessdate=2009-06-02}}</ref>。
|-
|nowrap|2005年5月19日
|NISTがFIPS 46-3を廃止<ref>{{cite web|url=https://www.gpo.gov/fdsys/pkg/FR-2005-05-19/pdf/05-9945.pdf|title=Federal Register vol 70, number 96|date=2005-05-19|accessdate=2016-10-09|publisher=Office of the Federal Register, National Archives and Records Administration|language=English|format=PDF}}</ref>
|-
|nowrap|2006年4月
|[[ルール大学ボーフム]]と[[キール大学 (ドイツ)|キール大学]]で[[FPGA]]を使った並列マシン{{lang|de|COPACOBANA}}を開発し、1万ドルのハードウェアコストで9日間をかけてDESを破った<ref name="copacobana-2006">S. Kumar, C. Paar, J. Pelzl, G. Pfeiffer, A. Rupp, M. Schimmler, "How to Break DES for Euro 8,980". 2nd Workshop on Special-purpose Hardware for Attacking Cryptographic Systems&nbsp;— SHARCS 2006, Cologne, Germany, April 3-4, 2006. </ref>。 その後1年以内にソフトウェアを改良し、平均で6.4日で破れるようになった。
|}

==詳細==
[[ファイル:DES-main-network.png|thumb|250px|''図 1''— DESのFeistel構造全体]]
[[ファイル:DES-f-function.png|thumb|250px|''図 2''— DESのFeistel関数（F-関数）]]
[[ファイル:DES-key-schedule.png|thumb|250px|''図 3''— DESの鍵スケジュール]]
DESは原型ともいうべき[[ブロック暗号]]であり、固定ビット長の[[平文]]を入力とし、一連の複雑な操作によって同じ長さの[[暗号文]]を出力する[[アルゴリズム]]である。DESの場合、ブロック長は64ビットである。また、変換をカスタマイズする[[鍵 (暗号)|鍵]]を使うため、暗号化に使った鍵を知っている者だけが復号できる。鍵は見た目は64ビットだが、そのうち8ビットは[[パリティビット|パリティ]]チェックに使うため、アルゴリズム上の実際の鍵の長さは56ビットである。

他のブロック暗号と同様、DES自体は暗号化の安全な手段ではなく、[[暗号利用モード]]で使う必要がある。FIPS-81 はDES用のいくつかのモードを示している<ref>{{cite web|url=http://csrc.nist.gov/publications/fips/fips81/fips81.htm|title=FIPS 81 - Des Modes of Operation|publisher=Itl.nist.gov|date=|accessdate=2016-10-09}}</ref>。その他のDESの利用法については FIPS-74 に詳しい<ref>{{cite web|url=http://www.itl.nist.gov/fipspubs/fip74.htm|archiveurl=https://web.archive.org/web/20140103013152/http://www.itl.nist.gov/fipspubs/fip74.htm|archivedate=2014-01-03|title=FIPS 74 - Guidelines for Implementing and Using the NBS Data|publisher=Itl.nist.gov|date=|accessdate=2016-10-09}}</ref>。

===全体構造===
アルゴリズムの全体構造を図1に示す。16の処理工程があり、それらを「ラウンド」と呼ぶ。また、最初と最後に[[順列|並べ替え]]処理があり、それぞれ ''IP'' および ''FP'' と呼ぶ。''IP'' と ''FP'' はちょうど逆の処理を行う。''IP'' と ''FP'' は暗号化にはほとんど関係ないが、1970年代の[[ハードウェア]]でブロックの入出力を行う部分として含まれており、同時にそれによって[[ソフトウェア]]によるDESの処理が遅くなる原因にもなっている。

ラウンドでの処理の前にブロックは半分（32ビット）ずつに分けられ、それぞれ異なる処理を施される。この十字交差構造を[[Feistel構造]]と呼ぶ。Feistel構造を使うと、暗号化と復号は非常に良く似た処理になる。違いは、復号ではラウンド鍵を逆の順序で適用するという点だけであり、アルゴリズムは同一である。このため実装が単純化でき、特にハードウェアで実装する場合に両者を別々に実装する必要が無い。

⊕ という記号は[[排他的論理和]] (XOR) を意味する。''F-関数''はブロックの半分を何らかの鍵でかき混ぜる。F-関数の出力をブロックの残り半分と結合し、次のラウンドに行く前にその半分同士を入れ替える。最後のラウンドの後には入れ替えは行わない。これは、暗号化と復号を似たプロセスで行うFeistel構造の特徴である。

===Feistel(F)関数===
図2にあるF-関数はブロックの半分（32ビット）を一度に処理する。以下の4段階がある。
# ''Expansion'' - ''expansion permutation'' と呼ばれる方式で32ビットを48ビットに拡張する。図では ''E'' で示されている部分である。入力のうち半分のビットの複製16ビット分を出力のビット列に追加する。その出力は8個の6ビットの部分からなり、それら6ビットのうちの中央4ビットは入力の対応する4ビットの部分と同じで、両端の1ビットずつは入力上で隣接する部分のビットの複製である。
# ''Key mixing'' - ラウンド鍵と上の出力結果をXOR操作で結合する。ラウンド鍵は48ビットで、もともとの鍵から「鍵スケジュール」（後述）によって16個のラウンド鍵が生成される。
# ''Substitution'' - ラウンド鍵を混ぜた後、6ビットずつに分けて[[Sボックス]] (substitution box) に入力する。8個のSボックスは入力の6ビットから4ビットの出力を生成し、このとき[[ルックアップテーブル]]の形で提供される非線形な変換を行う。SボックスがDESの安全性の根幹であり、これが無かったならば暗号化の処理は線形であり容易に破ることができることになる。
# ''Permutation'' - Sボックス群の出力である32ビットに固定の[[順列|並べ替え]]を施す。図では ''P'' で示した部分である。このとき、各Sボックスの出力が次のラウンドでSボックスに展開されるとき、6個の異なるSボックスに分散するよう並べ替える。

Sボックスでの置換とPボックスでの並べ替えとEでの拡張を交互に行うことで、[[クロード・シャノン]]が安全で実用的な暗号に必要な条件とした「[[拡散とかく乱]]」を提供する。

===鍵スケジュール===
図3は暗号化での「鍵スケジュール」、すなわちラウンド鍵を生成するアルゴリズムを示している。まず64ビットの入力から56ビットを選択して並べ替えを行う ''Permuted Choice 1'' (''PC-1'') がある。選ばれなかった8ビットは単に捨ててもよいし、[[パリティビット]]として鍵のチェックに使ってもよい。その56ビットは2つの28ビットに分割され、その後別々に処理される。ラウンドを次に進める際にそれぞれを左に1ビットか2ビット[[ビット演算#(キャリーなし)ローテート|ローテート]]する（ラウンドによってローテートするビット数が異なる）。そして、それらを ''Permuted Choice 2'' (''PC-2'') に入力して48ビットのラウンド鍵を出力する。このときそれぞれの半分（28ビット）から24ビットずつを選び、並べ替えも左右別々に行う。ローテートを行うことでラウンドごとに選択するビットが変化する（PC-2自体は固定であり、毎回同じ位置のビットを選んで同じ順序で並べ替える）。各ビットは16ラウンドのうち、だいたい14回使われる。

復号の際の鍵スケジュールもほぼ同様である。ラウンド鍵は暗号化のときとは逆順に適用される。その点を除けば暗号化と全く同じ工程で処理される。

==DESに代わるアルゴリズム==
DESについては安全性と[[ソフトウェア]]による処理が相対的に遅い点が懸念され、[[1980年代]]末から[[1990年代]]初めごろから研究者らが様々な[[ブロック暗号]]を代替案として提案してきた。例えば、[[RC5]]、[[Blowfish]]、[[International Data Encryption Algorithm|IDEA]]、[[NewDES]]、[[SAFER]]、[[CAST-128|CAST5]]、[[FEAL]]などがある。その多くはDESと同じ64ビットのブロック長で、そのまま代替として使えるようになっているが、鍵には64ビットか128ビットを使っているものが多い。[[ソビエト連邦]]では[[GOST (ブロック暗号)|GOST]]アルゴリズムが導入された。これはブロック長64ビットで256ビットの鍵を使っており、後に[[ロシア]]でも使われた。

DES自身をもっと安全な形にして再利用することもできる。かつてDESを使っていたところでは、DESの特許権保持者の1人が考案した[[トリプルDES]] (TDES) を使っている（[[Federal Information Processing Standards|FIPS]] Pub 46-3 参照）。この方式では2つ (2TDES) ないし3つ (3TDES) の鍵を用いて、暗号‐復号‐暗号の順でDESを3回行なう事で暗号化する。TDESは十分安全だが、極めて時間がかかる。それほど計算量が増えない代替方式として[[DES-X]]があり、鍵長を長くしてDESの処理の前後で外部鍵をXORする。[[GDES]]はDESの暗号処理を高速にする方式だが、差分解読法に弱いことが分かっている。

その後NISTがDESに代わる米国標準暗号方式 Advanced Encryption Standard (AES) を公募した。そして2000年10月、ベルギーの{{仮リンク|ホァン・ダーメン|en|Joan_Daemen}}と[[フィンセント・ライメン]]により提案されたRijndael（ラインデール）が新しい米国標準暗号方式[[Advanced Encryption Standard|AES]]に選ばれた。[[トリプルDES]]のような[[アドホック|ad-hoc]]な方法で設計された暗号方式とは異なり、AESは[[SPN構造]]と呼ばれるより整備された構造を持つ暗号方式である。公募には他に[[RC6]]、[[Serpent (暗号)|Serpent]]、[[MARS (暗号)|MARS]]、[[Twofish]]も応募したがどれも選ばれなかった。AESは2001年11月に FIPS 197 として正式に公表された。

==セキュリティと解読==
DESの解読法については他のブロック暗号よりも多数の情報があるが、今も最も実用的な攻撃法は総当り攻撃である。暗号解読上の各種特性が知られており、3種類の理論上の攻撃方法が知られている。それらは総当り攻撃よりも理論上は計算量が少ないが、非現実的な量の既知平文か選択平文を必要とし、実用化はされていない。

===総当り攻撃===
[[ファイル:Board300.jpg|thumb|The [[電子フロンティア財団|EFF]]が25万ドルで製作したDES解読機。1,856のカスタムチップで構成され、DESの鍵を総当りで数日間で破ることができる。写真は Deap Crack チップをいくつか装備したDES解読機用回路基板。]] 

どんな暗号についても、最も基本となる攻撃法は[[総当り攻撃]]、すなわち鍵のとりうる値を全て試す方法である。鍵の長さが鍵のとりうる値の個数に直接関係してくるため、総当りが現実的かどうかも鍵の長さで決まる。DESについては標準として採用される以前から鍵の短さが懸念されていた。NSAを含む外部コンサルタントを交えた議論の結果、1つのチップで暗号化できるよう鍵の長さを128ビットから56ビットに減らすことになった<ref name="stallings-2006">Stallings, W. ''Cryptography and network security:principles and practice''. Prentice Hall, 2006. p. 73</ref>。

学界では様々なDES解読機が提案されてきた。1977年、ディフィーとヘルマンは1日でDESの鍵を見つけることができるマシンのコストを2000万ドルと見積もった。1993年になると、ウィーナーは7時間で鍵を見つけることができる機械のコストを100万ドルと見積もった。しかし、そのような初期の提案に基づいて実際に解読機を製作した例はないし、少なくともそのような実例が公表されたことはなかった。DESの脆弱性が実際に示されたのは1990年代後半のことである。1997年、[[RSAセキュリティ]]は一連のコンテストを主催し、DESで暗号化されたメッセージを最初に解読したチームに1万ドルを賞金として提示した。このコンテストで優勝したのは、Rocke Verser、Matt Curtin、Justin Dolske が主導する [[:en:DESCHALL Project|DESCHALL Project]] で、インターネット上の数千台のコンピュータのアイドル時間（何もしていない時間）を利用したプロジェクトだった。1998年には[[電子フロンティア財団]] (EFF) が約25万ドルをかけてDES解読機を製作した。EFFの意図は、DESを理論上だけでなく実際に破ることができることを示すことであり、「多くの人々は実際に自分の目で見るまで真実を信じようとしない。DESを数日間で破ることができるマシンを実際に示すことで、DESによるセキュリティが信用できないことを明らかにできる」と述べている。この機械は2日強かけて総当り攻撃で鍵を見つけることができる。1999年1月に行われた3回目のコンテストでは、22時間で[[distributed.net]]によりDESが解読された<ref>{{cite web|url=https://www.distributed.net/images/d/d7/19990119_-_PR_-_release-des3.pdf|title=US GOVERNMENT'S ENCRYPTION STANDARD BROKEN IN LESS THAN A DAY|date=1999-01-19|accessdate=2016-10-09|publisher=distributed.net|language=English|format=PDF}}</ref>。この解読にはEFFのDES解読機とインターネット経由で募集された10万台の計算機が用いられた。

もう1つのDES解読機として[http://www.copacobana.org/ COPACOBANA]（cost-optimized parallel code breaker の略）が2006年、[[ドイツ]]の[[ルール大学ボーフム]]と[[キール大学 (ドイツ)|キール大学]]のチームで開発された。EFFの解読機とは異なり、COPACOBANAは一般に入手可能な部品（集積回路）のみを使っている。20個のDIMMモジュールで構成され、それぞれに6個の[[FPGA]]（[[ザイリンクス|XILINX]] Spartan3-1000）を装備し、それらが並列に動作する。FPGAを使っているため、DES以外の暗号解読にも応用可能である。COPACOBANAの重要な特徴はその低コストであり、1台を約1万ドルで製作できる。EFFのDES解読機に比べて約25分の1であり、8年間の物価上昇率を考慮すれば約30分の1ということができる。

===総当り攻撃よりも高速な攻撃法===
総当り攻撃よりも少ない計算量で16ラウンドのDESを破ることができる攻撃法が3種類知られている。[[差分解読法]] (DC)、[[線形解読法]] (LC)、[[:en:Davies' attack|Davies' attack]] である。しかし、これらの攻撃法は理論上のものであって、実際に応用するのは現実的ではない。これらを certificational weaknesses と呼ぶこともある。

;差分解読法
:[[1980年代]]末に[[エリ・ビハム]]と[[アディ・シャミア]]が再発見した。IBMとNSAにはそれ以前から知られていたが、秘密にされていた。16ラウンドのDESを破るには、2<sup>47</sup>の選択平文を必要とする。DESはDCへの耐性を考慮して設計されている。
;線形解読法
:1993年、[[松井充]]が発見。2<sup>43</sup>の既知平文を必要とする。これを実際に実装して(Matsui, 1994)、DESの解読実験が行われている。DESがこの解読法への耐性を考慮して設計されたという証拠はない。1994年には、これを拡張した ''multiple linear cryptanalysis'' (Kaliski and Robshaw) が提案され、その後も改良が Biryukov らによって行われている。研究によると、複数の線形近似を用いることで必要なデータ量が4分の1になる（つまり、2<sup>43</sup>を2<sup>41</sup>に減らせる）ことが示唆されている。また、選択平文を使った線形解読法でも同様にデータ量を削減できる (Knudsen and Mathiassen, 2000)。Junod (2001) は実験によって線形解読法の時間計算量を測定し、DESの解読は予想よりも時間がかからず 2<sup>39</sup> から 2<sup>41</sup> になるとした。
;Davies' attack
:差分解読法も線形解読法もDESだけに限らずに任意の暗号解読にも使えるが、Davies' attack はDES専用の解読法であり、[[ドナルド・ワッツ・デービス|ドナルド・デービス]]が1980年代に提案して、ビハムと[[:en:Alex Biryukov|Biryukov]] (1997) が改良を施した。最も強力な形式の攻撃には 2<sup>50</sup> の既知平文を必要とし、計算量も 2<sup>50</sup>、成功率は51%である。

ラウンド数を減らした暗号（DESの16ラウンドを減らしたもの）への攻撃法も提案されている。そのような研究によってラウンド数がどれだけあれば安全かという考察も行われている。また、16ラウンドのDESにどれだけ安全マージンがあるかも研究されてきた。1994年にはラングフォードとヘルマンが差分解読法と線形解読法を組み合わせた[[差分線形解読法]]を提案した。改良版の解読法では、9ラウンドのDESを 2<sup>15.8</sup> の既知平文を使って 2<sup>29.2</sup> の時間計算量で破ることができる (Biham et al., 2002)。

===その他の暗号解読上の特性===
DESには相補性がある。すなわち次が成り立つ。
:''E<sub>k</sub>(P) = C ⇔ E<sub><span style="text-decoration:overline">K</span></sub>(<span style="text-decoration:overline">P</span>) = <span style="text-decoration:overline">C</span>''
<!-- 添え字のオーバーラインがエラーになるので <math>E_K(P)=C \Leftrightarrow E_\overline{K}(\overline{P})=\overline{C}</math> -->
ここで <math>\overline{x}</math> は <math>x</math> のビット毎の反転である。<math>E_K</math> は鍵 <math>K</math> を使った暗号化を意味する。<math>P</math> は平文、<math>C</math> は暗号ブロック列である。相補性があるということは、[[総当り攻撃]]に必要な試行回数は2分の1で済むことを意味する。

DESには4つのいわゆる「弱い鍵」がある。暗号化 (''E'') と復号 (''D'') で弱い鍵を使うと、どちらも同じ効果がある。
:<math>E_K(E_K(P))=P</math> または <math>E_K=D_K</math>
また、6組の「やや弱い鍵」もある。弱い鍵の1つ <math>K_1</math> を使った暗号化は、ペアのもう一方の <math>K_2</math> を使った復号と等価である。
:<math>E_{K_1}(E_{K_2}(P))=P</math> または <math>E_{K_2}=D_{K_1}</math>
弱い鍵ややや弱い鍵を実装で使わないようにするのは容易である。もともと無作為に鍵を選んでも、それらを選ぶ確率は極めて低い。それらの鍵は理論上は他の鍵より弱いわけではなく、攻撃に際しても特に利用できるわけでもない。

DESは[[群 (数学)|群]]にならないことが証明されている。つまり、集合 <math>\{E_K\}</math>（鍵 <math>K</math> がとりうる全ての値の集合）は[[関数合成]]において群ではないし、1つの群に閉じていない (Campbell and Wiener, 1992)。これがもし群であるならば、DESは容易に破ることができ、トリプルDESにしても安全性は向上しなかったとされている。

DESの暗号学的安全性は最大でも約64ビットである。例えば、個々のラウンド鍵を元の1つの鍵から生成せずそれぞれ独立に供給すれば、安全性は768ビットになりそうなものだが、この限界によりそうならないことが知られている。

==関連項目==
*[[トリプルDES]]
*[[Advanced Encryption Standard|AES]]
*[[暗号理論]]
*[[スキップジャック (暗号)]]
*[[共通鍵暗号]]

==脚注・出典==
{{reflist|2}}

==参考文献==
*{{cite journal|author=Biham, Eli and [[アディ・シャミア|Adi Shamir]]|title=Differential Cryptanalysis of DES-like Cryptosystems|journal=Journal of Cryptology|volume=4|issue=1|year=1991|pages=3–72|url=http://www.springerlink.com/content/k54h077np8714058/|doi=10.1007/BF00630563}} ([http://nfotemple.free.fr/site_cryptokg/site_roy/differential%20cryptanalysis%20of%20des-like%20cryptosystems.pdf preprint])
*Biham, Eli and Adi Shamir, Differential Cryptanalysis of the Data Encryption Standard, Springer Verlag, 1993. ISBN 0-387-97930-1, ISBN 3-540-97930-1.
*Biham, Eli and Alex Biryukov:An Improvement of Davies' Attack on DES. J. Cryptology 10(3):195–206 (1997)
*Biham, Eli, Orr Dunkelman, Nathan Keller:Enhancing Differential-Linear Cryptanalysis. ASIACRYPT 2002:pp254–266
*Biham, Eli. A Fast New DES Implementation in Software [http://cryptome.org/jya/cracking-des/cracking-des.htm Cracking DES:Secrets of Encryption Research, Wiretap Politics, and Chip Design], [[電子フロンティア財団|Electronic Frontier Foundation]]
*{{cite journal|author=Biryukov, A, C. De Canniere and M. Quisquater|title=On Multiple Linear Approximations|journal=Lecture Notes in Computer Science|volume=3152|year=2004|pages=1–22|url=http://www.springerlink.com/content/16udaqwwl9ffrtxt/|doi=10.1007/b99099}} ([http://www.esat.kuleuven.ac.be/~abiryuko/mla.pdf preprint]).
*Campbell, Keith W., Michael J. Wiener:DES is not a Group. CRYPTO 1992:pp512–520
*Coppersmith, Don. (1994). [https://web.archive.org/web/20070316233309/http://www.research.ibm.com/journal/rd/383/coppersmith.pdf The data encryption standard (DES) and its strength against attacks]. ''IBM Journal of Research and Development'', '''38'''(3), 243–250.
*[[ホイットフィールド・ディフィー|Diffie, Whitfield]] and [[マーティン・ヘルマン|Martin Hellman]], "Exhaustive Cryptanalysis of the NBS Data Encryption Standard" IEEE Computer 10(6), June 1977, pp74–84
*Ehrsam et al., Product Block Cipher System for Data Security, {{US patent|3962539}}, Filed February 24, 1975
*[[ジョン・ギルモア|Gilmore, John]], "Cracking DES:Secrets of Encryption Research, Wiretap Politics and Chip Design", 1998, O'Reilly, ISBN 1-56592-520-3.
*Junod, Pascal. {{Wayback|url=http://crypto.junod.info/sac01.html|date=20090527065754|title=On the Complexity of Matsui's Attack.}} Selected Areas in Cryptography, 2001, pp199–211.
*Kaliski, Burton S., Matt Robshaw:Linear Cryptanalysis Using Multiple Approximations. CRYPTO 1994:pp26–39
*Knudsen, Lars, John Erik Mathiassen:A Chosen-Plaintext Linear Attack on DES. Fast Software Encryption - FSE 2000:pp262–272
*Langford,  Susan K., Martin E. Hellman:Differential-Linear Cryptanalysis. CRYPTO 1994:17–25
*Levy, Steven, Crypto:How the Code Rebels Beat the Government—Saving Privacy in the Digital Age, 2001, ISBN 0-14-024432-8.
*{{cite journal|first=Mitsuru|last=Matsui|title=Linear Cryptanalysis Method for DES Cipher|journal=Lecture Notes in Computer Science|volume=765|year=1994|pages=386–397|url=http://www.springerlink.com/content/92509p5l4ravyn62/|doi=10.1007/3-540-48285-7}}
*{{cite journal|author=Mitsuru Matsui|title=The First Experimental Cryptanalysis of the Data Encryption Standard|journal=Lecture Notes in Computer Science|volume=839|year=1994|pages=1–11|url=http://www.springerlink.com/content/vrteugmt7erqqbw1/|doi=10.1007/3-540-48658-5_1}}
*National Bureau of Standards, Data Encryption Standard, FIPS-Pub.46. National Bureau of Standards, U.S. Department of Commerce, Washington D.C., January 1977.

==外部リンク==
*[https://csrc.nist.gov/csrc/media/publications/fips/46/3/archive/1999-10-25/documents/fips46-3.pdf FIPS 46-3:DES標準についての公式文書] (PDF);[http://www.itl.nist.gov/fipspubs/fip46-2.htm やや古いHTML版]
*[https://www.copacobana.org/ COPACOBANA] 1万ドルでDESを破るマシン。ルール大学ボーフムとキール大学がFPGAを使って製作。
*[https://datatracker.ietf.org/doc/html/rfc4772 RFC4772 :Security Implications of Using the Data Encryption Standard (DES)]

{{cryptography navbox|block}}

[[Category:アメリカ国家安全保障局]]