公開鍵暗号

公開鍵暗号（こうかいかぎあんごう、Public-key cryptography）とは、暗号化と復号に別個の鍵（手順）を用い、暗号化の鍵を公開すらできるようにした暗号方式である。 暗号は通信の秘匿性を高めるための手段だが、それに必須の鍵もまた情報なので、鍵を受け渡す過程で盗聴されてしまうというリスクがあった。共通鍵を秘匿して受け渡すには（特使が運搬するというような）コストもかかり、一般人が暗号を用いるための障害であった。この問題に対して、暗号化鍵の配送問題を解決したのが公開鍵暗号である。 1960年代、イギリスの政府通信本部 (GCHQ) に所属するジェイムズ・エリス（英語版）が公開鍵暗号（非秘密暗号）を考案し提案は受諾された。しかし理論的には有用性が認められたが、一方向関数が見つけられずこのアイデアは実用化されなかった。1973年、同機関に入所したクリフォード・コックス（英語版）がこのアイデアに取り組み「作用は可能だが、逆転させられない関数」から素数と素因数分解を基に30分程度で数式を組み立て、さらにマルコム・ウィリアムソン（英語版）が鍵配送問題に解決の糸口を見つけ、今日の"RSA"と呼ばれる暗号システムの基礎を確立した。同時期に、彼らとは無関係な米国のアマチュア数学者、ウィットフィールド・デフィーが独学で公開鍵暗号開発に取り組んでいた。1976年に、ラルフ・マークルの研究の影響を受けたウィットフィールド・デフィーとマーティン・ヘルマンが公開鍵暗号に関する世界最初の論文を発表した。 公開鍵暗号という新規な発明は、本来、エリス＝コックス＝ウィリアムソン組が先であったが、論文にして公表し、その有用性を広く伝えたのは、デフィー＝ヘルマン＝マークル組となったため、本発明の特許権と栄誉は彼らが得た。先に考案していたエリス＝コックス＝ウィリアムソン組は、英軍の管理下であったGCHQが国家機密となっていたために、後発組が公開鍵暗号の論文を発表しても、契約により口外できなかった。後年、公開鍵暗号が広く普及したことで本暗号に関する機密扱いが解除され、エリス＝コックス＝ウィリアムソン組の功績が世に知られることになった。デフィーの「先に開発していたのは本当ですか？」との問いに、エリスは「我々より、君達の方がより多くの事をやっている」と答えている。 公開鍵暗号の概念を実現する具体的な方式は、MITの研究者であったロナルド・リヴェリスト、アディ・シャミル、レオナルド・アデルマンの3人が1977年に開発した。この方式は、開発者各人の頭文字を取って「RSA方式」と呼ばれるようになった。1982年、彼らはカリフォリニア州レッドウッド市にデータセキュリティ専門の会社「RSAデータセキュリティ社」を設立した。 1990年代初頭、フィル・ジマーマンがパーソナル・コンピュータに搭載可能な"PGP"(Pretty Good Privacy)を開発し公開した。このプログラム"PGP"が全世界に普及したことで、誰でも公開鍵暗号が使用できるようになった。 公開鍵暗号は、1980年ごろには「公衆暗号 (public cryptography)」とも呼ばれていた。用語「公衆暗号系 (public cryptosystem)」も使われていたが、DES のような公衆が用いる共通鍵暗号を含むかどうかが紛らわしかったので、これらの用語はすぐに使われなくなった。 1976年以前には、暗号といえば共通鍵暗号であった。これは、暗号化と復号に同じ（共通の）鍵を使うものである。共通鍵暗号には、鍵の配送を極秘に行わねばならないという課題（鍵配送問題）があった。 共通鍵暗号を用いた通信手順の概略 受信者は あらかじめ送信者に対して密かに共通鍵 C を渡しておく。（両者が逆でも良い） 送信者は C を使ってメッセージを暗号化し、受信者に向かって送信する。 受信者は C を使って暗号文を復号し、メッセージを読む。 1の過程で、送信者に対してセキュリティの保証されていない通信路を使って鍵を配送すると、傍受者に共通鍵 C を傍受されてしまった場合には、この暗号通信は容易に解読されてしまい意味を持たないことになる。共通鍵暗号方式では鍵の取り扱いが難しい。 共通鍵暗号に生じる鍵配送問題は、送信者と受信者の両者がただ1つ共通の鍵を用いるために起きる問題である。そのため両者が異なる鍵を用いる方法、すなわち公開鍵暗号が考案された。このことが鍵の配送問題を解決した。つまり : 通信を受ける者（受信者）は自分の公開鍵（暗号化のための鍵）P を全世界に公開する。 受信者に対して暗号通信をしたい者（送信者）は、公開鍵 P を使ってメッセージを暗号化してから送信する。 受信者は、公開鍵 P と対になる秘密鍵（復号のための鍵）S を密かに持っている。この S を使って受信内容を復号し、送信者からのメッセージを読む。 暗号通信を不正に傍受しようとする者（傍受者）が、送信者が送信した暗号化されたメッセージを傍受したとする。傍受者は、公開鍵 P は知っているが、秘密鍵 S は受信者だけが知っている情報であるので分からない。P から S を割り出すことは（計算時間の点から）極めて難しい。そのため、暗号文を復号することはおよそできない。 暗号化のための鍵と、復号のための鍵を別の（非対称の）ものにすることによって、鍵の配送の問題を解決したのである。 暗号の用語については、暗号理論の用語、暗号の用語を参照。 公開鍵暗号方式には、鍵生成アルゴリズム、暗号化アルゴリズム、復号アルゴリズムの3つのアルゴリズムがある。 鍵生成アルゴリズムは事前準備にあたるアルゴリズムで、（将来暗号文を受け取りたいと思う）全てのユーザは事前に鍵生成アルゴリズムを実行しておく必要がある。ユーザが鍵生成アルゴリズムを実行すると、アルゴリズムはそのユーザの公開鍵および秘密鍵（と呼ばれるデータ）を出力する。公開鍵は暗号文を作成するのに使い、秘密鍵はその暗号文からメッセージを復元するのに使う。 ユーザは鍵生成アルゴリズムを実行する際、セキュリティ・パラメータという値をこのアルゴリズムに入力する。セキュリティ・パラメータは、秘密鍵なしで暗号文の解読がどれだけ困難かの尺度である。 さらに鍵生成アルゴリズムには乱数も入力される。鍵生成アルゴリズムは実行ごとに異なる乱数を選ぶので、ユーザ毎に異なる公開鍵・秘密鍵ペアが割りふられる。 各ユーザは秘密鍵を秘密裏に保管し、公開鍵を皆に公開する。よってユーザの秘密鍵を知っているのはそのユーザ自身だけであるが、それに対しユーザの公開鍵を知っているのは全てのユーザである。 公開鍵、秘密鍵をそれぞれ暗号化鍵、復号鍵ともいう。 暗号文を送るには、送りたいメッセージと、そのメッセージの送信先（受信者）の公開鍵を、入力として暗号化アルゴリズムを実行する（公開鍵は公開情報なので、暗号文の送信者は受信者の公開鍵を手に入れる事ができる）。 それに対し、受信者は復号アルゴリズムに自分の秘密鍵と暗号文を入力して、もとのメッセージを復元する。 復号アルゴリズムでもとのメッセージを復元することを、復号（ふくごう、decryption）と呼ぶ。それに対し、悪意のあるユーザ（攻撃者）が、復号アルゴリズムに（必ずしも）頼らず無理矢理メッセージを復元しようとする試みを解読 (cryptanalysis) と呼ぶ。 公開鍵は公開情報であり、それに対応する秘密鍵は受信者本人しか知らない。よって公開されている公開鍵を使えば誰でも暗号文を作成できるが、それに対しその暗号文を復号できるのは受信者本人のみである。 安全性を確保するには、どの公開鍵がどのユーザのものであるのかという対応をきちんとつけておく必要がある。暗号化の際、受信者の公開鍵を用いていた事を思い出されたい。もし、公開鍵とユーザとの対応が間違っていると、間違ったユーザの公開鍵を使って暗号文を送信してしまう。これを悪用して、前もってあえて間違った対応表を作成することで暗号文を解くという攻撃が可能である（攻撃者はまず、自分の公開鍵をあたかも受信者の公開鍵であるかのように対応表を作る。受信者に当てて暗号文が送られたら、攻撃者はその暗号文を盗聴し、自身の秘密鍵で復号する）。 公開鍵とその持ち主を対応させる方法はいくつか考案されているが、代表的な方法は以下の2つである。 信頼できる第三者機関 (Trusted Third party) が各人のIDと公開鍵を対応付けた表（公開鍵簿）を作成し、公開する。 信頼できる第三者機関（達）が認証局を運営し、PKIの仕組みを使って各人のIDと公開鍵を対応付ける。 公開鍵暗号方式は以下の要件を満たさねばならない。 正当性 (Correctness) : 正当な受信者は、正当な方法で作成された暗号文を復号できる。 秘匿性 (Security) : 正当な方法で作成された暗号文を復号できる（もしくはメッセージのなんらかの部分情報を得られる）のは、正当な受信者のみである。 kをセキュリティ・パラメータとする。 Π = ( G , E , D ) {\displaystyle \Pi =(G,E,D)} を、次を満たす平均多項式時間確率アルゴリズム3つ組とする。 G {\displaystyle G} は鍵生成アルゴリズム (key generation algorithm) と呼ばれ、 1 k {\displaystyle 1^{k}} を入力されると公開鍵秘密鍵ペア ( p k , s k ) {\displaystyle (\mathrm {pk} ,\mathrm {sk} )} を出力する。 E {\displaystyle E} は暗号化アルゴリズム (encryption algorithm) と呼ばれ、 G {\displaystyle G} の出力した公開鍵 p k {\displaystyle \mathrm {pk} } と平文と呼ばれるビット列 m {\displaystyle m} を入力されると、 m {\displaystyle m} の暗号文(Ciphertext) を出力する。 D {\displaystyle D} は復号アルゴリズム (decryption algorithm) と呼ばれ、 G {\displaystyle G} の出力した秘密鍵 s k {\displaystyle \mathrm {sk} } と E {\displaystyle E} の出力した暗号文 C {\displaystyle C} とを入力されると平文を出力する。 Π = ( G , E , D ) {\displaystyle \Pi =(G,E,D)} が後述する正当性を満たすとき、 Π {\displaystyle \Pi } は公開鍵暗号方式であるといい、後述する秘匿性をさらに満たすとき、公開鍵暗号方式は安全であるという。 公開鍵暗号方式は2つの要件、正当性と秘匿性とを満たさねばならない。 定義 Π = ( G , E , D ) {\displaystyle \Pi =(G,E,D)} が以下の条件を満たすとき、 Π {\displaystyle \Pi } は正当性を満たすという : 任意の平文 m に対し、Pr((pk, sk) ← G(1k), C ← Epk(m) : Dsk(C) = m) は圧倒的 (overwhelming) である。 M 0 {\displaystyle M_{0}} 、 M 1 {\displaystyle M_{1}} を攻撃者が指定した2つのメッセージとし、 C {\displaystyle C} を M 0 {\displaystyle M_{0}} もしくは M 1 {\displaystyle M_{1}} を暗号化した暗号文とする。 このとき、攻撃者は C {\displaystyle C} が M 0 {\displaystyle M_{0}} 、 M 1 {\displaystyle M_{1}} のいずれを暗号化したものであるかを（1/2よりも有意な確率で）知る事はできない。 O 1 {\displaystyle O_{1}} , O 2 {\displaystyle O_{2}} を2つのオラクル、 b {\displaystyle b} をビットとする。 暗号に対する攻撃者 A {\displaystyle A} を用いて次の実験 (Experiment, ゲーム (game) ともいう) をする。 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)|} により定義する。 定義 任意の平均多項式時間確率アルゴリズム A {\displaystyle A} (攻撃者と呼ぶ) に対し、 A d v Π ( O 1 , O 2 ) ( A , k ) {\displaystyle {\mathsf {Adv}}_{\Pi }^{(O_{1},O_{2})}(A,k)} が k に関して無視できるとき、暗号方式 Π {\displaystyle \Pi } は ( O 1 , O 2 ) {\displaystyle (O_{1},O_{2})} -識別不可能 (indistinguishable) であるという。 （注：この「 ( O 1 , O 2 ) {\displaystyle (O_{1},O_{2})} -識別不可能」という言葉はあまり一般的ではない） 特に、 O 1 = ⊥ {\displaystyle O_{1}=\bot } 、 O 2 = ⊥ {\displaystyle O_{2}=\bot } のとき、公開鍵暗号方式 Π {\displaystyle \Pi } はKey Only Attackに対し、識別不可能であるという。 O 1 = O d e c ( s k , ∅ , ⋅ ) {\displaystyle O_{1}=O_{\mathsf {dec}}({\mathsf {sk}},\emptyset ,\cdot )} 、 O 2 = ⊥ {\displaystyle O_{2}=\bot } であるとき、公開鍵暗号方式 Π {\displaystyle \Pi } は選択暗号文攻撃 (Chosen Chiphertext Attack,(略してCCA1)) に対して識別不可能であるという。 O 1 = O d e c ( s k , ∅ , ⋅ ) {\displaystyle O_{1}=O_{\mathsf {dec}}({\mathsf {sk}},\emptyset ,\cdot )} 、 O 2 = O d e c ( s k , { m 0 , m 1 } , ⋅ ) {\displaystyle O_{2}=O_{\mathsf {dec}}({\mathsf {sk}},\{m_{0},m_{1}\},\cdot )} であるとき、公開鍵暗号方式 Π {\displaystyle \Pi } は適応的選択暗号文攻撃（Adaptive Chosen Chiphertext Attack,（略してCCA2））に対して識別不可能であるという。 ただしここで O d e c {\displaystyle O_{\mathsf {dec}}} は次の節で述べる復号オラクルである。 公開鍵暗号方式の場合暗号化用の鍵が公開されているので、攻撃者は（オラクルの助けを借りずとも）任意の平文を暗号化する事ができる。このため、Key Only Attackの事を選択平文攻撃（Chosen Plaintest Attack, CPAと略す）ともいう。 復号オラクル O d e c ( s k , X , ⋅ ) {\displaystyle O_{\mathsf {dec}}({\mathsf {sk}},X,\cdot )} は、攻撃者が任意の暗号文 C {\displaystyle C} を復号オラクル O d e c ( s k , X , ⋅ ) {\displaystyle O_{\mathsf {dec}}({\mathsf {sk}},X,\cdot )} に送信すると、 C ∉ X {\displaystyle C\notin X} である限り、 s k {\displaystyle {\mathsf {sk}}} を使って C {\displaystyle C} を復号した D s k ( C ) {\displaystyle D_{\mathsf {sk}}(C)} を攻撃者に送り返してくれるオラクルである。（下図参照） 復号オラクル O d e c ( s k , X , C ) {\displaystyle O_{\mathsf {dec}}({\mathsf {sk}},X,C)} If C ∈ X {\displaystyle C\in X} return ⊥ {\displaystyle \bot } . Otherwise return D s k ( C ) {\displaystyle D_{\mathsf {sk}}(C)} . 暗号文を知っていることは、平文を知る上で何の役にもたたない。すなわち、暗号文を知っている状況で攻撃者が知ることができる平文についての部分情報は、暗号文を知らなくても攻撃者が知ることができる情報のみである。 k {\displaystyle k} をセキュリティ・パラメータとし、 Π = ( G , E , D ) {\displaystyle \Pi =(G,E,D)} を公開鍵暗号方式とする。 A , B {\displaystyle A,B} を多項式時間機械とする。 さらに、 O 1 , O 2 {\displaystyle O_{1},O_{2}} をオラクルとする。 次の2つのゲームを考える。ただしゲーム中で、 M , f {\displaystyle M,f} は多項式時間機械（の動作を記したプログラム）、 S t {\displaystyle St} はビット列で、 A {\displaystyle A} の状態と呼ばれる。 E x p Π − S S − R e a l ( O 1 , O 2 ) ( A , k ) {\displaystyle {\mathsf {Exp}}_{\Pi -{\mathsf {SS-Real}}}^{(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 ← M {\displaystyle m\gets M} C ← E p k ( m ) {\displaystyle C\gets E_{\mathsf {pk}}(m)} ( y , f ) ← A O 2 ( C , S t ) {\displaystyle (y,f)\gets A^{O_{2}}(C,{\mathsf {St}})} If y = f ( m ) {\displaystyle y=f(m)} , return 1. Otherwise return 0. E x p Π − S S − I d e a l ( O 1 , O 2 ) ( B , k ) {\displaystyle {\mathsf {Exp}}_{\Pi -{\mathsf {SS-Ideal}}}^{(O_{1},O_{2})}(B,k)} ( p k , s k ) ← G ( 1 k ) {\displaystyle {\mathsf {(pk,sk)}}\gets G(1^{k})} ( M , S t ) ← B O 1 ( p k ) {\displaystyle (M,{\mathsf {St}})\gets B^{O_{1}}({\mathsf {pk}})} m ← M {\displaystyle m\gets M} ( y , f ) ← B O 2 ( S t ) {\displaystyle (y,f)\gets B^{O_{2}}({\mathsf {St}})} If y = f ( m ) {\displaystyle y=f(m)} , return 1. Otherwise return 0. 任意の多項式時間機械 A {\displaystyle A} に対し、ある多項式時間機械 B {\displaystyle B} が存在し、 | Pr ( E x p Π − S S − R e a l ( O 1 , O 2 ) ( A , k ) = 1 ) − Pr ( E x p Π − S S − I d e a l ( O 1 , O 2 ) ( B , k ) ) | {\displaystyle |\Pr({\mathsf {Exp}}_{\Pi -{\mathsf {SS-Real}}}^{(O_{1},O_{2})}(A,k)=1)-\Pr({\mathsf {Exp}}_{\Pi -{\mathsf {SS-Ideal}}}^{(O_{1},O_{2})}(B,k))|} が k に関して無視できるとき、公開鍵暗号方式 Π = ( G , E , D ) {\displaystyle \Pi =(G,E,D)} は ( O 1 , O 2 ) {\displaystyle (O_{1},O_{2})} -強秘匿 (Semantic Secure) であるという。 O 1 = ⊥ {\displaystyle O_{1}=\bot } 、 O 2 = ⊥ {\displaystyle O_{2}=\bot } のとき、公開鍵暗号方式 Π {\displaystyle \Pi } はKey Only Attackに対し、強秘匿であるという。 O 1 = O d e c ( s k , ∅ , ⋅ ) {\displaystyle O_{1}=O_{\mathsf {dec}}({\mathsf {sk}},\emptyset ,\cdot )} 、 O 2 = ⊥ {\displaystyle O_{2}=\bot } であるとき、公開鍵暗号方式 Π {\displaystyle \Pi } は選択暗号文攻撃（Chosen Chiphertext Attack,（略してCCA1）） に対して強秘匿であるという。 O 1 = O d e c ( s k , ∅ , ⋅ ) {\displaystyle O_{1}=O_{\mathsf {dec}}({\mathsf {sk}},\emptyset ,\cdot )} 、 O 2 = O d e c ( s k , { m 0 , m 1 } , ⋅ ) {\displaystyle O_{2}=O_{\mathsf {dec}}({\mathsf {sk}},\{m_{0},m_{1}\},\cdot )} であるとき、公開鍵暗号方式 Π {\displaystyle \Pi } は適応的選択暗号文攻撃（Adaptive Chosen Chiphertext Attack,（略してCCA2））に対して強秘匿であるという。 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. If m i ′ = ⊥ {\displaystyle m'_{i}=\bot } for some i {\displaystyle i} , return 0. If R ( m b , m 1 ′ , … , m n ′ ) = 0 {\displaystyle R(m_{b},m'_{1},\ldots ,m'_{n})=0} return 0. Return 1. ただし、上のゲームで、 M {\displaystyle M} は、常に同じビット数のメッセージを出力するアルゴリズムでなければならない。 任意の多項式時間機械 A {\displaystyle A} に対し、 | Pr ( E x p Π − N M − 1 ( O 1 , O 2 ) ( A , k ) = 1 ) − Pr ( E x p Π − N M − 0 ( O 1 , O 2 ) ( A , k ) = 1 ) | {\displaystyle |\Pr({\mathsf {Exp}}_{\Pi -{\mathsf {NM}}-1}^{(O_{1},O_{2})}(A,k)=1)-\Pr({\mathsf {Exp}}_{\Pi -{\mathsf {NM}}-0}^{(O_{1},O_{2})}(A,k)=1)|} が k に関して無視できるとき、公開鍵暗号方式 Π = ( G , E , D ) {\displaystyle \Pi =(G,E,D)} は ( O 1 , O 2 ) {\displaystyle (O_{1},O_{2})} -non malleableであるという。 O 1 = ⊥ {\displaystyle O_{1}=\bot } 、 O 2 = ⊥ {\displaystyle O_{2}=\bot } のとき、公開鍵暗号方式 Π {\displaystyle \Pi } はKey Only Attackに対し、頑強である (non malleable) という。 O 1 = O d e c ( s k , ∅ , ⋅ ) {\displaystyle O_{1}=O_{\mathsf {dec}}({\mathsf {sk}},\emptyset ,\cdot )} 、 O 2 = ⊥ {\displaystyle O_{2}=\bot } であるとき、公開鍵暗号方式 Π {\displaystyle \Pi } は選択暗号文攻撃（Chosen Chiphertext Attack,（略してCCA1））に対して頑強であるという。 O 1 = O d e c ( s k , ∅ , ⋅ ) {\displaystyle O_{1}=O_{\mathsf {dec}}({\mathsf {sk}},\emptyset ,\cdot )} 、 O 2 = O d e c ( s k , { m 0 , m 1 } , ⋅ ) {\displaystyle O_{2}=O_{\mathsf {dec}}({\mathsf {sk}},\{m_{0},m_{1}\},\cdot )} であるとき、公開鍵暗号方式 Π {\displaystyle \Pi } は適応的選択暗号文攻撃（Adaptive Chosen Chiphertext Attack,（略してCCA2））に対して頑強であるという。 公開鍵暗号にはさまざまな方式がある。ここでは典型的な公開鍵暗号方式である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暗号は公開鍵暗号として、実際に広く利用されることとなった。 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 秘匿通信 電子署名 素因数分解 エニグマ 非秘密暗号は開発以前にGCHQによるエニグマ解読チームが組まれた事にあった、チームの内訳は数学、統計、物理学者らの他にクロスワードパズルを得意としている者らからなり、総当たりで解読を行った。 暗号関連 暗号理論 暗号 ディフィー・ヘルマン鍵共有 RSA暗号 ElGamal暗号 楕円曲線暗号 Merkle-Hellmanナップサック暗号 - ラルフ・マークル - マークルのパズル NTRU暗号 ^ 井上孝司著、「通信と情報の保全 暗号化の話」『軍事研究2011年11月号』、（株）ジャパン・ミリタリー・レビュー、雑誌 03241-11、ISSN 0533-6716、227-228頁 ^ Press Releases Archived 2011年9月29日, at the Wayback Machine. - RSA社サイト（英語、2012年2月19日閲覧）