公開鍵暗号入門
情報セキュリティ大学院大学

有田正剛

平成 19 年 5 月 8 日

目次
1

はじめに

12

公開鍵暗号の基本機能

23

公開鍵暗号の定義

34Rabin 暗号
4.1 必要な整数論 . . . . . . . . . . . . . . . . . . . . . . . . .
4.2 暗号方式 . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3445暗号の強秘匿性
5.1 Rabin 暗号の問題点 . . . . . . . . . . . . . . . . . . . . . .
5.2 強秘匿性の定義 . . . . . . . . . . . . . . . . . . . . . . . .

5566

Blum-Goldwasser 暗号

77

おわりに

91

はじめに

公開鍵暗号は今や私たちにとってとても身近な存在である。我たちはそれとは意識せずに日々色々な場面で公開鍵暗号を使っている。Internet では SSL、高速道路では ETC、また駅では Suica が私たちの代理として暗号演算を実行している。
この入門講義では、そのような公開鍵暗号とはどんな技術か、そのからくりはどうなっているか、またなぜ安全といえるか、解説したい。
公開鍵暗号は予め秘密を共有しないで秘密の通信を行う方法である。そのような公開鍵暗号をつくる上で、数学の一分野である整数論がとても役1に立つ。ここでは例として Rabin 暗号を取り上げ、それが整数の平方演算を利用して作られることをみる。そして、私たちや私たちが作り出したコンピュータにとって整数を因数分解することが困難であるために、Rabin暗号が暗号として成立する（すなわち、暗号文から元のメッセージを求めることができない）のをみる。
しかし、公開鍵暗号をさらに「強秘匿」なものにするには、整数論だけでは足りない。我々にとって整数論的課題のどこが難しいのかを見極め、乱数をうまく用いて、ある工夫を施す必要がある。そのような工夫を用いて、Rabin 暗号を強化することで、強秘匿な暗号（すなわち、暗号文から元のメッセージのどのような部分情報さえ求めることができない暗号）である Blum-Goldwasser 暗号が作られることをみる。

2

公開鍵暗号の基本機能

暗号とは、秘密の通信を行うために利用される技術である。暗号には、大きく分けて、共通鍵暗号と公開鍵暗号がある。共通鍵暗号は、「予め共有した秘密を用いて秘密の通信を行う方法」である。予め共有した秘密は共通鍵と呼ばれる。送信者はメッセージを共通鍵で暗号化し、暗号文を受信者に送る。暗号文を受け取った受信者はそれを共通鍵で復号してもとのメッセージを得る。予め共有した秘密があるなら、それを用いれば秘密通信ができだろうことは、具体的な方法はともかくとして、もっともなことである。
一方、公開鍵暗号は「予め秘密を共有しないで秘密の通信を行う方法」である。これは、一見すると受けいれがたく、そんなことができるものか、と思えるが、我たちやコンピュータの能力が有限であることを利用すれば実現できる。
公開鍵暗号では各自の鍵は公開鍵と私有鍵の組からなる。公開鍵は（その所有者への）メッセージの暗号化に用い、私有鍵は（その所有者が自分宛の）暗号文の復号に用いる。ある公開鍵で暗号化された暗号文は、それとセットになっている私有鍵でしか、復号されないようになっている。
公開鍵暗号を用いて、実際にメッセージを暗号化して送るには、以下のようにする。まず、受信者は自分の公開鍵を、その名の通り、公開する。
送信者は、公開された受信者の公開鍵を手に入れ、この公開鍵を用いてメッセージを暗号化し、受信者に送る。暗号文を受け取った受信者はそれを自分の私有鍵で復号してもとのメッセージを得る。ここで、この受信者以外は、メッセージの暗号化に用いられた公開鍵に対応する私有鍵を持っていないので、この暗号文を復号することはできない。

2

3

公開鍵暗号の定義

公開鍵暗号は、鍵生成アルゴリズム G、暗号化アルゴリズム E そして復号アルゴリズム D の 3 つの効率的なアルゴリズムの組と定義される。
鍵生成アルゴリズム 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).
(1)
ただし、完全性 G によって生成された任意の鍵ペア (e, d) と任意のメッセージ mに対してD(d, E(e, m)) = mでなければならない。これは、暗号化して復号したら必ずもとのメッセージが得られるということを意味する。
また、暗号文 c(← E(e, m)) を入手した敵が、c および公開鍵 e を用いて、m を計算できるようでは暗号といえない。つまり、一方向性 どのような効率的なアルゴリズム A も e と c から m を求めることはできないことが必要である。
公開鍵暗号を作るとは、完全性と一方向性を同時に満たす 3 つのアルゴリズムの組 (G, E, D) を求めることに他ならない。

