黒澤 馨 （茨城大学） kurosawa@mx.ibaraki.ac.jp 情報セキュリティ特論（5） 黒澤　馨 （茨城大学） kurosawa@mx.ibaraki.ac.jp

演習 (2) p=11, q=17, e=3 gcd((p-1)(q-1), e)の値を求めよ。 公開鍵pk、秘密鍵skを求めよ。 演習 (2)　 p=11, q=17, e=3 gcd((p-1)(q-1), e)の値を求めよ。 公開鍵pk、秘密鍵skを求めよ。 平文m=7に対する暗号文Cを求めよ。 上記のCを復号せよ。 2018/11/11 confidential

演習 (2) p=11, q=17, e=3 の場合 (p-1)(q-1)=10×16=160 ユークリッドの互除法より、 演習 (2)　 p=11, q=17, e=3 の場合 (p-1)(q-1)=10×16=160 ユークリッドの互除法より、 　gcd((p-1)(q-1), e) = gcd(160, 3) = 1 2018/11/11 confidential

演習 (2) p=11, q=17, e=3 の場合 (p-1)(q-1)=10×16=160 ユークリッドの互除法より、 演習 (2)　 p=11, q=17, e=3 の場合 (p-1)(q-1)=10×16=160 ユークリッドの互除法より、 gcd((p-1)(q-1),3)=gcd(160, 3)=1 拡張ユークリッドの互除法より、 3×107=1 mod 160 2018/11/11 confidential

演習 (2) p=11, q=17, e=3 の場合 N=pq=187 公開鍵 pk=(N,e)=(187,3) 秘密鍵 d=107 演習 (2)　 p=11, q=17, e=3 の場合 N=pq=187 公開鍵 pk=(N,e)=(187,3) 秘密鍵 d=107 2018/11/11 confidential

演習 (2) 公開鍵 pk=(N,e)=(187,3) 平文 m=7 暗号文 C= me mod N = 73 mod 187 = 156 演習 (2)　 公開鍵 pk=(N,e)=(187,3) 平文 m=7 暗号文 C= me mod N = 73 mod 187 = 156 2018/11/11 confidential

演習 (2) 公開鍵 pk=(N,e)=(187,3) 秘密鍵 d=107 暗号文 C=156 復号 m= Cd mod N 演習 (2)　 公開鍵 pk=(N,e)=(187,3) 秘密鍵 d=107 暗号文 C=156 復号　　m= Cd mod N = 156107 mod 187 = 7 2018/11/11 confidential

ハッシュ関数 長いメッセージ m ハッシュ関数 Ｈ 短い H(m) SHA-1の場合、 160ビット

衝突ペア H(m)=H(m’) となる (m,m’) ただし、m≠m’

衝突困難なハッシュ関数 衝突ペア(m,m’)を求めることが困難な ハッシュ関数 H

鳩ノ巣原理 鳩：n+1羽 巣：n個 ２羽以上の鳩が入る巣が、 　少なくとも１つは存在する。

系１ 366人集まると、誕生日が一致するペアが 　必ず存在する。

系２ H(m)= k ビットのとき、 　 Hを 2k+1 回計算すると、 必ず衝突ペアが求まる。

証明 m=鳩 H(m)=巣：2k個 m1 0…0 … m_2k 1…1 m_{2k+1}

バースディ・パラドックス √365=19人集まっただけで、 　Pr[誕生日が一致するペアが存在]≧0.3

定理 q=√n個のボールを n個のバケツに投げ入れたとき、 　Pr[２個以上のボールが 　　　　　　　　同じバケツに入る]≧0.3

q個のボール バケツ １ バケツ ２ バケツ n …

