Diffie–Hellman key exchange

p是素数，g和x是整数，虽然$y = g^x \mod p$很快，但是逆过程求x就困难了。

以下是DH协议的方案： 1. Alice和Bob先对p 和g达成一致，而且公开出来。Eve也就知道它们的值了。 2. Alice取一个私密的整数a，不让任何人知道，发给Bob 计算结果：$A = g^a \mod p$. Eve 也看到了A的值。 3. 类似,Bob 取一私密的整数b,发给Alice计算结果$B = g^b \mod p$.同样Eve也会看见传递的B是什么。 4. Alice 计算出 $S = B^a \mod p = (g^b)^a \mod p = g^{ab} \mod p$. 5. Bob 也能计算出$S = A^b \mod p = (g^a)^b \mod p = g^{ab} \mod p$. 6. Alice 和 Bob 现在就拥有了一个共用的密钥S. 7. 虽然Eve看见了p,g, A and B, 但是鉴于计算离散对数的困难性，她无法知道a和b 的具体值。所以Eve就无从知晓密钥S 是什么了。

证明 $(g^b \mod p)^a = g^{ab} \mod p$ ：

$$\text{假设：} g = p+x \\ (g^b \mod p)^a = ((p+x)^b \mod p)^a = (x^b)^a = x^{ab} \\ g^{ab} \mod p = x^{ab} \\ (g^b \mod p)^a = g^{ab} \mod p$$