4Rabin 暗号

公開鍵暗号の一例として、Rabin 暗号を紹介する。Rabin 暗号は整数を法とする平方演算の特性を利用してつくられる。

3

4.1

必要な整数論

まず、必要となる整数論的な事実を述べる。
n を異なる 2 つの素数 p,q の積である整数とする。a mod n は整数 a を整数 n でわった余りを表す。
整数 n に対して Zn = {0, 1, . . . , n−1} とする。Qn を n を法とする平方剰余の集合とする。すなわち、Qn はある b(∈ Zn ) について a = b2 mod n となる a(∈ Zn ) の集合である。n を法とする平方剰余 a に対して、a = b2 mod nとなる b を、a の n を法とする平方根と呼ぶ。
事実 1 整数 n(= pq) の素因数分解を効率的に実行するアルゴリズムが存在しないならば、n を法とする平方根を計算する効率的なアルゴリズムも存在しない。
事実 2 任意の素数 p を法とするならば、平方根を計算する効率的なアルゴリズムが存在する。すなわち、ある効率的なアルゴリズム Sqrt があって、素数 p と、p を法とする平方剰余の集合 Qp からランダムに選ばれたa を入力として、a = b2 mod p となる b を出力する: b ← Sqrt(p, a).
事実 1 と事実 2 は、整数 n(= pq) に対して、平方関数 y = RABINn (x) =2x mod n がトラップドア付き一方向関数であることを示している。
すなわち、順方向の y = RABINn (x) の計算は、平方を計算し n で割り算するだけなので効率的に実行できる。しかし、事実 1 より、逆に y からx = RABIN−1n (y) を求める効率的なアルゴリズムは (素因数分解が困難ならば) 存在しない。
ところが、n の素因子 p, q が与えられれば、そのような逆方向の計算も効率的に実行できる: x = RABIN−1n (p, q, y). (この p, q のような一方向性を破る情報をトラップドアと呼ぶ。) 実際、アルゴリズム Sqrt を用いて
y の modp での平方根 xp を計算する。同様に、y の modq での平方根 xqを計算する。(xp , xq ) を中国人の剰余定理を用いて modn にリフトして yの n を法とする平方根 x を得る。

4.2

暗号方式

Rabin 暗号 Rabin = (G, E, D) は、トラップドア付き一方向関数 y =RABINn (x) を用いて、以下のように構成される。
鍵生成アルゴリズム G(k)それぞれ k ビットの異なる素数 p, q をランダムに生成する。n = pqを公開鍵 e とし、素数 p, q を私有鍵 d とする。

4暗号化アルゴリズム E(e, m)
公開鍵 e から n を取り出して、c = m2 mod n を計算し、c を出力する。
復号アルゴリズム D(d, c)
私有鍵 d から p と q を取り出して、アルゴリズム Sqrt を用いて c のmod p での平方根 ±mp を計算する。同様に、c の mod q での平方根±mq を計算する。(±mp , ±mq ) を中国人の剰余定理を用いて mod nにリフトして (得られる 4 通りのメッセージ候補から)m を得て、出力する。
トラップドア付き一方向関数 y = RABINn (x) の n を公開鍵、トラップ
ドア p, q を私有鍵とするわけである。
Rabin 暗号が完全性条件を満たしているのは、暗号化は平方演算で復号は平方根演算なので、明らかである。一方向性条件は、整数 n(= pq) の素因数分解が困難であるとの仮定のもと、事実 1 からしたがう。

5暗号の強秘匿性

5.1

Rabin 暗号の問題点

Rabin 暗号を用いて秘密通信をしてみる。今、送信者 Alice が受信者 Bobに (ある案件について) 賛成か反対かのいずれかを他者には秘密にして伝えたいとする。あらかじめ、賛成は整数 myes で反対は整数 mno で表すことになっている (このルールは公開されているとする)。Alice は賛成しているとして、そのことを以下のように Rabin 暗号で Bob に伝える。Aliceは、Bob の公開鍵 nB を入手し、c = m2yes mod nB を計算し、暗号文として c を Bob に送信する。Bob は、暗号文 c を受信し、自身の私有鍵 pB , qBを用いて c の nB を法とする平方根を求めて、Alice のメッセージ myes を得る。この送信の途中で敵 Eve が c を覗き見しているかも知れないが、敵Eve は暗号文 c と Bob の公開鍵 nB を 入手しても、対応する私有鍵 pB , qBを持たないので、c の nB を法とする平方根、すなわち myes を求めることはできない、はずだった。
ところが、このケースでは、敵 Eve は c から Alice のメッセージ myesを簡単に求めることができる。Eve はまず mno を Bob の公開鍵 nB で暗号化して c0 を求める。c0 と c を比較するとそれらは異なるので、c に暗号化されていたのは myes であることが分かる。
ここでは、メッセージのパターンが myes と mno の 2 通りという極端な設定で考え、そのせいでメッセージが丸ごとばれてしまったが、メッセー

