DES(Data Encryption Standard)
DES(Data Encryption Standard)
1976年に米国の国立標準局(NBS)が連邦情報処理標準(FIPS)として採用したブロック暗号(FIPS 46-3) 正式なアルゴリズム名はDEA(Data Encryption Algorithm)
使用箇所
UNIXシステムにおけるログイン時のパスワードによるユーザー認証でDESが使われているらしいいた
良いところ
暗号化処理と復号処理が一つの関数で済むらしい
一つの関数で済むので実装が楽
セキュリティ面
1993年 松井による線形解読法でも少ない計算量で解読できる アルゴリズム
入力は鍵64ビット、平文64ビットに対して適用される。
鍵自体は64ビットであるが、8ビット毎に奇数パリティが設定される。
1〜7ビットまでが鍵のビットで、8ビット目が奇数パリティ。
DESは大きく分けて以下の処理で暗号化処理をする。
最初に並び替えをする(IP: Initial Permutation)($ IP )
16回の暗号化または復号処理のラウンドを行う
最後に並び替えをする(FP: Final Permutaiton)($ IP^{-1} )
復号は上記の逆の処理をする。
最初の並び替え $ IP
入力のブロックに対して以下のような並び替え$ IP を行う。
$ \begin{pmatrix} 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 \end{pmatrix}
$ IP 処理の出力の左側32ビットを$ L_0 、右側32ビットを$ R_0 とする
暗号化・復号の処理
ラウンドの基本的な処理は以下になる。
64ビットのブロックを32ビットの左$ L と32ビットの右$ R に分けたものと、
32ビットの入力から32ビットの出力を返す関数$ f があったときに、ラウンドの暗号化関数$ F は以下の処理をする。
$ F(L, R) = (R, L \oplus f(R))
復号は復号関数$ G としたときに以下になる。
$ G(L, R) = (R \oplus f(L), L)
各ラウンドの処理は以下のように$ L,R を処理する。
$ L_{i} = R_{i-1}
$ R_{i} = L_{i} \oplus f(R_{i-1}, K_i)
$ K_i は鍵スケジュール$ \bm{KS} によって生成された副鍵
$ i は1..16?
鍵スケジュール$ \bm{KS} については別のところで説明する
ラウンドの暗号化処理$ F は以下
$ F(L_{i}, R_{i}) = (R_{i},\ \ L_{i} \oplus f(R_{i-1}, K_{i})) $ [i\ | \ 1..16]
ラウンドの復号処理の場合は以下になる。
$ L_{i-1} = R_{i} \oplus f(L_{i}, K_{i})
$ R_{i-1} = L_{i}
ラウンドの復号処理$ G は以下
$ G(L_{i-1}, R_{i-1}) = \lparen R_{i} \oplus f(L_{i}, K_{i}), \ \ L_{i} \rparen $ [i\ | \ 16..1]
鍵スケジュール$ KS
鍵から48ビットの副鍵(サブ鍵)を16個生成する。生成された副鍵は各ラウンドで使用される。
$ n がラウンド($ [n | 1...16] )、$ n ラウンドの鍵$ K_n 、$ \bm{K\!EY} が鍵とすると、
$ K_n = KS(n, \bm{KEY}) $ [n\ |\ 1 ... 16]
最後の並び替え($ IP^{-1} )
出力のブロックに対して$ IP^{-1} を適用する
$ \begin{pmatrix} 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 & 57 & 25 \end{pmatrix}
F関数
F関数
Expansion
Key mixing
Substitution
Permutation
ハードウェアで転置を行う場合
換え字処理
理解度チェック
Q. DES
平文を[]ビット長のブロックに分割し、各ブロックを[]ビット長の鍵で暗号化する[]暗号アルゴリズム
Q. 対称暗号アルゴリズム
Q. $ IP はどんな並び替えをしているか
Q. ラウンド
Q. ラウンドの暗号化処理はどんな風にやっているか
Q. ラウンドの復号処理はどんな風にやっているか
Q. 鍵スケジュール
Q. DESのf関数はどんなことをしているか
Q. $ IP^{-1} はどんな並び替えをしているか
Q. S-BOX
Q. PC-1
Q. PC-2
Q. Feistel構造
参考
読み辛過ぎる
DES、3DESの実装ソース
関連