在现代密码学中，许多算法都利用了数学上的难题。离散对数问题与大数分解问题这两个数学难题是非对称密码学的两块基石。本文着重介绍离散对数问题，以及它在 Diffie-Hellman 密钥交换协议当中的应用。

离散对数问题

在实数中对数 是指对于给定的实数 和 ，有一个数 ，使得。离散对数与此类似，但是它是定义在群（Group）上的。

定义：给定群 ，设 ，且有等式 ，那么求解 ，就是离散对数问题（Discrete Logarithm Problem）。 称为 以 为底的离散对数，用符号表示为 ，或者 。

设元素 的生成子群表示为 ，那么当 时，离散对数问题才有解。

注意这里 ，代表定义在 上的群运算对元素 作用 次。

离散对数问题在一些群上很容易计算，例如在整数加法群上，求解离散对数相当于做整数除法。但是在一些特殊的群上，求解离散对数相当困难。

密码学中离散对数问题常用的群是基于质数 的整数模 乘法群 （或者写作 ）。求解离散对数的难度，跟 的大小以及 的子群结构有关系。

如果对群论和 不熟悉，可以参考我之前写的两篇文章：
1. 密码学-02-群论基础
2. 密码学-03-整数模 n 乘法群

快速幂模运算

幂模运算有一种快速计算方法，叫做逐次平方法（Exponentiation by squaring 或者 binary exponentiation），或者直接叫做快速幂模运算。

计算 ，其算法如下：

  1. 将指数 做二进制展开，其中每个 要么是 0 要么是 1：

  2. 使用逐次平方求出做模 的 的幂次表。

    可以看到，在计算 的时候，是用之前计算出的 求平方，再对 取模，参与计算的数始终不会大于 ，这大大简化了计算。这一步的算法复杂度是 。

  3. 最终计算下列乘积得到

    因为 可以能为 0 或 1，上面这个乘积实际上是所有 为 1 的哪些 的乘积。这一步的算法复杂度也是 。

使用逐次平方法平方法可以使幂模运算的时间复杂度达到 ，因此幂模运算使用经典计算机可以很高效的计算。

基于离散对数的非对称密码系统，利用了如下性质：给定 和 ，做幂模运算（modular exponentiation）很快，即计算 很简单，但是给定 和 ，求解离散对数 却很困难。所以一般将 作为私钥，将 作为公钥，即便别人知道了 和 ，也无法求出 。

Diffie-Hellman 密钥交换

离散对数问题一个典型的应用就是 Diffie-Hellman 密钥交换协议（Diffie-Hellman Key Exchange），简称 DHKE。使用这个协议，通信双方可以在完全没有对方任何预先信息的条件下，通过不安全信道创建起一个密钥。这个密钥只有通信双方知道，其他人无法获得，可以在后续的通信中作为对称密钥来加密通信内容。

下面我们来看看基于 的 DHKE 是如何工作的。假设通信双方叫做 Alice 与 Bob，并且 Alice 作为通信的发起方。

第一步：Alice 告诉 Bob，她选取的群 的参数： 和 。其中 为 某个子群的生成元。为了安全性，子群 的阶要尽可能为一个大质数。

第二步：Alice 选取一个整数 ，计算 ，并将 发送给 Bob。同时，Bob 选取一个整数 ，计算 ，并将 发送给 Alice。

第三步：Bob 收到 之后，计算 。同样 Alice 收到 之后，计算 。这个 就是通过 DHKE 协议建立起来的密钥。

下图详细展示了 DHKE 的协议流程。

DHKE 协议流程

从非对称密码系统的角度理解， 和 是公钥，可以在不安全的信道中传输， 是 Alice 的私钥，只有 Alice 知道， 是 Bob 的私钥，只有 Bob 知道。通过协议生成的密钥 ，Alice 和 Bob 都知道，但是其他人无法通过信道上传输的信息计算得到 。

攻击者想要得到密钥 ，就需要计算 ，攻击者可以从公共信道上获取 和 ，但是由于 和 分别是 Alice 和 Bob 私钥，攻击者无法直接获得。不过攻击者可以从信道上获取 和 ，通过 来计算得到 ，同理也可以得到 。

已知 、、，通过 求解得到 ，就是在群 上解离散对数问题。当 足够大，且子群 的阶也为够大的质数时（例如 1024 比特的大数），求解这个离散对数将会非常困难。因此攻击者想要通过公共信息计算得到密钥 会非常困难，求解离散对数的复杂度保证了 DHKE 的安全。

离散对数当前的破解记录是由法国的数学家团队于 2019 年 12 月 2 日发布的，该团队破解了在 的大小为 240 个十进制位（795 比特位）的离散对数问题。以 Intel Xeon Gold 6130 CPU（运行于2.1GHz）为参考，他们方法计算离散对数需要消耗 3100 个内核年（core-year）。鉴于此，目前建议使用 2048 比特位的 DHKE。

参考文献：

[1] Discrete logarithm: https://en.wikipedia.org/wiki/Discrete_logarithm
[2] Discrete logarithm records: https://en.wikipedia.org/wiki/Discrete_logarithm_records
[3] Diffie–Hellman key exchange: https://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange
[4] 数论概论（原书第4版），约瑟夫H.西尔弗曼，第 16 章: https://book.douban.com/subject/26863822/