> For the complete documentation index, see [llms.txt](https://json007.gitbook.io/svm/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://json007.gitbook.io/svm/mathsui_sui_nian/diffiehellman_key_exchange.md).

# 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
$$