公開鍵暗号

公開鍵暗号（こうかいかぎあんごう、）とは、暗号化と復号とに異なる鍵（手順）を用い、暗号化用の鍵は公開できるようにした暗号方式である（復号用の鍵は秘匿）。対照的な暗号方式として、暗号化と復号に同一の鍵を用いる共通鍵暗号がある。
暗号化は通信の秘匿性を高めるための手段だが、それに必須の鍵もまた情報なので、鍵を受け渡す過程で盗聴されてしまうというリスクがあった。共通鍵を秘匿して受け渡すには（特使が運搬するというような）コストもかかり、一般人が暗号を用いる際の障害であった。このような暗号化鍵の配送問題を解決したのが公開鍵暗号である。
公開鍵暗号で使われるのと同じ数学的な理論に基づいて通信の安全性を保障する暗号技術全般を指して、広義に公開鍵暗号（あるいは公開鍵暗号技術、非対称暗号技術）と呼ぶこともある。この場合、秘匿を目的とする公開鍵暗号方式だけでなく、デジタル署名（秘匿機能は無い）、公開鍵通信路のみを用いて共通鍵を合意することのできるディフィー・ヘルマン鍵交換なども含まれる。
以下では、秘匿を目的とした狭義での公開鍵暗号について扱う。
共通鍵暗号の問題点.
1976年以前には、数理による暗号といえば共通鍵暗号であった。これは暗号化と復号に共通の鍵を使う方式である。共通鍵暗号には、鍵の受け渡しを密かに行わなければならないという課題（鍵配送問題）があった。
共通鍵暗号を用いた通信手順の概略は次のようになる。
もし段階 1. で、送信者に対してセキュリティが保証されていない通信路を用いて鍵を配送した場合、第三者に共通鍵 c を傍受されていると、この暗号通信は容易に解読されてしまう。
公開鍵暗号の考案.
共通鍵暗号に生じる鍵配送問題は、送信者と受信者の両者がただ1つの共通の鍵を用いるために起こる問題である。そこで、両者が異なる鍵を用いる方法、すなわち公開鍵暗号が考案された。
公開鍵暗号を用いた通信手順の概略：
暗号通信を不正に傍受しようとする者（傍受者）が公開鍵暗号の方式によって暗号化されたメッセージを傍受したとしても、公開鍵 p から秘密鍵 s を導き出すことは、計算時間の観点から極めて難しいため、暗号文を復号することはおよそできない。
暗号化のための鍵と復号のための鍵を異なるものにしたことで、鍵配送問題は解決された。
なお、暗号の用語については、暗号理論の用語、暗号の用語を参照。
公開鍵暗号方式の直観的な定義.
モデル.
公開鍵暗号方式では、鍵生成アルゴリズム、暗号化アルゴリズム、復号アルゴリズムを用いる。
鍵生成アルゴリズムは事前準備のためのアルゴリズムであり、（将来暗号文を受け取りたい）ユーザは事前に鍵生成アルゴリズムを実行しておく必要がある。ユーザが鍵生成アルゴリズムを実行すると、アルゴリズムはそのユーザの公開鍵および秘密鍵（それぞれ、そのように呼ばれるデータ）を出力する。公開鍵は暗号文を作成するのに使い、秘密鍵はその暗号文からメッセージを復元するのに使う。
ユーザは鍵生成アルゴリズムを実行する際、セキュリティ・パラメータという値をこのアルゴリズムに入力する。セキュリティ・パラメータは、秘密鍵なしでの暗号文の解読がどれだけ困難かを示す尺度である。
鍵生成アルゴリズムには乱数も入力される。鍵生成アルゴリズムは実行ごとに異なる乱数を選ぶので、ユーザ毎に異なる公開鍵・秘密鍵ペアが割りふられる。
各ユーザは秘密鍵を密かに保管し、公開鍵を公開する。ユーザの秘密鍵を知っているのはそのユーザ自身だけであり、ユーザの公開鍵を知っている(知ることができる)のは全てのユーザである。
メッセージを秘匿する暗号通信をするときの公開鍵、秘密鍵を、それぞれ暗号化鍵、復号鍵ともいう。
暗号文を送る際は、送りたいメッセージおよびそのメッセージの送信先（受信者）の公開鍵を入力として暗号化アルゴリズムを実行する。
受信者は復号アルゴリズムに自分の秘密鍵と暗号文を入力して、もとのメッセージを復元する。
公開鍵を使えば誰でも暗号文を作成できるが、その暗号文を正しく復号できるのは受信者本人だけである。
公開鍵の認証.
安全性を確保するには、どの公開鍵がどのユーザのものであるのかという対応をきちんとつけておく必要がある。暗号化に受信者の公開鍵 p を用いているので、もし、公開鍵 p とユーザとの対応が誤っていると、誤ったユーザの公開鍵を使って暗号文を送信してしまうことになる。これを悪用して、前もってあえて誤った対応表を作成しておくことによって暗号文を解くという攻撃が可能である（攻撃者は攻撃者自身の公開鍵をあたかも対象の受信者の公開鍵であるかのように見せた偽の対応表を作る。攻撃者の公開鍵を用いて暗号化された暗号文が対象の受信者へ送られたら、攻撃者はその暗号文を傍受して自身の秘密鍵で復号する。）。
公開鍵とその持ち主を対応させる方法はいくつか考案されている。代表的な方法は次の2つである。どちらも、（Trusted Third Party、TTP）が必要になる。
歴史.
1960年代、イギリスの政府通信本部 (GCHQ) に所属するが公開鍵暗号（非秘密暗号）を考案し提案は受諾された。しかし理論的には有用性が認められたが、一方向性関数が見つけられずこのアイデアは実用化されなかった。1973年、同機関に入所したがこのアイデアに取り組み「作用は可能だが、逆転させられない関数」から素数と素因数分解を基に30分程度で数式を組み立て、さらにが鍵配送問題に解決の糸口を見つけ、今日の"RSA"と呼ばれる暗号システムの基礎を確立した。同時期に、彼らとは無関係な米国のアマチュア数学者、ウィットフィールド・デフィーが独学で公開鍵暗号開発に取り組んでいた。1976年に、ラルフ・マークルの研究の影響を受けたデフィーとマーティン・ヘルマンが公開鍵暗号に関する世界最初の論文「"New Directions in Cryptography"」を発表した。
公開鍵暗号という新規な発明は、本来、エリス＝コックス＝ウィリアムソン組が先であったが、論文にして公表し、その有用性を広く伝えたのは、デフィー＝ヘルマン＝マークル組となったため、本発明の特許権と栄誉は彼らが得た。先に考案していたエリス＝コックス＝ウィリアムソン組は、英軍の管理下であったGCHQが国家機密となっていたために、後発組が公開鍵暗号の論文を発表しても、契約により口外できなかった。後年、公開鍵暗号が広く普及したことで本暗号に関する機密扱いが解除され、エリス＝コックス＝ウィリアムソン組の功績が世に知られることになった。デフィーの「先に開発していたのは本当ですか？」との問いに、エリスは「我々より、君達の方がより多くの事をやっている」と答えている。
公開鍵暗号の概念を実現する具体的な方式は、MITの研究者であったロナルド・リベスト、アディ・シャミア、レオナルド・エーデルマンの3人が1977年に開発した。この方式は、開発者各人の頭文字を取って「RSA方式」と呼ばれるようになった。1982年、彼らはカリフォリニア州レッドウッド市にデータセキュリティ専門の会社「RSAデータセキュリティ社」を設立した。
1990年代初頭、フィル・ジマーマンがパーソナル・コンピュータに搭載可能なプログラム「PGP（Pretty Good Privacy）」を開発し公開した。PGPが世界に普及したことで、誰でも公開鍵暗号が使用できるようになった。
公開鍵暗号は、1980年ごろには「公衆暗号 (public cryptography)」とも呼ばれていた。用語「公衆暗号系 (public cryptosystem)」も使われていたが、DES のような公衆が用いる共通鍵暗号を含むかどうかが紛らわしかったので、これらの用語はすぐに使われなくなった。
RSA暗号.
公開鍵暗号にはさまざまな方式がある。ここでは典型的な公開鍵暗号方式であるRSA暗号方式を説明する。
この方式の安全性は素因数分解の困難性に基づいている。詳しくはRSA暗号を参照。
大きな素数 p, q が与えられたとき、その積 n = pq を計算することは容易である。しかし、2つの大きな素数の積である自然数 n が与えられたとき、それを n = pq と素因数分解することは難しい。例えば n=21 のときは n が小さいので p=7, q=3 を求めるのは容易だが、鍵の大きさ（すなわち p, q のビット数）が十分に大きければ、素因数分解にはとてつもない時間が掛かる。
暗号化には n を、復号には p と q を必要とするようなうまい仕組みを作っておく。そして、n を公開鍵として公開する。傍受者は n から p, q を割り出そうとするが、これは時間が掛かりすぎて現実的でない。
根気強く素因数分解を試みていれば、いつかは復号できる。しかし、一般市民間の個人的な通信程度であれば、解読に数年を要する規模の暗号化を施しておけば、それ以上の手間を掛けて解読しようとする者はまずいない。これは、事実上秘密が守られているといえる（計算量的安全性）。
軍事用暗号の場合、専用のコンピュータで専門のプログラムを走らせても解読には数億年～数兆年を要するように設計されている。これも事実上解読不可能といってよい。
実際の使われ方.
一般的に、公開鍵暗号は共通鍵暗号よりも暗号化、復号に時間がかかる。そのため、実際の運用では、データの暗号化には「その場限りの共通鍵」を使用し、その共通鍵の配送だけを公開鍵暗号で行う方式がとられることが多い。
公開鍵暗号を初めて実現したのがRSA暗号である。RSA暗号は公開鍵暗号として、実際に広く利用されることとなった。
公開鍵暗号方式の厳密な定義.
モデル.
kをセキュリティ・パラメータとする。formula_1 を、次を満たす平均多項式時間確率アルゴリズム3つ組とする。
formula_1 が後述する正当性を満たすとき、formula_16 は公開鍵暗号方式であるといい、後述する秘匿性をさらに満たすとき、公開鍵暗号方式は安全であるという。
要件.
公開鍵暗号方式は、次の2つの要件を満たさねばならない。
秘匿性.
識別不可能性.
直観的な定義.
formula_19、formula_20 を攻撃者が指定した2つのメッセージとし、formula_14 を formula_19 もしくはformula_20 を暗号化した暗号文とする。
このとき、攻撃者は formula_14 が formula_19、formula_20 のいずれを暗号化したものであるかを（1/2よりも有意な確率で）知る事はできない。
厳密な定義.
formula_27, formula_28 を2つのオラクル、formula_29 をビットとする。
暗号に対する攻撃者 formula_30 を用いて次の実験 (Experiment, ゲーム (game) ともいう) をする。
攻撃者 formula_30 のアドバンテージ(advantage)を :formula_38
により定義する。
ただしここで formula_53 は次の節で述べる復号オラクルである。
公開鍵暗号方式の場合暗号化用の鍵が公開されているので、攻撃者は（オラクルの助けを借りずとも）任意の平文を暗号化する事ができる。このため、Key Only Attackの事を選択平文攻撃（Chosen Plaintest Attack, CPAと略す）ともいう。
復号オラクル.
復号オラクル formula_54 は、攻撃者が任意の暗号文 formula_14 を復号オラクルformula_54 に送信すると、formula_57 である限り、formula_58 を使って formula_14 を復号した formula_60 を攻撃者に送り返してくれるオラクルである。（下図参照）
強秘匿性 (Semantic Security).
直観的定義.
暗号文を知っていることは、平文を知る上で何の役にもたたない。すなわち、暗号文を知っている状況で攻撃者が知ることができる平文についての部分情報は、暗号文を知らなくても攻撃者が知ることができる情報だけである。
厳密な定義.
formula_65 をセキュリティ・パラメータとし、formula_1 を公開鍵暗号方式とする。formula_67 を多項式時間機械とする。
さらに、formula_68 をオラクルとする。
次の2つのゲームを考える。ただしゲーム中で、formula_69 は多項式時間機械（の動作を記したプログラム）、formula_70 はビット列で、formula_30 の状態と呼ばれる。
任意の多項式時間機械 formula_30 に対し、ある多項式時間機械 formula_86 が存在し、
が "k" に関して無視できるとき、公開鍵暗号方式 formula_1 は formula_42-強秘匿 (Semantic Secure) であるという。
頑強性 (Non Malleability) (Bellare等による定義).
formula_30 を攻撃者とし、以下のゲームを考える。
ただし、上のゲームで、formula_112 は、常に同じビット数のメッセージを出力するアルゴリズムでなければならない。
任意の多項式時間機械 formula_30 に対し、
が "k" に関して無視できるとき、公開鍵暗号方式 formula_1 は formula_42-non malleableであるという。
関連項目.
暗号関連