考え方 Pr[①、②が同じバケツに入る]=1/n Pr[②、③が同じバケツに入る]=1/n … Pr(衝突）～(1/n) ×qC2 = (1/n) ×q(q-1)/2 ～ (1/n) ×q2/2 q=√nのとき、Pr(衝突)～1/2=0.5

定理 q=√n個のボールを n個のバケツに投げ入れたとき、 　Pr[２個以上のボールが 　　　　　　　　同じバケツに入る]≧0.3

系3 H(m)= k ビットのとき、 　 Hを √2k=2k/2 回計算すると、 0.3以上の確率で、衝突ペアが求まる。

SHA-1 米国標準のハッシュ関数 H(m)=160ビット Hを2160/2= 280回計算すると、 0.3以上の確率で衝突ペアが求まる。 しかし、 280回=１億年

基本圧縮関数 512ビット f 160ビット 160ビット

メッセージのPadding m || 0…0 (512ビットの倍数) = x1 || x2 || … xB || M=x1 || x2 || … ||xB || L(=mのビット長) ただし、各|xi|=512ビット

Merkle-Damgard 変換 … L x1 f f ハッシュ値 H(m) hB IV=0…0 h1 …

定理 fが衝突困難なら、Hも衝突困難

証明 H(m)=H(m’)となる(m,m’)が見つかったと仮定 |m|≠|m’|の場合

|m|≠|m’|の場合 f f H(m)=H(m’)なので、f(|m|, hB)=f(|m’|, hB’) X B+1‘= |m’| xB+1= |m| f f H(m’) = f (|m’|, hB‘) H(m) = f (|m|, hB) hB hB‘ H(m)=H(m’)なので、f(|m|, hB)=f(|m’|, hB’) いま、|m|≠|m’|なので、fの衝突ペアが求まった。

|m|=|m’|の場合 f f H(m)=H(m’)なので、f(|m|, hB)=f(|m’|, hB’) X B+1‘=|m’| xB+1=|m| f f H(m’) = f (|m’|,hB‘) H(m) = f (|m|,hB) hB hB‘ H(m)=H(m’)なので、f(|m|, hB)=f(|m’|, hB’) hB≠hB’なら、fの衝突ペアが求まった。

hB=hB’の場合 f f hB=hB’なので、f(xB, hB-1)=f(xB’, hB-1’) いま、 (xB, hB-1)≠(xB’, hB-1’)なら、 　　　　fの衝突ペアが求まった。

m≠m’なので、 (x1, …, xB)≠(x1’, …, xB’) よって、 どこかで fの衝突ペアが求まる。 　　　　　　　　　　　　　　　　　　　　　（証明終）

RSA暗号 公開鍵：N(=p・q)、e 秘密鍵：d s.t. ed = 1 mod (p-1)(q-1) (1) 平文： M ∈ ZN 暗号文： 復号：

ディジタル署名 公開鍵：N(=p・q)、e 秘密鍵：d 平文：　 M 署名文： 　　　　dを知っている人しか計算できない

ディジタル署名 公開鍵：N(=p・q)、e 秘密鍵：d 平文：　 M 署名文： 検査：

デジタル署名 署名文σは、 　 秘密鍵dを知っている人しか計算できない。 (m, σ)の正当性は、 公開鍵(N,e)を使って誰でも検査できる。

敵の攻撃法 公開鍵only攻撃 既知平文攻撃 Non-adaptive 選択平文攻撃 Adaptive 選択平文攻撃 平文の代わりにメッセージという場合もあり。

公開鍵only攻撃 N(=p・q)、e 敵 (m*、σ*)

Hが無い場合(1) 公開鍵only攻撃 検査式は、σe=m mod N (1) σをランダムに選ぶ。 (2) m=σe mod Nとする。

既知平文攻撃 N(=p・q)、e 敵 署名 オラクル m1、m2、．．． σ1、σ2、．．． (m*、σ*)

Non-adaptive 選択平文攻撃 N(=p・q)、e m1、m2、．．． 敵 署名 オラクル σ1、σ2、．．． (m*、σ*)

Hが無い場合(2) σ＝md mod N N(=p・q)、e 敵 (m, σ’/r=md) 署名 オラクル σ’=(rem)d m’=rem mod N 敵 署名 オラクル σ’=(rem)d =(re)dmd =r md (m, σ’/r=md)

Adaptive 選択平文攻撃 N(=p・q)、e m1 敵 署名 オラクル σ1 (m*、σ*)

敵は、σ1に基づいてm2を選ぶ。 N(=p・q)、e m2 敵 署名 オラクル σ2 (m*、σ*)

敵は、σ1,σ2基づいてm3を選ぶ。 N(=p・q)、e m3 敵 署名 オラクル σ3 (m*、σ*)

望ましい署名方式 Adaptive選択平文攻撃に対しても、偽造が不可能な署名方式

ランダムオラクルモデル ハッシュ関数Hを理想化したモデル ランダムオラクル H H(x)　←　乱数 x 各参加者

選択平文攻撃 in the ランダムオラクルモデル N(=p・q)、e m’1、m’2、．．． m1、m2、．．． H H(m)←乱数 敵 署名 オラクル σ’1、σ’2、．．． σ1、σ2、．．．

RSA問題 N,e,y(=xe mod N)から、xを求めよ。 RSA仮定 RSA問題を解く多項式時間アルゴリズムは存在しない。

定理 RSA署名方式は、adaptive選択平文攻撃に対しても偽造が不可能 　under RSA仮定 　in the ランダムオラクルモデル。

証明 Adaptive 選択平文攻撃によって 偽造に成功する敵のプログラムAが 存在したと仮定すると、 RSA問題を解けるアルゴリズムBを 　 構成できることを示す。

B N(=p・q)、e 敵A N、e、y(=xe mod N) 確率εで出力 確率 x qH回質問 qs回質問 H 署名 H(m)←乱数 m’1、m’2、．．． m1、m2、．．． H H(m)←乱数 敵A 署名 オラクル σ1、σ2、．．． H(m’1), H(m’2), … 確率εで出力 確率 x

B N(=p・q)、e 敵A N、e、y(=xe mod N) 署名 Hオラクル オラクル Bがシミュレート Bがシミュレート このプログラムAはgiven Bがシミュレート

Bの動作 Hオラクル、署名オラクルをシミュレートする。 しかし、Bは秘密鍵dを知らない。 Bは、どうやって署名オラクルをシミュレート 　すればいいのか？

N、e、y(=xe mod N) B N(=p・q)、e m1 H 敵A 署名 オラクル

N、e、y(=xe mod N) B N(=p・q)、e m1 H 敵A 署名 オラクル H(m1)=r1e mod N

敵Aがm1をHオラクルに質問したとき、Bは i m H(m) σ 1 m1 r1e 2 … qs+qH

N、e、y(=xe mod N) B N(=p・q)、e m1 m1 H 敵A 署名 オラクル H(m1)=r1e mod N

N、e、y(=xe mod N) B N(=p・q)、e m1 m1 H 敵A 署名 オラクル σ=r1 H(m1)=r1e mod N

B N(=p・q)、e 敵A 署名 H オラクル こうすれば、検査式 H(m1)=σ1e mod N が成立 m1 m1 σ1=r1 H(m1)=r1e mod N 検査式 H(m1)= r1e =σ1e mod N

敵Aがm1を署名オラクルに質問した時、 i m H(m) σ 1 m1 r1e r1 2 … qs+qH

N、e、y(=xe mod N) B N(=p・q)、e m2 H 敵A 署名 オラクル

N、e、y(=xe mod N) B N(=p・q)、e m2 H 敵A 署名 オラクル σ=r2

敵Aがm2を署名オラクルに質問したとき、 i m H(m) σ 1 m1 r1e r1 2 m2 r2 … qs+qH

N、e、y(=xe mod N) B N(=p・q)、e m2 m2 H 敵A 署名 オラクル r2

N、e、y(=xe mod N) B N(=p・q)、e m2 m2 H 敵A 署名 オラクル r2 H(m2)=r2e mod N

敵Aがm2をHオラクルに質問したとき、Bは i m H(m) σ 1 m1 r1e r1 2 m2 r2e r2 … qs+qH

N、e、y(=xe mod N) B N(=p・q)、e H 敵A 署名 オラクル m*, σ*

N、e、y(=xe mod N) B N(=p・q)、e mi =m* H 敵A 署名 オラクル m*, σ*

N、e、y(=xe mod N) B N(=p・q)、e mi =m* H 敵A 署名 オラクル H(mi)=y m*, σ*

敵Aは、i番目のmで偽造 m H(m) σ 1 m1 r1e r1 2 m2 r2e r2 … i m* =偽造 qs+qH

Bは、H(m)=yとおく i m H(m) σ 1 m1 r1e r1 2 m2 r2e r2 … i=偽造 m* y qs+qH

B N(=p・q)、e 敵A N、e、y(=xe mod N) 署名 H オラクル mi =m* H(mi)=y 検査式 （σ*)e=H(m*)=y (=xe) mod N m*, σ* x= σ*

