离散对数难题

DH 密钥交换算法的安全性依赖于离散对数求解的困难

全称 Discrete Logarithm Problem，简称 DLP

前置知识

原根

1. 定义

   若 $n、a$ 为正整数，且 $n、a$ 互质，令 $a^{d} ≡ 1 (mod n)$，可知，使该式成立的 $d$ 的取值可能多个，又由欧拉定理可知 $d$ 中的一个取值一定为 $\varphi (n)$ ，只不过此时并不确定 $\varphi (n)$ 是否是 $d$ 中所有取值中最小的那个。重点来了，如果此时所有 $d$ 的可能取值中 $\varphi (n)$ 恰好是最小的，那么就称 $a$ 为模 $n$ 的原根

   还有一个问题：当 $n$ 为何值时，才会存在原根呢？因为并不是所有的素数都是有原根的

   答：只有当 $n=1、2、4、p^{e}、2p^{e}$ 时才会存在原根，其中 $p$ 为奇素数， $e$ 为正整数

   重新看下下面对原根的定义：

   一个素数 $q$ 的原根，为其各次幂能够产生从 $1$ 到 $q−1$ 所有整数

   也就是说，如果 $a$ 是素数 $q$ 的一个原根，那么数值 $a mod q, a^{2} mod q, ..., a^{q-1} mod q$ 是各不相同的整数，并且以某种排列方式组成了从 $1$ 到 $q-1$ 的所有整数。

2. 应用

   题目：已知若 $a$ 与 $n$ 互质，并且 $a$ 是 $n$ 的原根，求满足该式 $a^{x} \equiv 1 ( mod n )$ 的 $x$ 的最小值 ？

   答案：根据欧拉定理，若 $a$ 与 $n$ 互质，则 $a^{\varphi (n)} \equiv 1 ( mod n )$，又因为 $a$ 是 $n$ 的原根，所以 $x$ 的最小值一定为 $\varphi (n)$，即 $x = \varphi (n)$

离散对数

1. 定义

   对于一个整数 $b$ 和素数 $q$ 的一个原根 $a$，可以找到惟一的指数 $i$，使得 $b=a^{i} mod q$，其中 $0≤i≤(q−1)$ ，指数 $i$ 称为 $b$ 的以 $a$ 为基数的模 $q$ 的离散对数，该值被记为 $ind_{a, q}(b)$

   也就是说，已知 $b、a、q$，要想求其对应的离散对数 $i$ ，几乎是不可能的，尤其是在素数 $q$ 值很大的情况下

2. 应用

   公钥密码学

注意

原根和离散对数这两个概念即可以从数论的角度来理解，也可以从抽象代数之群论的角度来理解

模运算

1. 定义

   “模”是“Mod”的音译，意为求余 给定一个正整数 $p$，任意一个整数 $n$，一定存在等式 $n=kp+r$ 其中 $k、r$ 是整数，且 $0 \leqslant r<p$，称 $k$ 为 $n$ 除以 $p$ 的商， $r$ 为 $n$ 除以 $p$ 的余数

   取模运算： $a \% p$ （或 $a mod p$），表示 $a$ 除以 $p$ 的余数

