公開鍵暗号とは、対になる2つの鍵を使ってデータの暗号化・復号を行なう暗号方式。1976年にウィットフィールド・ディフィー(Whitfield Diffie)氏とマーティン・ヘルマン(Martin E. Hellman)氏によって基本原理が考案された。
公開鍵暗号では暗号化に使う鍵と復号に使う鍵が分離されており、暗号化に使った鍵で復号を行なうことはできず、片方からもう一方を割り出すことも容易にはできないようになっている。鍵の持ち主は復号に使う鍵のみを他人に知られないように管理し、暗号化に使う鍵は公開する。このため、暗号化に使う鍵は公開鍵、復号に使う鍵は秘密鍵と呼ばれる。
公開鍵暗号で秘密のメッセージを送受信する場合、送信者は受信者が公開している公開鍵を入手して暗号化を行なう。暗号化されたメッセージは受信者の持つ秘密鍵でしか復号できないため、途中で第三者に傍受されても中身を解読されることはない。
公開鍵暗号が考案されるまでは、暗号と言えば暗号化と復号に同じ鍵を用いる秘密鍵暗号(共通鍵暗号、対称鍵暗号)しかなかった。秘密鍵暗号ではメッセージの送信者と受信者が同じ鍵(暗号表など)を共有する必要があるため、鍵を安全な経路で相手に届けなければならない。公開鍵暗号では暗号に使う公開鍵は第三者に知られても解読されないため、鍵の安全な輸送が必要なく、安全性も高い。
公開鍵暗号は秘密鍵暗号よりも処理が複雑になりがちであり、より多くの計算資源や時間を必要とする。このため、暗号通信に利用する場合は、実際の通信内容の暗号化には即興で鍵を生成した秘密鍵暗号を使い、その鍵を送信者と受信者の間で安全に交換するために公開鍵暗号を使うといった使い方をすることが多い。また、公開鍵暗号は非対称な鍵を用いる特徴から、デジタル文書の正当性を保証するデジタル署名にも応用されている。
公開鍵暗号を実装するための具体的な暗号方式はいくつかの方式が提案されている。最も有名なのは、巨大な整数の素因数分解の困難さを利用したRSA暗号で、現在では様々な分野で利用されている。他に、離散対数問題の解の困難さを利用したElGamal暗号、楕円曲線上の離散対数問題を利用した楕円曲線暗号などがある。
