解決策を示します。
まずアリスとボブはある原始根と
生成元を使うことを確認し合います。
これは秘密ではありません。
この場合、17 と 3 にします。
次に、アリスは秘密の乱数、たとえば 15 を選んで
次のように計算します。
3 を 15 乗してから 17 で割り、
剰余をボブに公然と送ります。
同様に、ボブも自分の秘密の乱数、
たとえば 13 を選んで次のように計算します。
3 を 13 乗して、17 で割り、この計算の余り(剰余)を
特に秘密にせず、アリスに送ります。
ここからが、この手法の核心部分です。
アリスは、ボブから送られた数を
自分の秘密の数で累乗します。
これで、共有の秘密の数が得られます。
この場合は 10 です。
同様に、ボブもアリスが秘密にせずに送付した
計算結果を
自分の秘密の数値でべき乗すると、
同じ共有の秘密の数値が得られます。
一見、別々の計算のようですが、彼らは
まったく同じ計算を行っているのです。
アリスの場合、
ボブから受信した 12 は
3 を 13 乗して 17 で割った余りです。
このため、彼女の計算は、3 を 13 乗し、さらに 15乗して
17 で割った余りを求めるのと同じです。
ボブの場合、
彼がアリスから受信した 6 は、
3 を 15 乗して 17 で割った余りです。
このため彼の計算は
3 を 15 乗し、さらに 13 乗したのと
同じです。
彼らは同じ計算を、指数の順序を変えて
行っただけなのです。
指数の順序を入れ替えても、結果は変わりません。
このため、双方とも 3 を、
自分たちの秘密の数値で
累乗しています。
イブは、秘密の数値である 15,13 のいずれも知らないので、
答を出すことができません。
この方法を使えば安全です。
イブは、離散対数の問題に阻まれてしまうため、
十分に大きな数値を使えば、
イブは現実的な時間内では
この暗号を破ることができません。
こうして鍵交換の問題が解決されます。
この手法と疑似乱数生成機と併用すれば、
一度も会ったことのない人同士でも
暗号通信ができます。