暗号化は通信の秘匿性を高めるための手段だが、それに必須の鍵もまた情報なので、鍵を受け渡す過程で盗聴されてしまうというリスクがあった。共通鍵を秘匿して受け渡すには(特使が運搬するというような)コストもかかり、一般人が暗号を用いる際の障害であった。このような暗号化鍵の配送問題を解決したのが公開鍵暗号である。以下では、通信の秘匿を目的とした狭義での公開鍵暗号について扱う。共通鍵暗号の問題点.共通鍵暗号を用いた通信手順の概略は次のようになる。公開鍵暗号の考案.公開鍵暗号を用いた通信手順の概略:暗号化のための鍵と復号のための鍵を異なるものにしたことで、鍵配送問題は解決された。なお、暗号の用語については、暗号理論の用語、暗号の用語を参照。公開鍵暗号方式の直観的な定義.モデル.公開鍵暗号方式では、鍵生成アルゴリズム、暗号化アルゴリズム、復号アルゴリズムを用いる。鍵生成アルゴリズムは事前準備のためのアルゴリズムであり、(将来暗号文を受け取りたい)ユーザは事前に鍵生成アルゴリズムを実行しておく必要がある。ユーザが鍵生成アルゴリズムを実行すると、アルゴリズムはそのユーザの公開鍵および秘密鍵(それぞれ、そのように呼ばれるデータ)を出力する。公開鍵は暗号文を作成するのに使い、秘密鍵はその暗号文からメッセージを復元するのに使う。ユーザは鍵生成アルゴリズムを実行する際、セキュリティ・パラメータという値をこのアルゴリズムに入力する。セキュリティ・パラメータは、秘密鍵なしでの暗号文の解読がどれだけ困難かを示す尺度である。鍵生成アルゴリズムには乱数も入力される。鍵生成アルゴリズムは実行ごとに異なる乱数を選ぶので、ユーザ毎に異なる公開鍵・秘密鍵ペアが割りふられる。各ユーザは秘密鍵を密かに保管し、公開鍵を公開する。ユーザの秘密鍵を知っているのはそのユーザ自身だけであり、ユーザの公開鍵を知っている(知ることができる)のは全てのユーザである。メッセージを秘匿する暗号通信をするときの公開鍵、秘密鍵を、それぞれ暗号化鍵、復号鍵ともいう。暗号文を送る際は、送りたいメッセージおよびそのメッセージの送信先(受信者)の公開鍵を入力として暗号化アルゴリズムを実行する。受信者は復号アルゴリズムに自分の秘密鍵と暗号文を入力して、もとのメッセージを復元する。