5.Diffie-Hellman密钥交换

Someijam大约 6 分钟

Diffie-Hellman密钥交换

DH密钥交换由Ralph C. Merkle、Bailey Whitfield Diffie 和 Martin Edward Hellman 在1976年提出，早于1977年RSA加密算法出现（真的吗？）。也许有人很好奇我为什么先讲“后”出现的RSA，然后再讲DH。

公钥加密的起源

在讲经典的DH密钥交换之前，我想让更多人知道公钥加密算法创建之初时鲜为人知的故事。

首先是一个在1997年被GCHQ公开的曾经写于1973年的内部机密文件：

GCHQ-RSA

可以看出这其实就是RSA加密算法，中间虽然一直是关于两个素数的同余式，用中国剩余定理转换成一个式子就是我们现在更常见的RSA表示形式。（见WikiPedia关于RSA的描述）

还有一个现已公开但是来自1974年GCHQ的文件：

GCHQ-DH

这个文件中提到的算法就是稍后要讲的DH密钥交换，只不过当时D.和H.都还没有发现。

也就是说，现在大家知道的DH密钥交换和RSA算法在没有被这些密码学家发现前就已经诞生了。只不过一直被GCHQ保密。

算法简介

其实对于RSA来说，最大的缺点就是数据规模过于庞大，运算起来远远不如对称加密，一种比较好的构想是通过非对称算法来加密对称算法的密钥，此后双方通过秘密传输过的密钥进行对称加密，此即密钥交换。今天介绍的DH算法就是专门进行密钥交换的。

交换过程

以Alice和Bob二人的秘密通讯为例。

二人选定一个素数 $p$ ，和模 $p$ 乘法群的生成元 $g$ ，这两个参数可以被所有人知道
Alice选取一个随机数 $n_{a}$ ，计算 $A \equiv g^{n_{a}} (\mod p)$ 发给Bob
Bob选取一个随机数 $n_{b}$ ，计算 $B \equiv g^{n_{b}} (\mod p)$ 发送给Alice
Alice计算 $B^{n_{a}}$ ，Bob计算 $A^{n_{b}}$ ，这两个数应该相等，即为他们的公共密钥

证明比较简单，交换的密钥 $Key = g^{n_{a} n_{b}} = B^{n_{a}} = A^{n_{b}}$ ，此过程中，协商的密钥、生成的随机数不需要发送给对方，也不可以被公开。

对于攻击者而言，必须知道 $n_{a}, n_{b}$ 之中的一个人才可以破解密钥交换的过程，我们可以发现这两个参数都是处在指数的位置，在实数中，我们求指数的值可以计算对数实现，但是这里不一样，有个模 $p$ 就已经搅乱了一切。通常来说，只要 $p$ 很大，计算这个对数就会很难，这便是“离散对数问题”（DLP），不同于RSA，DH密钥交换便是基于离散对数难题构建的。

抽象推广

上面介绍的算法是“整数模p乘法群”中进行的，我们也可以把这里的思想推广到其他的群中。

二人选定一个有限循环群 $G$ 和一个生成元 $g$ ，阶记为 $p$ ，这些参数可以被所有人知道
Alice选取一个随机数 $n_{a}$ ，计算 $A \equiv g^{n_{a}} (\mod p)$ （乘法群），或者 $A \equiv n_{a} \cdot g (\mod p)$ （加法群）
Bob选取一个随机数 $n_{b}$ ，计算 $B \equiv g^{n_{b}} (\mod p)$ （乘法群），或者 $B \equiv n_{b} \cdot g (\mod p)$ （加法群）
Alice计算 $B^{n_{a}}$ （或 $n_{a} \cdot B$ ），Bob计算 $A^{n_{b}}$ （或 $n_{b} \cdot A$ ），这两个数应该相等，即为他们的公共密钥

只要在群里计算离散对数很难，那么这样的密钥交换就很有安全性。

离散对数

