鍵配送問題
前述の通り、共通鍵暗号を安全に使うためには、鍵の安全な事前共有という前提を満たす必要があります。軍事や外交においては、信頼できる密使に鍵を物理的に配送させることで解決できる場合もありますが、こういった方法ではインターネットで相互に何十億もの機器が接続し、暗号を利用して通信したいという場合に使えないなど明らかにスケールしませんし、scalabilityの問題が仮に解消されたとしてもあまりにコストがかかりすぎるので商用通信では使い物になりません。
この鍵配送問題を解決する方法としては、大きく分けて3つの方法が考えられます。
- 鍵配送センター
- Diffie-Hellman鍵共有
- 公開鍵暗号
1の鍵配送センターは、あとできちんと調べて書く。
2のDiffie-Hellmanは、スタンフォード大学の研究者であったHellmanとその研究室の大学院生Diffieによって考案された、盗聴されうる伝送路において通信したい相手とのみ共通の秘密情報を生成でき、かつ盗聴者には同じ秘密情報を作り出せないような秘密情報の共有法です。この「通信したい相手とのみ」という一見不可能そうな性質は、一方向性関数をうまく利用することで実現でき、実際には一方向性関数の候補である "有限体の乗法群の元から生成した巡回群上の離散対数問題" を利用します。 厳密には離散対数問題でなく、Diffie Hellman問題という問題の困難性を利用するのですが, それはおいおい説明します。
3の公開鍵暗号は、暗号化と復号に異なる鍵を使用するという非対称な暗号方式です。暗号化は誰にでも容易にできるものの、復号は困難であるという一方向性関数でありながら、ある特定の秘密情報 (トラップドア) をもった人にのみ復号が容易であるという性質をもった関数を利用します。このような一方向性関数を、トラップドア一方向性関数あるいは単にトラップドア関数といいます。
次節からは、まずDiffie-Hellman鍵共有法について述べたのち、公開鍵暗号としてElGamal暗号, RSA暗号を紹介し、その安全性の仮定や攻撃法について概説します。