5

ジがいく通りあってもやはり不都合がある。実際、Eve が自分でメッセージ m0 を選択し、それを暗号化した結果 c0 と c を比較すれば、m0 が c に暗号化されているかどうかがわかる。これを繰り返せば、(c に暗号化された)m のとり得る範囲を狭めていくことができる。Rabin 暗号では、暗号文からもとのメッセージに関する情報が漏れているということである。
暗号文を映像に例えれば、Rabin 暗号は衛星放送でよく見かけるスクランブル映像のようなものである。番組内容の詳細は分からないが、映画かスポーツ中継かぐらいは分かる。

5.2

強秘匿性の定義

前節で Rabin 暗号では暗号文からもとのメッセージに関する情報が漏れてしまっているのを見た。Rabin 暗号を、もとのメッセージに関するどのような情報も漏れないよう、強化することができ、そのようにして得られる暗号として 6 節で紹介する Blum-Goldwasser 暗号がある。
しかし、その前に、ゴールを明確にしたい。
「暗号文からもとのメッセージに関するどのような情報も漏れていない」とはどういうことか？個々の暗号方式に依存せず、普遍的でかつ容易に検証できる定義がほしい。それは暗号の強秘匿性と呼ばれ、つぎにように敵 A と挑戦者 C との間のゲームを用いて定式化することができる。
強秘匿性 公開鍵暗号 (G, E, D) に対して、敵 A と挑戦者 C との間でゲームを行う。ルールは以下の通り。まず、挑戦者 C が鍵生成アルゴリ
ズム G を実行し、鍵ペア (e, d) をつくる。挑戦者 C は公開鍵 e を敵A に渡す。e を受け取ったら、敵 A は何らかの計算をしてメッセージの組 (m0 , m1 ) を選択し、挑戦者 C に渡す。これに対して挑戦者C は m0 か m1 かのいずれかをランダムに選び（これを mb とかく）
公開鍵 e で暗号化して暗号文 c をつくる: c ← E(e, mb ). 挑戦者 C は暗号文 c を敵 A に渡す。敵 A は受け取った暗号文 c が m0 を暗号化したものか、m1 を暗号化したものかどちらかを推測し、推測結果b0 を出力する。推測が当たったら (b = b0 なら) 敵 A の勝ち (そうでないなら挑戦者 C の勝ち) とする。
このとき、どのような敵 A もせいぜい 1/2 の確率でしか勝てないな
らば、公開鍵暗号 (G, E, D) は強秘匿と呼ばれる。
もし、公開鍵暗号 (G, E, D) がメッセージの情報を 1 ビットも漏らしていないならば、敵 A がどんなに強力でも、c が m0 を暗号化したのか m1 を暗号化したのか、全く分からず、b0 をあてずっぽうで出力するしかない。
このとき敵 A が勝つ確率は 1/2 である。

6

一方、公開鍵暗号 (G, E, D) がメッセージの情報を何らかの形で漏らしているならば、巧みな敵 A が、その漏洩を突くようなメッセージの組 (m0 , m1 )を選択して挑戦者 C に提出すれば、その敵 A は高い確率で勝つはずである。

6

Blum-Goldwasser 暗号

