暗号理論入門　4.13〜4.15

作者: 林芳樹
出版社/メーカー: 丸善出版
発売日: 2012/04/20
メディア: 単行本
この商品を含むブログを見る

4.13 ヴィジュネル暗号とヒル暗号と置換暗号

アフィン線形暗号の例。

ヴィジュネル暗号

鍵空間は $K = \mathbb{Z}_{m}^{n}$ である。 $\vec{k} \in \mathbb{Z}_{m}^{n}$ であれば
　 $E_{\vec{k}}\ \ :\ \ \mathbb{Z}_{m}^{n} \to \mathbb{Z}_{m}^{n}\ ,\ \ \ \ \vec{v} \to \vec{v} + \vec{k}\ mod\ m$
であり、復号は
　 $D_{\vec{k}}\ \ :\ \ \mathbb{Z}_{m}^{n} \to \mathbb{Z}_{m}^{n}\ ,\ \ \ \ \vec{v} \to \vec{v} - \vec{k}\ mod\ m$
となる。
鍵空間は $m^{n}$ の元をもつ。

ヒル暗号

鍵空間は $K$ は、 $gcd(det\ A, m) = 1$ であるすべての行列 $A \in \mathbb{Z}^{n, n}$ 全体の集合である。 $A \in K$ に対して
　 $E_A\ \ :\ \ \mathbb{Z}_{m}^{n} \to \mathbb{Z}_{m}^{n}\ ,\ \ \ \ \vec{v} \to A \vec{v}\ mod\ m$
であり、ヒル暗号は最も一般的な線形ブロック暗号である（前の記事参照）。

置換暗号は線形暗号であり、ヒル暗号の特別な場合である。

4.14 アフィン線形ブロック暗号の暗号解読

アルファベットが $\mathbb{Z}_{m}$ でブロック長が $n$ であるアフィン線形ブロック暗号が、既知平文攻撃でどのように破られ得るかを示す。

鍵は固定されているものとし、暗号化関数は
　 $E\ :\ \mathbb{Z}_{m}^{n} \to \mathbb{Z}_{m}^{n}\ ,\ \ \ \ \vec{v} \to A \vec{v} + \vec{b}\ mod\ m$
となる。 $A \in \mathbb{Z}^{(n, n)}$ かつ $\vec{b} \in \mathbb{Z}^{n}$ である。

攻撃者は鍵 $(A, \vec{b})$ を決定したい。
$n + 1$ 個の平文 $\vec{w}_{i},\ \ \ \ 0 \le i \le n$ とそれに付随する暗号文 $\vec{c}_{i} = A \vec{w}_{i} + \vec{b}\ ,\ \ \ \ 0 \le i \le n$ を使う。
このとき
　 $\vec{c}_{i} - \vec{c}_{0} \equiv A( \vec{w}_{i} - \vec{w}_{0})\ mod\ m$
である。
$W$ を行列
　 $W = (\vec{w}_{1} - \vec{w}_{0}\ ,\ \ \ ...,\ \ \ \vec{w}_{n} - \vec{w}_{0})\ mod\ m$
とし、その列を差 $(\vec{w}_{i} - \vec{w}_{0})\ mod\ m,\ \ \ \ 1 \le i \le n$ とし、 $C$ は行列
　 $C = (\vec{c}_{1} - \vec{c}_{0}\ ,\ \ \ ...,\ \ \ \vec{c}_{n} - \vec{c}_{0})\ mod\ m$
で、その列を差 $(\vec{c}_{i} - \vec{c}_{0})\ mod\ m,\ \ \ \ 1 \le i \le n$ とする。
このとき
　 $AW \equiv C\ mod\ m$
となる。 $det W$ が $m$ に素であれば
　 $A \equiv C(w'\ adj\ W)\ mod\ m$
である。ここで $w'$ は $det\ W$ の $mod\ m$ での逆元である。さらに
　 $\vec{b} = \vec{c}_{0} - A \vec{w}_{0}$
となる。暗号が線形のときは $\vec{w}_{0} = \vec{c}_{0} = \vec{0}$ とおき、 $\vec{b} = 0$ となる。

例．ブロック長2のヒル暗号を復号化する。HANDがFUSSに暗号化されることを知っているとする。
$\vec{w}_{1} = (7, 0)$ が $\vec{c}_{1} = (5, 20)$ に暗号化され、 $\vec{w}_{2} = (13, 3)$ は $\vec{c}_{2} = (18, 18)$ に暗号化される。
このとき $W = \left( \begin{array}{cc} 7\ \ 13 \\0\ \ \ 3 \end{array} \right)$ 、 $C = \left( \begin{array}{cc} 5\ \ 18 \\ 20\ \ 18 \end{array} \right)$ である。
$det\ W = 21$ は26と素である。21の mod 26での逆元は5である。したがって

$A = 5C(adj\ W)\ mod\ 26 = 5 * \left( \begin{array}{cc} 5\ \ 18 \\ 20\ \ 18 \end{array} \right) \left( \begin{array}{cc} 3\ \ 13 \\ 0\ \ 7 \end{array} \right)\ mod\ 26$
から
$\left( \begin{array}{cc} 23\ \ 19 \\ 14\ \ 6 \end{array} \right)\$
を得る。 $AW = C$ である。

4.15 安全なブロック暗号

安全かつ効率的なブロック暗号を構成するのは複雑な問題。

混乱と拡散

重要な構成原理は混乱(confusion)と拡散(diffusion)である。
暗号文の統計的分布の、平文の分布への依存が複雑で、攻撃者がこの依存性を利用できないとき、ブロック暗号の混乱は大きい。置換暗号の混乱は小さい。

平文の個々の各ビットや鍵の各ビットが暗号文の可能な限り多くのビットに影響を及ぼせば、ブロック暗号の拡散は大きい。

全数探索(exhaustive key search)

最も単純な暗号文のみよる攻撃は全数探索である。攻撃者は暗号文から意味をもつ平文を見つけるまで試す。鍵空間が小さい場合に有効。
DESはこの方法で破ることが可能。平均して30分でDES鍵を見つけるコンピュータもある。

time-memory trade-off方式

平文xの暗号文がcとなることがわかっていると、全数探索の計算量は格納領域が大きければ加速可能。
鍵空間が $N$ 元をもつ場合、time-memory trade-offアルゴリズムを使用すると、平文xの暗号化に使用された秘密鍵を見つけるためには、時間 $O(N^{2/3}$ が必要となる。
このアルゴリズムには時間 $O(N)$ の前計算が必要となる。