ブロック暗号

ブロック暗号は、固定長メッセージを暗・復号するための共通鍵暗号である。共通鍵暗号では、送信者と受信者は同じ鍵を共有していることを前提とする。
鍵K 鍵K
メッセージ [暗号化] →暗号文→ [復号] メッセージ

ブロック暗号の数学的実体は、
  • と呼ばれる k ビット文字列 K と
  • 平文と呼ばれる n ビット文字列 M
を入力とし、
  • n ビットの暗号文と呼ばれる文字列 C
を出力する関数 E である:
E : {0,1}k x {0,1}n → {0,1}n
E(K, M) = C.
ただし、各鍵 K∈{0,1}k について
関数 EK(・) = E(K,・) は置換でなければならない。
関数 EK(・) を(計算するアルゴリズムを)暗号化アルゴリズム、逆関数 EK-1(・) を(計算するアルゴリズムを)復号アルゴリズムと呼ぶ。

ブロック暗号は、
  • 鍵 K があれば、暗号化 C=EK(M) や復号 M=EK-1(C) を高速に実行できるが、
  • 鍵 K がなければ、暗号文 C=EK(M) を見ても、その平文 M はわからない
ようにつくる必要がある。
理想は各 EK(・) がランダム置換。




DES

DESは鍵長 k=56、ブロック長 n=64 のブロック暗号である。

DESは、入力メッセージを左ブロックと右ブロックに分け、
  • 右ブロックを部分鍵に依存して撹拌したものを、
  • 左ブロックに足し込んで新たな左ブロックを作り、
  • ブロックの左右を入れ替える、
ということを繰り返す、フェイステル型変換である。すなわち、

DES(K, M) :
  • (K1,...,K16) ← KeySchedule(K)  
  • ※ 各Kiは48ビット。
  • M = IP(M)
  • L0 || R0 = M ※ 左右のブロックの初期値をセット。
  • r ∈ [1..16] :
  • ※ 左右のブロックを16ラウンドかけてフェイステル変換で撹拌。
    • Lr = Rr-1, Rr = f(K, Rr-1) \oplus Lr-1
  • C = IP-1(L16||R16)
  • return C


DES(K,・) は、f がどのような関数でも置換となる。実際、
  • Rr-1 = Lr, Lr-1 = f(Kr, Lr) \oplus Rr.

初期置換 IP :
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

撹拌関数 f : Jに依存する形で、Rを撹拌したい。
f(J, R):  ※ |J| = 48, |R| = 32
  • R = E(R), R = R \oplus J
  • R1∥R2∥・・・∥R8 = R
  • r ∈[1..8]
    • Ri = Si(Ri)
  • R = R1∥R2∥・・・∥R8  ※ |R| = 32
  • R = P(R)
return R

拡大置換 E : 32ビット文字列を48ビット文字列に拡大
32 1 2 3 4 5
4 5 6 7 8 9
8 9 10 11 12 13
12 13 14 15 16 17
16 17 18 19 20 21
20 21 22 23 24 25
24 25 26 27 28 29
28 29 30 31 32 1

最終置換 P :
16 7 20 21
29 12 28 17
1 15 23 26
5 18 31 10
2 8 24 14
32 27 3 9
19 13 30 6
22 11 4 25

S ボックス
Si : {0,1}6 → {0,1}4 : 一種の換字暗号  (i=1,...,8)
  1. 各 S ボックスは4対1関数。
  2. 各行は0から15を1回ずつとる。
  3. 入力の1ビットを変えると出力の少なくとも2ビットが変わる。

S1 :
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 0 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7
0 1 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8
1 0 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0
1 1 15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13

  •  ・ ・

S8 :
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 0 13 2 8 4 6 15 11 1 10 9 3 14 5 0 12 7
0 1 1 15 13 8 10 3 7 4 12 5 6 11 0 14 9 2
1 0 7 11 4 1 9 12 14 2 0 6 10 13 15 3 5 8
1 1 2 1 14 7 4 10 8 13 15 12 9 0 3 5 6 11
※ 最初の2ビットで行を、残りの4ビットで列を選択。

結局、DESの撹拌関数 f は、
  • 入力が1ビットでも変化すると、
  • S ボックスの効果により、その出力は最低でも2ビット変化し、
  • その変化が最終置換 P の効果でブロック全体へと飛び火する
ことを繰り返して、雪崩効果を実現している。

DESの問題点
  • 鍵長 k = 56 は小さすぎる。
  • ブロック長 n = 64 も短すぎる。
  • Sボックスの実装はソフトウェアに不向き。



トリプルDES

DESを3回繰り返すブロック暗号。
鍵長は112ビット、ブロック長は64ビット。

  • 3DES(K1 || K2, M) =
    • DES(K2, DES-1(K1, DES(K2, M))).

