簡単に説明します。大きな数gとaについて、gのa乗(g^aと書きます)は簡単に計算できますが、gのa乗だけが与えられたときにaを計算するのは困難です。特に、大きな素数pと、ある性質を満たすgがあったときにg^aをpで割った余り(g^a mod p)とgからaを復元する効率的な方法は知られていません。
ここで例えばアリスとボブが鍵の交換(共有)をしたいとします。アリスとボブはそれぞれ乱数を1つずつ選びます。ここではそれをaとbとします。 アリスはボブにg^a mod pを送ります。ボブはアリスにg^b mod pを送ります。 そしてアリスはボブから貰ったg^b mod pから(g^b mod p)^a mod pを計算します。これは実は(g^b)^a mod pと等しいことが知られています。 ボブも同様に(g^a)^b mod pを計算します。 ところで(g^a)^b mod p = (g^b)^a mod pなので、これを共有鍵とすれば暗号通信ができます。 一方通信を傍受している人はg^a mod pとg^b mod pを傍受できますが、ここから(g^a)^b mod pは直接計算できません。(g^a mod p) * (g^b mod p)はg^(a+b) mod pであって(g^a)^b mod pになりません。また、aやbもわからないので結局(g^a)^b mod pは計算できません。 という訳で他の人に知られずに無事共有鍵を共有できたのでした。
パーフェクトフォワードセキュリティとは (スコア:3)
通常、SSLでは最初だけ公開鍵/秘密鍵ペアを使って相手の確認と共有鍵の交換をして、その後は共有鍵暗号を使って通信します。
共有鍵の生成・交換方法はいくつかあるのですが、これが公開鍵/秘密鍵ペアから共有鍵を生成するような仕組みですと、後で秘密鍵を解読された場合に共有鍵もわかってしまいます。つまり、攻撃者に暗号通信を保存されて、あとで秘密鍵を解読されると全ての暗号通信が解読されてしまいます。
一方、毎回乱数などから生成して、しかも公開鍵/秘密鍵を使わずに交換するようにすると秘密鍵が解読されても過去の暗号通信の内容は解読できませんし、暗号通信の一部が解読されても他の部分は解読できません。このような性質をパーフェクトフォワードセキュリティと呼びます。
そのような交換方法としてはDiffie–Hellman鍵交換法があり、今回Twitterで採用されたのもその一種で、ほとんどのブラウザのSSL実装に含まれています(サポートしていないクライアントの場合は従来の方法が使われます)。
簡単に説明します。大きな数gとaについて、gのa乗(g^aと書きます)は簡単に計算できますが、gのa乗だけが与えられたときにaを計算するのは困難です。特に、大きな素数pと、ある性質を満たすgがあったときにg^aをpで割った余り(g^a mod p)とgからaを復元する効率的な方法は知られていません。
ここで例えばアリスとボブが鍵の交換(共有)をしたいとします。アリスとボブはそれぞれ乱数を1つずつ選びます。ここではそれをaとbとします。
アリスはボブにg^a mod pを送ります。ボブはアリスにg^b mod pを送ります。
そしてアリスはボブから貰ったg^b mod pから(g^b mod p)^a mod pを計算します。これは実は(g^b)^a mod pと等しいことが知られています。
ボブも同様に(g^a)^b mod pを計算します。
ところで(g^a)^b mod p = (g^b)^a mod pなので、これを共有鍵とすれば暗号通信ができます。
一方通信を傍受している人はg^a mod pとg^b mod pを傍受できますが、ここから(g^a)^b mod pは直接計算できません。(g^a mod p) * (g^b mod p)はg^(a+b) mod pであって(g^a)^b mod pになりません。また、aやbもわからないので結局(g^a)^b mod pは計算できません。
という訳で他の人に知られずに無事共有鍵を共有できたのでした。
Twitterで利用しているのは累乗を使う方法ではなく、楕円曲線を使う方法で、基本的な考え方は同じですが、これだと従来の方法と比べて15%ほどのオーバーヘッドで済んだそうです。累乗を使う方法では310%のオーバーヘッドがあったそうです。