Rabin 暗号を強化することで、強秘匿な暗号である Blum-Goldwasser暗号が得られる。強化のポイントは、暗号化に乱数を導入することと hardcore ビットの利用である。
4 節で見たように、関数 y = RABINn (x)(= x2 mod n) は一方向関数(の有力候補) である。しかし、y は x の全てを隠せているわけではない。
実際、x と (x とは異なる)x0 が与えられたとき、どちらが y の原像かと問われれば、x であると分かってしまう (x2 mod n が y になることを確認する)。このため、Rabin 暗号は強秘匿な暗号にはならないのだった。
ところが、y(= RABINn (x) = x2 mod n) は、x の最下位ビット x0 =LSB(x)、すなわち x が偶数かそれとも奇数かということ、は隠せていることが知られている。つまり、y が与えられても、0 と 1 のどちらが x の最下位ビットか分からない。このことを関数 y = RABINn (x) は hard-coreビットとして最下位ビット LSB(x) をもつという。関数 y = RABINn (x)に限らず、どのような一方向関数も hard-core ビットをもつ（ように変形できる）ことが知られている。
Blum-Goldwasser = (G, E, D) は以下のように構成される。
鍵生成アルゴリズム G(k)それぞれ k ビットの、8 でわって 7 余る、異なる素数 p, q をランダムに生成する。n = pq を公開鍵 e とし、素数 p, q を私有鍵 d とする。
暗号化アルゴリズム E(e, m)
m のビット長を l とする。公開鍵 e から n を取り出して、1. Zn からランダムに z を選び、x0 = z 2 mod n を求める。
2. i = 1, . . . , l に対して、xi = x2i−1 mod n を計算する。
3. mask = (LSB(x0 ), LSB(x1 ), . . . , LSB(xl−1 )) を求め、c1 = mask⊕
m を計算する (⊕ はビット毎の排他的論理和)。
4. c = (c1 , xl ) を出力する。
復号アルゴリズム D(d, c)
私有鍵 d から p と q を取り出して、c = (c1 , y) に対し、

7

1. p, q を用いて平方根演算を繰り返し、y(= xl ) から x0 を求める。
2. i = 1, . . . , l に対して、xi = x2i−1 mod n を計算する。
3. mask = (LSB(x0 ), LSB(x1 ), . . . , LSB(xl−1 )) を求め、m = mask⊕
c1 を計算し出力する。
Blum-Goldwasser 暗号では、Qn のランダム要素 x0 をとり、xi+1 =RABINn (xi ) の hard-core ビット LSB(xi ) を利用して、(メッセージ m と同じ長さの) ビット列 mask = (LSB(x0 ), LSB(x1 ), . . . , LSB(xl−1 )) を生成し、mask をメッセージ m に足しこむことによって暗号文 c1 = mask ⊕ mを生成している。ただし、c1 だけでは誰も復号できなくなるので、xl を暗号文に添付している: c = (c1 , xl ).
c = (c1 , xl ) を受け取った正当な復号者は、私有鍵 p, q を用いて平方根演算を繰り返し、xl から x0 を求めることができる。一旦 x0 が分かれば、暗号化のときと全く同じ手続きで mask を生成すれば、m = mask ⊕ c1によってメッセージ m が得られる。
一方、敵が暗号文 c(= (c1 , xl )) に含まれる xl を見ても、hard-core ビットの性質から c1 を作るのに用いた mask の各ビットは分からない。実際、
mask = (LSB(x0 ), LSB(x1 ), . . . , LSB(xl−1 )) の各ビットを見ると• LSB(xl−1 ) は xl (= x2l−1 mod n) の hard-core ビット• LSB(xl−2 ) は xl−1 (= x2l−2 mod n) の hard-core ビット• ...
• LSB(x0 ) は x1 (= x20 mod n) の hard-core ビットとなっている。敵は xl を知っているが、hard-core ビットの性質から、LSB(xl−1 ) は全く分からない。敵は、xl−1 の部分情報を知っているかもしれないが、LSB(xl−2 ) は全く分からない。(xl−1 を知っていても LSB(xl−2 )は全く分からないから。) 以下同様に繰り返し、敵は、x1 の部分情報を知っているかもしれないが、LSB(x0 ) は全く分からない。
以上から、mask は敵にとって未知の (メッセージ m と同じ長さの) 乱数列に等しいことが分かった。すると、c = mask ⊕ m は m の情報を完全に隠してしまうので、強秘匿性の定義のゲームに現れた攻撃者 A に勝ち目はなく、Blum-Goldwasser 暗号 (G, E, D) は強秘匿となる。映像に例えれば、Blum-Goldwasser 暗号はサンドストームといったところである。
映画かスポーツ中継か、そもそも放送中なのかも分からない。

8

7

おわりに公開鍵暗号の例として、整数を法とした平方関数の一方向性を利用した、Rabin 暗号を紹介し、それを hard-core ビットを利用して強化することで強秘匿な Blum-Goldwasser 暗号が構成されることを見た。
ここでは、攻撃モデルとしては選択メッセージ攻撃しか扱わなかった。
選択メッセージ攻撃とは、敵がメッセージを選択し、それに対する暗号文が与えられる攻撃モデルである。より強力な攻撃モデルとして、敵が暗号文を選択し、それに対するメッセージが与えられる攻撃である選択暗号文攻撃がある。また、安全性定義についても、強秘匿性のほかに頑健性と呼ばれる安全性がある。

9