11. 共通鍵の交換(1) --DiffieHellmanの鍵交換

2006.11.24　株式会社四次元データ　里見玲爾

JCE 11章　共通鍵の交換(1) --DiffieHellmanの鍵交換

11.1. DH法(2ユーザ間)
11.2. DH法(複数ユーザ間)

共通鍵暗号化方式では暗号化と復号化に同じ鍵を使うため、鍵をどのような安全な手段で相手に受け渡すかが重要になってきます。この章では公開鍵暗号化方式が考案される以前に開発されたDiffieHellman鍵交換法(DH法とも呼ぶ)について解説します。

11.1. DH法(2ユーザ間)

DH法は鍵を交換したい各自の非公開数と公開数のペアを用いて共通の数を生成するアルゴリズムです。つまりこの共通の数を生成したあとで、この数を情報としてもつ鍵を各自が生成すれば、それは共通鍵になっているというものです。 DH法は複数ユーザの間で鍵交換を行うことが可能ですが、まずはAさんとBさんの2者の間で共通の数を生成するDH法を考えます。
その手順は次のようなものです。

手順	Aさん側で行う作業	Bさん側で行う作業
注 : 以下では X^Y (mod Z) という表記がありますが、これは「XのY乗をZで割った余り」という計算を表しています。
1	まず両者で素数 p と自然数 g を決める。 p はなるべく大きい方が望ましく、g < p となるように選ぶ。
2	非公開数 xA を決める。ただし xA < p となるようにする。	非公開数 xB を決める。ただし xB < p となるようにする。
3	Aさんの公開数 yA = g^xA (mod p) とする。	Bさんの公開数 yB = g^xB (mod p) とする。
4	公開数 yAをBさんに送信する。	公開数 yBをAさんに送信する。
5	Bさんの公開数 yBを使って共通の数 k = yB^xA (mod p) を計算する。	Aさんの公開数 yAを使って共通の数 k = yA^xB (mod p) を計算する。

Aさん側の k とBさん側の k は、計算課程は違いますがどちらも g^(xA + xB) (mod p) を計算することになるので計算結果が必ず一致します(なぜそうなるかはここでは詳しくは解説しません)。公開数から非公開数の計算が可能なのではと思うかもしれませんが、 pを大きな素数でとれば簡単には計算できません。たとえばpが7999999999999、gが3568735243、 yAが5436899524631、yBが7559580693480と公開されてもxAとxBはなかなか計算できません。ちなみにこのときのxAは46327843266、xBは457823932510です。
このようにして両者が共通の情報を得ることで、共通の鍵を生成することができるようになります。ただし、このアルゴリズムは中間者攻撃(通信の間に入って情報をすりかえてしまうこと。通信者はすりかえに気付かない) に弱いことが知られているため、通信に証明書などを用いて確かに通信相手から送られてきたものであるということを確認する必要があります。証明書については後述します。

11.2. DH法(複数ユーザ間)

11.1節では2ユーザ間でのDH法の手順を解説しました。この節ではそれ以上のユーザ間での手順を解説します。
鍵を交換する全ユーザでp、gを決めること、各自が非公開数を決め、非公開数とp、gから各自の公開数を計算することは11.1節の手順と同じです。違うのは次からの手順です。
11.1節では相手の公開情報を使って計算するだけでよかったのに対し、複数ユーザではただ1ユーザの公開情報で計算を行っても、他のユーザの情報が何ら含まれていないため全ユーザ共通の情報にはなりません。では計算結果を次々とまだ情報が含まれていない他のユーザに渡していったらどうでしょうか。そうすればそのうちすべてのユーザの情報を含んだ計算結果を生成できるはずです。これは次のような手順で行います。鍵交換を行うユーザの数を n とします。

手順	各ユーザが行う作業
注 : 以下では X^Y (mod Z) という表記がありますが、これは「XのY乗をZで割った余り」という計算を表しています。
1	まず全ユーザで素数 p と自然数 g を決める。 p はなるべく大きい方が望ましく、g < p となるように選ぶ。さらに、全ユーザで情報を渡していく順番を決める(たとえば3人なら A -> B -> C -> A などと決める)。
2	自分の非公開数 x を決める。ただし x < p となるようにする。
3	自分の公開数 y = g^x (mod p) とする。
4	自分の公開数を次のユーザに渡す。
5	自分の非公開数 x と前のユーザから受け取った数 z を使って k = x^z (mod p)を計算する。計算したあとにこの手順が n 回繰り返されたかをチェックし、trueなら手順7へ、falseなら手順6へ。
6	k を次のユーザに渡して手順5に戻る。
7	このときの k が共通の数になっている。

このようにすれば、各自が最後に計算した結果 k はすべて g ^ (全ユーザの非公開数の和) (mod p) になります。また、繰り返し回数が n 回でないときに計算された k はユーザの中間情報を持った数であり、この情報を持った鍵のことをセッション鍵(中間鍵)と呼びます。

↑このページの先頭へ