📖

DES暗号とFeistel構造について

2023/07/16に公開

暗号化

tech

この記事について

DES暗号の仕組みについて，素人が学んだことをメモします．内容は世の中に溢れている記事と大差ないのですが，もしそれで理解できなかった場合にご参考にしてください．

記法と前提

平文を $p$ , 共通鍵を $k \in \mathcal{K}$ と表記します．
平文や鍵は $\{0, 1\}$ のビット列で書かれているとします．

Feistel構造について

DES暗号はFeistel構造と呼ばれている構造をしています．この節ではFeistel構造について説明します．
Festel構造では，平文を $r$ ラウンド回暗号化します． $i$ 回目のラウンドでは $f_{K_i}$ という関数を用いているのですが，この $f_{K_i}$ が非線形であっても良いということがFeistel構造の最大の特徴です．

と言ってもよく分からないので，具体的に見ていきましょう．Feistel構造は以下の図のような方式をとります．構造の話をしているので，抽象的な内容ですが，お付き合いください．

巡回鍵の生成

Feistel構造では，一つの鍵 $k \in \mathcal{K}$ から $r$ 個の巡回鍵（サブ鍵） $\{K_1, \ldots, K_r\}$ を生成します．
暗号化には，共通鍵 $k$ が直接的に用いられるのではなく，巡回鍵が用いられます．

暗号化について

はじめに平文を左右二つに分けます．これを $L_0, R_0$ とおきます．
暗号化関数 $E_k$ を用いて， $c = E_{k}(L_0, R_0)$ と暗号化します．ここで，暗号化関数の添え字 $k$ は共通鍵 $k$ を用いていることを意味しますが，実質的には $r$ 個の巡回鍵 $\{k_1, \ldots, k_r\}$ を使用しています．

暗号化関数 $E_k$ について詳しく説明しましょう．
$E_k$ は $r$ ラウンドに分かれており， $(L_0, R_0), (L_1, R_1), \ldots, (L_r, R_r)$ を段階的に生成したのち， $(L_r, R_r)$ の左と右をひっくり返した $(R_r, L_r)$ を出力するものです．

$(L_{i-1}, R_{i-1})$ から $(L_{i}, R_{i})$ の生成方法は画像の通りですが，このように書けます．

\begin{align*} L_i &\leftarrow R_{i-1} \\ R_i &\leftarrow L_{i-1} + f_{K_i}(R_{i-1}) \end{align*}

各ラウンドで重要になってくるのは $f_{K_r}(R_{i-1})$ であり，ここを複雑なものにしてデータを撹拌します．復号化の処理を見てもらえれば明らかですが，この $f$ は非線形でどんなに複雑なものであっても良く，その嬉しさは後述します．

復号化について

暗号化の処理を後ろから追っていくだけです． $R_{i-1}$ の複号はシンプルです．暗号化において， $R_{i-1}$ は次のラウンドで $L_{i}$ に代入されているので，復号化では， $R_{i-1}$ に既知の $L_i$ を代入すれば終わりです．

次に， $L_{i-1}$ の復号です．任意のビット列 $m \in \{0, 1\}^{n}$ に対して， $m \oplus m = 0$ となることに注意してください．例えば， $\{0, 1, 1, 0\} \oplus \{0, 1, 1, 0\} = \{0, 0, 0, 0\}$ です．そのため， $L_{i-1}$ を以下のように復号することができます．

\begin{align*} R_i + f_{K_i}(R_{i-1})&= L_{i-1} + f_{K_i}(R_{i-1}) + f_{K_i}(R_{i-1})\\ &= L_{i-1} \end{align*}

$f$ の非線形性について

$f$ の非線形性の嬉しさをもう少し語ります．任意の暗号は復号可能である必要があり，それは暗号が単射であることを要求していました．そのため，任意のブロック暗号は置換となります．そのこと自体はFeistel構造の暗号も例外ではないのですが， $f$ の部分に着目すると，復号時に $f_{K_i}(R_{i-1})$ から $R_{i-1}$ を求める必要はありません．つまり，単射である必要がないのです．よって，ここでなるべく複雑な処理を行えれば，安全な暗号になりそうだというのがFeistel構造の特徴となります．

DES暗号について

さて，DES暗号はFeistel構造をしています．DES暗号では，ラウンド数 $r=16$ です．また，平文空間と鍵空間は $\{0, 1\}^{64}$ です．つまり，平文も鍵もビット列であり，その長さは64文字であるということです．

DES暗号がFeistel構造から拡張されている点

DES暗号は，上記で説明したFeistel構造と二点の違いがあります．Feistel構造の最初と最後に処理が加わっています．

