Download presentation
Presentation is loading. Please wait.
1
黒澤 馨 （茨城大学） kurosawa@mx.ibaraki.ac.jp
情報セキュリティ特論（7） 黒澤 馨 （茨城大学）
2
RSA暗号 C=Me mod N C=0のとき、M=0とわかってしまう。 C=1のとき、M=1とわかってしまう。 平文Mのどんな部分情報も
漏れないようにするには？
3
公開鍵暗号系 鍵生成アルゴリズム G 暗号化アルゴリズム E 復号アルゴリズム D
4
公開鍵暗号系の安全性 IND-CPA安全性 Chosen Plaintext（平文）Attack IND-CCA安全性
Chosen Ciphertext（暗号文） Attack
5
IND-CPAを定義するゲーム チャレンジャー 敵 pk (pk,sk)←G m0, m1 b←{0,1} C=E(mb) b’
6
IND-CPA安全 if |Pr(b’=b)-1/2|<ε
チャレンジャー 敵 pk (pk,sk)←G m0, m1 b←{0,1} C=E(mb) b’
7
IND-CPA安全 if |Pr(b’=b)-1/2|<ε for 全ての多項式時間の敵
チャレンジャー 敵 pk (pk,sk)←G m0, m1 b←{0,1} C=E(mb) b’
8
ElGamal暗号のIND-CPA安全性
チャレンジャー 敵 g, y x←ランダム y=gx mod p m0, m1 b←{0,1} C=(gr, mbyr) C b’ Pr( b’=b )≃1/2
9
定理 ElGamal暗号はIND-CPA安全 under DDH仮定 （証明） 演習
10
RSA≠IND-CPA安全 チャレンジャー 敵の動作 m0=0, m1=1 b←{0,1} C=mbe mod N (N,e)
b’=0 if C=0 b’=1 if C=1 Pr( b’=b )=1
11
Pr(b’=b)=1なので、 |Pr(b’=b)-1/2|=|1-1/2|=1/2≧ε よって、 RSA暗号≠IND-CPA安全
12
IND-CPA安全なRSA-based暗号
c1=re mod N c2=M + H(r) mod N ただし、Hはハッシュ関数 暗号文 C=(c1, c2)
13
IND-CPA安全なRSA-based暗号
K=H(r) c1=re mod N c2=M+擬似乱数生成器(K) (One-Time-PAD) 暗号文 C=(c1, c2) 公開鍵暗号でKを暗号化 共通鍵暗号で平文Mを暗号化
14
IND-CPA安全なRSA-based暗号
c1=re mod N c2=M + H(r) mod N 暗号文 C=(c1, c2)
15
AES暗号を利用した擬似乱数生成器 Seed 出力 AES AES AES … … AES暗号が擬似ランダム置換と仮定すると、
これは、標準モデルで擬似乱数生成器
16
ハイブリッド暗号 C= 公開鍵暗号(共通鍵K) + 共通鍵暗号（K,平文m) 公開鍵を使うので、 ハイブリッド暗号は公開鍵暗号の１つ
17
ハイブリッド暗号 C= 公開鍵暗号(共通鍵K) ← KEM + 共通鍵暗号（K,平文m) ← DEM 公開鍵を使うので、
ハイブリッド暗号は公開鍵暗号の１つ
18
KEM-DEMフレームワーク CPA安全なKEM One-Time-PAD = IND-CPA安全な 公開鍵暗号（ハイブリッド暗号）
19
KEM 鍵生成アルゴリズム G 暗号化アルゴリズム E E(pk)=(暗号文 C, 鍵 K) 復号アルゴリズム D D(C, sk)=K
20
RSA-KEM 公開鍵 (N,e) 暗号化 r ← ランダム 暗号文 C=re mod N 鍵 K=H(r)
21
KEMのCPA安全性 チャレンジャー 敵 (pk,sk)←G (C, K0) ← E(pk) K1=ランダム b←{0,1} C, Kb
Pr( b’=b )～1/2
22
KEMはCPA安全 If 全ての多項式時間の敵に対し、 |Pr(b’=b)-1/2|<ε
23
KEMのＣPＡ安全性 in RO 敵 b’ H r1, r2, H(r1), H(r2), pk, C, Kb Pr( b’=b )～1/2
24
RSA-KEMのＣPＡ安全性 in RO 敵 b’ (N,e), C(=re mod N), K0 =H(r) or K1 =乱数 H
r1, r2, H(r1), H(r2), (N,e), C(=re mod N), K0 =H(r) or K1 =乱数
25
定理 RSA仮定の下で、 RSA-KEMはCPA安全 in the ランダム・オラクル・モデル
26
補題 Pr(b’=b)-1/2=ε (non-negligible) と仮定すると Pr(敵がrをHオラクルに質問する)≧2ε
27
証明 X=敵がrをHオラクルに質問する事象 Pr(b’=b)= Pr(b’=b, X)+ Pr(b’=b, ￢X)
28
証明 X=敵がrをHオラクルに質問する事象 Pr(b’=b)= Pr(b’=b, X)+ Pr(b’=b, ￢X)
=Pr(b’=b | X) Pr(X) + Pr(b’=b | ￢ X) Pr(￢ X)
29
証明 X=敵がrをHオラクルに質問する事象 Pr(b’=b)= Pr(b’=b, X)+ Pr(b’=b, ￢X)
=Pr(b’=b | X) Pr(X) + Pr(b’=b | ￢ X) Pr(￢ X) ≦Pr(X) + 1/2 Pr(￢ X)
30
証明 X=敵がrをHオラクルに質問する事象 Pr(b’=b)= Pr(b’=b, X)+ Pr(b’=b, ￢X)
=Pr(b’=b | X) Pr(X) + Pr(b’=b | ￢ X) Pr(￢ X) ≦Pr(X) + 1/2 Pr(￢ X) =Pr(X) + 1/2 (1-Pr(X))
31
証明 X=敵がrをHオラクルに質問する事象 Pr(b’=b)= Pr(b’=b, X)+ Pr(b’=b, ￢X)
=Pr(b’=b | X) Pr(X) + Pr(b’=b | ￢ X) Pr(￢ X) ≦Pr(X) + 1/2 Pr(￢ X) =Pr(X) + 1/2 (1-Pr(X)) =1/2+1/2Pr(X)
32
証明 X=敵がrをHオラクルに質問する事象 Pr(b’=b)= Pr(b’=b, X)+ Pr(b’=b, ￢X)
=Pr(b’=b | X) Pr(X) + Pr(b’=b | ￢ X) Pr(￢ X) ≦Pr(X) + 1/2 Pr(￢ X) =Pr(X) + 1/2 (1-Pr(X)) =1/2+1/2Pr(X) ゆえに、1/2Pr(X)≧ Pr(b’=b)-1/2=ε
33
補題 Pr(b’=b)-1/2=ε (non-negligible) と仮定すると Pr(敵がrをHオラクルに質問する)≧2ε （証明完了）
34
RSA-KEMのCPA安全性の証明 敵 b’ (N, e), C=re mod N (N, e), C, b←{0,1}、Kb =乱数 H
r1, r2, H(r1), H(r2), b’ (N, e), C=re mod N (N, e), C, b←{0,1}、Kb =乱数 r
35
(N, e), C=re mod N (N, e), C, Kb =乱数 補題より どこかでr H 敵
36
(N, e), C=re mod N (N, e), C, Kb =乱数 補題より どこかでr H 敵 r if C=re mod N
37
(N, e), C=re mod N (N, e), C, Kb =乱数 r1 H 敵 r=r1 if C=r1e mod N
38
(N, e), C=re mod N (N, e), C, Kb =乱数 r1 H 敵 C≠r1e mod Nのとき H(r1)=乱数
39
(N, e), C=re mod N (N, e), C, Kb =乱数 r2 H 敵 r=r2 if C=r2e mod N
40
定理 RSA仮定の下で、 RSA-KEMはCPA安全 in the RO モデル （証明完了）
41
定理 RSA仮定の下で、以下の暗号系はCPA安全 in the RO モデル r←ランダム、K=H(r) c1=re mod N
c2=M+擬似乱数生成器(K) (One-Time-PAD) 暗号文 C=(c1, c2) RSA-KEM
42
証明 CPA安全なKEM（公開鍵暗号） + One-Time-PAD = IND-CPA安全な公開鍵暗号
RSA-KEMはCPA安全、を証明した。 （証明終）
43
ハイブリッド暗号の効能 IND-CPA (IND-CCA) 安全な公開鍵暗号 を簡単に作れる 平文は、任意の長さのビット列でよい。
44
ハイブリッド暗号に関する定理 CPA安全なKEM（公開鍵暗号） One-Time-PAD = IND-CPA安全な公開鍵暗号 （証明）
45
ハイブリッド暗号のIND-CPA チャレンジャー 敵 (pk,sk)←G m0, m1 b←{0,1} (c1*, K*)←KEM(pk)
c2*=mb+擬似乱数(K*) C*=(c1*, c2*) b’
46
Game 0 チャレンジャー 敵 (pk,sk)←G m0, m1 b←{0,1} (c1*, K* )←KEM(pk)
c2*=mb+擬似乱数(seed=K* ) C*=(c1*, c2*) b’
47
Game 1 チャレンジャー 敵 (pk,sk)←G m0, m1 b←{0,1} (c1*, K*)←KEM(pk)
c2*=mb+擬似乱数(seed=乱数) C*=(c1*, c2*) b’
48
補題１ ハイブリッド暗号において Pr(b’=b in Game 0)～ Pr(b’=b in Game 1)
if KEM is CPA 安全 (証明） ハイブリッド暗号の敵を基に、 KEMの敵を以下のように構成する。
49
KEMの敵 KEMの チャレンジャー ハイブリッド暗号の敵 (pk,sk)←G (c1*, K0)←KEM K1←ランダム d←{0,1}
c1*, Kd m0, m1 b←{0,1} c2*= mb + 擬似乱数(seed=Kd) C*=(c1*, c2*) b’ d’ =1 if b’=b
50
d=0のとき KEMの敵 KEMの チャレンジャー ハイブリッド暗号の敵 Game 0 d←0 (pk,sk)←G
(c1*, K0)←KEM K1←ランダム d←0 c1*, K0 m0, m1 b←{0,1} c2*= mb + 擬似乱数(seed=K0) C*=(c1*, c2*) b’ d’ =1 if b’=b
51
d=1のとき KEMの敵 KEMの チャレンジャー ハイブリッド暗号の敵 Game 1 d←1 (pk,sk)←G
(c1*, K0)←KEM K1←ランダム d←1 c1*, K1 m0, m1 b←{0,1} c2*= mb + 擬似乱数(seed=K1) C*=(c1*, c2*) b’ d’ =1 if b’=b
52
d’=1 if b’=b なので、 Pr(d’=1 when d=0)=Pr(b’=b in Game 0)
53
証明 Pr(d’=1 when d=0)=Pr(b’=b in Game 0)
KEMの敵は、d=0 or 1を区別できないので、 Pr(d’=1 when d=0)～ Pr(d’=1 when d=1) よって、 Pr(b’=b in Game 0) ～ Pr(b’=b in Game 1)
54
補題１ ハイブリッド暗号において Pr(b’=b in Game 0)～ Pr(b’=b in Game 1)
if KEM is CPA 安全 （証明完了）
55
補題２ Pr(b’=b in Game 1)～1/2
56
Game 1 チャレンジャー 敵 (pk,sk)←G m0, m1 b←{0,1} (c1*, K*)←KEM(pk)
c2*=mb+擬似乱数(seed=乱数) C*=(c1*, c2*) b’
57
Game 1 チャレンジャー 敵 (pk,sk)←G m0, m1 b←{0,1} (c1*, K*)←KEM(pk)
c2*=mb+擬似乱数(seed=乱数) C*=(c1*, c2*) c2*は、c1*とは独立なone-time-pad なので、 Pr(b’=b)=1/2 b’
58
補題２ Pr(b’=b in Game 1)～1/2 （証明完了）
59
ハイブリッド暗号に関する定理 CPA安全なKEM（公開鍵暗号） + One-Time-PAD = IND-CPA安全な公開鍵暗号 （証明）
補題１、補題２より。
60
公開鍵暗号系の安全性 IND-CPA安全性 Chosen Plaintext（平文）Attack IND-CCA安全性
Chosen Ciphertext（暗号文） Attack
61
公開鍵暗号のIND-CCA安全性 チャレンジャー 復号オラクル 敵 (pk,sk)←G m0, m1 b←{0,1} C=E(mb) pk
復号してもらえる b’
62
KEMのCCA安全性 チャレンジャー (pk,sk)←G 敵 C, Kb 復号オラクル (C, K0) ← E(pk) K1=ランダム
復号してもらえる 復号オラクル (C, K0) ← E(pk) K1=ランダム b←{0,1}
63
DEM（共通鍵暗号）のCCA安全性 復号オラクル チャレンジャー 敵 m0, m1 K←ランダム b←{0,1} C=EK(mb)
復号してもらえる b’ CCA安全 if |Pr(b’=b)-1/2|<ε
64
KEM-DEMフレームワーク CCA安全なKEM（公開鍵暗号） + CCA安全なDEM（共通鍵暗号） = IND-CCA安全な公開鍵暗号
公開鍵暗号の暗号文 C=KEM(共通鍵K)+DEM(共通鍵K,m)
65
定理 RSA仮定の下で、 RSA-KEMはCCA安全 In the RO モデル
66
CCA安全なDEMの構成法 K → → 暗号文 C=(E, Tag) 擬似乱数生成器 敵は、MACオラクルに１回だけ質問して偽造する
67
IND-ＣＣＡ安全なハイブリッド暗号 r ← ランダム 共通鍵 Ｋ＝Ｈ（ｒ） 暗号文 C=(φ, χ) χ＝（E, Tag)
公開鍵 (N,e) r ← ランダム 共通鍵 Ｋ＝Ｈ（ｒ） 暗号文 C=(φ, χ) KEMの暗号文 χ＝（E, Tag) DEMの暗号文 （鍵K) RSA仮定の下で、IND-ＣＣＡ安全 in the RO model
68
ROモデル IND-CPA安全な ハイブリッド暗号の 構成法 IND-CCA安全な RSA-KEM + one-time-pad + MAC
69
ROなしで、IND-CPAな暗号 ElGamal暗号 Paillier暗号 DDH仮定 N次剰余仮定
70
N次剰余仮定 xN = a+bN mod N2 としたとき、 (a,b) と (a, 乱数）は
computationally indistinguishable ただし、 x←{1,2,…, N-1}
71
Paillier暗号 公開鍵 N=pq 秘密鍵 p, q 暗号化 x ←{1,2,…, N-1} xN=a+bN mod N2
C=(a, b+m mod N)
72
Paillier暗号 暗号化 x ←{1,2,…, N-1} xN=a+bN mod N2 C=(a, b+m mod N) 復号
xN =a mod N より、x=ad mod N xN=a+bN mod N2 により、bを求める
73
定理 Paillier暗号は、N次剰余仮定の下で IND-CPA安全
74
N次剰余仮定 xN = a+bN mod N2 としたとき、 (a,b) と (a, 乱数）は
computationally indistinguishable とは、どういう意味か？
75
確率変数 XとY Pr(X=a) Pr(Y=a) a
76
Statistically distance
|X-Y| Pr(X=a) Pr(Y=a) a
77
X and Y are statistically indistinguishable if
|X-Y|<ε Pr(X=a) Pr(Y=a) a
78
補題 この面積＝この面積 Pr(X=a) Pr(Y=a) a
79
証明 Pr(X=a) C=1-A B=1-A Pr(Y=a) A a
80
系 |X-Y| = 2×この面積 Pr(X=a) Pr(Y=a) a
81
Distinguisher D X 0 or 1 Px = Pr(D=1)
82
例(1) PX = Pr(D=1) Pr(X=a) Pr(Y=a) a D=1 D=0
83
例(1) PY = Pr(D=1) Pr(X=a) Pr(Y=a) a D=1 D=0
84
例 (1) 2×(PX-PY) = |X-Y| Pr(X=a) Pr(Y=a) a
85
例(2) PY = Pr(D=1) Pr(X=a) Pr(Y=a) a D=0 D=1
86
例(2) Px = Pr(D=1) Pr(X=a) Pr(Y=a) a D=0 D=1
87
例(2) 2×(PX-PY) < |X-Y| Pr(X=a) Pr(Y=a) a D=0 D=1
88
定理 2×maxD |PX-PY| = |X-Y| Dは、指数時間アルゴリズムでもよい。
89
定義 X and Y are computationally indistinguishable if
maxD |PX-PY| < ε ただし、Dは多項式時間アルゴリズム
90
DDH仮定 (g,ga,gb,gab)と(g,ga,gb,gc)は computationally indistinguishable
ただし、 a,b,cはランダム
91
Distinguisher Px = Pr(D=1) X= (g,ga,gb,gab) PY = Pr(D=1)
Y= (g,ga,gb,gc) PY = Pr(D=1) maxD |PX-PY| < ε ただし、Dは多項式時間アルゴリズム
92
N次剰余仮定 xN = a+bN mod N2 としたとき、 (a,b) と (a, 乱数）は
computationally indistinguishable ただし、 x←{1,2,…, N-1}
93
Paillier暗号 公開鍵 N=pq 秘密鍵 p, q 暗号化 x ←{1,2,…, N-1} xN=a+bN mod N2
C=(a, b+m mod N)
94
定理 Paillier暗号は、N次剰余仮定の下で IND-CPA安全
95
証明 暗号化 x ←{1,2,…, N-1} xN=a+bN mod N2 C=(a, b+m mod N) ≒
≒ (a, 乱数+m mod N) one-time pad
96
演習 ElGamal暗号のIND-CPA安全性を破る敵Aが存在したと仮定すると、 DDH仮定を破るdistinguisher D
が存在することを示せ。 （ヒント） Aをサブルーチンとして使い、Dを構成せよ。
97
ElGamal暗号 公開鍵： p, q, g, y(=gx mod p) 秘密鍵: x 平文： m 暗号化： r ← zp-1
E(m)=(gr, myr) 2018/9/17 confidential
98
直感的な証明 DDH仮定より (g,y,gr,yr)と(g,y,gr,gz)は多項式時間で区別不可能 ただし、zは乱数 暗号文：
E(m) = (gr, m・yr) ～(gr, m・gz ) m×gz=m×乱数 → one-time pad mに関する情報は、もれていない 2018/9/17 confidential
99
ElGamal暗号のIND-CPA安全性
チャレンジャー 敵 g, y x←ランダム y=gx mod p m0, m1 b←{0,1} C=(gr, mbyr) C b’ Pr( b’=b )≃1/2
Similar presentations
