（データ暗号化標準）、略してDES（デス、ディーイーエス）は、アメリカ合衆国の旧国家暗号規格、もしくはその規格で規格化されている共通鍵暗号である。ブロック暗号の一種であり、1976年国立標準局 (NBS) がアメリカ合衆国の公式連邦情報処理標準 (FIPS) として採用し、その後国際的に広く使われた。56ビットの鍵を使った共通鍵暗号を基盤としている。そのアルゴリズムは、機密設計要素、比較的短い鍵長、アメリカ国家安全保障局 (NSA) がバックドアを設けたのではないかという疑いなどで、当初物議をかもしていた。結果としてDESは、現代のブロック暗号とその暗号解読の理解に基づいて学究的に徹底した精査を受けた。DESは今では多くの用途において安全ではないと見なされている。これは主に56ビットという鍵長が短すぎることに起因する。1999年1月、distributed.netと電子フロンティア財団は共同で、22時間15分でDESの鍵を破ったことを公表した。この暗号の理論上の弱さを示した解析結果もあるが、そのような弱さを実際に利用することが可能というわけではない。アルゴリズム自体は実用上安全であるとされ、トリプルDESという形で使われているが、理論的攻撃方法は存在する。近年、 (AES)に取って代わられた。なお、標準としてのDESとアルゴリズムを区別することがあり、アルゴリズムを (DEA)と称することがある。DESの起源は1970年代初めに遡る。1972年、アメリカ政府はコンピュータセキュリティが重要であるという研究結果を得た。そこでNBS（National Bureau of Standard。合衆国標準局。現在のNIST（アメリカ国立標準技術研究所））が、政府全体で機密情報を暗号化するための標準規格が必要だと判断した。それに応じて1973年5月15日、NSAと相談の上、NBSが厳しい設計基準を満たした暗号を公募した。しかし応募のいずれも条件を満たしていなかったため、1974年8月27日に2回目の公募を行った。今回はIBMの応募した案が条件を満たしていると思われた。それは、以前からあったアルゴリズムに基づき1973年から1974年に開発されたホルスト・ファイステルの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構造に基づいて設計された。1975年3月17日、規格案としてのDESが "Federal Register" に発表された。そしてコメントが募集され、翌年には2回ワークショップを開催してこの規格案について議論した。各所から様々な批判が寄せられた。中には公開鍵暗号の先駆者であるマーティン・ヘルマンとホイットフィールド・ディフィーの批判があり、鍵長が短いという点と謎めいた「Sボックス」がNSAによる不適切な干渉を意味しているのではないかと指摘した。それは、このアルゴリズムを諜報機関が密かに弱め、その諜報機関だけが暗号化されたメッセージを容易に解読できるようにしたのではないかという疑いが持たれたのである。アラン・コンハイム（DES設計者の1人）はそれについて「我々はSボックスをワシントンに送った。戻ってきたものは送ったものとは全く異なっていた」と述べた。アメリカ合衆国上院諜報特別委員会がNSAの行為に不適切な干渉があったかどうかを調査した。調査結果の公開された要約には次のように書かれている。しかし、同時に次のようなことも判明している。DES設計チームのウォルト・タックマンは「我々はIBM内でIBMの人員だけでDESアルゴリズム全体を開発した。NSAに命じられて変更した部分は1つもない」と述べた。一方、機密解除されたNSAの暗号史に関する本には次のように書かれている。Sボックスに関する嫌疑の一部は1990年に鎮められることになった。同年、エリ・ビハムとアディ・シャミア（RSAのS）が差分解読法を独自に発見して公表した。差分解読法はブロック暗号を破る汎用技法である。DESのSボックスは無作為に選ばれた場合よりもこの攻撃法にずっと抵抗力があり、IBMが1970年代にこの攻撃法を知っていたことを強く示唆していた。1994年、ドン・コッパースミスがSボックスの元々の設計基準について一部を公表したことで、それが裏付けられた。スティーブン・レビーによれば、IBMでは1974年に差分解読法を発見していたが、NSAがそれを秘密にするよう要請していたという。コッパースミスはIBMの方針について「（差分解読法）は非常に強力なツールであり、様々な方式に応用でき、これを公にすると国家の安全に悪い影響を及ぼすことが懸念された」と述べている。レビーはタックマンの言葉として「彼らは我々のあらゆる文書に極秘というスタンプを押させようとした…それらは合衆国政府の機密と見なされたので、我々は実際にそれらに番号を振り、金庫に入れた。彼らがそうしろと言ったから、そうしたまでだ」と書いている。批判はあったがDESは1976年11月連邦規格として承認され、1977年1月15日には 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年まで承認している。このアルゴリズムは ANSI X3.92、NIST SP 800-67、ISO/IEC 18033-3 でも指定されている（TDEAの要素として）。もう1つの理論的攻撃法である線形解読法は1994年に公表された。1998年には総当り攻撃で実用的な時間でDESを破れることが実証され、アルゴリズムの更新の必要性が高まった。これら攻撃法については後の節で詳述する。DESの登場は暗号研究、特に暗号解読法の研究を活発化させる触媒の役割を果たした。NISTは後にDESについて次のように述べている。DESは原型ともいうべきブロック暗号であり、固定ビット長の平文を入力とし、一連の複雑な操作によって同じ長さの暗号文を出力するアルゴリズムである。DESの場合、ブロック長は64ビットである。また、変換をカスタマイズする鍵を使うため、暗号化に使った鍵を知っている者だけが復号できる。鍵は見た目は64ビットだが、そのうち8ビットはパリティチェックに使うため、アルゴリズム上の実際の鍵の長さは56ビットである。他のブロック暗号と同様、DES自体は暗号化の安全な手段ではなく、暗号利用モードで使う必要がある。FIPS-81 はDES用のいくつかのモードを示している。その他のDESの利用法については FIPS-74 に詳しい。アルゴリズムの全体構造を図1に示す。16の処理工程があり、それらを「ラウンド」と呼ぶ。また、最初と最後に並べ替え処理があり、それぞれ "IP" および "FP" と呼ぶ。"IP" と "FP" はちょうど逆の処理を行う。"IP" と "FP" は暗号化にはほとんど関係ないが、1970年代のハードウェアでブロックの入出力を行う部分として含まれており、同時にそれによってソフトウェアによるDESの処理が遅くなる原因にもなっている。ラウンドでの処理の前にブロックは半分（32ビット）ずつに分けられ、それぞれ異なる処理を施される。この十字交差構造をFeistel構造と呼ぶ。Feistel構造を使うと、暗号化と復号は非常に良く似た処理になる。違いは、復号ではラウンド鍵を逆の順序で適用するという点だけであり、アルゴリズムは同一である。このため実装が単純化でき、特にハードウェアで実装する場合に両者を別々に実装する必要が無い。⊕ という記号は排他的論理和 (XOR) を意味する。"F-関数"はブロックの半分を何からの鍵でかき混ぜる。F-関数の出力をブロックの残り半分と結合し、次のラウンドに行く前にその半分同士を入れ替える。最後のラウンドの後は入れ替えを行わない。これは、暗号化と復号を似たプロセスで行うFeistel構造の特徴である。図2にあるF-関数はブロックの半分（32ビット）を一度に動作する。以下の4段階がある。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については安全性とソフトウェア処理が相対的に遅い点が懸念され、1980年代末から1990年代初めごろから研究者らが様々なブロック暗号を代替案として提案してきた。例えば、RC5、Blowfish、IDEA、NewDES、SAFER、CAST5、FEALなどがある。その多くはDESと同じ64ビットのブロック長で、そのまま代替として使えるようになっているが、鍵には64ビットか128ビットを使っているものが多い。ソビエト連邦ではGOSTアルゴリズムが導入された。これはブロック長64ビットで256ビットの鍵を使っており、後にロシアでも使われた。DES自身をもっと安全な形にして再利用することもできる。かつてDESを使っていたところでは、DESの特許権保持者の1人が考案したトリプルDES (TDES) を使っている（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月、ベルギーのとフィンセント・ライメンにより提案されたRijndael（ラインデール）が新しい米国標準暗号方式AESに選ばれた。トリプルDESのようなad-hocな方法で設計された暗号方式とは事なり、AESはSPN構造と呼ばれるより整備された構造を持つ暗号方式である。公募には他にRC6、Serpent、MARS、Twofishも応募したが選ばれなかった。AESは2001年11月に FIPS 197 として正式に公表された。DESの解読法については他のブロック暗号よりも多数の情報があるが、今も最も実用的な攻撃法は総当り攻撃である。暗号解読上の各種特性が知られており、3種類の理論上の攻撃方法が知られている。それらは総当り攻撃よりも理論上は計算量が少ないが、非現実的な量の既知平文か選択平文を必要とし、実用化はされていない。どんな暗号についても、最も基本となる攻撃法は総当り攻撃、すなわち鍵のとりうる値を全て試す方法である。鍵の長さが鍵のとりうる値の個数に直接関係してくるため、総当りが現実的かどうかも鍵の長さで決まる。DESについては標準として採用される以前から鍵の短さが懸念されていた。NSAを含む外部コンサルタントを交えた議論の結果、1つのチップで暗号化できるよう鍵の長さを128ビットから56ビットに減らすことになった。学界では様々なDES解読機が提案されてきた。1977年、ディフィーとヘルマンは1日でDESの鍵を見つけることができるマシンのコストを2000万ドルと見積もった。1993年になると、ウィーナーは7時間で鍵を見つけることができる機械のコストを100万ドルと見積もった。しかし、そのような初期の提案に基づいて実際に解読機を製作した例はないし、少なくともそのような実例が公表されたことはなかった。DESの脆弱性が実際に示されたのは1990年代後半のことである。1997年、RSAセキュリティは一連のコンテストを主催し、DESで暗号化されたメッセージを最初に解読したチームに1万ドルを賞金として提示した。このコンテストで優勝したのは、Rocke Verser、Matt Curtin、Justin Dolske が主導する で、インターネット上の数千台のコンピュータのアイドル時間（何もしていない時間）を利用したプロジェクトだった。1998年には電子フロンティア財団 (EFF) が約25万ドルをかけてDES解読機を製作した。EFFの意図は、DESを理論上だけでなく実際に破ることができるということを示すことであり、「多くの人々は実際に自分の目で見るまで真実を信じようとしない。DESを数日間で破ることができるマシンを実際に示すことで、DESによるセキュリティが信用できないことを明らかにできる」と述べている。この機械は2日強かけて総当り攻撃で鍵を見つけることができる。1999年1月に行われた3回目のコンテストでは、22時間でdistributed.netによりDESが解読された。この解読にはEFFのDES解読機とインターネット経由で募集された10万台の計算機が用いられた。もう1つのDES解読機として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)、 である。しかし、これらの攻撃法は理論上のものであって、実際に応用するのは現実的ではない。これらを certificational weaknesses と呼ぶこともある。ラウンド数を減らした暗号（DESの16ラウンドを減らしたもの）への攻撃法も提案されている。そのような研究によってラウンド数がどれだけあれば安全かという考察も行われている。また、16ラウンドのDESにどれだけ安全マージンがあるかも研究されてきた。1994年にはラングフォードとヘルマンが差分解読法と線形解読法を組み合わせた差分線形解読法を提案した。改良版の解読法では、9ラウンドのDESを 2 の既知平文を使って 2 の時間計算量で破ることができる (Biham et al., 2002)。DESには相補性がある。すなわち次が成り立つ。ここで formula_1 は formula_2 のビット毎の反転である。formula_3 は鍵 formula_4 を使った暗号化を意味する。formula_5 は平文、formula_6 は暗号ブロック列である。相補性があるということは、総当り攻撃に必要な試行回数は2分の1で済むことを意味する。DESには4つのいわゆる「弱い鍵」がある。暗号化 ("E") と復号 ("D") で弱い鍵を使うと、どちらも同じ効果がある。また、6組の「やや弱い鍵」もある。弱い鍵の1つ formula_9 を使った暗号化は、ペアのもう一方の formula_10 を使った復号と等価である。弱い鍵ややや弱い鍵を実装で使わないようにするのは容易である。もともと無作為に鍵を選んでも、それらを選ぶ確率は極めて低い。それらの鍵は理論上は他の鍵より弱いわけではなく、攻撃に際しても特に利用できるわけでもない。DESは群にならないことが証明されている。つまり、集合 formula_13（鍵 formula_4 がとりうる全ての値の集合）は関数合成において群ではないし、1つの群に閉じていない (Campbell and Wiener, 1992)。これがもし群であるならば、DESは容易に破ることができ、トリプルDESにしても安全性は向上しなかったとされている。DESの暗号学的安全性は最大でも約64ビットである。例えば、個々のラウンド鍵を元の1つの鍵から生成せずそれぞれ独立に供給すれば、安全性は768ビットになりそうなものだが、この限界によりそうならないことが知られている。

出典:wikipedia