Diffie-Hellman鍵合意

結城浩、暗号技術入門第３版

1976年にスタンフォード大学のホイットフィールド・ディフィーとマーティン・ヘルマンは、公開鍵暗号の概念を提案しました。この本に具体的な手順が解説されています。

※当該論文ｐｄｆ

https://ee.stanford.edu/~hellman/publications/24.pdf

この鍵交換方式では、事前の打ち合わせ無しで、中間盗聴者が居ても安全に秘密鍵の合意をすることができます。この方式では、mod 剰余の計算を使います。

$$A\ mod\ B=C$$

の時、AをBで割った余りがCになります。時間の計算をして結果が何時になるかを調べる時計演算と同じ計算です。時計演算ではBが12ですね。

GもPも素数の時、次のような公式が成り立ちます。aとbは1からP-2のうちのどれかの整数です（P-1は偶数なのでダメ）。

$$G^{a + b}mod\ P=( G^{a} mod\ P ) \times  (G^{b} mod\ P) mod\ P$$

$$G^{a \times b}mod\ P=( G^{a} mod\ P )^{b} mod\ P$$

つまり、掛け算とかべき乗の剰余は、剰余を取ってから掛け算とかべき乗をやって剰余を取っても、最初に掛け算とかべき乗を計算してから剰余を取っても同じになるという性質を利用します。

1. アリスはボブに対して、２つの素数GとPを送信します。Gは比較的小さな素数、Pは大きな素数です。これは平文で通知されるので中間盗聴者イブに知られても構いません。
2. アリスは心の中で、１からP-2の整数のうちのひとつ a をランダムに選択し記憶します。
3. ボブは心の中で、１からP-2の整数のうちのひとつ b をランダムに選択し記憶します。
4. アリスはボブに対して、次の数を送信する。イブに知られても構いません。$$G^{a}mod\ P$$
5. ボブはアリスに対して、次の数を送信する。イブに知られても構いません。$$G^{b}mod\ P$$
6. アリスはボブから送られてきた数をa乗してmod を取って秘密鍵とする。$$G^{a \times b}mod\ P=( G^{b} mod\ P )^{a} mod\ P$$
7. ボブはアリスから送られてきた数をb乗してmod を取って秘密鍵とする。$$G^{a \times b}mod\ P=( G^{a} mod\ P )^{b} mod\ P$$
8. アリスとボブは共通の秘密鍵を取得したが、中間盗聴者であるイブは、自分が取得できる情報からは秘密鍵を計算することが極めて困難。総当たりで条件を満たす数値を調べることはできるが莫大な計算量が必要となる。

※参考記事

公開鍵暗号の起源