公開鍵暗号

公開鍵暗号とは、暗号化と復号とに異なる鍵を用い、暗号化用の鍵は公開できるようにした暗号方式である。対照的な暗号方式として、暗号化と復号に同一の鍵を用いる共通鍵暗号がある。

暗号化は通信の秘匿性を高めるための手段だが、それに必須の鍵もまた情報なので、鍵を受け渡す過程で盗聴されてしまうというリスクがあった。共通鍵を秘匿して受け渡すにはコストもかかり、一般人が暗号を用いる際の障害であった。このような暗号化鍵の配送問題を解決したのが公開鍵暗号である。

公開鍵暗号で使われるのと同じ数学的な理論に基づいて通信の安全性を保障する暗号技術全般を指して、広義に公開鍵暗号と呼ぶこともある。この場合、通信の秘匿を目的とする公開鍵暗号方式だけでなく、秘匿機能は無いデジタル署名、公開鍵通信路のみを用いて共通鍵を合意することができるディフィー・ヘルマン鍵交換なども含まれる。

以下では、通信の秘匿を目的とした狭義での公開鍵暗号について扱う。

1. 共通鍵暗号の問題点
------------

1976年以前には、数理による暗号といえば共通鍵暗号であった。これは暗号化と復号に共通の鍵を使う方式である。共通鍵暗号には、鍵の受け渡しを密かに行わなければならないという課題があった。

共通鍵暗号を用いた通信手順の概略は次のようになる。

あらかじめ、受信者と送信者は密かに共通鍵 c の受け渡しをしておく。
送信者は c を使ってメッセージを暗号化し、受信者に送信する。
受信者は c を使って暗号文を復号し、メッセージを読む。もし段階 1. で、送信者に対してセキュリティが保証されていない通信路を用いて鍵を配送した場合、第三者に共通鍵 c を傍受されていると、この暗号通信は容易に解読されてしまう。

2. 公開鍵暗号の考案
-----------

共通鍵暗号に生じる鍵配送問題は、送信者と受信者の両者がただ1つの共通の鍵を用いるために起こる問題である。そこで、両者が異なる鍵を用いる方法、すなわち公開鍵暗号が考案された。

公開鍵暗号を用いた通信手順の概略：

通信を受ける者は自分の公開鍵p を全世界に公開する。
受信者に対して暗号通信をする者は、公開鍵 p を使ってメッセージを暗号化してから送信する。
受信者は、公開鍵 p と対になる秘密鍵s を密かにもっている。この s を使って受信内容を復号し、送信者からのメッセージを読む。暗号通信を不正に傍受しようとする者が公開鍵暗号の方式によって暗号化されたメッセージを傍受したとしても、公開鍵 p から秘密鍵 s を導き出すことは、計算時間の観点から極めて難しいため、暗号文を復号することはおよそできない。

暗号化のための鍵と復号のための鍵を異なるものにしたことで、鍵配送問題は解決された。

なお、暗号の用語については、暗号理論の用語、暗号の用語を参照。

3. 公開鍵暗号方式の直観的な定義
-----------------

3.1. モデル
--------

公開鍵暗号方式では、鍵生成アルゴリズム、暗号化アルゴリズム、復号アルゴリズムを用いる。

鍵生成アルゴリズムは事前準備のためのアルゴリズムであり、ユーザは事前に鍵生成アルゴリズムを実行しておく必要がある。ユーザが鍵生成アルゴリズムを実行すると、アルゴリズムはそのユーザの公開鍵および秘密鍵を出力する。公開鍵は暗号文を作成するのに使い、秘密鍵はその暗号文からメッセージを復元するのに使う。

ユーザは鍵生成アルゴリズムを実行する際、セキュリティ・パラメータという値をこのアルゴリズムに入力する。セキュリティ・パラメータは、秘密鍵なしでの暗号文の解読がどれだけ困難かを示す尺度である。

