公開鍵暗号

出典: Wikipedio

公開鍵暗号（こうかいかぎあんごう、Public key cryptosystem）とは、暗号化と復号に別個の鍵（手順）を使い、暗号化の為の鍵を公開できるようにした暗号方式である。1980年代にかけ、日本で紹介された直後は「公衆暗号系」と訳されていた。

概要

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

1976年に、ウィットフィールド・デフィー (en:Whitfield Diffie)、マーティン・ヘルマン(en:Martin Hellman)によって、初めて公表された。

1976年以前には、暗号と言えば共通鍵暗号であった。これは、暗号化と復号に同じ（共通の）鍵を使うものである。

つまり、共通鍵暗号には、鍵の配送に問題があった。共通鍵暗号を用いた通信のおおまかな流れは次のようになる。

受信者は、あらかじめ送信者に対して密かに共通鍵 C を渡しておく。
送信者は C を使ってメッセージを暗号化し、受信者に向かって送信する。
受信者は、C を使って暗号文を復号し、メッセージを読む。

上の1の過程（送信者に対してセキュリティの保証されていない通信路を使って鍵を配送する過程）において、傍受者が共通鍵Cを傍受してしまっていた場合、この共通鍵を用いた送信者、受信者間の暗号通信は意味を持たないことになる。

すなわち、送信者はCを用いて、メッセージを暗号化するが、このメッセージを傍受した傍受者は、入手していたCによって暗号文を復号し、メッセージを読むことができる。

これは、共通鍵暗号方式が、暗号化と復号に共通の鍵を用いることにより発生してくる問題である。

これに対して公開鍵暗号は、鍵の配送（暗号化鍵をどのようにして送信者に手渡すか）が容易になる。つまり :

通信を受ける者（受信者）は自分の公開鍵（暗号化のための鍵）P を全世界に公開する。
受信者に対して暗号通信をしたい者（送信者）は、公開鍵 P を使ってメッセージを暗号化してから送信する。
受信者は、公開鍵 P と対になる秘密鍵（復号のための鍵）S を密かに持っている。この S を使って受信内容を復号し、送信者からのメッセージを読む。
暗号通信を不正に傍受しようとする者（傍受者）が、送信者が送信した暗号化されたメッセージを傍受したとする。傍受者は、公開鍵 P は知っているが、秘密鍵 S は受信者だけが知っている情報であるので分からない。P から S を割り出すことは（計算時間的に）極めて難しい。そのため、暗号文を復号することはおよそできない。

暗号化のための鍵と、復号のための鍵を別の（非対称の）ものにすることによって、鍵の配送の問題を解決したのである。

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

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

モデル

公開鍵暗号方式には、鍵生成アルゴリズム、暗号化アルゴリズム、復号アルゴリズムの3つのアルゴリズムがある。

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

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

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

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

公開鍵、秘密鍵をそれぞれ暗号化鍵、復号鍵ともいう。

暗号文を送るには、送りたいメッセージと暗号文を送りたい相手（受信者）の公開鍵とを入力して暗号化アルゴリズムを実行する（公開鍵は公開情報なので、暗号文の送信者は受信者の公開鍵を手に入れる事ができる）。

それに対し、受信者は復号アルゴリズムに自分の秘密鍵と暗号文を入力して、もとのメッセージを復元する。

復号アルゴリズムでもとのメッセージを復元することを、復号（ふくごう、decryption）と呼ぶ。それに対し、悪意のあるユーザ（攻撃者）が、復号アルゴリズムに（必ずしも）頼らず無理矢理メッセージを復元しようとする試みを攻撃 (attack) と呼ぶ。

公開鍵は公開情報であり、それに対応する秘密鍵は受信者本人しか知らない。よって公開されている公開鍵を使えば誰でも暗号文を作成できるが、それに対しその暗号文を復号できるのは受信者本人のみである。

公開鍵の認証

安全性を確保するには、どの公開鍵がどのユーザのものであるのかという対応をきちんとつけておく必要がある。暗号化の際、受信者の公開鍵を用いていた事を思い出されたい。もし、公開鍵とユーザとの対応が間違っていると、間違ったユーザの公開鍵を使って暗号文を送信してしまう。これを悪用して、前もってあえて間違った対応表を作成することで暗号文を解くという攻撃が可能である（攻撃者はまず、自分の公開鍵をあたかも受信者の公開鍵であるかのように対応表を作る。受信者に当てて暗号文が送られたら、攻撃者はその暗号文を盗聴し、自身の秘密鍵で復号する）。

