公開鍵暗号
公開鍵暗号の機能
公開鍵暗号は
予め秘密を共有しないで秘密の通信を行う方法。
暗号化には公開鍵を、復号には私有鍵を用いる。
- 受信者は自分の公開鍵を公開。
- 送信者は、受信者の公開鍵を入手。
- 送信者は、メッセージを受信者の公開鍵で暗号化し、受信者に送る。
- 受信者は、暗号文を自分の私有鍵で復号し、もとのメッセージを得る。
暗号文を復号できるのは、暗号化に用いた公開鍵と対になった私有鍵だけ。つまり、正当な受信者だけ。
公開鍵暗号の定義
公開鍵暗号は、3つの効率的な確率的アルゴリズムの組:
公開鍵暗号 = (G, E, D).
鍵生成アルゴリズム Gは、セキュリティパラメータ k を入力すると公開鍵 e と私有鍵 d の組を出力:
(e, d) ← G(k).
(セキュリティパラメータ k とは暗号の強度を指定するパラメータ。)
暗号化アルゴリズム Eは、公開鍵 e とメッセージ m を入力すると暗号文 c を出力:
c ← E(e, m).
復号アルゴリズム Dは、私有鍵 d と暗号文 c を入力するとメッセージ m を出力:
m ← D(d, c).
ただし、3つ組 (G, E, D) は以下の完遂性と一方向性を満たさなければならない。
完遂性:
G によって生成された任意の鍵ペア (e, d) と任意のメッセージ m について、 D(d, E(e,m)) = m .
暗号化して復号したらもとのメッセージに戻るということ。
一方向性:
どのような効率的なアルゴリズム A も、公開鍵 e と暗号文 c (← E(e,m)) から、もとのメッセージ mを求めることはできない。
公開鍵暗号を作るとは、完遂性と一方向性を同時に満たす、アルゴリズムの3つ組 (G, E, D)を求めることに他ならない。
RSA 暗号
RSA 暗号は、整数を法とするべき乗剰余演算を利用。
鍵生成アルゴリズム G (k) :
それぞれ k ビットの異なる素数 p, q を生成。
- n = p・q, l = φ(n) = (p-1)・(q-1)
とし、
となる e, d を生成する。
(n, e) を公開鍵 pk、(n, d) を私有鍵 sk として出力。
暗号化アルゴリズム E(pk, m) :
公開鍵 pk から n, e を取り出して、
を計算し、c を出力。
復号アルゴリズム D(sk, c) :
私有鍵 sk から n, d を取り出して、
を計算し、m を出力。
オイラーの定理より、RSA暗号は完遂性を満たす。
一方向性は、次のRSA仮定として
信じられている。
RSA仮定:
n ( = p・q) を十分大とする。y を {0,1,2,・・・,n-1}からランダムに選ぶ。このとき、(e, y, n) を与えられて
となる x を求める効率的なアルゴリズムは存在しない。
RSA仮定が成り立つためには、n の素因数分解が困難であることは必要条件。十分条件になるか否かは未解決。
RSA暗号の問題点
今、Alice が Bob に(ある事柄について)賛成か反対かのいずれかを他人には秘密に伝えたい。あらかじめ、賛成は整数 myes で反対は整数 mno で表すことになっている。
Alice は、自分が賛成していることを、RSA暗号で Bob に伝える。
1. Aliceは、Bobの公開鍵 (nB, eB) を入手し、
を計算し、暗号文 c を Bob に送る。
2. Bobは、自身の私有鍵 (nB, dB) を用いて、受け取った暗号文 c に対し、
を計算して、Aliceのメッセージ myes を得る。
この送信の途中で敵 Eve が 暗号文 c を覗き見しているかも知れないが、RSA暗号は一方向性をみたすので大丈夫、のはずだった。
ところが、敵 Eve は 暗号文 c から Alice のメッセージ myes を簡単に求めることができる。
1. Eveはまず mno を Bob の公開鍵 (nB, eB) で暗号化して c' を求める。
2. c' と c を比較するとそれらは異なるので、c に暗号化されていたのは、mnoではなく、myes である。
これは、RSA暗号では、暗号文からもとのメッセージに関する情報が漏れていることを示す。
公開鍵暗号の強秘匿性
「暗号文からもとのメッセージに関するどのような情報も漏れていない」ということを操作的に定義したい。
強秘匿性:
公開鍵暗号 (G, E, D) をめぐって、敵 A と挑戦者 C がゲームを行う。
1. まず、挑戦者Cが鍵生成アルゴリズム G を実行し、
鍵ペア (e, d) をつくり、公開鍵 e だけを敵 A に渡す。
2. 公開鍵 e を受け取ったら、敵 A は何らかの計算をしてメッセージの組 (m0, m1) を選び、挑戦者 C に渡す。
3. これに対して挑戦者 C は m0 か m1 かどちらかをランダムに選び(これを mb とかく)、公開鍵 e で暗号化して暗号文 c をつくる:
挑戦者Cは暗号文 c を敵 A に渡す。
4. 敵 A は暗号文 c が m0 を暗号化したのか、m1を暗号化したのかどちらかを推測し、推測結果 b' を出力する。
5. 推測が当たったら( b = b' なら)敵 A の勝ち、そうでないなら挑戦者 C の勝ちとする。
このとき、どのような敵 A もせいぜい 1/2 の確率でしか勝てないとき、公開鍵暗号 (G, E, D) は、強秘匿と呼ばれる。
もし、公開鍵暗号がメッセージの情報を1ビットも漏らしていないならば、敵 A がどんなに強力でも、c が m0 を暗号化したのか m1 を暗号化したのか、全く分からず、あてずっぽうで推測するしかない。このとき敵 A が勝つ確率は 1/2 。
一方、公開鍵暗号がメッセージの情報を何らかの形で漏らしていれば、ある巧妙な敵 A が、その遺漏を突くようなメッセージの組 (m0, m1) を選び、挑戦者 C に提出すれば、その敵Aは高い確率で勝つはず。
ハードコアビット
RSA 暗号が強秘匿にならない理由は、
において、
y は x の全てを隠せているわけではない
から。
ところが、関数 y = xe (mod n) は、(RSA 仮定のもとで)x の最下位ビット
は確実に隠せる(ことが知られている)。つまり、
y が与えられても、x0 が 0 なのか 1 なのか、まるで分からない。
この状況を、 「x0 は y の(RSA関数に関する)ハードコアビットである」という。
Blum-Goldwasser 型 RSA 暗号
Blum-Goldwasser 型 RSA 暗号 = RSA暗号 + ハードコアビット。
鍵生成アルゴリズム G(k) :
RSA 暗号の鍵生成と同じ。公開鍵 (n, e)、私有鍵 (n, d)とする。
暗号化アルゴリズム E(pk, m) :
メッセージ m のビット長を l とする。公開鍵 pk から (n, e) を取り出して、
- 0 以上 (n-1) 以下の乱数 x0 を選ぶ。
- i = 1, ・・・, l について、
- mask = (LSB(x0), LSB(x1), ・・・, LSB(xl-1))
- c1 = mask m
- 暗号文として c = (c1, xl) を出力する。
復号アルゴリズム D(sk, c) :
私有鍵 sk から (n, d) を取り出して、暗号文 c = (c1, y) に対し、
- (n, d) を用いて RSA復号演算を繰り返し、y ( = xl) から x0を求める。すなわち、i = (l-1), (l-2), ・・・, 0 について
- mask = (LSB(x0), LSB(x1), ・・・, LSB(xl-1))
- m = mask c1
- メッセージとしてmを出力する。
ここで、mask = (LSB(x0), LSB(x1), ・・・, LSB(xl-1))の各ビットを見ると
- LSB(xl-1) は xl ( = xl-1e mod n) のハードコアビット
- LSB(xl-2) は xl-1 ( = xl-2e mod n) のハードコアビット
- ・・・
- LSB(x0) は x1 ( = x0e mod n) のハードコアビット
となっている。
よって、
- 敵は xl を知っているが、ハードコアビットの性質から、LSB(xl-1) は全く分からない。
- 敵は、xl-1( の部分情報)を知っているかもしれないが、LSB(xl-2) は全く分からない。
- ・・・
- 敵は、x1 (の部分情報)を知っているかもしれないが、LSB(x0) は全く分からない。
以上から、
mask は敵にとって未知の(メッセージ m と同じ長さの)乱数列に等しい
ことが分かった。
すると、c = mask
m は m の情報を完全に隠すことになり(ワンタイムパッド)、Blum-Goldwasser 型 RSA 暗号は強秘匿となることがわかる。
公開鍵暗号の頑健性
現在、公開鍵暗号の暗号文は世の中に飛び回っている。
攻撃者がそのような暗号文を手に入れて、それをもとに別の暗号文を作り出し、もとの暗号文の代わりに放ったらどうなるだろうか。
なにかと不都合な事態が発生しそうである。
実際、状況によってはもとの暗号文の解読にまで至ることがある。
公開鍵暗号が頑健であるとは、
攻撃者が暗号文を入手しても、それが隠しているメッセージとなにか意味ある関係をもつ別のメッセージの、暗号化になっているような、別の暗号文を作り出すことができない
ことをいう。
RSA-OAEP 暗号
RSA-OAEP 暗号 = 「2段のFeistel構造」+ RSA.
2つのハッシュ関数
- G : {0,1}* → {0,1}k - k0
- H : {0,1}* → {0,1}k0
とRSA暗号を用いる。
公開鍵 (n, e) のRSA暗号化関数を
私有鍵 (n, d) のRSA復号関数を
とかく。
鍵生成アルゴリズム G(k) :
RSA 暗号の鍵生成と同じ。公開鍵 (n, e)、私有鍵 (n, d)。
暗号化アルゴリズム E(pk, m) :
公開鍵 pk から (n, e) を取り出して、
- k0 ビットの乱数 r を生成する。
- s = (m || 0k1) G(r)
- t = r H(s)
- c = RSAn,e(s||t) を暗号文とする。
復号アルゴリズム D(sk, m) :
私有鍵 sk から (n, d) を取り出して、
- (s, t) = RSA-1n,d(c) を暗号文とする。
- r = t H(s)
- m' = s G(r)
- m' の末尾 k1 ビットがすべて0ならば、暗号文を正当と認め、m'の残りの文字列をメッセージとして返す。
攻撃者が暗号文を「でっち上げよう」としたら、その m' の末尾 k1 ビットがすべて 0 というわけには、いかなくなりそうである。
でっち上げれないならば、暗号文は正直に作るしかない。とくに、メッセージを知った上で、それを暗号化するほかない。
実際、RSA-OAEP 暗号は頑健性をもつことが示されている。ただし、ランダムオラクルモデルのもとで。
付録
エルガマル暗号
エルガマル暗号は、離散対数ベースの公開鍵暗号である。
鍵生成アルゴリズム G (n) :
- p を十分大きな素数とし、g を、p を法とする位数が素数 q である整数(すなわち、g は q 乗すると初めてpを法として1となる)とする。
- x ← Zq, y = gx
- pk=(q,g,y), sk = (q,g,x).
暗号化アルゴリズム E(pk = (q,g,y), m) : // m∈<g>
- r ← {0,q-1}, c1 = gr, c2 = m yr
- return c = (c1, c2).
復号アルゴリズム Dec(sk=(q,g,x), c=(c1, c2)):
判定DH仮定のもとで、エルガマル暗号は選択平文攻撃に対し強秘匿である。
最終更新:2010年05月28日 15:03