Diffie-Hellman Key Exchange (part 2)

解決策を示します。

まずアリスとボブはある原始根と
生成元を使うことを確認し合います。

これは秘密ではありません。

この場合、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 のいずれも知らないので、

答を出すことができません。

この方法を使えば安全です。

イブは、離散対数の問題に阻まれてしまうため、

十分に大きな数値を使えば、

イブは現実的な時間内では

この暗号を破ることができません。

こうして鍵交換の問題が解決されます。

この手法と疑似乱数生成機と併用すれば、

一度も会ったことのない人同士でも
暗号通信ができます。