Title of presentation: 32 pt Arial

情報セキュリティ特論（6）
黒澤馨（茨城大学）
[email protected]
2015/10/1
confidential
1
• RSA暗号
素因数分解の困難さ
• ElGamal暗号
離散対数問題の困難さ
x
3  2 mod5　2015/10/1
confidential
2
• RSA暗号
素因数分解の困難さ
• ElGamal暗号
離散対数問題の困難さ
3  2 mod5　答えは、x=3
x
2015/10/1
confidential
3
離散対数問題
• y=ax mod p (=素数）
となるxを求めよ、という問題。
• p=1024ビットのとき、10億年
2015/10/1
confidential
4
• mod 5 において
21  2, 2 2  4, 23  3, 2 4  1　31  3, 32  4, 33  2, 34  1　41  4, 4 2  1, 43  4, 4 4  1　フェルマーの定理
2015/10/1
confidential
5
• mod 5 において
2の位数は4
21  2, 2 2  4, 23  3, 2 4  1　31  3, 32  4, 33  2, 34  1　41  4, 4 2  1, 43  4, 4 4  1　4の位数は2
フェルマーの定理
3の位数は4
2015/10/1
confidential
6
2の位数は4:
• mod 5 において
p-1(=4)を割り切る
21  2, 2 2  4, 23  3, 2 4  1　31  3, 32  4, 33  2, 34  1　41  4, 4 2  1, 43  4, 4 4  1　4の位数は2:
3の位数は4:
p-1(=4)を割り切る
p-1(=4)を割り切る
2015/10/1
confidential
7
• aの位数
n
a  1 mod p となる最小のn
• 定理
任意の元aの位数は、p-1を割り切る。
2015/10/1
confidential
8
Diffie-Hellmanの鍵共有法
• p = 大きな素数,
q = p-1を割り切る大きな素数
g = 位数が大きな素数qの元
gq=1 mod p
2015/10/1
confidential
9
Diffie-Hellmanの鍵共有法
A
B
a ランダム
x  g a mod p
2015/10/1
b ランダム
x
confidential
y
y  g b mod p
10
Diffie-Hellmanの鍵共有法
A
B
a ランダム
x  g a mod p
b ランダム
x
K  ( y ) a mod p
2015/10/1
y
y  g b mod p
K  ( x ) b mod p
 ( g b ) a 〃
 ( g a ) b 〃
 g ab 〃
 g ab 〃
confidential
11
Diffie-Hellmanの鍵共有法
A
B
a ランダム
x  g a mod p
b ランダム
y
x
K  ( y ) a mod p
y  g b mod p
K  ( x ) b mod p
 ( g b ) a 〃
 ( g a ) b 〃
 g ab 〃
 g ab 〃
敵
盗聴
2015/10/1
confidential
12
敵のゴール
p, q,
g, x  g , y  g
a
b
DH問題
g
ab
1億年(DH仮定)
2015/10/1
confidential
13
離散対数問題との関係
g, x  g
DLOG
a
10億年(離散対数仮定)
a
離散対数問題
?
g, x  g , y  g
a
b
DH問題
g
ab
1億年(DH仮定)
2015/10/1
confidential
14
（定理）
DLOGを解くアルゴリズムAが存在するなら
DHを解くアルゴリズムBが存在する
（証明）
B
g
a
g ,g
2015/10/1
b
a
A
a
g
confidential
ab
15
（定理）
DLOGを解くアルゴリズムAが存在するなら
DHを解くアルゴリズムBが存在する
（証明）
B
g
a
g ,g
2015/10/1
b
a
A
a
b a
(g )
confidential
g
ab
16
g, x  g
a
PPTアルゴリズム A
a
乱数テープ R
PPT : Probabilistic Polynomial Time
確率的
多項式
時間
2015/10/1
confidential
17
g, x  g
a
PPTアルゴリズム A
a
乱数テープ R
R
Aがaを
出力
この面積
Pr(Aが解く) =
全面積
a
2015/10/1
confidential
18
• 離散対数仮定
確率ε以上でDLOGを解くような
PPTアルゴリズムは存在しない
• DH仮定
確率ε以上でDH問題を解くような
PPTアルゴリズムは存在しない
2015/10/1
confidential
19
定理
• 離散対数仮定が成り立てば、
DH仮定が成り立つ。
2015/10/1
confidential
20
ElGamal暗号
• 公開鍵：
p= 大きな素数
q= p-1を割り切る大きな素数
g=位数がqとなる元
y (=gx mod p)
• 秘密鍵: x
2015/10/1
confidential
21
ElGamal暗号
• 公開鍵：
p, q, g, y(=gx mod p)
• 秘密鍵: x
• 平文： m
• 暗号化：
r ← zp-1
E(m)=(gr, myr)
2015/10/1
confidential
22
ElGamal暗号
•
•
•
•
•
公開鍵：p, q, g, y(=gx mod p)
秘密鍵: x
平文： m
暗号化：E(m)=(gr, myr)
復号：
myr / (gr)x=m(gx)r/grx=m mod p
2015/10/1
confidential
23
敵への入力
• 公開鍵：p,q,g,y
• 暗号文: (gr, m・yr) mod p
2015/10/1
confidential
24
巡回群
• <g>={1, g, g2, …, gq-1} は、
（生成元）gで生成される巡回群
2015/10/1
confidential
25
DDH仮定
• (g, gr, y, yr) と (g, gr, y, z)は
多項式時間で区別できない。
• ただし、
z は<g> からランダムに選ばれた要素
2015/10/1
confidential
26
DDH仮定より
• 平文： m∈{1, g, g2, …, gq-1} とする。
• 暗号文：
E(m) = (gr, myr)
～(gr, m z )
ただし、
zは<g>からランダムに選ばれた要素。
2015/10/1
confidential
27
DDH仮定より
• 平文： m∈{1, g, g2, …, gq-1} とする。
• 暗号文：
E(m) = (gr, myr)
～(gr, m z )
ただし、
zは<g>からランダムに選ばれた要素。
mz=m×乱数 → one-time pad
2015/10/1
confidential
28
DDH仮定より
• 平文： m∈{1, g, g2, …, gq-1} とする。
• 暗号文：
E(m) = (gr, myr)
～(gr, m z )
ただし、
zは<g>からランダムに選ばれた要素。
mz=m×乱数 → one-time pad
mに関する情報は、もれていない
2015/10/1
confidential
29
ElGamal暗号の安全性
• DDH仮定の下、
• 平文mに関する情報は、何ももれていない。
2015/10/1
confidential
30
なりすまし攻撃
B
A
オレオレ
2015/10/1
confidential
31
Aの公開鍵 v (=g-s mod p)
s
B
A
s
v =g-s mod p
をチェック
2015/10/1
confidential
32
Bが、なりすませてしまう
s
C
B
A
s
s
オレはAだ
2015/10/1
confidential
33
Schnorrの認証法
v =g-s mod p
s
B
A
r←ランダム
x=gr mod p
x
c
c←ランダム
y=r+sc mod q
y
2015/10/1
-c
gy=gr+sc=gr(gs)c=xv
confidential
x =gyvc mod p
34
Schnorrの認証法
v =g-s mod p
s
r←ランダム
x=gr mod p
B
A
x
c←ランダム
c
y=r+sc mod q
y
2015/10/1
confidential
x =gyvc mod p
をチェック
35
零知識性
• Bには、sに関する情報が一切漏れていない。
2015/10/1
confidential
36
零知識性
• Bには、sに関する情報が一切漏れていない
if
Bは、自分自身で通信系列(x,c,y)を
生成できる。
2015/10/1
confidential
37
定理
• Bは、自分自身で通信系列(x,c,y)を
生成できる。
2015/10/1
confidential
38
証明
v =g-s mod p
s
r←ランダム
x=gr mod p
B
A
x
c←ランダム
c
y=r+sc mod q
y
2015/10/1
confidential
x =gyvc mod p
をチェック
39
証明
B
B
x
1. c←ランダム
c
2. y←ランダム
y
3. x =gyvc mod p
2015/10/1
confidential
40
証明
B
B
4. x
1. c←ランダム
c
2. y←ランダム
y
3. x =gyvc mod p
2015/10/1
confidential
41
健全性
• Bをacceptさせられるなら、Aはsを知っている。
2015/10/1
confidential
42
健全性
• Bをacceptさせられるなら、Aはsを知っている。
• Aをサブルーチンとして使って、sを求めること
ができる
2015/10/1
confidential
43
定理
• AがBをacceptさせられる
• Aをサブルーチンとして使って、
sを求めることができる
2015/10/1
confidential
44
証明
B
A
x
c←ランダム
c
y
x =gyvc mod p
2015/10/1
confidential
45
Aを初期状態にリセット
B
A
2015/10/1
confidential
46
もう一度、Aを走らせる
B
A
x
2015/10/1
confidential
47
証明
B
A
x
c’
2015/10/1
c’←ランダム
confidential
48
証明
B
A
x
c’
c’←ランダム
y’
2015/10/1
confidential
x =gy’vc’ mod p
49
証明
B
A
x
c, c’
x =gyvc mod p
y, y’
2015/10/1
confidential
x =gy’vc’ mod p
50
証明
B
A
x
v –(c-c’) =gy-y’ mod p
c, c’
1 =gy-y’vc-c’ mod p
x =gyvc mod p
y, y’
2015/10/1
confidential
x =gy’vc’ mod p
51
証明
B
A
v =g-(y-y’)/(c-c’) mod p
x
v –(c-c’) =gy-y’ mod p
c, c’
1 =gy-y’vc-c’ mod p
x =gyvc mod p
y, y’
2015/10/1
confidential
x =gy’vc’ mod p
52
証明
v=g-s mod p
B
A
v =g-(y-y’)/(c-c’) mod p
x
v –(c-c’) =gy-y’ mod p
c, c’
1 =gy-y’vc-c’ mod p
x =gyvc mod p
y, y’
2015/10/1
confidential
x =gy’vc’ mod p
53
証明
v=g-s mod p
B
A
s=(y-y’)/(c-c’)
v =g-(y-y’)/(c-c’) mod p
x
v –(c-c’) =gy-y’ mod p
c, c’
1 =gy-y’vc-c’ mod p
x =gyvc mod p
y, y’
2015/10/1
confidential
x =gy’vc’ mod p
54
敵のモデル
• 学習段階
• なりすまし段階
2015/10/1
confidential
55
学習段階
s
r←ランダム
x=gr mod p
B
A
x
c
c←ランダム
y=r+sc mod q
y
2015/10/1
confidential
敵：盗聴
x =gyvc mod p
をチェック
56
なりすまし段階
B
敵
x
c←ランダム
c
y
x =gyvc mod p
2015/10/1
confidential
57
定理
• なりすましに成功する敵が存在したと仮定す
ると、離散対数問題を解ける。
2015/10/1
confidential
58
v=g-s mod p
B
なりすまし段階
学習段階
(x’’,c’’,y’’)
B
敵
x
c
敵
2015/10/1
y
sconfidential
59
v=g-s mod p
なりすまし段階
学習段階
(x’’,c’’,y’’)
B
敵
x
c,c’
敵
2015/10/1
y,y’
confidential
60
v=g-s mod p
なりすまし段階
学習段階
(x’’,c’’,y’’)
B
敵
x
c,c’
敵
2015/10/1
y,y’
confidential
s=(y-y’)/(c-c’)
61
Schnorrのデジタル署名
公開鍵：v =g-s mod p
秘密鍵：s
r←ランダム
x=gr mod p
A
A
x
c=H(x,m)
平文m
y=r+sc mod q
y
2015/10/1
confidential
62
Schnorrのデジタル署名
公開鍵：v =g-s mod p
秘密鍵：s
r←ランダム
x=gr mod p
B
A
A
x
c=H(x,m)
平文m
x =gyvc mod p
を計算
y=r+sc mod q
y
σ=(c,y)
署名文
2015/10/1
confidential
c=H(x,m)
をチェック
63
選択平文攻撃
署名
オラクル
署名文 σ
平文 m
公開鍵
2015/10/1
敵
confidential
（平文*、署名文*）
64
ランダム・オラクル・モデル
における選択平文攻撃
署名
オラクル
署名文 σ
平文 m
敵
公開鍵
(m, x)
2015/10/1
（平文*、署名文*）
乱数 c=H(m,x)
Hオラクル
confidential
65
定理
• ROモデルにおいて、
Schnorrの署名に対し、確率εで
偽造に成功する敵Aが存在する。
ただし、
AはHオラクルに高々h回質問すると仮定する。
• Schnorrの認証法において、確率ε/hで
なりすましに成功する敵Bが存在する。
2015/10/1
confidential
66
ランダム・オラクル・モデル
における選択平文攻撃
署名
オラクル
署名文 σi
平文 mi
敵A
公開鍵 v
(mj, xj)
2015/10/1
（m*、c*, y*）
乱数 cj=H(mj,xj)
Hオラクル
confidential
67
なりすましの敵 B
署名
オラクル
署名文 σi
平文 mi
公開鍵 v
偽造の
敵A
v
（m*、c*, y*）
な
り
す
ま
す
ぞ
！
乱数 cj=H(mj,xj)
(mj, xj)
Hオラクル
2015/10/1
confidential
68
Bのなりすまし戦略
• 偽造の敵Aは、Hオラクルに
偽造用の(m*, x*)をk番目に質問する。
B
偽造の
敵A
相手
(m*,x*)
Hオラクル
2015/10/1
confidential
69
Bはkをランダムに推測
• Bは、x*をAに送る。
敵
(m*,x*)
＝B
Hオラクル
2015/10/1
相手
x*
confidential
70
Bのなりすまし戦略
• 相手がc*を返してきた。
敵
(m*,x*)
＝B
Hオラクル
相手
x*
c*
2015/10/1
confidential
71
Bのなりすまし戦略
• Bは、c*=H(m*,x*)とする。
敵A
(m*,x*)
＝ B
c*=H(m*,x*)
相手
x*
c*
Hオラクル
2015/10/1
confidential
Bの内部
72
Bは、Aを最後まで走らせる
• Aは、偽造(m*,c*,y*)を出力する。
敵A
(m*,x*)
(m*, c*, y*)
B
相手
x*
c*=(m*,x*)
c*
Hオラクル
2015/10/1
Bの内部
confidential
73
Bは、このy*を相手に返す。
• (m*,c*,y*)及びx*は正しい偽造なので、
検査式 x*=g y* v c* mod pを満たす
敵A
(m*,x*)
(m*, c*, y*)
B
相手
x*
c*=H(m*,x*)
c*
Hオラクル
2015/10/1
Bの内部
y*
confidential
74
よって、相手はacceptする。
• (m*,c*,y*)及びx*は正しい偽造なので、
検査式 x*=g y* v c* mod pを満たす
敵A
(m*,x*)
(m*, c*, y*)
B
相手
x*
c*=H(m*,x*)
c*
Hオラクル
2015/10/1
Bの内部
y*
confidential
accept
75
これで、Bはなりすましに成功。
• (m*,c*,y*)及びx*は正しい偽造なので、
検査式 x*=g y* v c* mod pを満たす
敵A
(m*,x*)
(m*, c*, y*)
B
相手
x*
c*=H(m*,x*)
c*
Hオラクル
2015/10/1
Bの内部
y*
confidential
accept
76
さて、Bは署名オラクルを
どうシミュレート
B
署名
オラクル
平文 mi
公開鍵 v
v
敵A
（m*、c*, y*）
Hオラクル
2015/10/1
confidential
77
零知識性の証明の要領で
署名
オラクル
ci, yi ←ランダム
xi←gyivci
平文 mi
署名文 σi=(ci,yi)
公開鍵 v
v
敵A
（m*、c*, y*）
Hオラクル
2015/10/1
confidential
78
Hオラクルのシミュレート
署名
オラクル
ci, yi ←ランダム
xi←gyivci
σi=(ci,yi)
平文 mi
公開鍵 v
敵A
v
（m*、c*, y*）
(mi, xi)
Hオラクル
2015/10/1
confidential
79
ci=H(mi,xi) とすれば、
σi=(ci,yi)は検査式を満たす
署名
オラクル
ci, yi ←ランダム
xi←gyivci
σi=(ci,yi)
平文 mi
公開鍵 v
敵A
v
(mi, xi)
（m*、c*, y*）
ci=H(mi,xi)
Hオラクル
2015/10/1
confidential
80
平文m, 署名文σ＝(c,y)の検査法
• x=gyvc mod p とおく。
• c=H(m,x) をチェック
2015/10/1
confidential
81
Bは、両オラクルを正しくシミュレート
署名
オラクル
ci, yi ←ランダム
xi←gyivci
σi=(ci,yi)
平文 mi
公開鍵 v
敵A
v
(mi, xi)
（m*、c*, y*）
ci=H(mi,xi)
Hオラクル
2015/10/1
confidential
82
証明
• これで、BはAの環境を完全にシミュレート
• よって、Aは最後まで走り、
偽造(m*,c*,y*)を出力
• Bは、それを使ってなりすましに成功。
証明終わり
2015/10/1
confidential
83
定理
• Schnorrの署名に対し、確率εで
偽造に成功する敵Aが存在する。
• Schnorrの認証法において、確率ε/hで
なりすましに成功する敵Bが存在する。
2015/10/1
confidential
84
定理
• Schnorrの署名に対し、確率εで
偽造に成功する敵Aが存在する。
• Schnorrの認証法において、確率ε/hで
なりすましに成功する敵Bが存在する。
• 確率(ε/h)2で離散対数問題を解ける
2015/10/1
confidential
85
演習
• 教科書p.49, 問5.3, 問5.4
2015/10/1
confidential
86

Download Report