注意
下記のようにして、トリプルDESで168ビットの鍵を用いても、Meet-in-the-middle攻撃により、実効的な鍵長は112ビット。
  • 3DES3(K1 || K2 || K3, M) =
    • DES(K3, DES-1(K2, DES(K1, M))).



AES

AESは鍵長 k=128、ブロック長 n=128 のブロック暗号である。(鍵長は他のオプションもあり。)

128ビット=16バイトを4 x 4の行列に表す(状態行列)。各成分は、有限体GF(256)の要素と見なせる。有限体演算を効果的に用いることで、ソフトウェアによって高速に暗復号が可能である。

状態行列 s
s0 s4 s8 s12
s1 s5 s9 s13
s2 s6 s10 s14
s3 s7 s11 s15



AES(K, m) :
  • (k0,...,k10) ← Expand(K)  
  • s = m \oplus k0  ※ 状態行列 s の初期値をセット。
  • r ∈ [1..10] :
    • ※ 状態行列 s を10ラウンドかけて撹拌。
    • s ← S(s)
    • s ← ShiftRows(s)
    • r ≦ 9: s ← MixCols(s)
    • s ← s \oplus kr
  • return s
※ 各Kiは128ビット。

まず、S関数によって各成分ごとに状態行列を撹拌する。撹拌のメインは有限体GF(256)における逆数演算である。(その後のアフィン変換は、固定点をなくし、エラー訂正符号を利用して各成分の変化を強調するもの。)


S(s) :
  • sの16個の各成分ごとに
    • s = s-1 ※ GF(256)の要素としての逆数。
    • s = M s + v
  • return s
ここで、Mは以下の行列
1 0 0 0 1 1 1 1
1 1 0 0 0 1 1 1
1 1 1 0 0 0 1 1
1 1 1 1 0 0 0 1
1 1 1 1 1 0 0 0
0 1 1 1 1 1 0 0
0 0 1 1 1 1 1 0
0 0 0 1 1 1 1 1
vは以下のベクトル。
1
1
0
0
0
1
1
0

つぎに、ShiftRows関数で行列の成分を行方向にシフトする。

s0 s4 s8 s12
s5 s9 s13 s1
s10 s14 s2 s6
s15 s3 s7 s11

最後に、MixCols関数で状態行列sに左から定数行列Cを掛ける。

MixCols(s) :
  • s = C s
  • return s
ここで、Cは以下の行列
02 03 01 01
01 02 03 01
01 02 02 03
03 01 01 02

このようにして、逆数演算によってもたらされた各成分の撹拌が、まず行方向にそして列方向に拡散していき、状態行列全体におよぶ。




ブロック暗号の安全性

ブロック暗号の理想的な安全性はランダム置換と区別がつかないこと(疑似ランダム置換)である。


置換 f が疑似ランダム置換であるとは、

オラクルにアクセスできる、どのような識別者Dにとっても、それがオラクルから置換 f を与えらているのか、それとも真のランダム置換を与えられているのか、区別がつかないことをいう。

ただし、ここで、識別者Dはオラクルから、Dが適応的に選択した複数の値における識別対象関数の値を入手することができるとする。

差分解読
差分解読とは、識別者のクラスを差分識別者に限定したものである。

差分識別者は、差分特性を用いて、対象暗号かランダム置換かを見破ろうとする。

差分特性 DPf(a, b) = Pr[ f(X \oplus a) = f(X) \oplus b ]


差分識別者a,b :
  • パラメータ: a,b ∈ {0,1}n
  • 以下を(ある回数)繰り返す:
    • u ←$ {0,1}n
    • オラクルに u を尋ねて v1 を得る。
    • オラクルに u \oplus a を尋ねて v2 を得る。
    • if v2 = v1 \oplus b then output 1 and halt
    • else continue
  • output 0

DESは差分解読に対し安全だが、以下の線形解読には脆弱であることが知られている。(すなわち、パラメータa, b をうまくとるとDESは線形識別者a,bによって疑似ランダム性が破られてしまう。)


線形解読
線形解読とは、識別者のクラスを線形識別者に限定したものである。

線形識別者は、線形特性を用いて、対象暗号かランダム置換かを見破ろうとする。

線形特性 LPf(a, b) = ( 2 Pr[ a・X = b・f(X) ] - 1 )2


線形識別者a,b,A :
  • パラメータ: a,b ∈ {0,1}n, A ⊆ {0, 1, 2, …}
  • c ← 0
  • 以下を繰り返す:
    • u ←$ {0,1}n
    • オラクルに u を尋ねて v を得る。
    • if u ・ a = v ・ b then c = c + 1
  • if c ∈ A, output 1 else output 0

AESは差分解読や線形解読に対し証明可能安全であることが知られている。しかし、任意の識別者に対して安全であると証明されているわけではない。

また、上では、鍵はランダムかつ独立に選択されているとの前提を置いているが、昨今は複数の関連する鍵がセットされているとの設定でブロック暗号の安全性を考察することが多い。




















最終更新:2010年04月21日 14:41