Data Encryption Standard

Data Encryption Standard (DES) について

Data Encryption Standard（データ暗号化標準）、略してDESは、かつてアメリカ合衆国で国家暗号規格として採用されていた共通鍵[[暗号]]です。1976年に国立標準局（NBS、現在のNIST）によってFIPS（連邦情報処理標準）として採用され、国際的にも広く使われました。DESは56ビットの鍵を使用するブロック[[暗号]]で、そのアルゴリズムは当初、機密設計要素や短い鍵長、そしてアメリカ国家[[安全保障局]]（NSA）の関与疑惑から物議を醸しました。しかし、これらの議論を経てDESは、現代のブロック[[暗号]]の理解を深めるための徹底的な研究対象となりました。

DESの安全性

現代においてDESは、その56ビットという短い鍵長が原因で、多くの用途において安全ではないとみなされています。1999年には、分散コンピューティングによる鍵解読が22時間15分で成功しました。DESのアルゴリズム自体には理論的な弱点が存在しますが、実際の攻撃に利用することは困難です。しかし、理論的な攻撃方法は存在し、今日ではより安全なAdvanced Encryption Standard (AES)にその役割を譲っています。

DES制定までの経緯

1970年代初頭、アメリカ政府はコンピュータセキュリティの重要性を認識し、NBSが政府全体で機密情報を暗号化するための標準規格の必要性を感じました。1973年、NBSはNSAと協力し、厳しい設計基準を満たす暗号を公募しましたが、応募された暗号はいずれも基準を満たしませんでした。1974年、IBMが提案したLucifer暗号が採用されました。これは、ホルスト・ファイステルを中心とするIBMのチームによって開発されたFeistel構造を持つ暗号です。

NSAの関与

1975年、DESの規格案が発表されると、その短い鍵長と謎めいた「Sボックス」がNSAによる不適切な干渉を意味するのではないかと批判されました。この疑惑は、NSAが暗号アルゴリズムを弱め、諜報機関だけが容易に解読できるようにしたのではないかというものでした。しかし、アメリカ合衆国上院諜報特別委員会はNSAの行為を調査し、NSAがアルゴリズムの設計を改変した事実は確認されなかったと発表しました。ただし、NSAがSボックスの開発を支援し、IBMに鍵長を短くするよう働きかけたことは認めています。

1990年、エリ・ビハムとアディ・シャミアによって差分解読法が発見され、DESのSボックスがこの攻撃法に抵抗力があることが判明しました。これは、IBMが1970年代に差分解読法を知っていたことを示唆するものでした。ドン・コッパースミスは、Sボックスの設計基準の一部を公開し、IBMがこの技術を知っていたことを裏付けました。スティーブン・レビーによれば、IBMは1974年に差分解読法を発見していたものの、NSAがそれを秘密にするよう要請したということです。

標準暗号としてのDES

批判はありましたが、DESは1976年に連邦規格として承認され、1977年にFIPS PUB 46として公表され、政府の非機密通信での利用が認められました。1981年にはANSIの民間標準規格にもなり、1983年、1988年、1993年、1999年と再承認され、最終的にトリプルDESが定められました。しかし、2002年5月26日には、DESは公開コンペによって選ばれたAESに取って代わられました。2005年にはFIPS 46-3は廃止されましたが、NISTはトリプルDESの政府重要情報での利用を2030年まで認めています。

DESの構造

DESはブロック[[暗号]]であり、64ビットの平文を固定長で暗号化し、同じ長さの暗号文を出力します。暗号化に使用する鍵を知っている者だけが復号できます。鍵は64ビットに見えますが、実際には56ビットが使用され、残りの8ビットはパリティチェックに使われます。DES自体は安全な暗号化手段ではなく、暗号利用モードでの使用が必要です。

全体構造

DESのアルゴリズムは、16の処理工程（ラウンド）と初期および最終の並べ替え処理（IPとFP）から構成されます。IPとFPは互いに逆の処理を行い、暗号化には直接関係しませんが、1970年代のハードウェア環境での入出力を考慮したものでした。各ラウンドでは、ブロックが半分に分割され、Feistel構造と呼ばれる構造で処理されます。この構造により、暗号化と復号は非常に似た処理となり、実装を簡素化できます。

