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