写在前面

Diffie和Hellman在1970年代建立了公钥密码学^[1]的概念以及基于公钥密码的Diffie-Hellman密钥交换协议，这是密码学界的划时代事件，两人凭借该成就在2015年获得计算机科学最高奖-图灵奖^[2]。

Diffie-Hellman密钥交换协议建立在计算性Diffie-Hellman假设^[3](Computational Diffie-Hellman Assumption, CDH)之上，直觉上可以表述为：

$\text{compute } g^{ab} \text{ from } (g^a,g^b)\\$

这里 $a\overset{$}{\gets} \mathbb{Z}^*_q,b\overset{$}{\gets} \mathbb{Z}^*_q$。

如果我们可以解决离散对数问题^[4](Discrete Log Problem, DLP)，那么自然可以解决CDH；反过来，如果可以求解CDH, 人们不清楚是否能利用这个结果解决DLP。一个意义深远的结论是如果我们可以证明解决CDH(或者解决DLP)是困难的(不存在多项式时间算法), 那么 $P\neq NP$。

Diffie-Hellman假设另外一种常用形式，称之为判定性Diffie-Hellman假设(Decisional Diffie-Hellman Assumption, DDH)^[5]，直觉上可以表述成:

$(g^a,g^b,g^{ab})\approx_c (g^a,g^b,g^c)\\$

这里 $a\overset{$}{\gets} \mathbb{Z}^*_q,b\overset{$}{\gets} \mathbb{Z}^*_q,c\overset{$}{\gets} \mathbb{Z}^*_q$。需要注意的是DDH成立的条件是苛刻的，需要挑选合适的群。这里的乘法群 $\mathbb{Z}_q^*$ 实际上是不合适的，不安全的。这是因为可以通过计算 $g^a,g^b$ 的勒让德符号^[6]判断 $a,b$ 的奇偶性，进而判断 $ab$ 的奇偶性。实践中常用的群是二次剩余^[7]构成的乘法群，带限制条件的椭圆曲线的点构成的加法群等。

双方密钥交换

双方密钥交换是最简单的密钥交换形式，也是Diffie-Hellman在论文^[8]中具体讨论的问题。仅需一轮的数据交互，计算双方Alice和Bob就可以获得共享的密钥并保证该密钥不会被第三方获取。它的算法如下图所示：

算法正确性 容易看出$y_{BA}=y_{AB}=g^{ab}$

算法安全性 $y_A, y_B$ 服从均匀分布，且从 $y_A,y_B$ 反推 $a,b$ 需要解DLP; 从 $y_A,y_B$推出 $y_{AB}$ 需要解CDH，这都是不可能的。

Diffie-Hellman不能抵御中间人攻击(Man-in-the-Middle Attack, MITM Attack)^[9], 这是因为计算双方Alice和Bob在相互传递公钥 $y_A,y_B$ 的过程中无法认证(authenticate)对方的身份。假定中间人是Carol，那么具体的攻击方法^[10]如下：

1. Carol假扮Bob和Alice进行一次DH key exchange, 双方协商得到共享密钥 $K_0=g^{ac}$
2. Carol假扮Alice和Bob进行一次DH key exchange, 双方协商得到共享密钥 $K_1=g^{bc}$
3. Alice 使用 $K_0$ 加密自己的信息并发送给Bob, Carol截获该密文后使用 $K_0$ 进行解密得到Alice的信息，再使用 $K_1$ 对其进行加密并发送给Bob
4. Bob 使用 $K_1$ 加密自己的信息并发送给Alice, Carol 使用步骤3类似地进行操作

多方密钥交换

现在考虑最一般的情况，即 $N(N\ge3)$ 方密钥交换。这个问题是笔者近期在做一些多方安全计算协议需要解决的。当 $N=3$ ，可以使用双线性对^[11]构造三方密钥交换协议，但这只是多方密钥交换的一种特例，这里不展开讨论。笔者想讨论的是更一般的情况。

