3回目

情報セキュリティ
第３回
現代暗号の基礎数理
脅威と暗号技術
セキュリティに対する脅威
脅かされる特性
暗号技術
共通鍵暗号
盗聴
（秘密が漏れる）
機密性
公開鍵暗号
改竄
（情報が書き換えられる）
正真性
一方向ハッシュ関数
なりすまし
（正しい送信者のふりをする）
認証
メッセージ認証コード
否認
（後から私じゃないと言う）
否認不可能性
デジタル署名
情報理論的安全性その１
 暗号化アルゴリズムE

平文mと鍵kとアルゴリズムEから暗号文c=E(k,m)
が決まる。
 確率変数m, k, c

全く使われ
ない平文mi
は無い


平文mは集合M={m1,m2,..}の中の1つであり、ど
の平文かは確率分布で決まる。但し、任意の平文
mi∈Mに対し、Pr(m=mi)>0を満たす。
鍵kは、集合K={k1,k2,..}の中の1つであり、どの鍵
かは確率分布で決まる。
暗号文cは、c=E(k,m)から定まる集合C={c1,c2,..}
の中の1つである。
「確率変数m」とは、平文が
集合Mの中のどれかの値を
一つ取るため「変数」（定数
でない）であり、どれを取る
かは確率によって決まるか
ら、「確率変数」という。
確率分布に従って発生
平文
m
暗号文
c
暗号化
E
確率分布に従っ
て発生
鍵k
平文と鍵の確率
分布に依存して
決まる
平文mの確率分布
Pr(m)
m=m1
（緑）
m=m2
（赤）
m=m3
（青）
1/3
1/3
1/3
確率0はダメ
集合K={k1,k2,k3}
集合M={m1,m2,m3}
鍵K’の確率分布
Pr(k)
k=k1
k=k2
k=k3
1/3
1/3
1/3
情報理論的安全性その２
暗号文cjが与えられた場合、
cjの平文がmiである確率
 情報理論的に安全とは
Pr(mi|cj)=Pr(mi)
 条件付確率の定義：

E(m,k1)
平文
赤
青
緑
鍵k1で決
まる置換
暗号文
赤
青
緑
E(m,k1)
平文
赤
青
緑
感覚的に分
かりずらい
暗号化
E
Pr(mi|cj) = Pr(mi,cj) / Pr(cj)
Pr(m)
具体的なイ
メージで説明
平文m
任意のmi∈M とcj∈Cに対し、
暗号文
赤
青
緑
m=m2
（赤）
m=m3
（青）
1/3
1/3
1/3
E(m,k2)
暗号文
赤
青
緑
E(m,k2)
平文
赤
青
緑
暗号文
赤
青
緑
Pr(k)
E(m,k3)
平文
赤
青
緑
暗号文
赤
青
緑
E(m,k3)
平文
赤
青
緑
暗号文
赤
青
緑
Pr(m|c)
敵
Pr(m)
暗号文cから何も
情報が得られない
鍵k
m=m1
（緑）
平文
赤
青
緑
暗号文c
=

k=k1
k=k2
k=k3
1/3
1/3
1/3
平文m=m1(赤)
暗号文が赤（c1）の
場合、平文が赤で
ある確率が高い。
Pr(m|c)=Pr(m)
c3
c1
c2
Pr(m|c)≠Pr(m)
c3
c1
c2
安全性
平文の集合M={緑、赤、青}の
例では、|M|=|K|=3
 情報理論的に安全ならば、
暗号化
Ek
|K|≧|M|（|K|は集合Kの要素数）



暗号文cから平文mへ一意に復号
出来るためには、異なる平文mに
対し異なる鍵kが必要になる。
任意の暗号文cj∈Cに対し、集合M
の全ての平文がcjに対する平文で
ある可能性を持つ。なぜならば、
任意のmi∈M とcj∈Cに対し、
Pr(mi|cj)=Pr(mi)かつ、Pr(mi)>0
以上から、鍵の数|K|を平文の数
|M|よりも少なくすることは出来ない。
m1
m2
:
:
mi

情報理論的に安全でなくても、計算
時間が大きい（例えば１０億年）なら
ば安全と考える。
擬似ランダム置換族は計算量理論
的安全性の基本構成要素である。
同じ鍵
はダメ
:
:
cj
m1
m2
:
:
mi
?
:
:
二つの異なる平文を同じ鍵で
同じ暗号文にすると、どちらに
復号していいかわからない
 計算量理論的に安全

