Double DES（ダブルDES）とは？仕組みと中間一致攻撃のリスクを徹底解説

DES（データ暗号化標準）の基礎知識

DES（Data Encryption Standard：データ暗号化標準）は対称鍵ブロック暗号の一種で、64ビットの平文と56ビットの鍵を入力として受け取り、64ビットの暗号文を出力します。DESの処理はPボックスとSボックスによって構成されており、Pボックスがビットを転置し、Sボックスがビットを置換することで暗号文を生成します。

DESは「LUCIFER」と呼ばれるFeistelブロック暗号の実装であり、16ラウンドからなるFeistel構造を採用しているのが特徴です。各ラウンドでは異なる部分鍵を使用できます。DESを学ぶことの大きな意義は、それが数多くの暗号アルゴリズムの基礎となっている点にあります。DESの仕組みを理解しておけば、現在主流となっている、より高速な暗号アルゴリズムや手法の実装・動作原理も容易に習得できるようになります。

Double DES（ダブルDES）とは

Double DESとは、同じ平文に対して2つのDES処理を連続的に適用する暗号化方式です。それぞれの段階で異なる鍵を使用して平文を暗号化します。Double DESの仕組みは比較的シンプルで、理解しやすいのが特徴です。

Double DESでは、k1とk2という2つの鍵を使用します。まず元の平文に鍵k1を使ってDESを実行し、暗号文を生成します。次に、その暗号文に対して今度は別の鍵k2を使って再度DESを実行します。最終的な出力は、一度暗号化されたテキストをさらに暗号化したものとなります。

復号の流れ

二重に暗号化された暗号文ブロックは、まず鍵K2を使って復号され、一度だけ暗号化された状態の暗号文へと戻ります。その後、この暗号文ブロックを鍵K1で復号することで、元の平文ブロックが取得されます。

鍵空間の大きさと総当たり攻撃

仮に1ビットの鍵しか使えない場合、可能な鍵は0と1の2通りです。2ビットの鍵であれば、(00, 01, 10, 11)の4通りの鍵値が存在します。

一般に、nビットの鍵を使用する場合、暗号解読者はすべての鍵候補を試し切るために2ⁿ回の操作を行う必要があります。さらに、nビットの異なる鍵を2つ使用する場合、鍵を破るには2²ⁿ回の試行が必要になると考えられます。

Double DESの場合、必要な鍵探索量は2^2×56、すなわち2¹¹²個の鍵に相当します。一見すると非常に安全に思えますが、ここで「中間一致攻撃（meet-in-the-middle attack）」という概念が登場します。この攻撃は、片側からは暗号化を、もう片側からは復号を実行し、両者の結果を中間で照合するという手法です。

中間一致攻撃の仕組み

暗号解読者が、あるメッセージについてP（平文ブロック）とC（対応する最終的な暗号文ブロック）という2つの基本情報を入手できたと仮定します。このとき、Double DESの動作は次のような数式で表現できます。

最初の暗号化の結果はTと呼ばれ、T = E_k1(P)と表されます（鍵K1でブロックPを暗号化することを意味します）。続いて、この暗号化済みブロックを別の鍵K2でさらに暗号化すると、C = E_K2(E_K1(P))となります（既に暗号化されたブロックTを別の鍵K2で暗号化し、その最終的な暗号文をCと呼びます）。