鍵生成アルゴリズムには乱数も入力される。鍵生成アルゴリズムは実行ごとに異なる乱数を選ぶので、ユーザ毎に異なる公開鍵・秘密鍵ペアが割りふられる。

各ユーザは秘密鍵を密かに保管し、公開鍵を公開する。ユーザの秘密鍵を知っているのはそのユーザ自身だけであり、ユーザの公開鍵を知っているのは全てのユーザである。

メッセージを秘匿する暗号通信をするときの公開鍵、秘密鍵を、それぞれ暗号化鍵、復号鍵ともいう。

暗号文を送る際は、送りたいメッセージおよびそのメッセージの送信先の公開鍵を入力として暗号化アルゴリズムを実行する。 受信者は復号アルゴリズムに自分の秘密鍵と暗号文を入力して、もとのメッセージを復元する。 公開鍵を使えば誰でも暗号文を作成できるが、その暗号文を正しく復号できるのは受信者本人だけである。

3.2. 公開鍵の認証
-----------

安全性を確保するには、どの公開鍵がどのユーザのものであるのかという対応をきちんとつけておく必要がある。暗号化に受信者の公開鍵 p を用いているので、もし、公開鍵 p とユーザとの対応が誤っていると、誤ったユーザの公開鍵を使って暗号文を送信してしまうことになる。これを悪用して、前もってあえて誤った対応表を作成しておくことによって暗号文を解くという攻撃が可能である。

公開鍵とその持ち主を対応させる方法はいくつか考案されている。代表的な方法は次の2つである。どちらも、信頼できる第三者機関が必要になる。

信頼できる第三者機関が各人のIDと公開鍵を対応付けた表を作成して公開する。
信頼できる複数の第三者機関が認証局を運営し、公開鍵基盤  の仕組みを使って各人のIDと公開鍵とを対応付ける。

4. 歴史
-----

1960年代、イギリスの政府通信本部  に所属するジェイムズ・エリスが公開鍵暗号を考案し提案は受諾された。しかし理論的には有用性が認められたが、一方向性関数が見つけられずこのアイデアは実用化されなかった。1973年、同機関に入所したクリフォード・コックスがこのアイデアに取り組み「作用は可能だが、逆転させられない関数」から素数と素因数分解を基に30分程度で数式を組み立て、さらにマルコム・ウィリアムソンが鍵配送問題に解決の糸口を見つけ、今日の"RSA"と呼ばれる暗号システムの基礎を確立した。同時期に、彼らとは無関係な米国のアマチュア数学者、ウィットフィールド・デフィーが独学で公開鍵暗号開発に取り組んでいた。1976年に、ラルフ・マークルの研究の影響を受けたデフィーとマーティン・ヘルマンが公開鍵暗号に関する世界最初の論文「//New Directions in Cryptography//」を発表した。

公開鍵暗号という新規な発明は、本来、エリス＝コックス＝ウィリアムソン組が先であったが、論文にして公表し、その有用性を広く伝えたのは、デフィー＝ヘルマン＝マークル組となったため、本発明の特許権と栄誉は彼らが得た。先に考案していたエリス＝コックス＝ウィリアムソン組は、英軍の管理下であったGCHQが国家機密となっていたために、後発組が公開鍵暗号の論文を発表しても、契約により口外できなかった。後年、公開鍵暗号が広く普及したことで本暗号に関する機密扱いが解除され、エリス＝コックス＝ウィリアムソン組の功績が世に知られることになった。デフィーの「先に開発していたのは本当ですか？」との問いに、エリスは「我々より、君達の方がより多くの事をやっている」と答えている。

公開鍵暗号の概念を実現する具体的な方式は、MITの研究者であったロナルド・リベスト、アディ・シャミア、レオナルド・エーデルマンの3人が1977年に開発した。この方式は、開発者各人の頭文字を取って「RSA方式」と呼ばれるようになった。1982年、彼らはカリフォリニア州レッドウッド市にデータセキュリティ専門の会社「RSAデータセキュリティ社」を設立した。