公開鍵とその持ち主を対応させる方法はいくつか考案されているが、代表的な方法は以下の2つである。

信頼できる第3者機関 (Trusted Third party) が各人のIDと公開鍵を対応付けた表（公開鍵簿）を作成し、公開する。
信頼できる第3者機関（達）が認証局を運営し、PKIの仕組みを使って各人のIDと公開鍵を対応付ける。

要件

公開鍵暗号方式は以下の要件を満たさねばならない。

正当性 (Correctness) : 正当な受信者は、正当な方法で作成された暗号文を復号できる。
秘匿性 (Security) : 正当な方法で作成された暗号文を復号できる（もしくはメッセージのなんらかの部分情報を得られる）のは、正当な受信者のみである。

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

モデル

kをセキュリティ・パラメータとする。<math>\Pi=(G,E,D)</math> を、次を満たす平均多項式時間確率アルゴリズム3つ組とする。

<math>G</math> は鍵生成アルゴリズム (key generation algorithm) と呼ばれ、<math>1^k</math> を入力されると公開鍵秘密鍵ペア <math>(\mathrm{pk},\mathrm{sk})</math> を出力する。
<math>E</math >は暗号化アルゴリズム (encryption algorithm) と呼ばれ、<math>G</math> の出力した公開鍵 <math>\mathrm{pk}</math> と平文と呼ばれるビット列 <math>m</math> を入力されると、<math>m</math> の暗号文(Ciphertext) を出力する。
<math>D</math> は復号アルゴリズム (decryption algorithm) と呼ばれ、<math>G</math> の出力した秘密鍵 <math>\mathrm{sk}</math> と <math>E</math> の出力した暗号文 <math>C</math> とを入力されると平文を出力する。

<math>\Pi=(G,E,D)</math> が後述する正当性を満たすとき、<math>\Pi</math> は公開鍵暗号方式であるといい、後述する秘匿性をさらに満たすとき、公開鍵暗号方式は安全であるという。

要件

公開鍵暗号方式は二つの要件、正当性と秘匿性とを満たさねばならない。

正当性

定義: <math>\Pi=(G,E,D)</math> が以下の条件を満たすとき、<math>\Pi</math> は正当性を満たすという :; 任意の平文 m に対し、Pr((pk, sk) ← G(1^k), C ← E_pk(m) : D_sk(C) = m) は圧倒的 (overwhelming) である。

秘匿性

識別不可能性

直観的な定義

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

このとき、攻撃者は <math>C</math> が <math>M_0</math>、<math>M_1</math> のいずれを暗号化したものであるかを（1/2よりも有意な確率で）知る事はできない。

厳密な定義

<math>O_1</math>, <math>O_2</math> を2つのオラクル、<math>b</math> をビットとする。

暗号に対する攻撃者 <math>A</math> を用いて次の実験 (Experiment, ゲーム (game) ともいう) をする。

<math>\mathsf{Exp}^{(O_1,O_2)}_{\Pi-\mathsf{IND}-b}(A,k)</math>

<math>\mathsf{(pk,sk)}\gets G(1^k)</math>

<math>(m_0,m_1,\mathsf{St}) \gets A^{O_1}(\mathsf{pk})</math>

<math>C\gets E_{\mathsf{pk}}(m_b)</math>

<math>b' \gets A^{O_2}(\mathsf{pk},C,\mathsf{St})</math>

Return <math>b'</math>.

攻撃者 <math>A</math> のアドバンテージ(advantage)を :<math>\mathsf{Adv}^{(O_1,O_2)}_{\Pi-\mathsf{IND}}(A,k)=|\mathsf{Pk}(\mathsf{Exp}{}^{(O_1,O_2)}_{\Pi-\mathsf{IND}-0}(A,k)=1)-\mathsf{Pk}(\mathsf{Exp}{}^{(O_1,O_2)}_{\Pi-\mathsf{IND}-1}(A,k)=1)|</math> により定義する。

定義

任意の平均多項式時間確率アルゴリズム <math>A</math> (攻撃者と呼ぶ) に対し、

<math>\mathsf{Adv}^{(O_1,O_2)}_{\Pi}(A,k)</math> が k に関して無視できるとき、暗号方式 <math>\Pi</math> は <math>(O_1,O_2)</math>-識別不可能 (indistinguishable) であるという。

（注：この「<math>(O_1,O_2)</math>-識別不可能」という言葉はあまり一般的ではない）

特に、