k1
k1
復号
Dk
m1
m2
:
:
mi
k1
k2
ki
:
:
cj
:
:
k1
k2
ki
m1
m2
:
:
mi
暗号文cjに対して、全ての平文
がcjに対する平文の候補である
{0,1}2の置換π
識別不可能性
 選択平文攻撃
 神様は{0,1}n上のランダム置換族
Pnとその部分集合Anを知っている。
 神様にm∈{0,1}nを質問すると、
c=π(m)（暗号文）を教えてくれる。
 識別アルゴリズムDの識別利得
 Adv(D)=|Prandom－PA|
 Prandomとは：
Pnから選ばれたπがD =1を出力す
る（置換がある性質を持つ）確率。
 PAとは：
An（暗号アルゴリズムの置換集合）
の中の置換がD=1を出力する確率。
 擬似ランダム置換族
 質問回数をある値に制限した時、
どんなDに対しても、Adv(D)<ε（εは
暗号アルゴリズ
非常に小さい値を表す）となるとき、
ムは置換族An
Anは擬似ランダム置換族と呼ぶ。
であるが、Anを
特定するのに  神様への質問回数は現実的な値
時間がかかる
に制限する。例えば、250(=1015)回。
00
01
10
11
01
10
00
11
ランダム置換族
暗号アルゴリ
ズムの置換族
Pn
An
識別アルゴリズム
Dが1を出力する
置換族
D =1
PA=
交わりの面積
Ｄ=1の面積
P
=
random
|An|
|Pn|
DはAnの識別に有効
DはAnの識別に有効
Feistel型構造
（DES暗号）
平文は
2nビット
Fu(Ru-1)
Ru
Fu(Lu)
=Lu-1
L0
 ラウンド関数Fiは{0,1}nか
ら{0,1}nへの任意の関数。
 Feistel型構造は逆関数
が存在する（上への1対
1）ので {0,1}2n上の置換。
 Feistel型構造への入力
を(L0,R0)とする。但し、
L0∈{0,1}n、R0∈{0,1}n。
i=1,..,uに対して、 Li=Ri-1、
Ri=Li-1 Fi(Ri-1)。
 DES暗号は16段の
Feistel型構造である。
Ru Fu(Lu)
=Lu-1 Fu(Ru-1)
R0
Lu
F1
１段
Ru
Fu
ラウンド関数
L1
R1
F2
2段
L2
u段
暗号文
暗号化
Lu-1
Ru-1
Fu-1
R2
Lu-2
Ru-2
:
:
Fu
F1
Lu
Ru
u段構造
L0
復号
R0
逆関数
2段Feistelは擬似ランダム置換族でない
 2段Feistel型構造の置換集合ψ（F1,F2)
 識別アルゴリズムD: if (a a’=1n) then D=1 else D=0
但し、a=0n F1(0n)、a’=1n F1(0n)
 Pψ（F1, F2)=Pr(D=1)=1
十分大きい
 証明： a a’=0n
F1(0n) 1n F1(0n)=1n
Prandom=N3/N2
 Dの識別利得 Adv(D) = |Prandom － Pψ（F1, F2)| > 1-1/2n-1
攻撃のた
めに選択
した平文
入力=(0n,0n)の場合
0n
0n
入力=(1n,0n)の場合
1n
0n
0n=00….0
n
F1
F1
N3とN2は「復習３」
で求める
P2n
D =1
F1とF2は独
立な擬似ラ
ンダム関数
ψ（F1,F2)
F2
F2
暗号文
a=0n
F1
(0n)
b
a’=1n
F1
(0n)
b’
敵はD=1となる置換だけ
を解読の対象に出来る
強擬似ランダム
 ３段Feistel型構造は擬似ランダム置換であるが
段数が増えれば
強擬似ランダム置換でない。
攻撃に強くなる
 ４段Feistel型構造は強擬似ランダム置換
 強擬似ランダム置換族とは：
 長さ2nのランダム置換族P2nの部分集合A2nが、
選択暗号文攻撃においてP2nとA2nの識別が
困難ならば、A2nは「強擬似ランダム置換族」と
呼ばれる。
平文
暗号化
E
平文
敵
暗号文
暗号文
鍵K
選択暗号文攻撃
復号
D

Download Report