公開鍵暗号
公開鍵暗号(こうかいかぎあんごう、英語: Public-key cryptography)とは、暗号化と復号とに異なる鍵(手順)を用い、暗号化用の鍵は公開できるようにした暗号方式である(復号用の鍵は秘匿)。対照的な暗号方式として、暗号化と復号に同一の鍵を用いる共通鍵暗号がある。
暗号化は通信の秘匿性を高めるための手段だが、それに必須の鍵もまた情報なので、鍵を受け渡す過程で盗聴されてしまうというリスクがあった。共通鍵を秘匿して受け渡すには(特使が運搬するというような)コストもかかり、一般人が暗号を用いる際の障害であった。このような暗号化鍵の配送問題を解決したのが公開鍵暗号である。
公開鍵暗号で使われるのと同じ数学的な理論に基づいて通信の安全性を保障する暗号技術全般を指して、広義に公開鍵暗号(あるいは公開鍵暗号技術、非対称暗号技術)と呼ぶこともある。この場合、通信の秘匿を目的とする公開鍵暗号方式だけでなく、秘匿機能は無いデジタル署名、公開鍵通信路のみを用いて共通鍵を合意することができるディフィー・ヘルマン鍵交換なども含まれる。
以下では、通信の秘匿を目的とした狭義での公開鍵暗号について扱う。
D {\displaystyle D} は復号アルゴリズム (decryption algorithm) と呼ばれ、 G {\displaystyle G} の出力した秘密鍵 s k {\displaystyle \mathrm {sk} } と E {\displaystyle E} の出力した暗号文 C {\displaystyle C} とを入力されると平文を出力する。
Π = ( G , E , D ) {\displaystyle \Pi =(G,E,D)} が後述する正当性を満たすとき、 Π {\displaystyle \Pi } は公開鍵暗号方式であるといい、後述する秘匿性をさらに満たすとき、公開鍵暗号方式は安全であるという。
1976年以前には、数理による暗号といえば共通鍵暗号であった。これは暗号化と復号に共通の鍵を使う方式である。共通鍵暗号には、鍵の受け渡しを密かに行わなければならないという課題(鍵配送問題)があった。
共通鍵暗号を用いた通信手順の概略は次のようになる。
あらかじめ、受信者と送信者は密かに共通鍵 c の受け渡しをしておく。
送信者は c を使ってメッセージを暗号化し、受信者に送信する。
受信者は c を使って暗号文を復号し、メッセージを読む。
もし段階 1. で、送信者に対してセキュリティが保証されていない通信路を用いて鍵を配送した場合、第三者に共通鍵 c を傍受されていると、この暗号通信は容易に解読されてしまう。