鍵共有とは秘匿されていない通信経路を用いて安全に秘密情報を共有するための仕組み
L 1976年に鍵共有方法、公開鍵暗号、署名の概念を発表
### 冪乗
(g^a)^b = g^ab = g^ba = (g^b)^a
xをnで割った余りがrの時、r = x mod nと書く 。プログラミング言語では x % n と表記する
冪乗の性質を使ってアリスとボブは鍵共有をする(DH鍵交換という)
1. アリスとボブでgとnを決めて固定する
2. アリスは秘密の値aを決めて A = g^a mod n を求めてボブに渡す
3. ボブも秘密の値bを決めて B = g^b mod n を求めてアリスに渡す
4. アリスはボブからもらったBから s = B^a mod n を求める
5. ボブもアリスからもらったAから s’ = A^b mod n を求める
冪乗の性質から s = s’ = g^ab(mod n)となる これがアリスとボブで共有した値で、共通鍵暗号の秘密鍵など二人だけしか知らない秘密の情報として利用する
DH鍵共有の安全性… DHP(DH Problem)はスーパーコンピュータでも解けないだろうとされている
ある向きの計算は簡単だが、その逆向きの計算が難しい関数を一方向性関数という
DH鍵共有はDHPやDLPといった数学的な問題の困難さを安全性の根拠にしている