接下来我们来谈谈离散对数，常见计算离散对数的算法有BSGS（~~北上广深~~大步小步）算法和Pollard $ρ$ 算法。

比较可惜的是，并非所有的离散对数问题都是难解的。比如当阶 $p$ 可以被分解成很多小素数的乘积时，这时的 $p$ 就白选了。

比如：

A \equiv g^{n_{a}} (\mod p), p = p_{1}^{e 1} \cdot p_{2}^{e_{2}} \dots p_{r}^{e_{r}}

这里 $p_{1}, p_{2}, \dots, p_{r}$ 都比较小时，问题便转化为了：

{\begin{matrix} A \equiv g^{n_{a}} (\mod p_{1}^{e_{1}}) \\ A \equiv g^{n_{a}} (\mod p_{2}^{e_{2}}) \\ \dots \\ A \equiv g^{n_{a}} (\mod p_{r}^{e_{r}}) \end{matrix}

因为 $p_{i}$ 都变得很小了，有时小到我们甚至可以枚举 $n_{a}$ 来爆破的地步，这时我们解出每一组的 $n_{a}$ ，记为 $x_{i}$ ，有：

{\begin{matrix} n_{a} \equiv x_{1} (\mod p_{1}^{e_{1}}) \\ n_{a} \equiv x_{2} (\mod p_{2}^{e_{2}}) \\ \dots \\ n_{a} \equiv x_{r} (\mod p_{r}^{e_{r}}) \end{matrix}

这几个模数互素，用中国剩余定理就可以解出 $n_{a} (\mod p)$ 。

这个例子是Pohlig-Hellman算法的一种情况，将一个大规模离散对数问题分解成若干个小离散对数问题。

再比如……选择的群不大恰当，比如

在圆锥曲线 $H : x^{2} - d^{2} y^{2} = 1$ 上定义一个加法群，设双曲线上的两点 $A (x_{1}, y_{1}), B (x_{2}, y_{2})$ ，我们定义它们的加法 $A + B = C$ ， $C$ 也是双曲线上的一点，坐标为 $C (x_{1} x_{2} + d^{2} y_{1} y_{2}, x_{1} y_{2} + x_{2} y_{1})$ ，这个点也在双曲线上，几何意义为过双曲线右顶点 $(1, 0)$ 作 $A B$ 的平行线，这条线与双曲线的另一个交点就是 $C$ ，见下图：

将这个群的定义改成在一个有限域 $F_{p}$ 上，就可以得到一个循环群，这样也可以引出一个离散对数问题。并且问题的关键在于，由于是自定义的“加法”运算，所以不会太被计算机优化。枚举能接受的数据规模上限要远小于整数模p乘法群的数据规模，也从一种方式加大了破解这个问题的难度。

真的是这样吗？

一个坏消息是，这样定义的群 $H$ 与一个简单的整数加法群同构：

φ : H \to F_{p}

P (x, y) \to w = x - d y

点 $P$ 可以被映射到一个整数 $w$ 上，人话就是绕了一大圈做了一件很简单的事情……

将DH密钥交换放到双曲线群里，就是 $A = n_{a} \cdot G$ ，放到同构的群里，就变成了 $a = n_{a} \cdot g$ ，两个式子的 $n_{a}$ 是相等的。我们求左边的离散对数因为是自定义的加法，要重新造轮子，即使满足上面Pohlig-Hellman的条件，运算的效率肯定要低不少（我做过这样一道题，用点来算的话，到最后还是要逐个枚举int空间的量，耗时约两天）。而在右边这么简单的情况下，相关的算法早已成熟，只需不到一秒。

小结

DH密钥交换算法基于离散对数问题，这么一种非对称的思想为公钥加密的应用奠基，向三位学者在数学领域为和平的贡献致谢。

‍

5.Diffie-Hellman密钥交换

# Diffie-Hellman密钥交换

# 公钥加密的起源

# 算法简介

# 交换过程

# 抽象推广

# 离散对数

# 小结