2. 性质

   1. $(a + b) mod p = (a mod p + b mod p) mod p$

   2. $(a - b) mod p = (a mod p - b mod p) mod p$

   3. $(a * b) mod p = (a mod p * b mod p) mod p$

      • $\color{#f40} (a^b) mod p = ((a mod p)^b) mod p$

   其中第三条性质很重要，对于后面 DH 算法的证明很关键

DH 算法

步骤

1. 第一步：选取两个全局公开的参数，一个素数 $q$ 和一个整数 $a$，其中 $a$ 是 $q$ 的一个原根

2. 第二步：用户 A 生成私钥和公钥，私钥保密，公钥公开

   1. 私钥：$S_{A}$，它是一个随机数，并且满足 $S_{A}<q$

   2. 公钥：$P_{A}=a^{S_{A}} mod q$，其中 $S_{A}$ 称为 $P_{A}$ 的以 $a$ 为基数的模 $q$ 的离散对数

3. 第三步：用户 B 生成私钥和公钥，私钥保密，公钥公开

   1. 私钥：$S_{B}$，它是一个随机数，并且满足 $S_{B}<q$

   2. 公钥 ：$P_{B}=a^{S_{B}} mod q$，其中 $S_{B}$ 称为 $P_{B}$ 的以 $a$ 为基数的模 $q$ 的离散对数

4. 第四步：用户 A 生成共享秘密密钥

   $$K_{A}=(P_{B}^{S_{A}}) mod q$$

5. 第五步：用户 B 生成共享秘密密钥

   $$K_{B}=(P_{A}^{S_{B}}) mod q$$

至此，用户 A 和用户 B 都生成了一个共享秘密密钥 $K_{A}$ 和 $K_{B}$，并且它们是相等的，WHY?

证明

如何证明共享秘密密钥 $K_{A}$ 与 $K_{B}$ 相等呢？

已知

$$K_{A}=(P_{B}^{S_{A}}) mod q$$

因为

$$P_{B}=a^{S_{B}} mod q$$

所以

$$K_{A}=((a^{S_{B}} mod q)^{S_{A}}) mod q$$

又因为模运算的第三条性质

$$\color{#f40} (a^b) mod p = ((a mod p)^b) mod p$$

所以

$$K_{A}=  (a^{S_{B}})^{S_{A}} mod q =  (a^{S_{A}})^{S_{B}} mod q = (a^{S_{A}} mod q)^{S_{B}} mod q$$

又因为

$$P_{A}=a^{S_{A}} mod q$$

所以

$$K_{A} = (P_{A})^{S_{B}} mod q = (P_{A}^{S_{B}}) mod q$$

又因为

$$K_{B}=(P_{A}^{S_{B}}) mod q$$

所以

$$K_{A} = K_{B}$$

为什么很难破解共享秘密密钥 $K_{A}$？

攻击者可以获得的数据有 $q、a、P_{A}、P_{B}$

要想由这些数据获取共享秘密密钥 $K_{A}=(P_{B}^{S_{A}}) mod q$，就必须再知道 $S_{A}$

又因为 $S_{A}$ 是 $P_{A}$ 的以 $a$ 为基数的模 $q$ 的离散对数

当 $q$ 值很大时，离散对数 $S_{A}$ 几乎不可求，这就是离散对数难解之题

所以攻击者很难破解共享秘密密钥 $K_{A}$

同理，$K_{B}$ 也很难破解

ElGamal 算法

ElGamal 加密算法是基于 DH 密钥交换算法的非对称加密算法，其原理如下

1. 密钥生成过程

   选择一个素数 $p$ 以及两个小于 $p$ 的随机数 $g$ 和 $x$，计算

   $$y = g^{x} mod p$$

   其中公钥 $(y,g,p)$ ，私钥 $x$

   由离散对数的定义可知，$x$也称为 $y、g、p$ 的离散对数

   因此，当素数 $p$ 很大时，由公钥 $(y,g,p)$ 推导出私钥 $x$ 是极其困难的事

2. 加密过程，使用公钥 $(y,g,p)$

   对于明文信息 $M$，随机选择一个与 $p-1$ 互素的整数 $k$，计算

   $$C_{1} = g^{k} mod p$$
   $$C_{2} = y^{k} M mod p$$

   密文为 $C=(C_{1},C_{2})$

3. 解密过程，使用私钥 $x$

   $$M = \frac{C_{2}}{C_{1}^{x}} mod p$$

因为

$$\frac{C_{2}}{C_{1}^{x}} mod p = \frac{y^{k} M mod p}{g^{kx} mod p} mod p =  \frac{y^{k} M }{g^{kx}} mod p =  \frac{y^{k} M }{y^{k}} mod p =  M mod p$$

参考资料

• 应用密码学 | Diffie-Hellman密钥交换算法 (opens new window)
• 离散对数问题 (opens new window)
• 离散对数为什么是难题? - 知乎 (opens new window)
• 证明与计算(2): 离散对数问题(Discrete logarithm Problem, DLP) - ffl - 博客园 (opens new window)