公開鍵暗号
公開鍵暗号方式では、鍵生成アルゴリズム、暗号化アルゴリズム、復号アルゴリズムを用いる。
鍵生成アルゴリズムは事前準備のためのアルゴリズムであり、(将来暗号文を受け取りたい)ユーザは事前に鍵生成アルゴリズムを実行しておく必要がある。ユーザが鍵生成アルゴリズムを実行すると、アルゴリズムはそのユーザの公開鍵および秘密鍵(それぞれ、そのように呼ばれるデータ)を出力する。公開鍵は暗号文を作成するのに使い、秘密鍵はその暗号文からメッセージを復元するのに使う。
ユーザは鍵生成アルゴリズムを実行する際、セキュリティ・パラメータという値をこのアルゴリズムに入力する。セキュリティ・パラメータは、秘密鍵なしでの暗号文の解読がどれだけ困難かを示す尺度である。
鍵生成アルゴリズムには乱数も入力される。鍵生成アルゴリズムは実行ごとに異なる乱数を選ぶので、ユーザ毎に異なる公開鍵・秘密鍵ペアが割りふられる。
各ユーザは秘密鍵を密かに保管し、公開鍵を公開する。ユーザの秘密鍵を知っているのはそのユーザ自身だけであり、ユーザの公開鍵を知っている(知ることができる)のは全てのユーザである。
メッセージを秘匿する暗号通信をするときの公開鍵、秘密鍵を、それぞれ暗号化鍵、復号鍵ともいう。
暗号文を送る際は、送りたいメッセージおよびそのメッセージの送信先(受信者)の公開鍵を入力として暗号化アルゴリズムを実行する。 受信者は復号アルゴリズムに自分の秘密鍵と暗号文を入力して、もとのメッセージを復元する。 公開鍵を使えば誰でも暗号文を作成できるが、その暗号文を正しく復号できるのは受信者本人だけである。
A {\displaystyle A} を攻撃者とし、以下のゲームを考える。
E x p Π − N M − b ( O 1 , O 2 ) ( A , k ) {\displaystyle {\mathsf {Exp}}_{\Pi -{\mathsf {NM}}-b}^{(O_{1},O_{2})}(A,k)} ( p k , s k ) ← G ( 1 k ) {\displaystyle {\mathsf {(pk,sk)}}\gets G(1^{k})} ( M , S t ) ← A O 1 ( p k ) {\displaystyle (M,{\mathsf {St}})\gets A^{O_{1}}({\mathsf {pk}})} m 0 , m 1 ← M {\displaystyle m_{0},m_{1}\gets M} C ← E p k ( m b ) {\displaystyle C\gets E_{\mathsf {pk}}(m_{b})} ( R , C 1 ′ , ... , C n ′ ) ← A O 2 ( C , S t ) {\displaystyle (R,C'_{1},\ldots ,C'_{n})\gets A^{O_{2}}(C,{\mathsf {St}})} m 1 ′ ← D s k ( C 1 ′ ) , ... , m n ′ ← D s k ( C n ′ ) {\displaystyle m'_{1}\gets D_{\mathsf {sk}}(C'_{1}),\ldots ,m'_{n}\gets D_{\mathsf {sk}}(C'_{n})} If C = C i ′ {\displaystyle C=C'_{i}} for some i {\displaystyle i} , return 0.
一般的に、公開鍵暗号は共通鍵暗号よりも暗号化、復号に時間がかかる。そのため、実際の運用では、データの暗号化には「その場限りの共通鍵」を使用し、その共通鍵の配送だけを公開鍵暗号で行う方式がとられることが多い。
公開鍵暗号を初めて実現したのがRSA暗号である。RSA暗号は公開鍵暗号として、実際に広く利用されることとなった。
安全性を確保するには、どの公開鍵がどのユーザのものであるのかという対応をきちんとつけておく必要がある。暗号化に受信者の公開鍵 p を用いているので、もし、公開鍵 p とユーザとの対応が誤っていると、誤ったユーザの公開鍵を使って暗号文を送信してしまうことになる。これを悪用して、前もってあえて誤った対応表を作成しておくことによって暗号文を解くという攻撃が可能である(攻撃者は攻撃者自身の公開鍵をあたかも対象の受信者の公開鍵であるかのように見せた偽の対応表を作る。攻撃者の公開鍵を用いて暗号化された暗号文が対象の受信者へ送られたら、攻撃者はその暗号文を傍受して自身の秘密鍵で復号する。)。
公開鍵とその持ち主を対応させる方法はいくつか考案されている。代表的な方法は次の2つである。どちらも、信頼できる第三者機関(英語版)(Trusted Third Party、TTP)が必要になる。
信頼できる第三者機関が各人のIDと公開鍵を対応付けた表(公開鍵簿)を作成して公開する。
信頼できる複数の第三者機関が認証局を運営し、公開鍵基盤 (PKI) の仕組みを使って各人のIDと公開鍵とを対応付ける。
E x p Π − I N D − b ( O 1 , O 2 ) ( A , k ) {\displaystyle {\mathsf {Exp}}_{\Pi -{\mathsf {IND}}-b}^{(O_{1},O_{2})}(A,k)} ( p k , s k ) ← G ( 1 k ) {\displaystyle {\mathsf {(pk,sk)}}\gets G(1^{k})} ( m 0 , m 1 , S t ) ← A O 1 ( p k ) {\displaystyle (m_{0},m_{1},{\mathsf {St}})\gets A^{O_{1}}({\mathsf {pk}})} C ← E p k ( m b ) {\displaystyle C\gets E_{\mathsf {pk}}(m_{b})} b ′ ← A O 2 ( p k , C , S t ) {\displaystyle b'\gets A^{O_{2}}({\mathsf {pk}},C,{\mathsf {St}})} Return b ′ {\displaystyle b'} .
攻撃者 A {\displaystyle A} のアドバンテージ(advantage)を : A d v Π − I N D ( O 1 , O 2 ) ( A , k ) = | P r ( E x p Π − I N D − 0 ( O 1 , O 2 ) ( A , k ) = 1 ) − P r ( E x p Π − I N D − 1 ( O 1 , O 2 ) ( A , k ) = 1 ) | {\displaystyle {\mathsf {Adv}}_{\Pi -{\mathsf {IND}}}^{(O_{1},O_{2})}(A,k)=|{\mathsf {Pr}}({\mathsf {Exp}}{}_{\Pi -{\mathsf {IND}}-0}^{(O_{1},O_{2})}(A,k)=1)-{\mathsf {Pr}}({\mathsf {Exp}}{}_{\Pi -{\mathsf {IND}}-1}^{(O_{1},O_{2})}(A,k)=1)|} により定義する。