敵Aは、偽造文σ*を出力 i m H(m) σ 1 m1 r1e r1 2 m2 r2e r2 … i=偽造 m* y σ* qs+qH

Bは、y=xe mod Nの解として、x=σ*を出力 i m H(m) σ 1 m1 r1e r1 2 m2 r2e r2 … i=偽造 m* y x=σ* qs+qH

B Bは、iの値を知らない 敵A N、e、y(=xe mod N) 署名 H オラクル mi =m* H(mi)=y m*, σ*

Bは、iの値をランダムに推測 i m H(m) σ 1 m1 r1e r1 2 m2 r2e r2 … i=推測 m* y x=σ* qs+qH

Pr(ランダムなiの値が当たる)=1/ (qs+qH) m H(m) σ 1 m1 r1e r1 2 m2 r2e r2 … i=推測 m* y x=σ* qs+qH

B N(=p・q)、e 敵A N、e、y(=xe mod N) 確率εで出力 確率 x qH回質問 qs回質問 H 署名 H(m)←乱数 m’1、m’2、．．． m1、m2、．．． H H(m)←乱数 敵A 署名 オラクル σ1、σ2、．．． H(m’1), H(m’2), … 確率εで出力 確率 x

B N(=p・q)、e 敵A N、e、y(=xe mod N) 確率εで出力 確率 x qs回質問 H 署名 H(m)←乱数 オラクル m’1、m’2、．．． m1、m2、．．． H H(m)←乱数 敵A 署名 オラクル σ’1、σ’2、．．． σ1、σ2、．．． 確率εで出力 確率 (Coron’2000) x

