ikautak.log

C/C++, Python, CUDA, Android, Linux kernel, Network, etc.

暗号理論入門　4.4〜4.7

暗号

暗号理論入門 原書第3版

暗号理論入門 原書第3版

4.4 アルファベットと語

アルファベットを有限かつ空でない集合 \Sigma とする。 \Sigma の長さ(length)とは \Sigma の中の元の個数であるとする。

  • \Sigma 上の語(word)または記号列(string)とは、\Sigma の記号の有限列を意味する。空列は \varepsilon で表され、空語(empty word)と呼ばれる。
  • \Sigma 上の語 \vec{w} の長さとは、その記号の個数である。それを | \vec{w} | で表す。
  • \Sigma 上のすべての語の集合は、空集合を含めて \Sigma^{*} で表す。
  • \vec{v},\ \ \ \vec{w} \in \Sigma^{*} であれば、\vec{v} と \vec{w} の結合によって得られる記号列 \vec{v} \vec{w} = \vec{v} \circ \vec{w} は、\vec{v} と \vec{w} の連結と呼ばれる。特に \vec{v} \circ \varepsilon = \varepsilon \circ \vec{v} = \vec{v} である。
  • n が負でない整数であれば、 \Sigma^{n} を \Sigma 上の長さ n のすべての語の集合とする。

4.5 置換

X を集合とし、X の置換(permiutation)を全単射 f\ :\ X \to X で定義する。X のすべての置換の集合を S(X) で表す。

n が自然数であれば、S_n により集合 {1, 2, ..., n} の置換群を表す。

群 S_n はちょうど n! = 1 * 2 * 3 * ... * n 個の元をもつ。

X = \{0, 1\}^{n} を長さ n のすべてのビット列の集合であるとする。ビットの位置のみを換える X の置換をビット置換(bit permutation)という。
ビット置換として巡回左シフト(circular leftshift)、巡回右シフト(circular rightshift)がある。

4.6 ブロック暗号

ブロック暗号とは、平文空間と暗号文空間が \Sigma^{n} である暗号方式であるとする。ここで \Sigma^{n} はアルファベット \Sigma 上の長さ n のすべての語の集合である。
ブロック暗号の一例としてシーザー暗号があり、そのブロック長は１である。ブロック長１のブロック暗号は換字暗号(substitution cipher)という。

4.7 多重暗号化

ブロック暗号の安全性を高めるため、種々の異なった鍵を使用してブロック暗号に何重にも適用する方法がある。
よく使用されるのはE-D-E三重暗号化(triple encryption)であり、
　c = E_{k_1} (D_{k_2} (E_{k_3}(p)))
と暗号化する。ここで k_i,\ \ \ 1 \le i \le 3 は３つの鍵であり、E_{k_i} は暗号化関数、 D_{k_i} は鍵 k_i,\ \ \ 1 \le i \le 3 に対する復号化鍵である。
鍵の長さを２倍にするのみの場合は、 k_1 = k_3 とする。