IKEの解説の最後に,安全でない通信路を使用して動的に暗号鍵を生成・共有する,IKEの核であるDiffie-Hellman交換の原理を簡単に解説します。まずは具体的な実例で処理を追ってみましょう。

Diffie-Hellman交換

 3と67という数字をDiffie-Hellman交換の前提条件として使用するとします。そしてこの前提条件はDiffie-Hellman交換を行う装置(これをA,Bとします)および盗聴者のすべてが知っているとします。

 Aは乱数xを作り,2のx乗を67で割った余りをBに送信します。例えばxが11だったすると,AがBに送信する数字は2の11乗を67で割ったものの余り,つまり2048を67で割ったものの余りなので,38となります。Aは図1のようにこの「38」という値だけをBに送信します。


  A   B  
  乱数11を生成。
2^11 mod 67 = 38
をBに送信
38
   

 Bも同様に乱数yを作り,2のy乗を67で割った余りをAに送信します。例えばyが9だったとすると,2の9乗を67で割ったものの余り,つまり512を67で割ったものの余りである43という値を送信することになります。


  A   B  
   
43
乱数9を生成。
2^9 mod 67 = 43
をAに送信
 

 Aは,Bから送られてきた43という数字と自分で作った乱数x(ここでは11)を使って,43の11乗を67で割った余りを計算します。ここでは,92京9293兆7394億7122万2707 を67で割った余り,つまり66となります。

 Bも,Aから送られてきた38という数字と自分で作った乱数y(ここでは 9)を使って,38の9乗を67で割った余りを計算します。ここでは,165兆2161億0126万2848を67で割った余り,つまり66となります。


  A   B  
  43^11 mod 67
66
(66は
両者で
一致)
38^9 mod 67
66
 

 AとBの2つの値は一致しました。つまり,AとBはそれぞれが作った乱数から計算した値を交換することで,66という数字を共有することに成功したのです。これはもちろん偶然一致したのではありません。最初に合意していた2つの値をn(素数,例では67)とg(nより小さい整数,例では2)とし,AがBに送信した値をa,BがAに送信した値をbとすると,次の関係が一般的に成立するのです。

b^x mod n = g^(xy) mod n = a^y mod n

 前述の具体的な数字をこの式に入れてみると,次のようになります。

43^11 mod 67 = 2^(11×9) mod 67 = 38^9 mod 67

 交換された38と43という数字から,共有された値66を計算することは可能でしょうか。AとBは それぞれ43^11 mod 67と8^9 mod 67を計算すればよく,これは電卓でもできるような簡単な計算です。しかし攻撃者はxもyも知らないので,

43^x mod 67 = 2^(xy)mod 67 = 38^y mod 67

となるようなx,yを見つけ出さなければなりません。

 この条件を満たす値を見つけ出すということは,つまりa^xb mod n をxについて解くのと同じ作業をしなければならないということです。このxを,底Aに対するnの離散対数といい,このような離散対数を計算することは素因数分解と同じくらい大変難しい問題であると知られています。離散対数を十分に効率よく見つけ出すアルゴリズムは発見されていないため,nを極めて大きく(数百ビットから数千ビット)とった場合には,離散対数を解くことは事実上不可能になります。したがって,攻撃者はAとBが交換する値を見ることができても,離散対数を計算することはできないため,Diffie-Hellman交換によって安全に秘密対称鍵を共有することができるのです。

IKEにおけるDiffie-Hellman交換

 IKEで使用されるgとnは,原則的にいくつかに決まっています。これらの組はDHグループと呼ばれ,どのグループを鍵生成に使用するかは選択することができます。

 例えばDHグループ1ではg^(xy) mod n においてgに 2,n に次の値(10進数)を使用します。

155251809230070893513091813125848175563133404943451431320235 119490296623994910210725866945387659164244291000768028886422 915080371891804634263272761303128298374438082089019628850917 0691316593175367469551763119843371637221007210577919

 またDHグループ2では,gに2,nに次の値(10進数)を使用します。

179769313486231590770839156793787453197860296048756011706444 423684197180216158519368947833795864925541502180565485980503 646440548199239100050792877003355816639229553136239076508735 759914822574862575007425302077447712589550957937778424442426 617334727629299387668709205606050270810842907692932019128194 467627007

 この他にも DH グループは定義されていますが,広く使われているのはこの2つです。nにこれほど大きな値をとることで,IKEにおける暗号鍵生成は極めて安全なものとなっています。