1976(昭和51)年に米スタンフォード大学のW.DiffieとM.E.Hellmanにより考案された鍵交換アルゴリズムで、通常はDHと略称で呼ばれる。

目次 特徴 用例 ロジック (1) generatorとprimeの合意 (2) Aliceの乱数作成 (3) Aliceの配送鍵Aを作成 (4) Bobの乱数作成 (5) Bobの配送鍵Bを作成 (6) Aliceの計算 (7) Bobの計算 (8) 成功 秘匿性の証明

特徴

これ自体は暗号化の機能も電子署名の機能も持たないが、これを利用することで公開された場所で秘密の共有鍵に付いて合意することができる。

その後は、その鍵を使って慣用暗号方式(秘密鍵方式)の暗号を使用して通信する。

Diffie-Hellmanの暗号的強度は、離散対数問題という数学の困難さに依存している。

アメリカで1997(平成9)年9月に特許が切れたことから、その後広く使われることになった。

用例

例えば、PGPで使われる暗号でDH/DSS(またばDH/DSA)などとあるうちのDHが、これである。

また、IPsecなどで使われる鍵交換プロトコルIKEでも使われている。

ロジック

AliceとBobが、暗号鍵を共有するロジックを下に追う。

(1) generatorとprimeの合意

AliceとBobは、generatorとprime(素数)という二つの値について合意する。

この値は第三者が知っていても構わず、RFC 2409やRFC 3526などで「Diffie-Hellmanグループ」として一般的な値が定義されている。

計算、解読が困難なように、この素数は非常に大きな値が使われており、DH/DSSなどでは2048ビット程度が多い。

ここでは計算が簡単なように、generatorは2、primeは53と、小さな値とする。

(2) Aliceの乱数作成

Aliceは、乱数xを作る。これはBobに教える必要はない。

ここではx=9とする。

(3) Aliceの配送鍵Aを作成

Aliceは、次の計算式によって公開値つまり配送鍵Aを作り、これをBobに送る。この配送鍵は、途中で第三者に傍受されても良い。

A = g^x mod p

g=2、x=9、p=53とすると、次のようになる。

• A = 2⁹ mod 53
• A = 35

(4) Bobの乱数作成

Bobは、乱数yを作る。これはAliceに教える必要はない。

ここではy=3とする。

(5) Bobの配送鍵Bを作成

Bobも、次の計算式によって同様に配送鍵Bを作り、これをAliceに送る。この配送鍵は、途中で第三者に傍受されても良い。

B = g^y mod p

g=2、y=3、p=53とすると、次のようになる。

• B = 2³ mod 53
• B = 8

(6) Aliceの計算

Aliceは、Bobから受け取った配送鍵Bを使い、次の計算を行なう。

B^x mod p

B=8、x=9、p=53とすると、次のようになる。

• 8⁹ mod 53
• 51

(7) Bobの計算

Bobも、Aliceから受け取った配送鍵Aを使い、次の計算を行なう。

A^y mod p

A=35、y=3、p=53とすると、次のようになる。

• 35³ mod 53
• 51

(8) 成功

こうして、AliceとBobは、直接秘密鍵を送ることなく、同じ鍵「51」を共有することに成功した。

秘匿性の証明

この方式では、互いの乱数であるxとy以外の全ての値(g、p、A、B)が公開されている。果たして、傍受されたこれらの値から、本当に秘密鍵を得ることができないのだろうか。

ここで、秘密鍵をKとすると、各値は次の関係が成り立つ。

K = B^x mod p = g^xy mod p = A^y mod p

ここに、上の例で示した、第三者が知ることができる全ての値を代入すると、次のようになる。

K = 8^x mod 53 = 2^xy mod 53 = 35^y mod 53

この式は簡単には解くことができない。離散対数問題を効率的に解くアルゴリズムは現在は発見されておらず、x・yに順番に値を入れて計算して行く以外に方法がない。

このため、pの値が充分に大きければ、この式を解くことは事実上不可能となる。これが、Diffie-Hellman法が充分に安全であることの証明となる。

リンク

用語の所属
暗号
公開鍵暗号方式
DH
関連する用語
電子署名
DSA
PGP

[再検索] [戻る]