1990年代初頭、フィル・ジマーマンがパーソナル・コンピュータに搭載可能なプログラム「PGP」を開発し公開した。PGPが世界に普及したことで、誰でも公開鍵暗号が使用できるようになった。

公開鍵暗号は、1980年ごろには「公衆暗号 」とも呼ばれていた。用語「公衆暗号系 」も使われていたが、DES のような公衆が用いる共通鍵暗号を含むかどうかが紛らわしかったので、これらの用語はすぐに使われなくなった。

5. RSA暗号
--------

公開鍵暗号にはさまざまな方式がある。ここでは典型的な公開鍵暗号方式であるRSA暗号方式を説明する。

この方式の安全性は素因数分解の困難性に基づいている。詳しくはRSA暗号を参照。

大きな素数 p, q が与えられたとき、その積 n = pq を計算することは容易である。しかし、2つの大きな素数の積である自然数 n が与えられたとき、それを n = pq と素因数分解することは難しい。例えば n=21 のときは n が小さいので p=7, q=3 を求めるのは容易だが、鍵の大きさが十分に大きければ、素因数分解にはとてつもない時間が掛かる。

暗号化には n を、復号には p と q を必要とするようなうまい仕組みを作っておく。そして、n を公開鍵として公開する。傍受者は n から p, q を割り出そうとするが、これは時間が掛かりすぎて現実的でない。

根気強く素因数分解を試みていれば、いつかは復号できる。しかし、一般市民間の個人的な通信程度であれば、解読に数年を要する規模の暗号化を施しておけば、それ以上の手間を掛けて解読しようとする者はまずいない。これは、事実上秘密が守られているといえる。

軍事用暗号の場合、専用のコンピュータで専門のプログラムを走らせても解読には数億年～数兆年を要するように設計されている。これも事実上解読不可能といってよい。

6. 実際の使われ方
----------

一般的に、公開鍵暗号は共通鍵暗号よりも暗号化、復号に時間がかかる。そのため、実際の運用では、データの暗号化には「その場限りの共通鍵」を使用し、その共通鍵の配送だけを公開鍵暗号で行う方式がとられることが多い。

公開鍵暗号を初めて実現したのがRSA暗号である。RSA暗号は公開鍵暗号として、実際に広く利用されることとなった。

7. 公開鍵暗号方式の厳密な定義
----------------

7.1. モデル
--------

kをセキュリティ・パラメータとする。 を、次を満たす平均多項式時間確率アルゴリズム3つ組とする。

は鍵生成アルゴリズム  と呼ばれ、 を入力されると公開鍵秘密鍵ペア を出力する。
は暗号化アルゴリズム  と呼ばれ、 の出力した公開鍵 と平文と呼ばれるビット列 を入力されると、 の暗号文 を出力する。
は復号アルゴリズム  と呼ばれ、 の出力した秘密鍵 と の出力した暗号文 とを入力されると平文を出力する。 が後述する正当性を満たすとき、 は公開鍵暗号方式であるといい、後述する秘匿性をさらに満たすとき、公開鍵暗号方式は安全であるという。

7.2. 要件
-------

公開鍵暗号方式は、次の2つの要件を満たさねばならない。

正当性  : 正当な受信者は、正当な方法で作成された暗号文を復号できる。
秘匿性  : 正当な方法で作成された暗号文を復号できるのは、正当な受信者だけである。

7.3. 正当性
--------

定義 が以下の条件を満たすとき、 は正当性を満たすという : 任意の平文 m に対し、Pr ← G, C ← Epk : Dsk = m) は圧倒的  である。

7.4. 秘匿性
--------

7.4.1. 識別不可能性
-------------

7.4.1.1. 直観的な定義
---------------

、 を攻撃者が指定した2つのメッセージとし、 を もしくは を暗号化した暗号文とする。

