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

Presentation on theme: "黒澤 馨 （茨城大学） kurosawa@mx.ibaraki.ac.jp 情報セキュリティ特論（5） 黒澤　馨 （茨城大学） kurosawa@mx.ibaraki.ac.jp."— Presentation transcript:

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

2 演習 (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

3 演習 (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

4 演習 (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

5 演習 (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

6 演習 (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

7 演習 (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 = mod 187 = 7 2018/11/11 confidential

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

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

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

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

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

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

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

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

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

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

18 考え方 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

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

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

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

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

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

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

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

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

27 |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の衝突ペアが求まった。

28 |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の衝突ペアが求まった。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

50 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

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

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

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

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

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

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

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

58 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

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

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

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

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

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

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

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

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

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

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

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

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

71 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= σ*

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

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

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

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

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

77 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

78 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

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

80 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

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

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

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

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

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

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

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

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

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

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

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

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