黒澤 馨 （茨城大学） kurosawa@mx.ibaraki.ac.jp 情報セキュリティ特論（6） 黒澤　馨 （茨城大学） kurosawa@mx.ibaraki.ac.jp 2017/3/13 confidential

RSA暗号 　　 素因数分解の困難さ ElGamal暗号 　　 離散対数問題の困難さ 2017/3/13 confidential

RSA暗号 　　 素因数分解の困難さ ElGamal暗号 　　 離散対数問題の困難さ 　　答えは、x=3 2017/3/13 confidential

離散対数問題 y=ax mod p (=素数） となるxを求めよ、という問題。 p=1024ビットのとき、10億年 2017/3/13 confidential

mod 5 において フェルマーの定理 2017/3/13 confidential

mod 5 において 2の位数は4 フェルマーの定理 4の位数は2 3の位数は4 2017/3/13 confidential

mod 5 において 2の位数は4: p-1(=4)を割り切る 4の位数は2: p-1(=4)を割り切る 3の位数は4: 2017/3/13 confidential

aの位数 　　 となる最小のn 定理 　　 任意の元aの位数は、p-1を割り切る。 2017/3/13 confidential

Diffie-Hellmanの鍵共有法 p = 大きな素数, q = p-1を割り切る大きな素数 g = 位数が大きな素数qの元 　　　gq=1 mod p 2017/3/13 confidential

Diffie-Hellmanの鍵共有法 2017/3/13 confidential

Diffie-Hellmanの鍵共有法 2017/3/13 confidential

Diffie-Hellmanの鍵共有法 敵 盗聴 2017/3/13 confidential

敵のゴール p, q, DH問題 1億年(DH仮定) 2017/3/13 confidential

離散対数問題との関係 離散対数問題 DLOG 10億年(離散対数仮定) ? DH問題 1億年(DH仮定) 2017/3/13 confidential

DLOGを解くアルゴリズムAが存在するなら DHを解くアルゴリズムBが存在する （証明） （定理） DLOGを解くアルゴリズムAが存在するなら DHを解くアルゴリズムBが存在する （証明） B A 2017/3/13 confidential

DLOGを解くアルゴリズムAが存在するなら DHを解くアルゴリズムBが存在する （証明） （定理） DLOGを解くアルゴリズムAが存在するなら DHを解くアルゴリズムBが存在する （証明） B A 2017/3/13 confidential

PPT : Probabilistic Polynomial Time 確率的 多項式 時間 確率的　　　　 多項式　　　 時間 PPTアルゴリズム A 乱数テープ R 2017/3/13 confidential

R a PPTアルゴリズム A 乱数テープ R Aがaを 出力 この面積 Pr(Aが解く) = 全面積 2017/3/13 confidential

離散対数仮定 確率ε以上でDLOGを解くような PPTアルゴリズムは存在しない DH仮定 PPTアルゴリズムは存在しない 2017/3/13 confidential

定理 離散対数仮定が成り立てば、 　DH仮定が成り立つ。 2017/3/13 confidential

ElGamal暗号 公開鍵： p= 大きな素数 q= p-1を割り切る大きな素数 g=位数がqとなる元 y (=gx mod p) 2017/3/13 confidential

ElGamal暗号 公開鍵： p, q, g, y(=gx mod p) 秘密鍵: x 平文： m 暗号化： r ← zp-1 E(m)=(gr, myr) 2017/3/13 confidential

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

敵への入力 公開鍵：p,q,g,y 暗号文: (gr, m・yr) mod p 2017/3/13 confidential

巡回群 <g>={1, g, g2, …, gq-1} は、 （生成元）gで生成される巡回群 2017/3/13 confidential

DDH仮定 (g, gr, y, yr) と (g, gr, y, z)は 多項式時間で区別できない。 ただし、 　多項式時間で区別できない。 ただし、 　z は<g> からランダムに選ばれた要素 2017/3/13 confidential

DDH仮定より 平文： m∈{1, g, g2, …, gq-1} とする。 暗号文： E(m) = (gr, myr) ～(gr, m z ) ただし、 　　zは<g>からランダムに選ばれた要素。 2017/3/13 confidential

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

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

ElGamal暗号の安全性 DDH仮定の下、 平文mに関する情報は、何ももれていない。 2017/3/13 confidential

なりすまし攻撃 B A オレオレ 2017/3/13 confidential

Aの公開鍵 v (=g-s mod p) B A s s v =g-s mod p をチェック 2017/3/13 confidential

Bが、なりすませてしまう C B A s s s オレはAだ 2017/3/13 confidential

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

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

零知識性 Bには、sに関する情報が一切漏れていない。 2017/3/13 confidential

零知識性 Bには、sに関する情報が一切漏れていない if Bは、自分自身で通信系列(x,c,y)を 生成できる。 2017/3/13 confidential

定理 Bは、自分自身で通信系列(x,c,y)を 生成できる。 2017/3/13 confidential

証明 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

証明 1. c←ランダム 2. y←ランダム 3. x =gyvc mod p B B x c y 2017/3/13 confidential

証明 1. c←ランダム 2. y←ランダム 3. x =gyvc mod p B B 4. x c y 2017/3/13 confidential

健全性 Bをacceptさせられるなら、Aはsを知っている。 2017/3/13 confidential

健全性 Bをacceptさせられるなら、Aはsを知っている。 Aをサブルーチンとして使って、sを求めることができる 2017/3/13 confidential

定理 AがBをacceptさせられる Aをサブルーチンとして使って、 sを求めることができる 2017/3/13 confidential

証明 B A x c c←ランダム y x =gyvc mod p 2017/3/13 confidential

Aを初期状態にリセット B A 2017/3/13 confidential

もう一度、Aを走らせる B A x 2017/3/13 confidential

証明 B A x c’ c’←ランダム 2017/3/13 confidential

証明 B A x c’ c’←ランダム y’ x =gy’vc’ mod p 2017/3/13 confidential

証明 x =gyvc mod p x =gy’vc’ mod p B A x c, c’ y, y’ 2017/3/13 confidential

証明 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

証明 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

証明 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

証明 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

敵のモデル 学習段階 なりすまし段階 2017/3/13 confidential

学習段階 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

なりすまし段階 B 敵 x c c←ランダム y x =gyvc mod p 2017/3/13 confidential

定理 なりすましに成功する敵が存在したと仮定すると、離散対数問題を解ける。 2017/3/13 confidential

v=g-s mod p B なりすまし段階 学習段階 B 敵 (x’’,c’’,y’’) x c 敵 y s 2017/3/13 confidential s

v=g-s mod p なりすまし段階 学習段階 B 敵 (x’’,c’’,y’’) x c,c’ 敵 y,y’ 2017/3/13 confidential

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’)

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

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