このとき、攻撃者は が 、 のいずれを暗号化したものであるかを知る事はできない。

7.4.1.2. 厳密な定義
--------------

, を2つのオラクル、 をビットとする。

暗号に対する攻撃者 を用いて次の実験  ともいう) をする。

Return .攻撃者 のアドバンテージを : により定義する。

定義 任意の平均多項式時間確率アルゴリズム  に対し、 が //k// に関して無視できるとき、暗号方式 は -識別不可能  であるという。 特に、
、 のとき、公開鍵暗号方式 はKey Only Attackに対し、識別不可能であるという。
、 であるとき、公開鍵暗号方式 は選択暗号文攻撃 ) に対して識別不可能であるという。
、 であるとき、公開鍵暗号方式 は適応的選択暗号文攻撃に対して識別不可能であるという。ただしここで は次の節で述べる復号オラクルである。

公開鍵暗号方式の場合暗号化用の鍵が公開されているので、攻撃者は任意の平文を暗号化する事ができる。このため、Key Only Attackの事を選択平文攻撃ともいう。

7.4.1.3. 復号オラクル
---------------

復号オラクル は、攻撃者が任意の暗号文 を復号オラクル に送信すると、 である限り、 を使って を復号した を攻撃者に送り返してくれるオラクルである。

復号オラクル If return . Otherwise return .

7.4.2. 強秘匿性 
-------------------------------

7.4.2.1. 直観的定義
--------------

暗号文を知っていることは、平文を知る上で何の役にもたたない。すなわち、暗号文を知っている状況で攻撃者が知ることができる平文についての部分情報は、暗号文を知らなくても攻撃者が知ることができる情報だけである。

7.4.2.2. 厳密な定義
--------------

をセキュリティ・パラメータとし、 を公開鍵暗号方式とする。 を多項式時間機械とする。

さらに、 をオラクルとする。

次の2つのゲームを考える。ただしゲーム中で、 は多項式時間機械、 はビット列で、 の状態と呼ばれる。

If , return 1. Otherwise return 0. If , return 1. Otherwise return 0.任意の多項式時間機械 に対し、ある多項式時間機械 が存在し、

が //k// に関して無視できるとき、公開鍵暗号方式 は -強秘匿  であるという。

、 のとき、公開鍵暗号方式 はKey Only Attackに対し、強秘匿であるという。
、 であるとき、公開鍵暗号方式 は選択暗号文攻撃 に対して強秘匿であるという。
、 であるとき、公開鍵暗号方式 は適応的選択暗号文攻撃に対して強秘匿であるという。

7.4.3. 頑強性  
---------------------------------------------

を攻撃者とし、以下のゲームを考える。

If for some , return 0. If for some , return 0. If return 0. Return 1.ただし、上のゲームで、 は、常に同じビット数のメッセージを出力するアルゴリズムでなければならない。

任意の多項式時間機械 に対し、

が //k// に関して無視できるとき、公開鍵暗号方式 は -non malleableであるという。

、のとき、公開鍵暗号方式はKey Only Attackに対し、頑強である  という。
、であるとき、公開鍵暗号方式は選択暗号文攻撃に対して頑強であるという。
、であるとき、公開鍵暗号方式は適応的選択暗号文攻撃に対して頑強であるという。

8. 参考文献
-------

8.1. 論文
-------

[1], M. Bellare, A. Desai, D. Pointcheval and P. Rogaway
[2], Mihir Bellare, Alexandra Boldyreva, Anand Desai, David Pointcheval

9. 関連項目
-------

秘匿通信
電子署名
素因数分解暗号関連

暗号理論
暗号
ディフィー・ヘルマン鍵共有
RSA暗号
ElGamal暗号
楕円曲線暗号
Merkle-Hellmanナップサック暗号 - ラルフ・マークル - マークルのパズル
NTRU暗号
アリスとボブ

10. 脚注
------

10.1. 注釈
--------

10.2. 出典
--------

11. 外部リンク
---------