Diffie-Hellman鍵交換
他人に知られてもかまわない情報を2人が交換するだけで、共通の秘密の数を作り出すという方法です。（結城・暗号技術入門)
1976年に発明された
実際には交換するわけではなく作り出す
https://datatracker.ietf.org/doc/html/rfc4253#section-8 で説明されている
ここに書いてある$ GF(p)の意味は https://manabitimes.jp/math/1341#2 でわかる
手順
Alice, Bobが鍵共有したいがEveが盗聴しているという場面設定
AliceがBobに素数$ pと$ gを送信する
pは大きな素数
gは生成元で、pに依存するが、小さくても良い
フェルマーの小定理で$ a^{p-1} \equiv 1になる
式$ g^xが1からp-1までの全ての値を取るかどうかはわからないが]
Aliceが乱数Aを用意する
1からp-2の範囲の整数で、アリスだけが知っている（ボブに伝える必要はない）
Bobが乱数Bを用意する
1からp-2の範囲の整数で、ボブだけが知っている（アリスに伝える必要はない）
Aliceがbobに$ g^a \mod pを送信する
BobがAliceに$ g^b \mod pを送信する
Aliceは受け取った数$ xに対して$ x^a \mod pを計算して鍵とする
計算された鍵は$ g^{ab} \mod p
Bobは受け取った数$ xに対して$ x^b \mod pを計算して鍵とする
計算された鍵は$ g^{ab} \mod p
イブが鍵を計算する困難さ
イブが盗聴できる数は次の4つ
$ p, g
$ g^a \mod p
$ g^b \mod p
$ a, bのどちらかが分かれば簡単だが、それには方程式$ g^x \equiv \alpha \mod pを解く必要がある
この問題が有限体上の離散対数問題と呼ばれていて、困難であることが知られている
一般化
上記の例だと群として$ \mathbb{Z}/pを使ったことになる
離散対数問題が困難であるような群であれば代わりに使える
楕円曲線の群を使えば楕円曲線Diffie-Hellman鍵交換になる