Dlog

1. 概念

Dlog是离散对数（discrete logarithm）的简称，它定义为：对于给定的群 $G$ 和 $g\in G$ ，以及 $y\in G$ ，找到满足 $g^x=y$ 的 $x$ 值。这个问题是一个重要的密码学问题，因为它是目前广泛使用的公钥加密系统和数字签名算法的基础。

具体来说，当 $g$ 是一个生成元， $q$ 是循环群 $G$ 的阶数， $h\in G$ 时，若存在一个整数 $x \in \{0,1,\ldots,q-1\}$ ，使得 $g^x=h$ ，则整数 $x$ 被称为 $h$ 相对于基元 $g$ 的离散对数，用数学符号表示为：

$x = \log_{g}{h}$

2. 离散对数问题

在离散对数问题（Discrete Logarithm Problem，DLOG Problem）中,给定一个生成元 $g$ 和一个循环群 $G=\langle g \rangle$ 的阶 $q$ ，以及 $G$ 中的一个元素 $h=g^x$ ，其中 $x$ 是一个整数，但 $x$ 的值未知。问题是要求解 $x$ 的值，即计算 $h$ 相对于基元 $g$ 的离散对数。

Input： $G$ and $h=g^x$ for $x \in \{0,1,\ldots,q-1\}$

Output： $f_{DLOG}(q,G,g;h)=\log_g h$

CDH

CDH是“计算Diffie-Hellman”（Computational Diffie-Hellman）的缩写，它是一种基于离散对数问题的密钥交换协议。CDH问题指的是在给定生成元 $g$ 、 $g^a$ 、 $g^b$ 的情况下，计算 $g^{ab}$ 的难题。

Input: $G=\langle g \rangle$ of order $q$ and $A=g^a$ , $B=g^b$ for $a,b \in \{0,1,\ldots,q-1\}$

Output: $f_{CDH}(q,G,g;A,B)=g^{ab}$

CDH问题是 Diffie-Hellman 密钥交换协议的基础，该协议可以让两个人在没有事先共享密钥的情况下建立起一个共享密钥，从而保证通信的机密性。具体来说，设 Alice 和 Bob 分别选择一个私钥 $a$ 和 $b$ ，然后通过公共信道交换计算 $g^a$ 和 $g^b$ ，最终他们可以利用这两个值计算出共享密钥 $g^{ab}$ 。由于 CDH 问题的难解性，即使攻击者拥有 $g$ 、 $g^a$ 、 $g^b$ 这三个值，也无法在多项式时间内计算出 $g^{ab}$ ，因此 Diffie-Hellman 密钥交换协议是安全的。

Dlog 和 CDH 的安全性

1. Dlog

Dlog问题的困难性体现在它的计算复杂度上，具体来说，解决Dlog问题需要的时间随着循环群 $G$ 的阶 $q$ 的增长而指数级增加，即该问题是指数级时间复杂度的问题。

具体来说，如果攻击者想要暴力破解离散对数，需要遍历整个循环群 $G$ ，尝试每一个可能的 $x$ 值，直到找到满足 $h=g^x$ 的 $x$ 值。但由于循环群 $G$ 的阶 $q$ 通常非常大，因此暴力破解的时间复杂度为 $O(q)$ ，这在实际中是不可行的。

目前，最好的已知算法是基于数学上的数论方法，例如 Pohlig-Hellman算法、Pollard rho算法、Index Calculus算法等，目前最强的算法的时间复杂度 $exp(O(\sqrt{\ln q \cdot \ln\ln{q}}))$ 为但对于大型的循环群，仍然需要相当长的时间才能解决Dlog问题。

因此，Dlog问题的困难性是公钥密码学中基于离散对数问题的安全性的基础，许多现代加密算法，例如 Diffie-Hellman密钥交换、ElGamal加密等都依赖于该问题的困难性。

2. CDH

CDH问题的困难性基于离散对数问题的困难性。具体来说，CDH问题是指在给定生成元 $g$ 、 $g^a$ 、 $g^b$ 的情况下，计算 $g^{ab}$ 的难题。

假设存在一个算法 $A$ ，可以在多项式时间内解决CDH问题，即对于任意给定的 $g$ 、 $g^a$ 、 $g^b$ ，算法 $A$ 可以在多项式时间内计算出 $g^{ab}$ 。那么我们可以利用算法 $A$ 解决离散对数问题，即对于任意给定的 $g$ 和 $g^x$ ，算法 $A$ 可以在多项式时间内计算出 $x$ 。这是因为我们可以把 $g^x$ 表示为 $g^{ax/b} = (g^a)^{x/b}$ ，然后利用算法 $A$ 计算 $(g^a)^{x/b}$ 的值，最终再计算出 $x$ 的值。由于离散对数问题被认为是困难的，因此如果存在多项式时间算法解决CDH问题，那么离散对数问题也将被多项式时间内解决，这与离散对数问题的困难性相悖，因此CDH问题被认为是困难的。

需要注意的是，CDH问题的困难性是基于离散对数问题的困难性，但它们并不完全等价。对于某些具体的离散对数问题和CDH问题，可能存在不同的求解算法和复杂度分析方法。

Diffie-Hellman 密钥交换

当一人和另一人要进行加密通信时，他们需要一个共享密钥^[1]，以便在传输过程中对消息进行加密和解密。Diffie-Hellman密钥交换协议是一种常用的方法，用于在公共信道上安全地交换密钥。

过程

设 $G = \langle g \rangle$ 是一个阶为素数 $q$ 的循环群。
Alice: $a \leftarrow \mathbb{Z}_q$ , $A = g^a$ ; send $(q,G,g,A)$ to Bob

Bob: $b \leftarrow \mathbb{Z}_q$ , $B = g^b$ ; send $B$ to Alice; output $k = A^b$

Alice: output $k = B^a$

讲解

Alice 和 Bob 首先公开协商两个公共参数：一个质数 $q$ 和一个生成元 $g$ ，这两个参数可以公开传输。

Alice 随机选择一个私有数 $a$ ，并计算出 $A = g^a \bmod q$ ，然后将 $(q, g, A)$ 传输给 Bob。

Bob 随机选择一个私有数 $b$ ，并计算出 $B = g^b \bmod q$ ，然后将 $B$ 传输给 Alice。

Alice 和 Bob 使用对方传输的公共值计算出共享密钥，即 Bob 计算 $K = A^b \bmod q$ ，而 Alice 计算 $K = B^a \bmod q$ 。这样，Alice 和 Bob 都得到了相同的共享密钥 K，而其他人无法在没有私有数 $a$ 和 $b$ 的情况下计算出它。

因此，Diffie-Hellman协议可以实现在公共信道上安全地交换密钥，因为即使一个攻击者能够截获Alice和Bob之间传输的信息，他们也无法计算出密钥 $K$ ，除非他们知道私有数 $a$ 和 $b$ 。

1.相当于不分公钥和私钥的 RSA 加密 ↩

青山后小塘

数论与加密学 [9]