今回は、共有鍵暗号の１つである DES（Data Encryption Standard）暗号のアルゴリズムについて解説していこうと思います。

DES とは？

今回扱う DES による暗号と復号の流れを簡単に見てみましょう。

まず、送信者（アリス）が受信者（ボブ）に送りたいメッセージ（平文：m）を、ある「鍵」によって暗号化します。アリスは暗号化したメッセージをボブに送り、ボブがそのメッセージを復号できるように、暗号化に使用した鍵をボブに送信しておきます。ここで重要なことは、もし鍵が第三者に見られてしまったらメッセージを解読されてしまうので、鍵は安全な通信路で渡す必要があります。鍵と暗号化されたメッセージを受け取ったボブは、復号してアリスからのメッセージを読むことができます。

暗号の種類

DES は暗号の部類で言うと、対称鍵ブロック暗号と言います。

暗号アルゴリズムには大きく分けて２種類あります。

対称鍵暗号（共通鍵暗号）と非対称鍵暗号（公開鍵暗号）です。対称鍵暗号は、暗号と復号に同じ鍵が使用されます。これには、今回紹介する DES や AES、RC4 などが含まれます。

一方で、非対称鍵暗号とは暗号と復号で使用される鍵が異なります。これには、RSA や DH、DSA などが含まれます。

また、暗号にはストリーム暗号とブロック暗号の２種類があります。

ストリーム暗号は平文を小さい範囲（bit, byte, word）で逐次処理を行う暗号です。平文と鍵の XOR（排他的論理和）を取ることで暗号化と復号を行います。

ブロック暗号は、一定の大きさ（ブロック）の平文を処理します。ブロックサイズを超える平文を暗号化する際には、暗号化モード（いいね、または購入が多ければ他の記事で書きます）が適用されます。

つまり・・・DES はブロック暗号という種類の対称鍵暗号です。

それでは、DES はどうやって暗号化と復号を行なっているのか見ていきましょう。

DES のアルゴリズム

DES の基本構造はファイステルネットワーク（Feistel Network）です。ラウンドと呼ばれる暗号化の１ステップを繰り返す構造であり、多くのブロック暗号で使われています。

また、DES では 64bit の鍵（8bit のパリティビットを含む）が必要になります。

ファイステルネットワーク

それでは、DES アルゴリズムの肝となるファイステルネットワークについて見ていきたいと思います。DES を用いた暗号化の全体像を以下に示します。

左右2つのブロックに分けて書いてみました。左側に注目してください。上から平文が入力として入ってきます。最初に、初期転置を行い各ビットを攪拌します。

その後、右側の鍵生成器（鍵（64bit）を入力とします）で生成されたサブ鍵を用いて、ラウンド関数を実行します。このラウンドを 16 回行います。

ラウンド 16 から出力されたものに対して、最終転置をしたものが暗号文になります。

サブ鍵生成アルゴリズム

それでは、サブ鍵生成アルゴリズムについて見ていきます。これは、上図で言うと、右側の鍵生成器にあたる部分を説明します。

サブ鍵生成アルゴリズムでは、64bit の鍵を入力として、48bit のサブ鍵を 16 本出力します。（詳細は図に全て書いています）

上図にある縮小転置（PC1, PC2）はビットの並び替えです（下図参考）。例えば、鍵（64bit）を入力として縮小転置を通すと、57bit 目、49bit 目、41bit 目、33bit 目...と順番に並び替えていきます。（64bit のうち、使われないビットが 8 つあります）

データ暗号アルゴリズム

ここでは、データ暗号アルゴリズムについて説明します。これは、ファイステルネットワークの全体図で言うと、左側の部分を指します。

入力の平文を初期転置した後に 32bit ずつ（右 bit、左 bit）に分割します。右 bit とサブ鍵生成アルゴリズムで生成した鍵を入力としてラウンド関数を行い、その出力と左 bit の XOR を取ります。最後に左右 bit を入れ替えます。

ラウンド関数

データ暗号アルゴリズムの中にあるラウンド関数について説明します。

入力はサブ鍵（48bit）と右 bit（32bit）です。まず、右 bit をサブ鍵と同じ長さにするために、拡大転置を行います。48bit に拡大された右 bit とサブ鍵の XOR を取ります。その 48bit を 6bit ずつに分割して、各 S-box に入れます。

S-box の例を見せます。

Row Column Number
No.| 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
--------------------------------------------------
0 | 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7
1 | 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8
2 | 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0
3 | 15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13

DES では上の表のように、S1 から S8 までの S-box が用意されています。例えば、入力が100110 の 6bit だとします。まず、このうちの最初と最後のビットを組み合わせます（10）。10 は 10 進数表現で 2 なので、上の表の「2」の行を見ます。そして、入力の 2-5bit（0011）が 10 進数表現で 3 なので、上の表の「3」の列を見ます。すると、「8」が出力で出てきます。

8 は 2 進数表現で 1000 なので、出力は 4bit になることがわかると思います。

データ復号アルゴリズム

今まで DES のデータ暗号アルゴリズムについて見ていきました。では、DES のデータ復号についても見てみましょう。

DES はラウンド数が 16 ですが、ラウンドが１つしかないと仮定してみましょう。ラウンド１は最終ラウンドなので出力時に左右 bit の入れ替えを行わないことに注意してください。

下図を見るとわかりやすいと思いますが、同じ鍵を使用すればもとの平文に復号することができます。

実際の DES では、暗号化に使ったサブ鍵を逆順にしてファイステルネットワークを通せば復号することができます。

これは、DES の大きな利点でもあります。

DES では暗号化と復号に同じアルゴリズムが使えるのです。

なぜ使われなくなったのか？

DES は安全性に対する懸念から、すでに現在では非推奨の暗号化アルゴリズムとなっています。DES では 64bit のデータブロックと 56bit の鍵（パリティビットを除いています）を使っています。しかし、この鍵長が短すぎるため、コンピュータの進化に伴い暗号に用いた鍵を特定するブルートフォース（総当たり）攻撃が可能になってしまいました。

現在では後継の AES などの暗号化技術の使用が推奨されています。

ブルートフォース攻撃などの DES に対する攻撃の実現性については別の記事にまとめたいと思います。

DES 暗号が徐々に強度が通じなくなったことがわかる事例があります。それは、RSA 社が行なった DES 解読チャレンジです。1997年に行われた最初のチャレンジでは、解読に 96 日かかりました。しかし、2 年後の 1999 年でのチャレンジでは、1 日も経過せずに解読ができてしまいました。

トリプル DES

DES は鍵長が短いために強度が足りなくなりました。そこで考えられたのがトリプル DES です。これは、DES アルゴリズムの暗号化、復号、暗号化を連続して行っています。

各フェーズに異なる鍵を用いる方法（図左）と２種類のみ使う方法（図右）があります。前者は 56bit の鍵が 3 つあるので、鍵長は 168bit になります。後者は 112bit になります。

さらば DES 暗号、2023年へのカウントダウン

1970 年代に登場し、暗号アルゴリズムの標準として長年にわたり使われてきた DES ですが、いよいよ完全終了に向けたカウントダウンに入っています。米国立標準技術研究所（NIST）が 2018 年 7 月 19 日、DES を強化した暗号アルゴリズムであるトリプル DES について、これから開発するアプリケーションで採用することをやめ、2023 年以降は使用を禁止することを提案しました。これによって、DES は表舞台から完全に姿を消すことになります。

さいごに

よければアンケートに協力をお願いします。

この記事を読んで、面白かったらぜひフォローを！

そして、カンパの方もお待ちしています！

↓「気に入ったらサポート」からカンパできます↓