Title of presentation: 32 pt Arial

情報セキュリティ特論（2）
黒澤馨（茨城大学）
[email protected]
2015/10/1
confidential
1
前回の演習(1)
• 以下の方式について、
Pr(なりすまし成功)=Pr(改ざん成功)=1/p
を証明せよ。
• 平文 m1, m2 ∈ {0, 1, …, p-1}
• 鍵 (a, b, c) ← {0, 1, …, p-1}
• Tag=a・m1+b・m2+c mod p
2015/10/1
confidential
2
なりすまし確率
M=(m1,m2)
Tag=a・m1+b・m2+c mod p (1)
ボブ
敵
K=(a,b,c):ランダム
Pr(ボブ accepts)
=式(1)を満たす(a,b,c)の数 / (a,b,c)の総数
2015/10/1
confidential
3
なりすまし確率
M=(m1,m2)
Tag=a・m1+b・m2+c mod p (1)
ボブ
敵
K=(a,b,c):ランダム
(a,b)を決めると、cが自動的に定まる。
よって、
式(1)を満たす(a,b,c)の数= (a,b)の総数＝p2
2015/10/1
confidential
4
なりすまし確率
M=(m1,m2)
Tag=a・m1+b・m2+c mod p (1)
ボブ
敵
K=(a,b,c):ランダム
Pr(ボブ accepts)
=式(1)を満たす(a,b,c)の数 / (a,b,c)の総数
=p2/p3=1/p
2015/10/1
confidential
5
改ざん攻撃
アリス
鍵 K
（m1,m2,Tag）
ボブ
鍵 K
=
=
（a,b,c）
（a,b,c）
敵
Tag=a・m1+b・m2+c mod p
(1)
Pr(改ざん)
=式(1),(2)を満たす(a,b,c)の数 /式(1)を満たす(a,b,c)の数
2015/10/1
confidential
6
改ざん攻撃
アリス
鍵 K
（m1,m2,Tag）
（m1’,m2’,Tag’）
ボブ
鍵 K
=
=
（a,b,c）
敵
（a,b,c）
Tag=a・m1+b・m2+c mod p (1)
Tag’=a・m1’+b・m2’+c mod p (2)
Pr(改ざん)
=式(1),(2)を満たす(a,b,c)の数 /式(1)を満たす(a,b,c)の数
2015/10/1
confidential
7
式(1)(2)を満たす(a,b,c)の数
• Tag=a・m1+b・m2+c mod p (1)
• Tag’=a・m1’+b・m2’+c mod p (2)
Tag-Tag’=a(m1-m1’)+b(m2-m2’) mod p
2015/10/1
confidential
8
式(1)(2)を満たす(a,b,c)の数
• Tag=a・m1+b・m2+c mod p (1)
• Tag’=a・m1’+b・m2’+c mod p (2)
Tag-Tag’=a(m1-m1’)+b(m2-m2’) mod p
• (m1,m2)≠ (m1,m2)なので、
m1-m1’≠0 またはm2-m2’≠0
• m1-m1’≠0 と仮定。
2015/10/1
confidential
9
式(1)(2)を満たす(a,b,c)の数
• Tag=a・m1+b・m2+c mod p (1)
• Tag’=a・m1’+b・m2’+c mod p (2)
Tag-Tag’=a(m1-m1’)+b(m2-m2’) mod p
• (m1,m2)≠ (m1,m2)なので、
m1-m1’≠0 またはm2-m2’≠0
• m1-m1’≠0 と仮定。
• bを決めるとaが一意に決まる。
2015/10/1
confidential
10
式(1)(2)を満たす(a,b,c)の数
• Tag=a・m1+b・m2+c mod p (1)
• Tag’=a・m1’+b・m2’+c mod p (2)
Tag-Tag’=a(m1-m1’)+b(m2-m2’) mod p
• (m1,m2)≠ (m1,m2)なので、
m1-m1’≠0 またはm2-m2’≠0
• m1-m1’≠0 と仮定。
• bを決めるとaが一意に決まる。
• すると、式(1)からcが決まる。
2015/10/1
confidential
11
式(1)(2)を満たす(a,b,c)の数=p
• Tag=a・m1+b・m2+c mod p (1)
• Tag’=a・m1’+b・m2’+c mod p (2)
Tag-Tag’=a(m1-m1’)+b(m2-m2’) mod p
• (m1,m2)≠ (m1,m2)なので、
m1-m1’≠0 またはm2-m2’≠0
• m1-m1’≠0 と仮定。
• bを決めるとaが一意に決まる。
• すると、式(1)からcが決まる。
2015/10/1
confidential
12
改ざん攻撃
アリス
鍵 K
（m1,m2,Tag）
（m1’,m2’,Tag’）
ボブ
鍵 K
=
=
（a,b,c）
敵
（a,b,c）
Tag=a・m1+b・m2+c mod p (1)
Tag’=a・m1’+b・m2’+c mod p (2)
Pr(改ざん)
=式(1),(2)を満たす(a,b,c)の数 /式(1)を満たす(a,b,c)の数
=p/p2=1/p
2015/10/1
confidential
13
演習(2)
以下の方式の
Ｐｒ(なりすまし成功)、Pr(改ざん成功)
を求めよ。
• 平文 m1, m2 ∈ {0, 1, …, p-1}
• 鍵 (a, c) ← {0, 1, …, p-1}
• Tag=a・m1+a2・m2+c mod p
2015/10/1
confidential
14
改ざん攻撃
アリス
鍵 K
（m1,m2,Tag）
（m1’,m2’,Tag’）
ボブ
鍵 K
=
=
（a,c）
敵
（a,c）
Tag=a・m1+a2・m2+c mod p (1)
Tag’=a・m1’+a2・m2’+c mod p (2)
Pr(改ざん)
=式(1),(2)を満たす(a,b,c)の数 /式(1)を満たす(a,b,c)の数
2015/10/1
confidential
15
式(1)(2)を満たす(a,c)の数
• Tag=a・m1+a2・m2+c mod p (1)
• Tag’=a・m1’+a2・m2’+c mod p (2)
Tag-Tag’=a(m1-m1’)+a2(m2-m2’) mod p
2015/10/1
confidential
16
式(1)(2)を満たす(a,c)の数
• Tag=a・m1+a2・m2+c mod p (1)
• Tag’=a・m1’+a2・m2’+c mod p (2)
Tag-Tag’=a(m1-m1’)+a2(m2-m2’) mod p
• (m1,m2)≠ (m1,m2)なので、
m1-m1’≠0 またはm2-m2’≠0
• m2-m2’≠0 と仮定。
2015/10/1
confidential
17
式(1)(2)を満たす(a,c)の数
• Tag=a・m1+a2・m2+c mod p (1)
• Tag’=a・m1’+a2・m2’+c mod p (2)
Tag-Tag’=a(m1-m1’)+a2(m2-m2’) mod p
• (m1,m2)≠ (m1,m2)なので、
m1-m1’≠0 またはm2-m2’≠0
• m2-m2’≠0 と仮定。
• aに関する２次方程式：解は高々２個。
2015/10/1
confidential
18
式(1)(2)を満たす(a,c)の数≦2
• Tag=a・m1+a2・m2+c mod p (1)
• Tag’=a・m1’+a2・m2’+c mod p (2)
Tag-Tag’=a(m1-m1’)+a2(m2-m2’) mod p
• (m1,m2)≠ (m1,m2)なので、
m1-m1’≠0 またはm2-m2’≠0
• m2-m2’≠0 と仮定。
• aに関する２次方程式：解は高々２個。
2015/10/1
confidential
19
改ざん攻撃
アリス
鍵 K
（m1,m2,Tag）
（m1’,m2’,Tag’）
ボブ
鍵 K
=
=
（a,c）
敵
（a,c）
Tag=a・m1+a2・m2+c mod p (1)
Tag’=a・m1’+a2・m2’+c mod p (2)
Pr(改ざん)
=式(1),(2)を満たす(a,b,c)の数 /式(1)を満たす(a,b,c)の数
≦2/p
2015/10/1
confidential
20
共通鍵暗号系
鍵k
平文m
暗号化
アルゴリズム
暗号文 C
E
m
D
敵
2015/10/1
復号
アルゴリズム
confidential
解読したい
21
乱数
鍵生成アルゴリズム G
鍵k
鍵k, 平文 m
暗号化アルゴリズム E
暗号文 C
復号アルゴリズム
平文 m
鍵k, 暗号文C
D
共通鍵暗号系は、
上記３つのアルゴリズム（プログラム）
(G,E,D)により定義される
2015/10/1
confidential
22
乱数
鍵生成アルゴリズム G
鍵k
鍵k, 平文 m
暗号化アルゴリズム E
暗号文 C
復号アルゴリズム
平文 m
鍵k, 暗号文C
D
（使用例）
(G, E, D)は、良い（悪い）共通鍵暗号系
2015/10/1
confidential
23
乱数
鍵生成アルゴリズム G
鍵k
鍵k, 平文 m
暗号化アルゴリズム E
暗号文 C
復号アルゴリズム
平文 m
鍵k, 暗号文C
D
平文 m の集合：M = { m }
M上の確率関数を PM
鍵 k の集合： K = { k }
独立
K上の確率関数を PK
2015/10/1
confidential
24
乱数
鍵生成アルゴリズム G
鍵k
鍵k, 平文 m
暗号化アルゴリズム E
暗号文 C
復号アルゴリズム
平文 m
鍵k, 暗号文C
D
平文 m の集合：M = { m }
M上の確率関数を PM
鍵 k の集合： K = { k }
独立
K上の確率関数を PK
2015/10/1
confidential
25
乱数
鍵生成アルゴリズム G
鍵k
鍵k, 平文 m
暗号化アルゴリズム E
暗号文 C
復号アルゴリズム
平文 m
鍵k, 暗号文C
D
平文の集合M = { m }上の確率関数 PM
鍵の集合 K = { k }上の確率関数 PK
暗号文の集合 C = { c }上の確率関数 PC
2015/10/1
confidential
26
• 定義（Shannon）
共通鍵暗号系（G,E,D）は、
無条件に安全 if
・ M上の任意の確率関数 PM
に対し、
・ ∀m ∈ M
・ ∀C ∈ C
~
~
~
Pr( M = m | C = C ) = Pr( M = m )
2015/10/1
confidential
27
•
•
∀x
,P(x)
全てのx
各x
任意のx
For any x
に対し、P(x)が成り立つ
∀x ,∀y,P(x,y)
全ての(x,y)
各(x,y)
任意の(x,y)
2015/10/1
に対し、P(x,y)が成り立つ
confidential
28
• 定義（Shannon）
共通鍵暗号系（G,E,D）は、
無条件に安全 if
・ M上の任意の確率関数 PM
に対し、
・ ∀m ∈ M
・ ∀C ∈ C
~
~
~
Pr( M = m | C = C ) = Pr( M = m )
2015/10/1
confidential
29
M={好き、きらい}
c
アリス
ボブ
敵
(恋がたき)
2015/10/1
confidential
30
平文の確率分布
0.5
好
き
2015/10/1
き
ら
い
confidential
31
暗号文を見た後の確率分布
（悪い暗号系の場合）
0.5
好
き
2015/10/1
き
ら
い
confidential
32
なぜ悪い暗号系か
敵はショック大
0.5
好
き
2015/10/1
き
ら
い
confidential
33
暗号文を見た後の確率分布
（敵はショック大）
敵に情報がもれている
0.5
好
き
2015/10/1
き
ら
い
confidential
34
暗号文を見た後の確率分布
（良い暗号系の場合）
0.5
好
き
2015/10/1
き
ら
い
confidential
35
暗号文を見た後の確率分布
（良い暗号系の場合）
（敵は何もショックを受けない）
敵に何も情報がもれていない
0.5
好
き
2015/10/1
き
ら
い
confidential
36
平文の確率分布(2)
0.5
好
き
2015/10/1
き
ら
い
confidential
37
暗号文を見た後の確率分布
（良い暗号系）
0.5
好
き
2015/10/1
き
ら
い
confidential
38
無条件に安全な暗号系
• どのような平文の確率分布に対しても、
元の平文の確率分布
＝
暗号文を見た後の確率分布
2015/10/1
confidential
39
• 定義（Shannon）
共通鍵暗号系（G,E,D）は、
無条件に安全 if
・ M上の任意の確率関数 PM
に対し、
・ ∀m ∈ M
・ ∀C ∈ C
~
~
~
Pr( M = m | C = C ) = Pr( M = m )
2015/10/1
confidential
40
One - time - pad (バーナム暗号）
• 1917年に Vernam が特許
• Shannon が無条件安全を証明
2015/10/1
confidential
41
Mod 2 の世界
•
•
•
•
0+0=0
0+1=1
1+0=1
1+1=0
2015/10/1
confidential
42
Mod 2 の世界
•
•
•
•
•
•
0+0=0
0+1=1
1+0=1
1+1=0
移項すると、1= -1
すなわち、-1=1
2015/10/1
confidential
43
Mod 2の世界 (2)
• A=(a1, …, an), B=(b1, …, bn) に対し、
A+B = (a1, …, an) + (b1, …, bn)
= (a1+b1, …, an+bn)
2015/10/1
confidential
44
One-Time Pad
• 鍵
K=(k1, …, kn)
• 平文 M=(m1, …, mn)
• 暗号化
C=K+M
• 復号
M=C-K = C+K
2015/10/1
confidential
45
鍵の確率分布
一様分布
1/2n
0…0
2015/10/1
1…１
confidential
K
46
定理
• One-Time Padは、無条件に安全
2015/10/1
confidential
47
証明 (n=1の場合）
• 敵が暗号文c=0を入手した。
• このとき、
Pr(M=0 | C=0)=Pr(M=0)
Pr(M=1 | C=0)=Pr(M=1)
• を証明する。
2015/10/1
confidential
48
c=m+k mod 2
なので、c=0となる(m,k)は、
k
1
0
(0,1)
(1,1)
(0,0)
(1,0)
0
2015/10/1
1
m
confidential
49
c=m+k mod 2
c=0という条件の下で、m=0となる事象は、
k
1
0
(0,1)
(1,1)
(0,0)
(1,0)
0
2015/10/1
1
m
confidential
50
k
1
0
(0,1)
(1,1)
(0,0)
(1,0)
0
1
m
Pr( M=0, K=0)
Pr(M=0 | C=0) =
Pr( M=0, K=0)+Pr( M=1, K=1)
2015/10/1
confidential
51
k
1
0
(0,1)
(1,1)
(0,0)
(1,0)
0
1
m
Pr(M=0, K=0)
Pr(M=0 | C=0) =
Pr(M=0, K=0)+Pr(M=1, K=1)
Pr(M=0, K=0)=Pr(M=0)・Pr(K=0)
2015/10/1
confidential
52
k
1
0
(0,1)
(1,1)
(0,0)
(1,0)
0
1
m
Pr(M=0, K=0)
Pr(M=0 | C=0) =
Pr(M=0, K=0) +Pr(M=1, K=1)
Pr(M=0, K=0) =Pr(M=0)・Pr(K=0)=Pr(M=0)・(1/2)
2015/10/1
confidential
53
k
1
0
(0,1)
(1,1)
(0,0)
(1,0)
0
1
m
Pr(M=0, K=0)
Pr(M=0 | C=0) =
Pr(M=0, K=0)+Pr(M=1, K=1)
Pr(M=0, K=0)=Pr(M=0)・Pr(K=0)=Pr(M=0)・(1/2)
Pr(M=1, K=1) =Pr(M=1)・Pr(K=1)=Pr(M=1)・(1/2)
2015/10/1
confidential
54
k
1
0
(0,1)
(1,1)
(0,0)
(1,0)
0
1
m
Pr(M=0)・(1/2)
Pr(M=0 | C=0) =
Pr(M=0)・(1/2) + Pr(M=1)・(1/2)
Pr(M=0, K=0)=Pr(M=0)・Pr(K=0)=Pr(M=0)・(1/2)
Pr(M=1, K=1)=Pr(M=1)・Pr(K=1)=Pr(M=1)・(1/2)
2015/10/1
confidential
55
k
1
0
(0,1)
(1,1)
(0,0)
(1,0)
0
1
m
Pr(M=0)・(1/2)
Pr(M=0 | C=0) =
Pr(M=0)・(1/2) +Pr(M=1)・(1/2)
Pr(M=0)
=
= Pr(M=0)
Pr(M=0) + Pr(M=1)
2015/10/1
confidential
56
Pr(M=0 | C=0)=Pr(M=0)
• 同様にして、
Pr(M=1 | C=0) = Pr(M=1)
• 同様にして、
Pr(M=0 | C=1) = Pr(M=0)
Pr(M=1 | C=1) = Pr(M=1)
2015/10/1
confidential
57
n=1の場合、証明できた
• n=2の場合、同様。
• 一般のnの場合、
2015/10/1
confidential
58
ベイズの定理より
~
~
P r(M  m | C  C )
~
~
~
P r(C  C | M  m) P r(M  m)

~
~
~
 P r(C  C | M  a) P r(M  a)
aM
2015/10/1
confidential
59
ベイズの定理より
~
~
P r(M  m | C  C )
~
~
~
P r(C  C | M  m) P r(M  m)

~
~
~
 P r(C  C | M  a) P r(M  a)
aM
2015/10/1
confidential
60
分子について
~
~
P r(C  C | M  m)
~
 P r(K  m  C )
~
 P r(K  m  C )
1
 n
2
2015/10/1
confidential
61
ベイズの定理より
~
~
P r(M  m | C  C )
~
~
~
P r(C  C | M  m) P r(M  m)

~
~
~
 P r(C  C | M  a) P r(M  a)
aM
1
2n
2015/10/1
confidential
62
1
~
分母   n P r(M  a )
aM 2
1
~
 n  P r(M  a )
2 aM
1
 n
2
2015/10/1
confidential
63
ベイズの定理より
~
~
P r(M  m | C  C )
~
~
~
P r(C  C | M  m) P r(M  m)

~
~
~
 P r(C  C | M  a) P r(M  a)
aM
1
~
Pr(M  m)
n
2
1
n
2
~
 Pr(M  m) (証明終了)
2015/10/1
confidential
64
• 定理
無条件に安全な暗号系においては
|K| ≧ |M|
(証明)
・敵が (C = 0・・・0)を盗聴したとき
∀m∈M に対して
~
~
~
Pr(M  m | C  0    0)  Pr(M  m)  0
2015/10/1
confidential
65
C =（0・・・0)
鍵 k1
m = 0・・・・0
k2
m = 0・・・01
・
・
・
kN
上図より
2015/10/1
・
・
・
m = 1・・・・1
|K| ≧ |M|
confidential
66
• 定義１
以下の性質が成り立つとき、
（標本空間 U、確率関数Pr）の組を
確率分布と呼ぶ.
（１）各 u∈ U に対し、 Pr(u)≧0
（２） Σu Pr(u) = 1
2015/10/1
confidential
67
平文の集合M = { m }上の確率関数 PM
鍵の集合 K = { k }上の確率関数 PK
暗号文の集合 C = { c }上の確率関数 PC
上記の標本空間は何か？
2015/10/1
confidential
68
直積
• ２つの集合A, Bの直積を
A×B={ (a,b) | a∈A, b∈B}
と定義する。
2015/10/1
confidential
69
共通鍵暗号系の場合、
標本空間： M×K = { (m,k) | m∈M, k ∈ K }
K
(mn,kl)
kl
= M×K (直積)
k1
k0
(m0,k0)
m0 m 1
2015/10/1
mn
confidential
M
70
標本空間： M×K = { (m,k) | m∈M, k ∈ K }
確率関数： Pr(m,k) = PM(m)・PK(k)
たとえば、
Pr(m0,k0)=PM(m0)・PK(k0)
K
(mn,kl)
kl
= M×K
k1
k0
(m0,k0)
m0 m 1
2015/10/1
mn
confidential
M
71
標本空間： M×K = { (m,k) | m∈M, k ∈ K }
確率関数： Pr(m,k) = PM(m)・PK(k)
たとえば、
Pr(m0,k0)=PM(m0)・PK(k0)
暗号文 c の確率分布は？
2015/10/1
confidential
72
|
1
6
1 1 1
Pr(A) = + =
6 6 3
1
2
3
4
5
6
事象A
• 定義３
標本空間Uの部分集合Aを事象と呼び、
Pr(A) =  Pr(μ)
と定義する。
μ
A
2015/10/1
confidential
73
暗号文が (0,…,0) となる事象は ?
K
~
C = (0,…,0)
kl
k1
k0
となる事象
E(m,k)=(0,…,0)
となる(m,k)
m0 m1
mn
~
Pｒ( C = 0・・・0) =
M

Pr(m,k)
( m, k ):E ( m , k ) 00
2015/10/1
confidential
74
K
kl
k1
k0
(m0,k l)
~
M = m0 となる事象
(m0,k0)
m0 m1
mn
M
標本空間M×Kにおける平文の確率分布は？
2015/10/1
confidential
75
K
kl
k1
k0
(m0,k l)
Pr(M = m0) =
 Pr(m0,k)
k
=
PM(m0) PK(k)
PM(m0) PK(k)
k
(m0,k0)
m0 m1
2015/10/1
~
~
M = m0
=
mn
M
confidential
k
= PM(m0)
76
K
kl
k1
k0
(m0,k l)
Pr(M = m0) =
 Pr(m0,k)
k
=
PM(m0) PK(k)
PM(m0) PK(k)
k
(m0,k0)
m0 m1
2015/10/1
~
~
M = m0
=
mn
M
confidential
k
= PM(m0)
77
K
kl
~
K = k0 となる事象
k1 (m0,k0)
k0
m0 m1
Pr( K = k0) =  Pr(m,k0)
~
m
同様に
(mn,k0)
Pr( K~ = k0) = PK(k0)
mn
M
標本空間M×Kにおける鍵の確率分布は？
2015/10/1
confidential
78
条件付確率は？
K
~
C = (0, …, 0)となる事象
kl
k1
k0
m0 m1
mn
M
~
~
Pr( M = m0 | C = (0, …, 0))=
2015/10/1
confidential
79
条件付確率は？
K
kl
k1
k0
m0 m1
mn
M
~
~
Pr( M = m0 | C = (0, …, 0))=
2015/10/1
confidential
この面積
~ = (0, …, 0)となる面積
C
80
~, ~ , ~ ：確率変数
C M K
標本空間からある集合への写像
~ ： M×K → M
M
~ ： M×K → K
K
~ ： M×K → C = { C }
C
2015/10/1
confidential
81
• 定義（Shannon）
共通鍵暗号系（G,E,D）は、
無条件に安全 if
・ M上の任意の確率関数 PM
に対し、
・ ∀m ∈ M
・ ∀C ∈ C
~
~
~
Pr( M = m | C = C ) = Pr( M = m )
2015/10/1
confidential
82
演習 (1)
One-time padについて考える。
• 鍵K=(001101)で、平文m=(111111)を
暗号化せよ。
• 鍵K=(001101)で、暗号文c=(101101)を
復号せよ。
2015/10/1
confidential
83
演習 (2)
• One-Time Padが無条件に安全であることを、
n=1ビットの場合と同様に、
n=2ビットに対し、証明せよ。
2015/10/1
confidential
84
演習 (3)
共通鍵暗号系（G,E,D）が無条件に安全
であるための必要十分条件は、
・ M上の任意の確率関数 PM
・ ∀m ∈ M
・ ∀C ∈ C
に対し、
~
~
~
Pr( C = c | M = m ) = Pr( C = c )
であることを証明せよ。
2015/10/1
confidential
85

Download Report