密码学考古之迪菲-赫尔曼密钥交换(Diffie–Hellman Key Exchange)

写在前面

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