ヾノ*>ㅅ<)ノシ帳

ノンジャンルのふりーだむなブログです。

『暗号理論入門』(丸善出版)勉強メモ 4.8.1 ECBモード

大学の本屋で15%OFFのセールがあった日に『暗号理論入門』(丸善出版)を買いました。\高い/

暗号理論入門 原書第3版

暗号理論入門 原書第3版

以下は 4.6節の「ブロック暗号」と、4.8節の「ブロック暗号のモード」のうち4.8.1節「ECBモード」の勉強メモです。 といってもすんなり理解できなかった所に自分の説明を追加しただけです。

準備

定義 4.6.1 ブロック暗号とは、平文空間と暗号文空間が {\Sigma}^n である暗号方式であるとする。ここで、 {\Sigma}^n はアルファベット {\Sigma} 上の長さ n の全ての語の集合である。ブロック長 n自然数である。

定理 4.6.2 ブロック暗号の暗号化関数は置換である。

証明省略

最も一般的なブロック暗号を以下のように説明することができる。ブロック長 n と一つのアルファベット \Sigma を固定するとする。平文空間と暗号文空間は  \mathcal{P} = \mathcal{C} = {\Sigma}^n とする。 鍵空間は、 {\Sigma}^n 上のすべての置換の集合 S({\Sigma}^n) とする。一つの鍵 \pi \in S({\Sigma}^n) に暗号化関数

 E_{\pi}: {\Sigma}^n \rightarrow {\Sigma}^n, \quad \vec{v} \mapsto \pi(\vec{v})

が対応する。これに対する復号化関数は

 D_{\pi}: {\Sigma}^n \rightarrow {\Sigma}^n, \quad \vec{v} \mapsto {\pi}^{-1}(\vec{v})

である。

この本では次の置換暗号を取り上げていました。

置換暗号を考えてみると、この暗号では記号の位置の変換により成立する置換のみを使う。 \Sigma = \{0, 1\} であれば、この置換はビット置換である。 鍵空間は置換群 S_n である。 \pi \in S_n に対して、

 E_{\pi}: {\Sigma}^n \rightarrow {\Sigma}^n, \quad (v_1, \ldots, v_n) \mapsto (v_{\pi(1)}, \ldots, v_{\pi(n)})

とおけば、それに対する復号化関数は

 D_{\pi}: {\Sigma}^n \rightarrow {\Sigma}^n, \quad (x_1, \ldots, x_n) \mapsto x_{{\pi}^{-1}\,(1)}, \ldots, x_{{\pi}^{-1} \,(n)}

であるので、鍵空間は  n! 個の元をもち、個々の鍵は  n 個の数の数列としてコード化できる。

ECBモードの例題

ここからが僕がハマった箇所です。

例 4.8.1 長さ  4 のビットベクトル上でビット置換を行うブロック暗号を考える。すなわち、アルファベット  \Sigma = \{0, 1\} とブロック長  4 の置換暗号を考える。ここでは  \mathcal{K} = S_4 であり、  \pi \in S_4 に対して

 \{0, 1\}^4 \rightarrow \{0, 1\}^4, \quad b_1 b_2 b_3 b_4 \mapsto b_{\pi (1)} b_{\pi (2)} b_{\pi (3)} b_{\pi (4)}

となる。 平文  m

 m = 101100010100101

とし、鍵を

$$ \pi = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 2 & 3 & 4 & 1 \end{pmatrix} $$

とする。

ブロック長が4なので、この長さでmをブロックに分けます。

 m_1 = 1{\color{red}0}11, m_2 = 000{\color{red}1}, m_3 = 0100, m_4 = 1010

さて  m_1, m_2, m_3, m_4 を10進変換するとそれぞれ  11, 1, 4, 10 なのですが、  \pi で置換できなそうですね。 …と考えるのはダメで、問題文をよく読まないといけません。(僕は問題文をよく読まない人です。) 「置換暗号」と書いてありますね?しかも「ビット置換」をするとあります。 準備で説明したことを思い出すと、 \pi の見方は、 各 n 番目の数をそれぞれ  \pi(n) 番目に持っていくということです。 下位ビットから  1, \ldots, n 番目という割り当てです。 例えば  m_1 の3番め(0)と  m_2の1番目(1)はそれぞれ4番めと2番めに移動します。 よって、各ブロックの暗号化の結果は、

 c_1 = E_{\pi}(m_1) = {\color{red}0}111, c_2 = E_{\pi}(m_2) = 00{\color{red}1}0, c_3 = E_{\pi}(m_3) = 1000, c_4 = E_{\pi}(m_4) = 0101

で、暗号文は

 c = {\color{blue}{0111}}0010{\color{blue}{1000}}0101

になります。


はてなブログの数式モードクソすぎだね。 そういえば4.10節の「アフィン暗号」を読んでいるときに network & crypto なCTFの問題を思いつきました。