事实上，可以在上文提到的经典的双方密钥交换进一步构造多方密钥交换。为了表述方便，这里以 $N=3$ 为例进行描述^[12]，最后将该方法推广到更一般的情形。

三方密钥（假定计算方分别为Alice, Bob, Charlie）需要进行两轮的数据通讯交互完成。在第一轮交互中，Alice发送数据 $y_A$ 给Bob, Bob发送数据 $y_B$ 给Charlie，最后Charlie发送数据 $y_C$ 给Alice，如下图所示：

依据离散对数问题假设，容易看出 $y_A=g^a,y_B=g^b,y_C =g^c$ 是对私密的 $a,b,c$ 的加密。

在第二轮交互中, Alice发送数据 $y_{CA}$ 给Bob, Bob发送数据 $y_{AB}$ 给Charlie，最后Charlie发送数据 $y_{BC}$ 给Alice，并最终算出共享私钥 $y_{ABC}$, 如下图所示：

算法正确性 容易看出 $y_{CA}=g^{ca},y_{AB}=g^{ab},y_{BC} =g^{bc}$，进而有 $y_{BCA}=g^{bca}, y_{CAB}=g^{cba},y_{ABC}=g^{abc}$, 最终获得共享私钥匙 $y_{BCA}=y_{CAB}=y_{ABC}$。

算法安全性 算法的安全性关键在于证明它是零知识(zero knowledge^[13])的。不失一般性地，现在构造Alice的模拟器 $\mathcal{S}_{Alice}$ 在给定输入 $(a,g^{abc})$的前提下模拟Alice的视角。 在第一轮数据交互中，Alice看到的是 $y_C=g^c$, 因此 $\mathcal{S}_{Alice}$随机生成 $r\overset{$}{\gets} \mathbb{F}_q$ 满足 $y_c\approx_s r$；在第二轮数据交互中，Alice看到的是 $y_{BC}=g^{bc}$, 并计算 $y_{BCA}\gets (y_{BC})^a$ 最终得到共享私钥。因此 $\mathcal{S}_{Alice}$计算 $y_{BC}'\gets (y_{BCA})^{-a}$, 并用 $y_{BC}'$ 模拟 $y_{BC}$， 显然有 $y'_{BC}=y_{BC}$，得证。

最后，考虑 $P_0,P_1,\cdots,P_{N-1}(N>3)$ 之间的密钥交换协议。假定 $P_i$ 拥有随机私密的 $a_i$, 那么经过 $N-1$ 轮的数据交互(每一轮的数据传输方向均为 $P_i\to P_{i+1\bmod N}$且 $P_i$ 传输的是 $g^{\prod_{k=0}^{j-1} a_{(i-k)\bmod N}}$ for all $i=0,\cdots,N-1$), $P_i$ 最终算得共享私钥 $g^{\prod_{i=0}^{N-1} a_i}$。

参考

1. ^https://en.wikipedia.org/wiki/Public-key_cryptography
2. ^https://amturing.acm.org/award_winners/diffie_8371646.cfm
3. ^https://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_problem
4. ^https://en.wikipedia.org/wiki/Discrete_logarithm
5. ^https://en.wikipedia.org/wiki/Decisional_Diffie%E2%80%93Hellman_assumption
6. ^https://en.wikipedia.org/wiki/Legendre_symbol
7. ^https://en.wikipedia.org/wiki/Quadratic_residue
8. ^Diffie, Whitfield, and Martin E. Hellman. "New directions in cryptography." Democratizing Cryptography: The Work of Whitfield Diffie and Martin Hellman. 2022. 365-390.
9. ^https://en.wikipedia.org/wiki/Man-in-the-middle_attack
10. ^https://stackoverflow.com/questions/10471009/how-does-the-man-in-the-middle-attack-work-in-diffie-hellman
11. ^https://en.wikipedia.org/wiki/Pairing-based_cryptography
12. ^https://crypto.stackexchange.com/questions/1025/can-one-generalize-the-diffie-hellman-key-exchange-to-three-or-more-parties
13. ^https://zhuanlan.zhihu.com/p/588114150