<math>O_1=\bot</math>、<math>O_2=\bot</math> のとき、公開鍵暗号方式 <math>\Pi</math> はKey Only Attackに対し、識別不可能であるという。
<math>O_1=O_{\mathsf{dec}}(\mathsf{sk},\emptyset,\cdot)</math>、<math>O_2=\bot</math> であるとき、公開鍵暗号方式<math>\Pi</math> は選択暗号文攻撃 (Chosen Chiphertext Attack,(略してCCA1)) に対して識別不可能であるという。
<math>O_1=O_{\mathsf{dec}}(\mathsf{sk},\emptyset,\cdot)</math>、<math>O_2=O_{\mathsf{dec}}(\mathsf{sk},\{m_0,m_1\},\cdot)</math> であるとき、公開鍵暗号方式 <math>\Pi</math> は適応的選択暗号文攻撃（Adaptive Chosen Chiphertext Attack,（略してCCA2））に対して識別不可能であるという。

ただしここで <math>O_{\mathsf{dec}}</math> は次の節で述べる復号オラクルである。

公開鍵暗号方式の場合暗号化用の鍵が公開されているので、攻撃者は（オラクルの助けを借りずとも）任意の平文を暗号化する事ができる。このため、Key Only Attackの事を選択平文攻撃（Chosen Plaintest Attack, CPAと略す）ともいう。

復号オラクル

復号オラクル <math>O_{\mathsf{dec}}(\mathsf{sk},X,\cdot)</math> は、攻撃者が任意の暗号文 <math>C</math> を復号オラクル<math>O_{\mathsf{dec}}(\mathsf{sk},X,\cdot)</math> に送信すると、<math>C\notin X</math> である限り、<math>\mathsf{sk}</math> を使って <math>C</math> を復号した <math>D_{\mathsf{sk}}(C)</math> を攻撃者に送り返してくれるオラクルである。（下図参照）

復号オラクル<math>O_{\mathsf{dec}}(\mathsf{sk},X,C)</math>

If <math>C\in X</math> return <math>\bot</math>.

Otherwise return <math>D_{\mathsf{sk}}(C)</math>.

強秘匿性 (Semantic Security)

直観的定義

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

厳密な定義

<math>k</math> をセキュリティ・パラメータとし、<math>\Pi=(G,E,D)</math> を公開鍵暗号方式とする。<math>A,B</math> を多項式時間機械とする。

さらに、<math>O_1,O_2</math> をオラクルとする。

次の2つのゲームを考える。ただしゲーム中で、<math>M,f</math> は多項式時間機械（の動作を記したプログラム）、<math>St</math> はビット列で、<math>A</math> の状態と呼ばれる。

<math>\mathsf{Exp}^{(O_1,O_2)}_{\Pi-\mathsf{SS-Real}}(A,k)</math>

<math>\mathsf{(pk,sk)}\gets G(1^k)</math>

<math>(M,\mathsf{St}) \gets A^{O_1}(\mathsf{pk})</math>

<math>C \gets E_{\mathsf{pk}}(m)</math>

<math>(y,f) \gets A^{O_2}(C,\mathsf{St})</math>

If <math>y=f(m)</math>, return 1.

Otherwise return 0.

<math>\mathsf{Exp}^{(O_1,O_2)}_{\Pi-\mathsf{SS-Ideal}}(B,k)</math>

<math>\mathsf{(pk,sk)}\gets G(1^k)</math>

<math>(M,\mathsf{St}) \gets B^{O_1}(\mathsf{pk})</math>

<math>(y,f) \gets B^{O_2}(\mathsf{St})</math>

If <math>y=f(m)</math>, return 1.

Otherwise return 0.

任意の多項式時間機械 <math>A</math> に対し、ある多項式時間機械 <math>B</math> が存在し、

<math>|\Pr(\mathsf{Exp}^{(O_1,O_2)}_{\Pi-\mathsf{SS-Real}}(A,k)=1)-\Pr(\mathsf{Exp}^{(O_1,O_2)}_{\Pi-\mathsf{SS-Ideal}}(B,k))|</math>

が k に関して無視できるとき、公開鍵暗号方式 <math>\Pi=(G,E,D)</math> は <math>(O_1,O_2)</math>-強秘匿 (Semantic Secure) であるという。