Katz and Wang (2003) 署名文： 検査： 定理：

B N(=p・q)、e 敵A N、e、y(=xe mod N) 確率ε 確率 x qs回質問 署名 H オラクル (0,m1) m1、m2、．．． H H(0,m1)←乱数 H(1,m2)←乱数 敵A 署名 オラクル σ1、σ2、．．． ．．． Bがうまくシミュレート 確率ε Bがうまくシミュレート 確率 x

Bはオラクルを以下の様にシミュレート ．．． ．．． ．．． ．．． 敵Aの出力する は mi bi ←ランダム σi m1 r1 m2 1 r1 m2 1 r2 ．．． ．．． ．．． ．．． （注）ri、tiはランダムに選ばれる 敵Aの出力する　　は

の場合 mi bi ←ランダム σi m1 r1 m2 1 r2 ．．． ．．． ．．． ．．． mj = = = 1

なので Bがxを出力する確率は

の場合 mi bi ←ランダム σi m1 r1 m2 1 r2 ．．． ．．． ．．． ．．． mj = = = 1

なので Bがxを出力する確率は

今、敵Aが　　　　 を確率　　 で 出力すると仮定する。 このとき、Bが x を出力する確率は Pr[xを出力] =

演習(1) n>kと仮定する。 このとき、nビットのメッセージをkビットに圧縮すると、必ず衝突ペアが存在するのはなぜか。

演習(2) ハッシュ値が40ビットであるハッシュ関数Hを考える。確率0.3以上で衝突ペアを求めたい。Hを何回計算すればいいか。

メッセージのPadding m || 0…0 (512ビットの倍数) = x1 || x2 || … xB || M=x1 || x2 || … ||xB || L(=mのビット長) ただし、各|xi|=512ビット

Merkle-Damgard 変換 … L x1 f f ハッシュ値 H(m) hB IV=0…0 h1 …

演習(3) … xB x1 f f hB-1 H(m)=hB IV=0…0 h1 … 上記の構成においては、衝突ペアが求まることを示せ。

演習(4) … xB x1 f f hB-1 IV=0…0 h1 … hB H(m)=hB||L 上記の構成は、衝突困難であることを示せ。