公開鍵暗号

公開鍵暗号
廣瀬勝一
廣瀬
公開鍵暗号
1 / 23
公開鍵暗号系（非対称暗号系）
暗号化鍵は公開できる．
• 誰でも送りたいメッセージを暗号化できる．
• 送信者はあらかじめ受信者と秘密鍵を共有する必要はない．
暗号化鍵
?
- 暗号化手続き
平文
廣瀬
復号鍵
暗号文
-
公開鍵暗号
?
復号手続き
平文
-
2 / 23
ハイブリッド暗号
共通鍵暗号と公開鍵暗号の組み合わせ
KP
PKE
K
M
SKE
KS
CK
(CK, CM)
CK
PKE−1
CM
CM
K
SKE−1
M
• メッセージは高速な共通鍵暗号で暗号化
• 共通鍵暗号で使用する秘密鍵を公開鍵暗号で暗号化
廣瀬
公開鍵暗号
3 / 23
公開鍵暗号系
鍵生成アルゴリズム Gen（確率的アルゴリズム）
(pk, sk) ← Gen(1ℓ )
ℓ はセキュリティパラメータ（例えば，生成する鍵の長さ）
(pk, sk) は公開鍵・秘密鍵の組
暗号化アルゴリズム Enc（確率的または決定的アルゴリズム）
C ← Enc(pk, M )
M は平文，C は暗号文
復号アルゴリズム Dec（決定的アルゴリズム）
M ← Dec(pk, sk, C)
廣瀬
公開鍵暗号
4 / 23
落し戸付き一方向関数 (Trapdoor one-way function)
暗号化関数 Enc(pk, ·) は一方向関数．
• Enc(pk, ·) は容易に計算できる．
• Enc(pk, ·) の逆関数は計算が困難．
Enc(pk, ·) は落し戸付き一方向関数．
• Enc(pk, ·) の逆関数，即ち，復号関数は sk を知っていれば容易に計
算できなければならない．
• sk は落し戸と呼ばれる．
但し，一方向関数でさえ，本当に存在するかどうかは未解決問題！
廣瀬
公開鍵暗号
5 / 23
RSA 方式
Rivest, Shamir, Adleman 1977
公開鍵 n, e
• n = pq ．ここで，p, q は相異なる奇素数
• gcd(e, ϕ(n)) = 1．ここで，ϕ(n) = (p − 1)(q − 1)
秘密鍵 d
• d e ≡ 1 (mod ϕ(n))
暗号化平文 M ∈ Zn は以下のように暗号文 C に暗号化される．
C = M e mod n
復号暗号文 C は以下のように平文 M に復号される．
M = C d mod n
安全性の根拠
非常に大きな整数について，素因数分解問題を解くことが困難
廣瀬
公開鍵暗号
6 / 23
RSA 方式
Theorem
すべての M ∈ Zn について (M e )d mod n = M である．
（証明）e d ≡ 1 (mod ϕ(n)) より，ある k について e d = k ϕ(n) + 1．
M ∈ Z∗n のときは，M ϕ(n) ≡ 1 (mod n) より明らか．
一方，M ∈ Zn \ Z∗n のときは，p | M または q | M である．p | M ならば
{
M k ϕ(n)+1 ≡ M (≡ 0) (mod p)
M k ϕ(n)+1 ≡ M (mod q)
したがって，中国人剰余定理より，
M k ϕ(n)+1 mod n = M
q | M のときも同様に証明できる．
廣瀬
公開鍵暗号
7 / 23
素因数分解と RSA
RSA 問題
素因数分解問題
入力： n(= pq)
出力： p, q
入力： n, e, C
1
出力： C e mod n
素因数分解問題が解ける ⇒ RSA 問題が解ける
問題の困難さを不等号で表すと
RSA 問題 ≤ 素因数分解問題
「素因数分解問題 ≤ RSA 問題」かどうかは未解決問題
素因数分解問題を解かずに RSA を破れる可能性は否定されていない．
廣瀬
公開鍵暗号
8 / 23
RSA の誤用 (共通の法の使用)
Alice と Bob が同じ法を使用するとき
n, eA
n, eB
Alice の公開鍵
Bob の公開鍵
Alice と Bob の両方に同じメッセージを安全に送ることができない．
{
CA = M eA mod n
CB = M eB mod n
gcd(eA , eB ) = 1 ならば，a eA + b eB = 1 を満たす a, b が計算できる．
a < 0 かつ b > 0 のとき
(CA −1 )−a CB b mod n = M a eA M b eB mod n = M
a > 0 かつ b < 0 のときも同様．
廣瀬
公開鍵暗号
9 / 23
RSA の誤用 (小さなべき指数の使用)
Alice, Bob, Carol が 3 をべき指数として使用するとき
nA , 3
nB , 3
nC , 3
Alice の公開鍵
Bob の公開鍵
Carol の公開鍵
Alice, Bob, Carol のすべてに同じメッセージを安全に送ることができない．
廣瀬
公開鍵暗号
10 / 23
Rabin 方式
Rabin 1979
公開鍵 n = pq
• p と q は相異なる素数で p ≡ 3 (mod 4) かつ q ≡ 3 (mod 4)．
秘密鍵 p, q
暗号化平文 M ∈ Z∗n は以下のように暗号文 C に暗号化される．
C = M 2 mod n
復号暗号文 C は以下のように復号される．
1
C 2 mod n
安全性の根拠
非常に大きな整数について，素因数分解問題を解くことが困難
廣瀬
公開鍵暗号
11 / 23
復号法
平文は以下の方程式を解くことによって得られる．
{ 2
x ≡ C (mod p)
2
x ≡ C (mod n) ⇔
x2 ≡ C (mod q)
p ≡ 3 (mod 4) のとき，p を法とする C の平方根は容易に得られる．
{
p+1
(mod p)
x ≡ ±C 4
q+1
x ≡ ±C 4
(mod q)
中国人剰余定理により n を法とする C の平方根が 4 個得られる．
• 任意の暗号文に対して 4 個の可能な平文が存在する．
• 一意に復号するためには，平文に冗長性を持たせなければならない．
廣瀬
公開鍵暗号
12 / 23
素因数分解と Rabin 方式
素因数分解問題
入力： n(= pq)
出力： p, q
Rabin 問題
入力： n, C
出力： x2 ≡ C (mod n) を満たす x
Rabin 問題と素因数分解問題は同程度に難しい．
Theorem
Rabin 問題が解けるならば，素因数分解問題が確率 1/2 で解ける．
（証明）与えられた n について，無作為に r ∈ Z∗n を選び，
C = r2 mod n を計算する．次に，Rabin 問題を解くアルゴリズムに n, C
を入力として与え，その出力 x を得る．このとき，x ̸≡ ±r (mod n) なら
ば gcd(x + r, n) ∈ {p, q} である．x ̸≡ ±r (mod n) の確率は 1/2．
廣瀬
公開鍵暗号
13 / 23
ElGamal 方式
ElGamal 1982
公開鍵 p, g, y （すべての利用者が同一の p と g を利用できる）
• p は素数，g は乗法群 Z∗p の原始元
• y = g x mod p
秘密鍵 x ∈ Zp−1
暗号化平文 M ∈ Z∗p は以下のように暗号文 (a, b) に暗号化される．
1 k ∈ Zp−1 を無作為に選ぶ．
2 a = g k mod p, b = y k M mod p
復号暗号文 (a, b) は以下のように平文 M ∈ Z∗p に復号される．
M = b/ax mod p
安全性の根拠
離散対数問題を解くことが困難
廣瀬
公開鍵暗号
14 / 23
剰余べき乗算の計算法
square-and-multiply 法
g x mod p は，高々2|x| 回の剰余乗算で計算できる．
（より正確には |x| + (x のハミング重み) 回）
x の 2 進数表記を (xℓ−1 , xℓ−2 , . . . , x1 , x0 ) とする．
x = x0 + 2x1 + 22 x2 + · · · + 2ℓ−2 xℓ−2 + 2ℓ−1 xℓ−1
(xi ∈ {0, 1})
【例】ℓ = 4
1 12 = 1
2 g x3 1 = g x3
3 (g x3 )2 = g 2x3
4 g x2 g 2x3 = g x2 +2x3
2
5 (g x2 +2x3 )2 = g 2x2 +2 x3
2
2
6 g x1 g 2x2 +2 x3 = g x1 +2x2 +2 x3
2
2
3
7 (g x1 +2x2 +2 x3 )2 = g 2x1 +2 x2 +2 x3
2
3
2
3
8 g x0 g 2x1 +2 x2 +2 x3 = g x0 +2x1 +2 x2 +2 x3
廣瀬
公開鍵暗号
15 / 23
鍵長（NIST SP 800-57 より）
安全性
80
112
128
192
256
SKA
2TDEA
3TDEA
AES-128
AES-192
AES-256
FFC
(1024, 160)
(2048, 224)
(3072, 256)
(7680, 384)
(15360, 512)
IFC
1024
2048
3072
7680
15360
ECC
160 ∼ 223
224 ∼ 255
256 ∼ 383
384 ∼ 511
512 ∼
安全性は log2 (攻撃計算量)
SKA: Symmetric Key Algorithms
FFC: Finite-Field Cryptography (DSA, DH), (公開鍵長, 秘密鍵長)
IFC: Integer-Factorization Cryptography (RSA)
ECC: Elliptic Curve Cryptography
2TDEA: 2-key Triple DES
3TDEA: 3-key Triple DES
廣瀬
公開鍵暗号
16 / 23
公開鍵暗号方式の安全性
安全性の達成度
• 一方向性（one-wayness）
• 識別不能性（indistinguishability）
• 頑強性（non-malleability）
攻撃
• 選択平文攻撃
暗号化鍵は公開なので常に適用可能
• 選択暗号文攻撃
廣瀬
公開鍵暗号
17 / 23
一方向性 (One-wayness)
(pk, sk) ← Gen(1ℓ ) と無作為に選ばれた平文 M について，
C ← Enc(pk, M )
Definition (一方向性)
C が与えられたとき，M を得ることが困難である．
一方向性が満たされても，M の部分情報が得られる可能性がある．
【例】何ら脆弱性のない Enc について
Enc′ (pk, M ) = ML ∥Enc(pk, MR )
Enc′ は一方向性を満たすが，安全な暗号化関数とは言えない．
廣瀬
公開鍵暗号
18 / 23
識別不能性 (Indistinguishability)
攻撃者 A
M0 , M1 を任意に選ぶ
b を推定
M0, M1
C
オラクル O
b ∈ {0, 1} を無作為に選ぶ
C ← Enc(pk, Mb )
Definition (識別不能性)
1/2 より無視できない位大きな確率で b を正しく言い当てることが困難
廣瀬
公開鍵暗号
19 / 23
選択暗号文攻撃
攻撃者 A
(xi , ti ) を任意に選ぶ
...
(x1, t1)
y1
(xq, tq)
yq
オラクル O
{
Eec(pk, xi )
yi ←
Dec(pk, sk, xi )
(ti = 0)
(ti = 1)
• A は yi−1 を得た後にその情報を利用して (xi , ti ) を選べる．
• (xi , 1) に対応する平文が存在しない場合，yi = ⊥（該当なし）．
廣瀬
公開鍵暗号
20 / 23
RSA-OAEP [Bellare-Rogaway 1994]
OAEP (Optimal Asymmetric Encryption Padding)
0....0
M
r
G
H
s
t
RSA-OAEP
s = (M ∥0 · · · 0) ⊕ G(r) ,
t = r ⊕ H(s)
C = (s∥t)e mod n
廣瀬
公開鍵暗号
21 / 23
RSA-OAEP
Theorem
以下の条件が満たされるとき，RSA-OAEP は選択暗号文攻撃に対して識
別不能性を満たす
• RSA 関数 (xe mod n) は一方向
• G と H はランダムオラクル
ランダムオラクルは以下を満たす理想的なブラックボックスである．
• 与えられた入力に対して無作為に選ばれた出力を返す．
• 同じ入力に対しては同じ出力を返す．
廣瀬
公開鍵暗号
22 / 23
演習問題
1
RSA における小さなべき指数の使用が不都合であることを説明せよ．
2
Rabin 方式の復号アルゴリズムが正しく動作することを確認せよ．
選択暗号文攻撃に対する以下の脆弱性を証明せよ．
3
1
2
3
RSA 方式は一方向性を満たさない．
ElGamal 方式は一方向性を満たさない．
Rabin 方式は完全に解読可能である（秘密鍵が得られる）．
廣瀬
公開鍵暗号
23 / 23

Download Report