公開鍵暗号
共通鍵暗号に生じる鍵配送問題は、送信者と受信者の両者がただ1つの共通の鍵を用いるために起こる問題である。そこで、両者が異なる鍵を用いる方法、すなわち公開鍵暗号が考案された。
公開鍵暗号を用いた通信手順の概略:
通信を受ける者(受信者)は自分の公開鍵(暗号化のための鍵)p を全世界に公開する。
受信者に対して暗号通信をする者(送信者)は、公開鍵 p を使ってメッセージを暗号化してから送信する。
受信者は、公開鍵 p と対になる秘密鍵(復号のための鍵)s を密かにもっている。この s を使って受信内容を復号し、送信者からのメッセージを読む。
暗号通信を不正に傍受しようとする者(傍受者)が公開鍵暗号の方式によって暗号化されたメッセージを傍受したとしても、公開鍵 p から秘密鍵 s を導き出すことは、計算時間の観点から極めて難しいため、暗号文を復号することはおよそできない。
暗号化のための鍵と復号のための鍵を異なるものにしたことで、鍵配送問題は解決された。
なお、暗号の用語については、暗号理論の用語、暗号の用語を参照。
公開鍵暗号にはさまざまな方式がある。ここでは典型的な公開鍵暗号方式である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 を割り出そうとするが、これは時間が掛かりすぎて現実的でない。
根気強く素因数分解を試みていれば、いつかは復号できる。しかし、一般市民間の個人的な通信程度であれば、解読に数年を要する規模の暗号化を施しておけば、それ以上の手間を掛けて解読しようとする者はまずいない。これは、事実上秘密が守られているといえる(計算量的安全性)。
軍事用暗号の場合、専用のコンピュータで専門のプログラムを走らせても解読には数億年~数兆年を要するように設計されている。これも事実上解読不可能といってよい。