✲゚。.ヾ(⌒(ノ'ω')ノ☆.。

変色系男子の日常。

Diffie-Hellman で鍵交換しましょ★

概要

暗号技術入門 を読み終えて、はや 2 ヶ月弱が経過しました。だいぶん中身を忘れてきているので、復習がてら Diffie-Hellman 鍵交換 についてまとめてみたいと思います。

鍵配送問題について

Diffie-Hellman 鍵交換について語るには、まず鍵配送問題について話しておく必要があります。

暗号は 2 つに大別できます。
その 1 つは対象暗号です。対象暗号では暗号化と復号化に同じ鍵を使用します。つまり、送信者 (平文を暗号化して受信者へ暗号を送信する人) と受信者 (送信者から受信した暗号を復号化して平文を得る人) は同じ鍵を所有する必要があります。 強固な暗号化アルゴリズムを用いて最強の暗号を用意することができれば、たとえ盗聴者に暗号を盗聴されたとしても、それを解読される心配はないでしょう。しかし、ここで問題となるのは、送信者が暗号化に用いた鍵を受信者に渡さなければいけないということです。いかに最強の暗号でも鍵を盗聴されてしまえば意味がありません。では鍵も暗号化すればよいでしょうか。…そしたら鍵を暗号化する際に使用した鍵はどうやって渡すのでしょうか。

というように鍵の配送にはこのようなジレンマがつきまといます。それを解決する手段の 1 つが、2 つ目の暗号である非対称暗号です。以前にブログで取り上げた公開鍵暗号 (RSA) がそれにあたり、この暗号の発明のおかげで鍵配送問題は解決されましたが、詳細は割愛します。 代わりに今回は別の鍵配送問題の解決法についてお話します。

f:id:quanon:20150520205751p:plain にこちゃんに鍵を盗まれない (鍵の内容を盗聴されない) ようにするにはどうしたら!?

Diffie-Hellman 鍵交換

ここで登場するのが Diffie-Hellman 鍵交換 です。

Diffie-Hellman 鍵交換では鍵の代わりに以下の 4 つの数を交換します。

  1. P : 非常に大きな素数
    • 送信者が受信者に送ります。
  2. G : P の原始根 (生成元)
    • 送信者が受信者に送ります。
    • 原始根については後述します。
  3. GA mod P
    • A は送信者が用意した乱数 (1 以上 P-2 以下) です。この A は秘密にしなければなりません。
  4. GB mod P
    • B は受信者が用意した乱数 (1 以上 P-2 以下) です。この B は秘密にしなければなりません。

これらの 4 つの数は盗聴者に盗聴されても構いません。秘密にしておかなくてはならないのは A, B のみです。 なんとこのように特定の数を公開するだけで 2 人だけの秘密の鍵を共有する (鍵を生成する) ことができるのです!

f:id:quanon:20150520211812p:plain

次に送信者と受信者はそれぞれ、これら 4 つの数をもとに鍵を生成します。

送信者は受信者から受け取った GB mod P と自身が持っている秘密の乱数 A を元に以下の数を計算します。

(GB mod P)A mod P = (G mod P)A×B

受信者は、送信者から受け取った GA mod P と自身が持っている秘密の乱数 B を元に以下の数を計算します。

(GA mod P)B mod P = (G mod P)B×A

送信者と受信者が計算したそれぞれの値は同じ値となるはずです。

僕は (GB mod P)A mod P = (G mod P)A×B となる理由が理解できていません (書中でさらっと流されている) 。なぜこの法則がなりたつのか、参考になる資料があればご教示ください orz

原始根とは

原始根の定義は以下のとおりです。

素数 p と 1 以上 p 未満の整数 r が以下の性質を満たすとき r を法 p に対する原始根と呼ぶ。
「r, r2, ⋯, rp−2 のいずれもが p で割って余り 1 でない。」

うーん、よく分からんので具体例を挙げてみます。

P = 5 として GA mod P を計算すると、結果は以下のようになります。

G\A 1 2 3 4
1 1 1 1 1
2 2 4 3 1
3 3 4 2 1
4 4 1 4 1

この表の G = 2, 3 の行に注目して下さい。これらの行は各列の値がすべて異なります。 この 2, 3 が法 5 に対する原始根です。原始根のべき乗は 1 〜 P-1 の値に 1 対 1 で対応しているわけです。

なぜ Diffie-Hellman 鍵交換が安全なのか

これは有限上の離散対数問題を解くことの難しさを利用しています。これは G, P が判明していても GA mod P から A を、あるいは GB mod P から B を算出することが困難ということです。 そのため A, B さえ秘密にしておけば、G, P, GA mod P, GB mod P は公開しても問題ありません。

実際にやってみた

Ruby を使って実際に Diffie-Hellman 鍵交換を再現してみました。

(1) 送信者が P と G を決定して受信者に送る

まずは任意の素数 P を決定します。本当は十分に大きい素数である必要がありますが、今回は計算の都合上小さい数を選択します。

P = 499

次に法 P に対する原始根 G を求めます。 これを算出するための具体的な法則を僕は知らないので、プログラムを使って強引に求めます。

# 整数 n を法とする原始根を求める。
def calcurate_primitive_roots(n)
  range = (1..n-1)

  range.select do |g|
    # g が法 n に対する原始根ならば計算結果は重複しない。
    range.map { |a| g ** a % n }.uniq.length == range.to_a.length
  end
end

# 複数の原始根の中から 1 つをランダムに選ぶ。
G = calcurate_primitive_roots(P).sample #=> 86

これで P, G が決定しました。これらの値は受信者に公開します。

(2) 送信者が A を決定する

A = rand(1..P-2) #=> 173

これで A が決定しました。この値は秘密にしておきます。

(3) 受信者が B を決定する

B = rand(1..P-2) #=> 354

これで B が決定しました。この値は秘密にしておきます。

(4) 送信者が受信者に GA mod P を送る

G ** A % P #=> 398

(5) 受信者が送信者に GB mod P を送る

G ** B % P #=> 406

(6) 送信者が鍵を計算する

406 ** A % P #=> 447

(7) 受信者が鍵を計算する

398 ** B % P #=> 447

これで盗聴者に盗聴されることなく、共通の鍵 447 を得られました。

感想

公開鍵暗号 (RSA) と同様に、とてもシンプルなアルゴリズムで実現できるのは不思議ですね。RSA素因数分解問題、Diffie-Hellman 鍵交換は離散対数問題という数学上の困難さをうまく暗号技術に応用している点が非常に面白いなと思いました。