Diffie-Hellman鍵交換ってナニ?

Last Modified: Wed Apr 7 10:54:05 UTC 2010

Diffie-Hellman鍵交換 (Diffie-Hellman Key Exchange) に関する説明 (約11分)。


Diffie-Hellman鍵交換は1976年に考案された鍵配送アルゴリズムで、一見、まったく関係のなさそうな 2つの数字をお互いに交換して、お互いが共通な数 (暗号鍵) をもつことができる。 現在では SSH を含む多くの暗号プロトコルで使われている。

  1. Alice は秘密の数 A を決め、3A (mod 65537) を送る。
  2. Bob は秘密の数 B を決め、3B (mod 65537) を送る。
  3. Alice はさらに A を使って (3B)A を計算する。
  4. Bob はさらに B を使って (3A)B を計算する。
  5. (3B)A ≡ (3A)B
盗聴している人物は、お互いが送った数 3A と 3B を見ても、 本来の AB の値を知らないかぎり暗号鍵を推測できない。 そして、3A (mod 65537) の値から A を求める問題は 離散対数問題と呼ばれ、mod が大きくなるとほぼ計算不可能になる。

なお、ここでは 3n の値を求めるのに本当のべき乗を使っているが、 実際にはこの値はもっと効率的に計算できる。 3(2n) ≡ (3n)2 であることを利用すると、 乗算回数は O(log n) 回ですむ。


Yusuke Shinyama