公開鍵暗号方式とは
奇妙なことですが，ドアを閉める鍵と開く鍵が全く異なる鍵にすることができる数学的な方法（後述のＲＳＡ）が確立しました。
ドアを閉めるのは誰に閉められても困りませんから，その鍵は公開してもかまいません。これを公開鍵といいます。一方、ドアを開く鍵は自分だけが持っていて他人には秘密にする必要があります。これを秘密鍵といいます。
鍵といっても物理的な鍵ではなく、１０２４ビット（方式により異なる）のビット列です。１０進数にすれば数百桁になります。
このような方式を公開鍵暗号方式といいます。どのように暗号鍵と公開鍵を作るのかは省略しますが、公開鍵暗号方式は共通鍵暗号方式がもつ「鍵の送付」「鍵の管理」の欠点を解決できます。
公開鍵暗号方式による暗号メールの送受信
公開鍵暗号方式で送信者Ａが受信者Ｂに暗号文を送るときには、次のようになります。
・送信者は、Ｂの公開鍵で電文を暗号化する。
Ｂの公開鍵は公開してある。
それで、誰でもＢに暗号文を送ることができる。
・受信者ＢはＢの秘密鍵で復号する。
Ｂの秘密鍵は、Ｂだけがもっている。
第三者が電文を見ても、復号できない。
公開鍵暗号方式の特徴
公開鍵暗号方式は、共通鍵暗号方式の欠点である「鍵の送付」「鍵の管理」を解決しています。
- 「鍵の送付」の解決
公開鍵は、公開しているのですから、電子メールで送るときに盗聴されても、ＷｅｂページでのＦＯＲＭに組込んだものがソースを見て調べられてもかまいません。 - 「鍵の管理」の解決
暗号通信の相手がどんなに増加しても、不特定多数と暗号で通信する場合ですら、自分の秘密鍵１つを管理するだけでよいことになります。
しかし、共通鍵暗号方式にくらべて暗号化や復号に時間がかかる欠点があります。長文を対象にするのは適していません。それで実際には、この二つの方式を巧みに組み合わせた方式が広く使われています（→ ハイブリッド暗号方式）。
ＲＳＡ：公開鍵暗号方式の理論
公開鍵暗号方式の代表的なものにＲＳＡ（Rivest Shamir Adleman：開発者３人の名前）があります。
ＲＳＡは，「素数と素数の掛け算は簡単だが、その逆の素因数分解は難しい」という数学的な一方向性に基づいています。数百桁にもなる素数の積を素因数分解をするには膨大な計算が必要で、現在のコンピュータを使って現実的な時間内に答えを出すことは不可能です（参照：「公開鍵暗号方式の原理」）。
公開鍵暗号方式の発展
暗号理論は、アルゴリズムの計算量にコンピュータ性能が追い付かないことに基づいています。鍵の長さ（ビット数）を大にすれば計算量は増大しますが、理論的には同じことです。
近年量子コンピュータが実用化されようとしています。これが発展すると現在のコンピュータが数百年かかる計算を数秒で計算してしまうといわれ，現在の公開鍵暗号方式が役立たなくなるともいわれています。
- EIGamal暗号
- 位数が大きな群の離散対数問題に基づいたDiffie-Hellman鍵共有方式を暗号方式として利用したものです。
- 楕円曲線暗号
- 楕円曲線上の離散対数問題を解くことが困難であることを利用した公開鍵暗号方式です。
- 格子暗号
- 超多次元空間において、ある格子点から移動した点に最も近い格子点を与えて移動の方向を見つけることは困難だという「最近傍格子点問題」に基づく暗号です。量子コンピュータにも耐えうると注目されています。