暗号化にはほとんど関係ないが、1970年代のハードウェアでブロックの入出力を行う部分として含まれており、同時にそれによってソフトウェアによるDESの処理が遅くなる原因にもなっている。ラウンドでの処理の前にブロックは半分(32ビット)ずつに分けられ、それぞれ異なる処理を施される。この十字交差構造をFeistel構造と呼ぶ。Feistel構造を使うと、暗号化と復号は非常に良く似た処理になる。違いは、復号ではラウンド鍵を逆の順序で適用するという点だけであり、アルゴリズムは同一である。このため実装が単純化でき、特にハードウェアで実装する場合に両者を別々に実装する必要が無い。F-関数はブロックの半分を何らかの鍵でかき混ぜる。F-関数の出力をブロックの残り半分と結合し、次のラウンドに行く前にその半分同士を入れ替える。最後のラウンドの後には入れ替えは行わない。これは、暗号化と復号を似たプロセスで行うFeistel構造の特徴である。Feistel(F)関数[編集]図2にあるF-関数はブロックの半分(32ビット)を一度に処理する。呼ばれる方式で32ビットを48ビットに拡張する。示されている部分である。入力のうち半分のビットの複製16ビット分を出力のビット列に追加する。その出力は8個の6ビットの部分からなり、それら6ビットのうちの中央4ビットは入力の対応する4ビットの部分と同じで、両端の1ビットずつは入力上で隣接する部分のビットの複製である。ラウンド鍵と上の出力結果をXOR操作で結合する。ラウンド鍵は48ビットで、もともとの鍵から「鍵スケジュール」(後述)によって16個のラウンド鍵が生成される。8個のSボックスは入力の6ビットから4ビットの出力を生成し、このときルックアップテーブルの形で提供される非線形な変換を行う。SボックスがDESの安全性の根幹であり、これが無かったならば暗号化の処理は線形であり容易に破ることができることになる。Sボックス群の出力である32ビットに固定の並べ替えを施す。このとき、各Sボックスの出力が次のラウンドでSボックスに展開されるとき、6個の異なるSボックスに分散するよう並べ替える。Sボックスでの置換とPボックスでの並べ替えとEでの拡張を交互に行うことで、クロード・シャノンが安全で実用的な暗号に必要な条件とした「拡散とかく乱」を提供する。鍵スケジュール[編集]図3は暗号化での「鍵スケジュール」、すなわちラウンド鍵を生成するアルゴリズムを示している。選ばれなかった8ビットは単に捨ててもよいし、パリティビットとして鍵のチェックに使ってもよい。その56ビットは2つの28ビットに分割され、その後別々に処理される。ラウンドを次に進める際にそれぞれを左に1ビットか2ビットローテートする(ラウンドによってローテートするビット数が異なる)。入力して48ビットのラウンド鍵を出力する。このときそれぞれの半分(28ビット)から24ビットずつを選び、並べ替えも左右別々に行う。ローテートを行うことでラウンドごとに選択するビットが変化する(PC-2自体は固定であり、毎回同じ位置のビットを選んで同じ順序で並べ替える)。各ビットは16ラウンドのうち、だいたい14回使われる。復号の際の鍵スケジュールもほぼ同様である。ラウンド鍵は暗号化のときとは逆順に適用される。その点を除けば暗号化と全く同じ工程で処理される。DESに代わるアルゴリズム[編集]DESについては安全性とソフトウェアによる処理が相対的に遅い点が懸念され、1980年代末から1990年代初めごろから研究者らが様々なブロック暗号を代替案として提案してきた。RC5、Blowfish、IDEA、NewDES、SAFER、CAST5、FEALなどがある。その多くはDESと同じ64ビットのブロック長で、そのまま代替として使えるようになっているが、鍵には64ビットか128ビットを使っているものが多い。ソビエト連邦ではGOSTアルゴリズムが導入された。これはブロック長64ビットで256ビットの鍵を使っており、後にロシアでも使われた。DES自身をもっと安全な形にして再利用することもできる。順でDESを3回行なう事で暗号化する。TDESは十分安全だが、極めて時間がかかる。それほど計算量が増えない代替方式としてDES-Xがあり、鍵長を長くしてDESの処理の前後で外部鍵をXORする。GDESはDESの暗号処理を高速にする方式だが、差分解読法に弱いことが分かっている。2000年10月、ベルギーのホァン・ダーメン(英語版)とフィンセント・ライメンにより提案されたRijndael(ラインデール)が新しい米国標準暗号方式AESに選ばれた。トリプルDESのようなad-hocな方法で設計された暗号方式とは異なり、AESはSPN構造と呼ばれるより整備された構造を持つ暗号方式である。公募には他にRC6、Serpent、MARS、Twofishも応募したがどれも選ばれなかった。して正式に公表された。セキュリティと解読[編集]DESの解読法については他のブロック暗号よりも多数の情報があるが、今も最も実用的な攻撃法は総当り攻撃である。暗号解読上の各種特性が知られており、3種類の理論上の攻撃方法が知られている。それらは総当り攻撃よりも理論上は計算量が少ないが、非現実的な量の既知平文か選択平文を必要とし、実用化はされていない。EFFが25万ドルで製作したDES解読機。1,856のカスタムチップで構成され、DESの鍵を総当りで数日間で破ることができる。どんな暗号についても、最も基本となる攻撃法は総当り攻撃、すなわち鍵のとりうる値を全て試す方法である。鍵の長さが鍵のとりうる値の個数に直接関係してくるため、総当りが現実的かどうかも鍵の長さで決まる。DESについては標準として採用される以前から鍵の短さが懸念されていた。NSAを含む外部コンサルタントを交えた議論の結果、1つのチップで暗号化できるよう鍵の長さを128ビットから56ビットに減らすことになった[20]。学界では様々なDES解読機が提案されてきた。1977年、ディフィーとヘルマンは1日でDESの鍵を見つけることができるマシンのコストを2000万ドルと見積もった。1993年になると、ウィーナーは7時間で鍵を見つけることができる機械のコストを100万ドルと見積もった。そのような初期の提案に基づいて実際に解読機を製作した例はないし、少なくともそのような実例が公表されたことはなかった。DESの脆弱性が実際に示されたのは1990年代後半のことである。1997年、RSAセキュリティは一連のコンテストを主催し、DESで暗号化されたメッセージを最初に解読したチームに1万ドルを賞金として提示した。インターネット上の数千台のコンピュータのアイドル時間(何もしていない時間)を利用したプロジェクトだった。約25万ドルをかけてDES解読機を製作した。EFFの意図は、DESを理論上だけでなく実際に破ることができることを示すことであり、「多くの人々は実際に自分の目で見るまで真実を信じようとしない。DESを数日間で破ることができるマシンを実際に示すことで、DESによるセキュリティが信用できないことを明らかにできる」と述べている。この機械は2日強かけて総当り攻撃で鍵を見つけることができる。1999年1月に行われた3回目のコンテストでは、22時間でdistributed.netによりDESが解読された[21]。この解読にはEFFのDES解読機とインターネット経由で募集された10万台の計算機が用いられた。略)が2006年、ドイツのルール大学ボーフムとキール大学のチームで開発された。EFFの解読機とは異なり、COPACOBANAは一般に入手可能な部品(集積回路)のみを使っている。Spartan3-1000)を装備し、それらが並列に動作する。FPGAを使っているため、DES以外の暗号解読にも応用可能である。COPACOBANAの重要な特徴はその低コストであり、1台を約1万ドルで製作できる。EFFのDES解読機に比べて約25分の1であり、8年間の物価上昇率を考慮すれば約30分の1ということができる。総当り攻撃よりも高速な攻撃法[編集]総当り攻撃よりも少ない計算量で16ラウンドのDESを破ることができる攻撃法が3種類知られている。これらの攻撃法は理論上のものであって、実際に応用するのは現実的ではない。差分解読法1980年代末にエリ・ビハムとアディ・シャミアが再発見した。IBMとNSAにはそれ以前から知られていたが、秘密にされていた。16ラウンドのDESを破るには、247の選択平文を必要とする。DESはDCへの耐性を考慮して設計されている。線形解読法1993年、松井充が発見。243の既知平文を必要とする。1994)、DESの解読実験が行われている。DESがこの解読法への耐性を考慮して設計されたという証拠はない。らによって行われている。研究によると、複数の線形近似を用いることで必要なデータ量が4分の1になる(つまり、243を241に減らせる)ことが示唆されている。