<math>O_1=\bot</math>、<math>O_2=\bot</math> のとき、公開鍵暗号方式 <math>\Pi</math> はKey Only Attackに対し、強秘匿であるという。
<math>O_1=O_{\mathsf{dec}}(\mathsf{sk},\emptyset,\cdot)</math>、<math>O_2=\bot</math> であるとき、公開鍵暗号方式 <math>\Pi</math> は選択暗号文攻撃（Chosen Chiphertext Attack,（略してCCA1））に対して強秘匿であるという。
<math>O_1=O_{\mathsf{dec}}(\mathsf{sk},\emptyset,\cdot)</math>、<math>O_2=O_{\mathsf{dec}}(\mathsf{sk},\{m_0,m_1\},\cdot)</math> であるとき、公開鍵暗号方式 <math>\Pi</math> は適応的選択暗号文攻撃（Adaptive Chosen Chiphertext Attack,（略してCCA2））に対して強秘匿であるという。

頑強性 (Non Malleability) (Bellare等による定義)

<math>A</math> を攻撃者とし、以下のゲームを考える。

<math>\mathsf{Exp}^{(O_1,O_2)}_{\Pi-\mathsf{NM}-b}(A,k)</math>

<math>\mathsf{(pk,sk)}\gets G(1^k)</math>

<math>(M,\mathsf{St})\gets A^{O_1}(\mathsf{pk})</math>

<math>C \gets E_{\mathsf{pk}}(m_b)</math>

<math>(R,C'_1,\ldots,C'_n) \gets A^{O_2}(C,\mathsf{St})</math>

<math>m'_1 \gets D_{\mathsf{sk}}(C'_1),\ldots,m'_n \gets D_{\mathsf{sk}}(C'_n)</math>

If <math>C=C'_i</math> for some <math>i</math>, return 0.

If <math>m'_i=\bot</math> for some <math>i</math>, return 0.

If <math>R(m_b,m'_1,\ldots,m'_n)=0</math> return 0.

Return 1.

ただし、上のゲームで、<math>M</math> は、常に同じビット数のメッセージを出力するアルゴリズムでなければならない。

任意の多項式時間機械 <math>A</math> に対し、

<math>|\Pr(\mathsf{Exp}^{(O_1,O_2)}_{\Pi-\mathsf{NM}-1}(A,k)=1)-\Pr(\mathsf{Exp}^{(O_1,O_2)}_{\Pi-\mathsf{NM}-0}(A,k)=1)|</math>

が k に関して無視できるとき、公開鍵暗号方式 <math>\Pi=(G,E,D)</math> は <math>(O_1,O_2)</math>-non malleableであるという。

<math>O_1=\bot</math>、<math>O_2=\bot</math>のとき、公開鍵暗号方式<math>\Pi</math>はKey Only Attackに対し、頑強である (non malleable) という。
<math>O_1=O_{\mathsf{dec}}(\mathsf{sk},\emptyset,\cdot)</math>、<math>O_2=\bot</math>であるとき、公開鍵暗号方式<math>\Pi</math>は選択暗号文攻撃（Chosen Chiphertext Attack,（略してCCA1））に対して頑強であるという。
<math>O_1=O_{\mathsf{dec}}(\mathsf{sk},\emptyset,\cdot)</math>、<math>O_2=O_{\mathsf{dec}}(\mathsf{sk},\{m_0,m_1\},\cdot)</math>であるとき、公開鍵暗号方式<math>\Pi</math>は適応的選択暗号文攻撃（Adaptive Chosen Chiphertext Attack,（略してCCA2））に対して頑強であるという。

RSA暗号

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

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

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

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

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

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

実際の使われ方

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

また、公開鍵暗号はデジタル署名のために利用されることも多い。署名のような認証機能を提供できることが公開鍵暗号の最大の特長であるとも言える。

公開鍵暗号を初めて実現したのがRSA暗号であり、RSA暗号はデジタル署名が可能な方式でもある。したがって、RSA暗号は公開鍵暗号として、実際によく利用されている。

参考文献

論文

Relations among notions of security for public-key encryption schemes, M. Bellare, A. Desai, D. Pointcheval and P. Rogaway
Key-Privacy in Public-Key Encryption, Mihir Bellare, Alexandra Boldyreva, Anand Desai, David Pointcheval

公開鍵暗号

出典: Wikipedio

目次

概要

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

モデル

公開鍵の認証

要件

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

モデル

要件

正当性

秘匿性

識別不可能性

直観的な定義

厳密な定義

復号オラクル

強秘匿性 (Semantic Security)

直観的定義

厳密な定義

頑強性 (Non Malleability) (Bellare等による定義)

RSA暗号

実際の使われ方

参考文献

論文

関連項目

表示

個人用ツール

ナビゲーション

検索

ツールボックス