第3回：DESとは一体何か？

今回は今までとちょっと趣向を変えて、Windowsのセキュリティの一部を解説したいと思います。

Windows2000には標準で高度暗号化パックというのがついてきます。こいつはDES(Data Encryption Standards)という暗号法を用いたもので、ほかにもInternet Explorerでも用いられている暗号方であり、暗号の強度は128bitという強度です。その他、Windows Updateでオプションとしてダウンロードできるかと思いましたが、定かではありません。
この強度の数値はN bitの暗号では考えられる鍵が2^N通り存在するということです。強度がN bitだとすると、必ずこうなるということではないですが、暗号を解読する際に｢総当り｣で暗号解読を試みたときに2^N回の計算を必要とすると思っていいでしょう。
DESの場合128bitなので2¹²⁸＝340,282,366,920,938,463,463,374,607,431,768,211,456回…途方もないですね。
現代のスーパーコンピュータを使っても約10²⁰年というとんでもない年数を必要とします。これは｢現状では｣十分すぎるといえます。が、今後のコンピュータの発展の仕方によっては更に強い暗号が必要になるかもしれません。

ではこのDESとは何なのでしょうか。
まずDES開発の経緯から説明していきましょう。
第二次世界大戦を通じて、情報の秘匿性がいかに大事かを知った米国政府は、1973年に商用暗号の技術を公募しました。このときに2つの条件がつけられたのです。

　1. アルゴリズムを公開して、暗号の安全性を鍵の秘匿のみに依存させること。
　2. 不特定多数の人々の利用に今日するため集積回路(LSI)技術を用いて暗号装置を安価に量産できること。

このときに採用され、DESの元になったのがIBMの開発した"Lucifer"という暗号技術でした。このLucuferが開発された当時は128bitの強度を持っていましたが、DESを決定するに当たってその強度は56bitに縮小されてしまっていました。これは当時のコンピュータの処理能力に合わせたものだと思います。
こうして1977年にDESが確立されました。この暗号の特徴はそれまでの暗号のプラットフォームが歯車などを用いた｢機械暗号｣であったのに対して、コンピュータにプラットフォームを移した事でより複雑な暗号方を高速に処理できるようになったことでしょう。それともう一つ、今までの機械暗号では文字の種類が26種類であったのが、1バイトの幅、すなわち256種類に広がったこともこの暗号の大きな特徴であるといえます。

それではつぎにDESがどの様にしたデータを暗号化するかを解説します。
DESの暗号化は簡単な3つの単純な演算、すなわちビットシフト、論理演算、転置で表現できます。まず以下の図がDESの大まかな流れです。

1. まず暗号化するデータ(以下"平文"といいます)から64bit分のデータ(ブロック)に区切ります。
2. そのビットブロックを｢初期転置｣と呼ばれるビット間の入れ替えを行います。入れ替えの順序は以下の表で表されます。この表は転置前の第何ビットがどこに来るかを表しており、例えば転置前の第58ビットは転置後の第1ビットに移されます。

初期転置IP (Initial Permutation)

58	50	42	34	26	18	10	2
60	52	44	36	28	20	12	4
62	54	46	38	30	22	14	6
64	56	48	40	32	24	16	8
57	49	41	33	25	17	9	1
59	51	43	35	27	19	11	3
61	53	45	37	29	21	13	5
63	55	47	39	31	23	15	7

3. 初期転置をかけた後、64bitのブロックは左右32bitづつのブロックに分けられる。
4. 右32bitはユーザの入力した鍵から生成された内部鍵と一緒に｢f関数｣と呼ばれる関数に放り込まれ、出てきた結果と左32bitと排他的論理和演算を計算して左ブロックとします。
5. 右32bitと左32bitを入れ替えます。
6. 4.と5.を16回繰り返した後、左右を統合してから再び｢最終転置｣と呼ばれるビット間の入れ替えを行います。表の見かたは初期転置と同じです。ちなみにこの最終転置はちょうど初期転置の逆関数になっています。つまり初期転置で入れ替えたビット順序を元の位置に戻すように入れ替えているのです。

最終転置FP (Final Permutation)

40	8	48	16	56	24	64	32
39	7	47	15	55	23	63	31
38	6	46	14	54	22	62	30
37	5	45	13	53	21	61	29
36	4	44	12	52	20	60	28
35	3	43	11	51	19	59	27
34	2	42	10	50	18	58	26
33	1	41	9	49	17	58	25

f関数内部では下の図のような処理が行われます。

拡大転置E (Expantion)

32	1	2	3	4	5
4	5	6	7	8	9
8	9	10	11	12	13
12	13	14	15	16	17
16	17	18	19	20	21
20	21	22	23	24	25
24	25	26	27	28	29
28	29	30	31	32	1

転置P (Permutation)

16	7	20	21
29	12	38	17
1	15	23	26
5	18	31	10
2	8	24	14
32	27	3	9
19	13	30	6
22	11	4	25

1. 入力された32bitは拡大転置によって48ビットに冗長部を付加させます。
2. 拡大されたデータは入力された鍵から生成された内部鍵と排他的論理和演算を計算した後、6bitづつのビットブロックに分割します。
3. 分割されたデータは先頭からS₁～S₈までそれぞれ異なった換字表を持つ関数に入力され、4bitのデータに縮小して出力される。
S₁～S₈の換字表と説明はこちら
4. 最後に出力された4bitを元に順番に統合してから転置が行われ、32bitに縮小されてから、f関数より出力されます。

今度は鍵の生成についてです。以下の図がその流れです。

選択転置1 (Permuted Choice-1)

57	49	41	33	25	17	9
1	58	50	42	34	26	18
10	2	59	51	43	35	27
19	11	3	60	52	44	36
63	55	47	39	31	23	15
7	62	54	46	38	30	22
14	6	61	53	45	37	29
21	13	5	28	20	12	4

選択転置2 (Permuted Choice-2)

14	17	11	24	1	5
3	28	15	6	21	10
23	19	12	4	26	8
16	7	27	20	13	2
41	52	31	37	47	55
30	40	51	45	33	48
44	49	39	56	34	53
46	42	50	36	29	32

1. ユーザがパリティつきの鍵を入力します。
2. 入力ビットに選択転置1という転置をかけます。
3. その後、左右28bitづつに分けてからNの値によって異なった数だけ左にビットシフトします。Nとシフトする数は以下の表のようになっています。

段数 (N)	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
シフト数	1	1	2	2	2	2	2	2	1	2	2	2	2	2	2	1

4. その後左右を結合してからそれをK_Nとして出力して、再び左右ビットを保持したまま3.に戻ってN＜16の間、繰り返します。

これで私がDESについて知っているすべてです。
まあ高校の卒論で暗号の事を書いて結構いい点をとったこともあり、かなり詳しくなってしまったわけなのです。
今度は気が向いたらもう一つ有名なRSA暗号とか書いてみたりするかもしれません。でもなんかこのコンテンツの趣旨に外れる気がする…。

clefの連絡先はこちら↓
clef@mutt.freemail.ne.jp