選択平文攻撃 署名 オラクル 署名文 σ 平文 m 敵 公開鍵 （平文*、署名文*） 2017/3/13 confidential

ランダム・オラクル・モデル における選択平文攻撃 署名 オラクル 署名文 σ 平文 m 敵 公開鍵 （平文*、署名文*） 乱数 c=H(m,x) (m, x) Hオラクル 2017/3/13 confidential

定理 ROモデルにおいて、 Schnorrの署名に対し、確率εで 偽造に成功する敵Aが存在する。 ただし、 　ただし、 　AはHオラクルに高々h回質問すると仮定する。 Schnorrの認証法において、確率ε/hで なりすましに成功する敵Bが存在する。 2017/3/13 confidential

ランダム・オラクル・モデル における選択平文攻撃 署名 オラクル 署名文 σi 平文 mi 敵 A 公開鍵 v （m*、c*, y*） 乱数 cj=H(mj,xj) (mj, xj) Hオラクル 2017/3/13 confidential

なりすましの敵 B 署名 オラクル 署名文 σi 平文 mi なりすますぞ！ 偽造の 敵 A 公開鍵 v v （m*、c*, y*） 乱数 cj=H(mj,xj) (mj, xj) Hオラクル 2017/3/13 confidential

Bのなりすまし戦略 偽造の敵Aは、Hオラクルに 偽造用の(m*, x*)をk番目に質問する。 相手 B 偽造の 敵A (m*,x*) 2017/3/13 confidential

Bはkをランダムに推測 Bは、x*をAに送る。 敵 Hオラクル (m*,x*) ＝ B 相手 x* 2017/3/13 confidential

Bのなりすまし戦略 相手がc*を返してきた。 敵 Hオラクル (m*,x*) ＝ B 相手 x* c* 2017/3/13 confidential

Bのなりすまし戦略 Bは、c*=H(m*,x*)とする。 敵 A B 相手 ＝ (m*,x*) x* c*=H(m*,x*) c* 2017/3/13 confidential

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

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

よって、相手は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

これで、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

さて、Bは署名オラクルを どうシミュレート 平文 mi 敵 A 公開鍵 v v （m*、c*, y*） Hオラクル 2017/3/13 confidential

零知識性の証明の要領で 署名 オラクル ci, yi ←ランダム xi←gyivci 署名文 σi=(ci,yi) 平文 mi 敵 A （m*、c*, y*） Hオラクル 2017/3/13 confidential

Hオラクルのシミュレート 署名 オラクル ci, yi ←ランダム xi←gyivci σi=(ci,yi) 平文 mi 敵 A 公開鍵 v （m*、c*, y*） (mi, xi) Hオラクル 2017/3/13 confidential

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

平文m, 署名文σ＝(c,y)の検査法 x=gyvc mod p とおく。 c=H(m,x) をチェック 2017/3/13 confidential

Bは、両オラクルを正しくシミュレート 署名 オラクル ci, yi ←ランダム xi←gyivci σi=(ci,yi) 平文 mi 敵 A （m*、c*, y*） (mi, xi) ci=H(mi,xi) Hオラクル 2017/3/13 confidential

証明 これで、BはAの環境を完全にシミュレート よって、Aは最後まで走り、 偽造(m*,c*,y*)を出力 証明終わり 2017/3/13 confidential

定理 Schnorrの署名に対し、確率εで 偽造に成功する敵Aが存在する。 Schnorrの認証法において、確率ε/hで なりすましに成功する敵Bが存在する。 2017/3/13 confidential

定理 Schnorrの署名に対し、確率εで 偽造に成功する敵Aが存在する。 Schnorrの認証法において、確率ε/hで なりすましに成功する敵Bが存在する。 確率(ε/h)2で離散対数問題を解ける 2017/3/13 confidential

演習 教科書p.49, 問5.3, 問5.4 2017/3/13 confidential