この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方）
出典検索?: "公開鍵暗号" ? ニュース ・ 書籍 ・ スカラー ・ CiNii ・ J-STAGE ・ NDL ・ dlib.jp ・ ジャパンサーチ ・ TWL（2012年2月）
推測できない数（典型的にはランダムに生成した巨大な数）を用いて、最初に非対称鍵アルゴリズムに適した鍵のペアを生成する。非対称鍵暗号化のスキームでは、公開鍵を使用して誰でもメッセージを暗号化できるが、そのメッセージを復号できるのはペアの秘密鍵の所有者だけである。システムの安全性は、秘密鍵が秘匿されているという点に依存するので、秘密鍵は決して他の誰にも知られてはいけない。この例では、メッセージは暗号化されたデジタル署名である。まず、Aliceはメッセージを秘密鍵で署名する。次に、Bobは、Aliceがメッセージを送ったこと、そしてそのメッセージが変更されていないことを検証できる。

公開鍵暗号（こうかいかぎあんごう、英語: Public-key cryptography）とは、暗号化と復号とに異なる鍵（手順）を用い、暗号化用の鍵は公開できるようにした暗号方式である（復号用の鍵は秘匿）。対照的な暗号方式として、暗号化と復号に同一の鍵を用いる共通鍵暗号がある。

暗号化は通信の秘匿性を高めるための手段だが、それに必須の鍵もまた情報なので、鍵を受け渡す過程で盗聴されてしまうというリスクがあった。共通鍵を秘匿して受け渡すには（特使が運搬するというような）コストもかかり、一般人が暗号を用いる際の障害であった。このような暗号化鍵の配送問題を解決したのが公開鍵暗号である。

公開鍵暗号で使われるのと同じ数学的な理論に基づいて通信の安全性を保障する暗号技術全般を指して、広義に公開鍵暗号（あるいは公開鍵暗号技術、非対称暗号技術）と呼ぶこともある。この場合、通信の秘匿を目的とする公開鍵暗号方式だけでなく、秘匿機能は無いデジタル署名、公開鍵通信路のみを用いて共通鍵を合意することができるディフィー・ヘルマン鍵交換なども含まれる。

以下では、通信の秘匿を目的とした狭義での公開鍵暗号について扱う。
共通鍵暗号の問題点

1976年以前には、数理による暗号といえば共通鍵暗号であった。これは暗号化と復号に共通の鍵を使う方式である。共通鍵暗号には、鍵の受け渡しを密かに行わなければならないという課題（鍵配送問題）があった。

共通鍵暗号を用いた通信手順の概略は次のようになる。
あらかじめ、受信者と送信者は密かに共通鍵 c の受け渡しをしておく。

送信者は c を使ってメッセージを暗号化し、受信者に送信する。

受信者は c を使って暗号文を復号し、メッセージを読む。

もし段階 1. で、送信者に対してセキュリティが保証されていない通信路を用いて鍵を配送した場合、第三者に共通鍵 c を傍受されていると、この暗号通信は容易に解読されてしまう。
公開鍵暗号の考案

共通鍵暗号に生じる鍵配送問題は、送信者と受信者の両者がただ1つの共通の鍵を用いるために起こる問題である。そこで、両者が異なる鍵を用いる方法、すなわち公開鍵暗号が考案された。

公開鍵暗号を用いた通信手順の概略：
通信を受ける者（受信者）は自分の公開鍵（暗号化のための鍵）p を全世界に公開する。

受信者に対して暗号通信をする者（送信者）は、公開鍵 p を使ってメッセージを暗号化してから送信する。

受信者は、公開鍵 p と対になる秘密鍵（復号のための鍵）s を密かにもっている。この s を使って受信内容を復号し、送信者からのメッセージを読む。

暗号通信を不正に傍受しようとする者（傍受者）が公開鍵暗号の方式によって暗号化されたメッセージを傍受したとしても、公開鍵 p から秘密鍵 s を導き出すことは、計算時間の観点から極めて難しいため、暗号文を復号することはおよそできない。

暗号化のための鍵と復号のための鍵を異なるものにしたことで、鍵配送問題は解決された。

なお、暗号の用語については、暗号理論の用語、暗号の用語を参照。
公開鍵暗号方式の直観的な定義
モデル

公開鍵暗号方式では、鍵生成アルゴリズム、暗号化アルゴリズム、復号アルゴリズムを用いる。

鍵生成アルゴリズムは事前準備のためのアルゴリズムであり、（将来暗号文を受け取りたい）ユーザは事前に鍵生成アルゴリズムを実行しておく必要がある。ユーザが鍵生成アルゴリズムを実行すると、アルゴリズムはそのユーザの公開鍵および秘密鍵（それぞれ、そのように呼ばれるデータ）を出力する。公開鍵は暗号文を作成するのに使い、秘密鍵はその暗号文からメッセージを復元するのに使う。

ユーザは鍵生成アルゴリズムを実行する際、セキュリティ・パラメータという値をこのアルゴリズムに入力する。セキュリティ・パラメータは、秘密鍵なしでの暗号文の解読がどれだけ困難かを示す尺度である。

鍵生成アルゴリズムには乱数も入力される。鍵生成アルゴリズムは実行ごとに異なる乱数を選ぶので、ユーザ毎に異なる公開鍵・秘密鍵ペアが割りふられる。

各ユーザは秘密鍵を密かに保管し、公開鍵を公開する。ユーザの秘密鍵を知っているのはそのユーザ自身だけであり、ユーザの公開鍵を知っている(知ることができる)のは全てのユーザである。

メッセージを秘匿する暗号通信をするときの公開鍵、秘密鍵を、それぞれ暗号化鍵、復号鍵ともいう。

暗号文を送る際は、送りたいメッセージおよびそのメッセージの送信先（受信者）の公開鍵を入力として暗号化アルゴリズムを実行する。受信者は復号アルゴリズムに自分の秘密鍵と暗号文を入力して、もとのメッセージを復元する。公開鍵を使えば誰でも暗号文を作成できるが、その暗号文を正しく復号できるのは受信者本人だけである。
公開鍵の認証

安全性を確保するには、どの公開鍵がどのユーザのものであるのかという対応をきちんとつけておく必要がある。