$p$,g$g$,Ya$Y_a$ 通过 gAmod p=Ya$g^{A}modp=Y_a$ 计算出 A$A$ 吗？ 目前所知的最佳算法Pollard's rho algorithm for logarithms 时间复杂度是 O(p–√)$O\left(\sqrt{p}\right)$, 但是实际应用中的 p$p$ 为二进制，假设这个 p$p$ 的长度为 n$n$, 这个复杂度实际上是 O(2n2)$O\left(2^{\frac{n}{2}}\right)$，这个一个指数级的复杂度，是非常高的。因此求解该问题在计算上的困难程度保证了DH算法的安全性。

安全性问题#

那DH密钥协商算法是否就一定安全呢？我们所熟知的，存在一种伪装者攻击(中间人攻击)能够对这种密钥协商算法造成威胁。

假设密钥协商过程中，在Alice和Bob有一个称为Alan的主动攻击者，他能够截获Alice和Bob的消息并伪造假消息，考虑以下情况。

1. Alice和Bob已经共享一个素数 p$p$ 以及其该素数 p$p$ 的本原根 g$g$，当然Alan也监听到报文得知了这个两个消息。
2. 此时Alice计算 gAmod p=Ya$g^{A}modp=Y_a$ ，然而将 Ya$Y_a$ 发送给Bob的过程中被Alan拦截了，Alan自己选定了一个随机数 C$C$, 计算 Yc=gC mod p$Y_c=g^{C}modp$, 然后将 Yc$Y_c$ 发送给Bob。

3. 同时Bob计算 gBmod p=Yb$g^{B}modp=Y_b$，同样在将 Yb$Y_b$ 发送给Alice的过程中被Alan拦截下来，Alan自己选定了一个随机数D ，计算 gDmod p=Yd$g^{D}modp=Y_d$ 发送给了Alice

4. 由于Alice和Bob通讯的消息被替换，Alice计算出来的密钥实际上为Alice和Alan之间协商的密钥：Kad=gD×A mod p$K_{ad}=g^{D\times A}modp$；Bob计算出来的密钥实际上是Blob和Alan之间协商的密钥：Kb