公開鍵暗号の安全性 - Kaoru Kurosawa Laboratory

情報セキュリティ特論（7）
黒澤馨（茨城大学）
[email protected]
RSA暗号
• C=Me mod N
• C=0のとき、M=0とわかってしまう。
• C=1のとき、M=1とわかってしまう。
• 平文Mのどんな部分情報も
漏れないようにするには？
公開鍵暗号系
• 鍵生成アルゴリズム G
• 暗号化アルゴリズム E
• 復号アルゴリズム D
公開鍵暗号系の安全性
• IND-CPA安全性
Chosen Plaintext（平文）Attack
• IND-CCA安全性
Chosen Ciphertext（暗号文） Attack
IND-CPAを定義するゲーム
チャレンジャー
(pk,sk)←G
敵
pk
m 0, m 1
b←{0,1}
C=E(mb)
b’
IND-CPA安全 if |Pr(b’=b)-1/2|<ε
チャレンジャー
(pk,sk)←G
敵
pk
m 0, m 1
b←{0,1}
C=E(mb)
b’
IND-CPA安全 if |Pr(b’=b)-1/2|<ε
for 全ての多項式時間の敵
チャレンジャー
(pk,sk)←G
敵
pk
m 0, m 1
b←{0,1}
C=E(mb)
b’
ElGamal暗号のIND-CPA安全性
チャレンジャー
x←ランダム
y=gx mod p
敵
g, y
m 0, m 1
b←{0,1}
C=(gr, mbyr)
C
b’
Pr( b’=b )≃1/2
定理
• ElGamal暗号はIND-CPA安全
under DDH仮定
• （証明）
演習
RSA≠IND-CPA安全
チャレンジャー
敵の動作
(N,e)
m0=0, m1=1
b←{0,1}
C=mbe mod N
b’=0 if C=0
b’=1 if C=1
Pr( b’=b )=1
Pr(b’=b)=1なので、
• |Pr(b’=b)-1/2|=|1-1/2|=1/2≧ε
• よって、
RSA暗号≠IND-CPA安全
IND-CPA安全なRSA-based暗号
• r←ランダム
• c1=re mod N
• c2=M + H(r) mod N
ただし、Hはハッシュ関数
• 暗号文 C=(c1, c2)
IND-CPA安全なRSA-based暗号
•
•
•
•
r←ランダム
公開鍵暗号でKを暗号化
K=H(r)
c1=re mod N
c2=M+擬似乱数生成器(K)
(One-Time-PAD)
共通鍵暗号で平文Mを暗号化
• 暗号文 C=(c1, c2)
IND-CPA安全なRSA-based暗号
• r←ランダム
• c1=re mod N
• c2=M + H(r) mod N
• 暗号文 C=(c1, c2)
AES暗号を利用した擬似乱数生成器
Seed
(0) 2
K
出力
AES
k0
(2) 2
(1) 2
K
AES
k1
K
AES
…
k2
…
AES暗号が擬似ランダム置換と仮定すると、
これは、標準モデルで擬似乱数生成器
ハイブリッド暗号
• C= 公開鍵暗号(共通鍵K)
+ 共通鍵暗号（K,平文m)
• 公開鍵を使うので、
ハイブリッド暗号は公開鍵暗号の１つ
ハイブリッド暗号
• C= 公開鍵暗号(共通鍵K) ← KEM
+ 共通鍵暗号（K,平文m) ← DEM
• 公開鍵を使うので、
ハイブリッド暗号は公開鍵暗号の１つ
KEM-DEMフレームワーク
• CPA安全なKEM
+ One-Time-PAD
= IND-CPA安全な
公開鍵暗号（ハイブリッド暗号）
KEM
• 鍵生成アルゴリズム G
• 暗号化アルゴリズム E
E(pk)=(暗号文 C, 鍵 K)
• 復号アルゴリズム D
D(C, sk)=K
RSA-KEM
• 公開鍵 (N,e)
• 暗号化
r ← ランダム
暗号文 C=re mod N
鍵
K=H(r)
KEMのCPA安全性
チャレンジャー
(pk,sk)←G
(C, K0) ← E(pk)
K1=ランダム
敵
pk
C, Kb
b←{0,1}
b’
Pr( b’=b )～1/2
KEMはCPA安全
• If 全ての多項式時間の敵に対し、
|Pr(b’=b)-1/2|<ε
KEMのＣPＡ安全性 in RO
pk, C, Kb
r1, r2,
敵
H
H(r1), H(r2),
b’
Pr( b’=b )～1/2
RSA-KEMのＣPＡ安全性 in RO
(N,e), C(=re mod N),
K0 =H(r) or K1 =乱数
r1, r2,
敵
H
H(r1), H(r2),
b’
定理
• RSA仮定の下で、
RSA-KEMはCPA安全
in the ランダム・オラクル・モデル
補題
• Pr(b’=b)-1/2=ε (non-negligible)
と仮定すると
Pr(敵がrをHオラクルに質問する)≧2ε
証明
• X=敵がrをHオラクルに質問する事象
• Pr(b’=b)= Pr(b’=b, X)+ Pr(b’=b, ￢X)
証明
• 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)
証明
• 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)
証明
• 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))
証明
• 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)
証明
• 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=ε
補題
• Pr(b’=b)-1/2=ε (non-negligible)
と仮定すると
Pr(敵がrをHオラクルに質問する)≧2ε
• （証明完了）
RSA-KEMのCPA安全性の証明
(N, e), C=re mod N
(N, e), C,
b←{0,1}、Kb =乱数
r1, r2,
敵
H
H(r1), H(r2),
b’
r
(N, e), C=re mod N
(N, e), C, Kb =乱数
補題より
どこかでr
H
敵
(N, e), C=re mod N
(N, e), C, Kb =乱数
補題より
どこかでr
H
敵
r if C=re mod N
(N, e), C=re mod N
(N, e), C, Kb =乱数
r1
H
敵
r=r1 if C=r1e mod N
(N, e), C=re mod N
(N, e), C, Kb =乱数
r1
敵
H
H(r1)=乱数
C≠r1e mod Nのとき
(N, e), C=re mod N
(N, e), C, Kb =乱数
r2
H
敵
r=r2 if C=r2e mod N
定理
• RSA仮定の下で、
RSA-KEMはCPA安全
in the RO モデル
• （証明完了）
定理
• RSA仮定の下で、以下の暗号系はCPA安全
in the RO モデル
RSA-KEM
• r←ランダム、K=H(r)
• c1=re mod N
• c2=M+擬似乱数生成器(K)
(One-Time-PAD)
• 暗号文 C=(c1, c2)
証明
• CPA安全なKEM（公開鍵暗号）
+ One-Time-PAD
= IND-CPA安全な公開鍵暗号
RSA-KEMはCPA安全、を証明した。
（証明終）
ハイブリッド暗号の効能
• IND-CPA (IND-CCA) 安全な公開鍵暗号
を簡単に作れる
• 平文は、任意の長さのビット列でよい。
ハイブリッド暗号に関する定理
• CPA安全なKEM（公開鍵暗号）
+ One-Time-PAD
= IND-CPA安全な公開鍵暗号
（証明）
ハイブリッド暗号のIND-CPA
チャレンジャー
(pk,sk)←G
敵
pk
m0, m1
b←{0,1}
(c1*, K*)←KEM(pk)
c2*=mb+擬似乱数(K*)
m 0, m 1
C*=(c1*, c2*)
b’
Game 0
チャレンジャー
(pk,sk)←G
敵
pk
m0, m1
b←{0,1}
(c1*, K* )←KEM(pk)
c2*=mb+擬似乱数(seed=K* )
m 0, m 1
C*=(c1*, c2*)
b’
Game 1
チャレンジャー
(pk,sk)←G
敵
pk
m0, m1
b←{0,1}
(c1*, K*)←KEM(pk)
c2*=mb+擬似乱数(seed=乱数)
m 0, m 1
C*=(c1*, c2*)
b’
補題１
• ハイブリッド暗号において
Pr(b’=b in Game 0)～ Pr(b’=b in Game 1)
if KEM is CPA 安全
• (証明）
ハイブリッド暗号の敵を基に、
KEMの敵を以下のように構成する。
KEMの敵
KEMの
チャレンジャー
ハイブリッド暗号の敵
pk
pk
(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
d=0のとき
KEMの敵
KEMの
チャレンジャー
ハイブリッド暗号の敵
pk
pk
(pk,sk)←G
(c1*, K0)←KEM
K1←ランダム
Game 0
c1*, K0
m0, m1
d←0
b←{0,1}
c2*= mb + 擬似乱数(seed=K0)
C*=(c1*, c2*)
b’
d’ =1
if b’=b
d=1のとき
KEMの敵
KEMの
チャレンジャー
ハイブリッド暗号の敵
pk
pk
(pk,sk)←G
(c1*, K0)←KEM
K1←ランダム
Game 1
c1*, K1
m0, m1
d←1
b←{0,1}
c2*= mb + 擬似乱数(seed=K1)
C*=(c1*, c2*)
b’
d’ =1
if b’=b
d’=1 if b’=b なので、
• Pr(d’=1 when d=0)=Pr(b’=b in Game 0)
• Pr(d’=1 when d=1)=Pr(b’=b in Game 1)
証明
• Pr(d’=1 when d=0)=Pr(b’=b in Game 0)
• Pr(d’=1 when d=1)=Pr(b’=b in Game 1)
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)
補題１
• ハイブリッド暗号において
Pr(b’=b in Game 0)～ Pr(b’=b in Game 1)
if KEM is CPA 安全
（証明完了）
補題２
• Pr(b’=b in Game 1)～1/2
Game 1
チャレンジャー
(pk,sk)←G
敵
pk
m0, m1
b←{0,1}
(c1*, K*)←KEM(pk)
c2*=mb+擬似乱数(seed=乱数)
m 0, m 1
C*=(c1*, c2*)
b’
Game 1
チャレンジャー
(pk,sk)←G
敵
pk
m0, m1
b←{0,1}
(c1*, K*)←KEM(pk)
c2*=mb+擬似乱数(seed=乱数)
c2*は、c1*とは独立なone-time-pad
なので、
Pr(b’=b)=1/2
m 0, m 1
C*=(c1*, c2*)
b’
補題２
• Pr(b’=b in Game 1)～1/2
• （証明完了）
ハイブリッド暗号に関する定理
• CPA安全なKEM（公開鍵暗号）
+ One-Time-PAD
= IND-CPA安全な公開鍵暗号
（証明）
補題１、補題２より。
公開鍵暗号系の安全性
• IND-CPA安全性
Chosen Plaintext（平文）Attack
• IND-CCA安全性
Chosen Ciphertext（暗号文） Attack
公開鍵暗号のIND-CCA安全性
チャレンジャー
(pk,sk)←G
復号オラクル
敵
pk
m 0, m 1
b←{0,1}
C=E(mb)
C以外の暗号文を
復号してもらえる
b’
KEMのCCA安全性
チャレンジャー
(pk,sk)←G
(C, K0) ← E(pk)
K1=ランダム
敵
復号オラクル
pk
C, Kb
C以外の暗号文を
復号してもらえる
b←{0,1}
b’
DEM（共通鍵暗号）のCCA安全性
復号オラクル
チャレンジャー
敵
m 0, m 1
K←ランダム
b←{0,1}
C=EK(mb)
C
C以外の暗号文を
復号してもらえる
b’
CCA安全 if |Pr(b’=b)-1/2|<ε
KEM-DEMフレームワーク
• CCA安全なKEM（公開鍵暗号）
+ CCA安全なDEM（共通鍵暗号）
= IND-CCA安全な公開鍵暗号
公開鍵暗号の暗号文
C=KEM(共通鍵K)+DEM(共通鍵K,m)
定理
• RSA仮定の下で、
• RSA-KEMはCCA安全
• In the RO モデル
CCA安全なDEMの構成法
• K→
擬似乱数生成器
→
K1 , K 2
• 暗号文 C=(E, Tag)
E  M  K1
Tag  One Time MACK2 (E)
敵は、MACオラクルに１回だけ質問して偽造する
（通常のMACで十分）
IND-ＣＣＡ安全なハイブリッド暗号
公開鍵 (N,e)
r ← ランダム
共通鍵Ｋ＝Ｈ（ｒ）
暗号文 C=(φ, χ)
  r modN
KEMの暗号文
χ＝（E, Tag)
DEMの暗号文（鍵K)
e
RSA仮定の下で、IND-ＣＣＡ安全
in the RO model
ROモデル
IND-CPA安全な
ハイブリッド暗号の
構成法
IND-CCA安全な
ハイブリッド暗号の
構成法
RSA-KEM
+ one-time-pad
RSA-KEM
+ one-time-pad
+ MAC
ROなしで、IND-CPAな暗号
ElGamal暗号
Paillier暗号
DDH仮定
N次剰余仮定
N次剰余仮定
• xN = a+bN mod N2 としたとき、
• (a,b) と (a, 乱数）は
computationally indistinguishable
• ただし、
x←{1,2,…, N-1}
Paillier暗号
• 公開鍵 N=pq
• 秘密鍵 p, q
• 暗号化
x ←{1,2,…, N-1}
xN=a+bN mod N2
C=(a, b+m mod N)
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を求める
定理
• Paillier暗号は、N次剰余仮定の下で
IND-CPA安全
N次剰余仮定
• xN = a+bN mod N2 としたとき、
• (a,b) と (a, 乱数）は
computationally indistinguishable
とは、どういう意味か？
確率変数 XとY
Pr(X=a)
Pr(Y=a)
a
Statistically distance
|X-Y|
Pr(X=a)
Pr(Y=a)
a
X and Y are statistically
indistinguishable if
|X-Y|<ε
Pr(X=a)
Pr(Y=a)
a
補題
この面積＝この面積
Pr(X=a)
Pr(Y=a)
a
証明
Pr(X=a)
C=1-A
B=1-A
Pr(Y=a)
A
a
系
|X-Y| = 2×この面積
Pr(X=a)
Pr(Y=a)
a
Distinguisher
X
D
Px = Pr(D=1)
0 or 1
例(1)
PX = Pr(D=1)
Pr(X=a)
Pr(Y=a)
a
D=1
D=0
例(1)
PY = Pr(D=1)
Pr(X=a)
Pr(Y=a)
a
D=1
D=0
例 (1)
2×(PX-PY) = |X-Y|
Pr(X=a)
Pr(Y=a)
a
例(2)
PY = Pr(D=1)
Pr(X=a)
Pr(Y=a)
a
D=1
D=0
例(2)
Px = Pr(D=1)
Pr(X=a)
Pr(Y=a)
a
D=1
D=0
例(2)
2×(PX-PY) < |X-Y|
Pr(X=a)
Pr(Y=a)
a
D=1
D=0
定理
• 2×maxD |PX-PY| = |X-Y|
• Dは、指数時間アルゴリズムでもよい。
定義
• X and Y are
computationally indistinguishable
if
maxD |PX-PY| < ε
ただし、Dは多項式時間アルゴリズム
DDH仮定
• (g,ga,gb,gab)と(g,ga,gb,gc)は
computationally indistinguishable
• ただし、
a,b,cはランダム
Distinguisher
X= (g,ga,gb,gab)
D
Px = Pr(D=1)
Y= (g,ga,gb,gc)
D
PY = Pr(D=1)
maxD |PX-PY| < ε
ただし、Dは多項式時間アルゴリズム
N次剰余仮定
• xN = a+bN mod N2 としたとき、
• (a,b) と (a, 乱数）は
computationally indistinguishable
• ただし、
x←{1,2,…, N-1}
Paillier暗号
• 公開鍵 N=pq
• 秘密鍵 p, q
• 暗号化
x ←{1,2,…, N-1}
xN=a+bN mod N2
C=(a, b+m mod N)
定理
• Paillier暗号は、N次剰余仮定の下で
IND-CPA安全
証明
• 暗号化
x ←{1,2,…, N-1}
xN=a+bN mod N2
C=(a, b+m mod N)
≒
(a, 乱数+m mod N)
one-time pad
演習
• ElGamal暗号のIND-CPA安全性を破る敵A
が存在したと仮定すると、
DDH仮定を破るdistinguisher D
が存在することを示せ。
（ヒント）
Aをサブルーチンとして使い、Dを構成せよ。
ElGamal暗号
• 公開鍵：
p, q, g, y(=gx mod p)
• 秘密鍵: x
• 平文： m
• 暗号化：
r ← zp-1
E(m)=(gr, myr)
2015/9/30
confidential
97
直感的な証明
• 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に関する情報は、もれていない
2015/9/30
confidential
98
ElGamal暗号のIND-CPA安全性
チャレンジャー
x←ランダム
y=gx mod p
敵
g, y
m 0, m 1
b←{0,1}
C=(gr, mbyr)
C
b’
Pr( b’=b )≃1/2

Download Report