平文 $p$ を直接 $(L_0, R_0)$ に分割するのではなく，置換 $IP$ を通してから分割を行います．つまり， $(L_0, R_0) = IP(p)$ となります．
$E_k$ によって出力された $(R_r, L_r)$ を暗号文 $c$ とするのではなく，置換 $IP^{-1}$ を通してから暗号文として出力しまう．つまり $c = IP^{-1}((R_r, L_r))$ となります．

ここでの置換 $IP$ はDES暗号で共通のものであり，全世界に公開されています．

ここからは，巡回鍵の生成方法と暗号化関数 $E_k$ を具体的に見ていきましょう．

巡回鍵の生成方法

$f_{K_i}$ で用いられる $K_i$ は48ビットです．なので，DES暗号の巡回鍵生成アルゴリズムでは，64ビットの鍵 $k$ から48ビットの鍵 $K_i$ を16個生成することになります．

※画像はWikipediaから引用

鍵 $k$ から，縮小転置 $PC1$ によって28ビット×2のビット列 $(C_0, D_0) = PC1(k)$ を生成します． $PC1$ でやっていることは， $C_0$ 用に $k$ から28ビットを選び，同様に $D_0$ 用に $k$ から28ビットを選んでいるという作業です．
$1 \le i \le 16$ について，以下の処理を順番に繰り返し， $K_{1}, \ldots, K_{16}$ を生成します．
1. $(C_i, D_i)$ を $(C_{i-1}, D_{i-1})$ から良い感じに計算します．具体的には，i=1, 2, 9, 16のときは左に1ビット，それ以外のときは左に2ビット巡回させます．
2. 縮小転置PC2を用いて， $K_{i} = PC2((C_i, D_i))$ として生成します．

PC2では，56ビットの $(C_i, D_i)$ から48ビットを選んでいます．

PC1, PC2はDES暗号で共通のものであり，全世界に公開されています．

（私見）縮小転置を使っているので，仮に $K_{i}$ がバレたとしても，そこから $K_{i-1}$ とかを求めるのが意外とむずいのかな？

$f_{K_i}(R_{i-1})$ について

一番大事なところの説明がめんどくさくなってきてしまいました…

復習をします． $f_{K_i}(R_{i-1}): \{0, 1\}^{32} \to \{0, 1\}^{32}$ という関数は各ラウンド $i$ で鍵 $K_i$ を用いて， $R_{i-1}$ から $R_i$ を生成する際に使う関数です．与えられた鍵 $K_i$ は48ビットです．この $f_{K_i}(R_{i-1})$ の構造をこの節では説明します．

※画像はWikipediaから引用したものを一部改変

まずは拡大置換 $E$ を使って $R_{i-1} \in \{0, 1\}^{32}$ から $E(R_{i-1}) \in \{0, 1\}^{48}$ を作ります．拡大置換は32文字から重複ありで48文字を選んで並べる処理です．
$B = E(R_{i-1}) \oplus K_i$ によって，鍵との和をとります．
$B = (B_1, B_2, \ldots, B_8)$ という風に $B$ を6ビット×8に分割する．
Sボックス $1 \le l \le 8, S_{l}: \{0, 1\}^{6} \to \{0, 1\}^{4}$ によって， $c_l = S_l(B_l)$ を生成する．
最後に置換 $P: \{0, 1\}^{32} \to \{0, 1\}^{32}$ によって $f_{K_i}(R_{i-1}) = P((c_1, \ldots, c_8))$ を出力する

拡大置換 $E$ , Sボックス, 置換 $P$ は全て一般に公開されています．

Sボックスについて

この説明は完全に力尽きてしまいました…書籍とかを適宜参照してください…

Sボックスは6ビットのものを4ビットに変換する関数です．Sボックスは文字数を減らしているため単射ではなく，非線形になっており，強度のために非常に重要だとされています．

その他

鍵 $k$ は64文字なのですが，8, 16, 24, ..., 64文字目はパリティビットと呼ばれ，伝送エラーを検知するためのものです．

どういうことでしょうか？鍵 $k$ を8バイト×8つの行に分割したとき，各行のビット和は奇数になるように鍵が生成されます．これによって，鍵の伝送時に各行のうち1ビットが欠けていても復号が可能になります．

具体的に見てみましょう．
$k = 10000110|...|...|...|...|...|...|00110111$ というように64ビットを8ビット×8に分割します．
ここで，例えば一つ目に注目すると10000110の各ビット列の和は3であり，確かに奇数であることが分かります．もし，伝送時にどこかのビットが欠けて10?00110となったとしても，和が奇数であるということから，不明な部分が埋められるということです（今回は?以外の和が3であるので，?が0だとわかる）．

実際，巡回鍵の生成方法で用いられたPC1を見てみると，8, 16, 24, ..., 64は捨てられています．これらの文字は暗号鍵というよりもパリティビットであるためです．

参考文献

暗号理論入門
 暗号技術のすべて