パブリック・キー・クリプトグラフィー
公開鍵暗号
 | この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 (2012年2月) |
公開鍵暗号（こうかいかぎあんごう、英語: Public-key cryptography）とは、暗号化と復号とに異なる鍵（手順）を用い、暗号化用の鍵は公開できるようにした暗号方式である（復号用の鍵は秘匿）。対照的な暗号方式として、暗号化と復号に同一の鍵を用いる共通鍵暗号がある。
暗号化は通信の秘匿性を高めるための手段だが、それに必須の鍵もまた情報なので、鍵を受け渡す過程で盗聴されてしまうというリスクがあった。共通鍵を秘匿して受け渡すには（特使が運搬するというような）コストもかかり、一般人が暗号を用いる際の障害であった。このような暗号化鍵の配送問題を解決したのが公開鍵暗号である。
公開鍵暗号で使われるのと同じ数学的な理論に基づいて通信の安全性を保障する暗号技術全般を指して、広義に公開鍵暗号（あるいは公開鍵暗号技術、非対称暗号技術）と呼ぶこともある。この場合、通信の秘匿を目的とする公開鍵暗号方式だけでなく、秘匿機能は無いデジタル署名、公開鍵通信路のみを用いて共通鍵を合意することができるディフィー・ヘルマン鍵交換なども含まれる。
以下では、通信の秘匿を目的とした狭義での公開鍵暗号について扱う。
共通鍵暗号の問題点
1976年以前には、数理による暗号といえば共通鍵暗号であった。これは暗号化と復号に共通の鍵を使う方式である。共通鍵暗号には、鍵の受け渡しを密かに行わなければならないという課題（鍵配送問題）があった。
共通鍵暗号を用いた通信手順の概略は次のようになる。
- あらかじめ、受信者と送信者は密かに共通鍵 c の受け渡しをしておく。
- 送信者は c を使ってメッセージを暗号化し、受信者に送信する。
- 受信者は c を使って暗号文を復号し、メッセージを読む。
もし段階 1. で、送信者に対してセキュリティが保証されていない通信路を用いて鍵を配送した場合、第三者に共通鍵 c を傍受されていると、この暗号通信は容易に解読されてしまう。
公開鍵暗号の考案
共通鍵暗号に生じる鍵配送問題は、送信者と受信者の両者がただ1つの共通の鍵を用いるために起こる問題である。そこで、両者が異なる鍵を用いる方法、すなわち公開鍵暗号が考案された。
公開鍵暗号を用いた通信手順の概略：
- 通信を受ける者（受信者）は自分の公開鍵（暗号化のための鍵）p を全世界に公開する。
- 受信者に対して暗号通信をする者（送信者）は、公開鍵 p を使ってメッセージを暗号化してから送信する。
- 受信者は、公開鍵 p と対になる秘密鍵（復号のための鍵）s を密かにもっている。この s を使って受信内容を復号し、送信者からのメッセージを読む。
暗号通信を不正に傍受しようとする者（傍受者）が公開鍵暗号の方式によって暗号化されたメッセージを傍受したとしても、公開鍵 p から秘密鍵 s を導き出すことは、計算時間の観点から極めて難しいため、暗号文を復号することはおよそできない。
暗号化のための鍵と復号のための鍵を異なるものにしたことで、鍵配送問題は解決された。
なお、暗号の用語については、暗号理論の用語、暗号の用語を参照。
公開鍵暗号方式の直観的な定義
モデル
公開鍵暗号方式では、鍵生成アルゴリズム、暗号化アルゴリズム、復号アルゴリズムを用いる。
鍵生成アルゴリズムは事前準備のためのアルゴリズムであり、（将来暗号文を受け取りたい）ユーザは事前に鍵生成アルゴリズムを実行しておく必要がある。ユーザが鍵生成アルゴリズムを実行すると、アルゴリズムはそのユーザの公開鍵および秘密鍵（それぞれ、そのように呼ばれるデータ）を出力する。公開鍵は暗号文を作成するのに使い、秘密鍵はその暗号文からメッセージを復元するのに使う。
ユーザは鍵生成アルゴリズムを実行する際、セキュリティ・パラメータという値をこのアルゴリズムに入力する。セキュリティ・パラメータは、秘密鍵なしでの暗号文の解読がどれだけ困難かを示す尺度である。
鍵生成アルゴリズムには乱数も入力される。鍵生成アルゴリズムは実行ごとに異なる乱数を選ぶので、ユーザ毎に異なる公開鍵・秘密鍵ペアが割りふられる。
各ユーザは秘密鍵を密かに保管し、公開鍵を公開する。ユーザの秘密鍵を知っているのはそのユーザ自身だけであり、ユーザの公開鍵を知っている(知ることができる)のは全てのユーザである。
メッセージを秘匿する暗号通信をするときの公開鍵、秘密鍵を、それぞれ暗号化鍵、復号鍵ともいう。
暗号文を送る際は、送りたいメッセージおよびそのメッセージの送信先（受信者）の公開鍵を入力として暗号化アルゴリズムを実行する。 受信者は復号アルゴリズムに自分の秘密鍵と暗号文を入力して、もとのメッセージを復元する。 公開鍵を使えば誰でも暗号文を作成できるが、その暗号文を正しく復号できるのは受信者本人だけである。
公開鍵の認証
安全性を確保するには、どの公開鍵がどのユーザのものであるのかという対応をきちんとつけておく必要がある。暗号化に受信者の公開鍵 p を用いているので、もし、公開鍵 p とユーザとの対応が誤っていると、誤ったユーザの公開鍵を使って暗号文を送信してしまうことになる。これを悪用して、前もってあえて誤った対応表を作成しておくことによって暗号文を解くという攻撃が可能である（攻撃者は攻撃者自身の公開鍵をあたかも対象の受信者の公開鍵であるかのように見せた偽の対応表を作る。攻撃者の公開鍵を用いて暗号化された暗号文が対象の受信者へ送られたら、攻撃者はその暗号文を傍受して自身の秘密鍵で復号する。）。
公開鍵とその持ち主を対応させる方法はいくつか考案されている。代表的な方法は次の2つである。どちらも、信頼できる第三者機関（Trusted Third Party、TTP）が必要になる。
- 信頼できる第三者機関が各人のIDと公開鍵を対応付けた表（公開鍵簿）を作成して公開する。
- 信頼できる複数の第三者機関が認証局を運営し、公開鍵基盤 (PKI) の仕組みを使って各人のIDと公開鍵とを対応付ける。
歴史
1960年代、イギリスの政府通信本部 (GCHQ) に所属するジェイムズ・エリスが公開鍵暗号（非秘密暗号）を考案し提案は受諾された。しかし理論的には有用性が認められたが、一方向性関数が見つけられずこのアイデアは実用化されなかった。1973年、同機関に入所したクリフォード・コックスがこのアイデアに取り組み「作用は可能だが、逆転させられない関数」から素数と素因数分解を基に30分程度で数式を組み立て、さらにマルコム・ウィリアムソンが鍵配送問題に解決の糸口を見つけ、今日の"RSA"と呼ばれる暗号システムの基礎を確立した。同時期に、彼らとは無関係な米国のアマチュア数学者、ウィットフィールド・デフィーが独学で公開鍵暗号開発に取り組んでいた。1976年に、ラルフ・マークルの研究の影響を受けたデフィーとマーティン・ヘルマンが公開鍵暗号に関する世界最初の論文「New Directions in Cryptography[1]」を発表した。
公開鍵暗号という新規な発明は、本来、エリス＝コックス＝ウィリアムソン組が先であったが、論文にして公表し、その有用性を広く伝えたのは、デフィー＝ヘルマン＝マークル組となったため、本発明の特許権と栄誉は彼らが得た。先に考案していたエリス＝コックス＝ウィリアムソン組は、英軍の管理下であったGCHQが国家機密となっていたために、後発組が公開鍵暗号の論文を発表しても、契約により口外できなかった。後年、公開鍵暗号が広く普及したことで本暗号に関する機密扱いが解除され、エリス＝コックス＝ウィリアムソン組の功績が世に知られることになった[2]。デフィーの「先に開発していたのは本当ですか？」との問いに、エリスは「我々より、君達の方がより多くの事をやっている」と答えている。
公開鍵暗号の概念を実現する具体的な方式は、MITの研究者であったロナルド・リベスト、アディ・シャミア、レオナルド・エーデルマンの3人が1977年に開発した。この方式は、開発者各人の頭文字を取って「RSA方式」と呼ばれるようになった。1982年、彼らはカリフォリニア州レッドウッド市にデータセキュリティ専門の会社「RSAデータセキュリティ社」を設立した[3]。
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をセキュリティ・パラメータとする。
カテゴリ
- Public Key Cryptographyのページへのリンク
