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