Feistel関数

Feistel関数（F関数）は、ブロックの半分（32ビット）を処理し、以下の4段階を経ます。

1. Expansion（拡張）: 32ビットを48ビットに拡張します。
2. Key mixing（鍵混合）: ラウンド鍵と拡張されたビットをXOR演算で結合します。
3. Substitution（置換）: 6ビットずつに分割し、Sボックスに入力して非線形な変換を行います。
4. Permutation（並べ替え）: Sボックスの出力である32ビットに対して固定の並べ替えを行います。

これらの処理を通じて、暗号化に必要な「拡散とかく乱」が実現されます。

鍵スケジュール

鍵スケジュールは、56ビットの鍵から各ラウンドで使用する48ビットのラウンド鍵を生成します。このプロセスでは、鍵のビットをローテートさせ、異なるビットが各ラウンドで使用されるようにします。復号では、暗号化とは逆順でラウンド鍵が適用されます。

DESに代わるアルゴリズム

DESの安全性とソフトウェアでの処理速度が懸念され、1980年代後半から多くの代替暗号が提案されました。例えば、RC5、Blowfish、IDEAなどがあります。また、DESをより安全にしたトリプルDESやDES-Xも利用されました。その後、NISTはDESに代わる新しい標準暗号としてAESを公募し、2000年にRijndaelが選ばれました。AESはSPN構造を持つより整備された構造を持ちます。

セキュリティと解読

DESの解読法は数多く研究されていますが、最も現実的な攻撃は総当たり攻撃です。他にも理論的な攻撃法はありますが、現実的な実行は困難です。

総当たり攻撃

総当たり攻撃は、全ての鍵の可能性を試す最も基本的な攻撃法です。DESの56ビットという鍵長は、当時から短いと指摘されていました。1990年代後半には、総当たり攻撃によるDESの解読が実際に成功しました。電子フロンティア財団（EFF）が製作したDES解読機は、2日強でDESの鍵を解読することができました。1999年にはdistributed.netによって、22時間でDESが解読されました。また、2006年には、より低コストのDES解読機COPACOBANAが開発されました。

総当たり攻撃より高速な攻撃法

総当たり攻撃よりも少ない計算量でDESを破ることができる攻撃法には、差分解読法、線形解読法、Davies' attackがあります。これらの攻撃法は理論上のものであり、実際に応用するのは困難です。

1. 差分解読法: 選択平文を必要とする攻撃法で、DESの設計にも影響を与えました。
2. 線形解読法: 既知平文を必要とする攻撃法で、実験的な解読も行われています。
3. Davies' attack: DES専用の攻撃法で、既知平文を必要とします。

その他の暗号解読上の特性

DESには、相補性、弱い鍵、やや弱い鍵などの特性があります。これらの特性は、DESの安全性に影響を与えるものではありませんが、DESの暗号理論的な分析において重要な役割を果たします。DESが群にならないことも証明されており、このことはトリプルDESの安全性を保証する上で重要です。

まとめ

DESは、暗号技術の発展に大きく貢献した暗号アルゴリズムです。その歴史的な役割、設計、安全性に関する議論は、現代の暗号技術を理解する上で重要な教訓を与えてくれます。

参考文献

Biham, Eli and Adi Shamir (1991). “Differential Cryptanalysis of DES-like Cryptosystems”. Journal of Cryptology 4 (1): 3–72.
Biham, Eli and Adi Shamir, Differential Cryptanalysis of the Data Encryption Standard, Springer Verlag, 1993.
Diffie, Whitfield and Martin Hellman, "Exhaustive Cryptanalysis of the NBS Data Encryption Standard" IEEE Computer 10(6), June 1977, pp74–84
National Bureau of Standards, Data Encryption Standard, FIPS-Pub.46. National Bureau of Standards, U.S. Department of Commerce, Washington D.C., January 1977.

もう一度検索