公開鍵暗号


公開鍵暗号の機能

公開鍵暗号は
予め秘密を共有しないで秘密の通信を行う方法。
暗号化には公開鍵を、復号には私有鍵を用いる。

  1. 受信者は自分の公開鍵を公開。
  2. 送信者は、受信者の公開鍵を入手。
  3. 送信者は、メッセージを受信者の公開鍵で暗号化し、受信者に送る。
  4. 受信者は、暗号文を自分の私有鍵で復号し、もとのメッセージを得る。
暗号文を復号できるのは、暗号化に用いた公開鍵と対になった私有鍵だけ。つまり、正当な受信者だけ。





公開鍵暗号の定義

公開鍵暗号は、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 ≡ 1 (mod l)
となる e, d を生成する。
(n, e) を公開鍵 pk、(n, d) を私有鍵 sk として出力。

暗号化アルゴリズム E(pk, m) :

公開鍵 pk から n, e を取り出して、
  • c = me  (mod n)
を計算し、c を出力。

復号アルゴリズム D(sk, c) :

私有鍵 sk から n, d を取り出して、
  • m = cd  (mod n)
を計算し、m を出力。

オイラーの定理より、RSA暗号は完遂性を満たす。
一方向性は、次のRSA仮定として信じられている

RSA仮定:

n ( = p・q) を十分大とする。y を {0,1,2,・・・,n-1}からランダムに選ぶ。このとき、(e, y, n) を与えられて
  • y=xe  (mod n)
となる x を求める効率的なアルゴリズムは存在しない。

RSA仮定が成り立つためには、n の素因数分解が困難であることは必要条件。十分条件になるか否かは未解決。




RSA暗号の問題点

今、Alice が Bob に(ある事柄について)賛成か反対かのいずれかを他人には秘密に伝えたい。あらかじめ、賛成は整数 myes で反対は整数 mno で表すことになっている。

Alice は、自分が賛成していることを、RSA暗号で Bob に伝える。

1. Aliceは、Bobの公開鍵 (nB, eB) を入手し、
  • c = myeseB  (mod nB)
を計算し、暗号文 c を Bob に送る。

2. Bobは、自身の私有鍵 (nB, dB) を用いて、受け取った暗号文 c に対し、
  • myes = cdB  (mod nB)
を計算して、Aliceのメッセージ myes を得る。

この送信の途中で敵 Eve が 暗号文 c を覗き見しているかも知れないが、RSA暗号は一方向性をみたすので大丈夫、のはずだった。

ところが、敵 Eve は 暗号文 c から Alice のメッセージ myes を簡単に求めることができる。

1. Eveはまず mno を Bob の公開鍵 (nB, eB) で暗号化して c' を求める。
  • c' = mnoeB  (mod nB)

2. c' と c を比較するとそれらは異なるので、c に暗号化されていたのは、mnoではなく、myes である。

これは、RSA暗号では、暗号文からもとのメッセージに関する情報が漏れていることを示す。




公開鍵暗号の強秘匿性

「暗号文からもとのメッセージに関するどのような情報も漏れていない」ということを操作的に定義したい。

強秘匿性:

公開鍵暗号 (G, E, D) をめぐって、敵 A と挑戦者 C がゲームを行う。

1. まず、挑戦者Cが鍵生成アルゴリズム G を実行し、
  • (e, d) ← G(k)
鍵ペア (e, d) をつくり、公開鍵 e だけを敵 A に渡す。

2. 公開鍵 e を受け取ったら、敵 A は何らかの計算をしてメッセージの組 (m0, m1) を選び、挑戦者 C に渡す。

3. これに対して挑戦者 C は m0 か m1 かどちらかをランダムに選び(これを mb とかく)、公開鍵 e で暗号化して暗号文 c をつくる:
  • c ← E(e, mb).
挑戦者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 = xe  (mod n)
において、
y は x の全てを隠せているわけではない
から。

ところが、関数 y = xe  (mod n) は、(RSA 仮定のもとで)x の最下位ビット
  • x0 = LSB(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 について、
    • xi = xi-1e  mod n
  • mask = (LSB(x0), LSB(x1), ・・・, LSB(xl-1))
  • c1 = mask \oplus 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 について
    • xi = xi+1d  mod n.
  • mask = (LSB(x0), LSB(x1), ・・・, LSB(xl-1))
  • m = mask \oplus 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 \oplus 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暗号化関数を
  • c = RSAn,e(m),
私有鍵 (n, d) のRSA復号関数を
  • m = RSA-1n,d(c)
とかく。

鍵生成アルゴリズム G(k) :
RSA 暗号の鍵生成と同じ。公開鍵 (n, e)、私有鍵 (n, d)。

暗号化アルゴリズム E(pk, m) :
公開鍵 pk から (n, e) を取り出して、

  • k0 ビットの乱数 r を生成する。
  • s = (m || 0k1) \oplus G(r)
  • t = r \oplus H(s)
  • c = RSAn,e(s||t) を暗号文とする。

復号アルゴリズム D(sk, m) :
私有鍵 sk から (n, d) を取り出して、

  • (s, t) = RSA-1n,d(c) を暗号文とする。
  • r = t \oplus H(s)
  • m' = s \oplus G(r)
  • m' の末尾 k1 ビットがすべて0ならば、暗号文を正当と認め、m'の残りの文字列をメッセージとして返す。
    • そうでなければ、Reject を返す。


攻撃者が暗号文を「でっち上げよう」としたら、その 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)):
  • return c2/c1x.


判定DH仮定のもとで、エルガマル暗号は選択平文攻撃に対し強秘匿である。





















最終更新:2010年05月28日 15:03