离散对数问题(DLP) && Diffie-Hellman问题(DHP)

离散对数问题

基于$Z_p^{\ast }$的离散对数问题(DLP)

  给定一个阶为 $p-1$ 的有限循环群$Z_p^{\ast }$，一个本原元$\alpha \in Z_p^{\ast }$和另一个元素$\beta \in Z_p^{\ast }$。DLP是确定满足以下条件的整数$x$(其中$1\le x\le p-1$)的问题:$${\alpha }^x=\beta modp$$

  有群$Z_p^{\ast }$的性质可知这样的整数$x$肯定存在，因为$\alpha$是一个本原元，而每个群元素可以表示为任何本原元的幂值。这个整数$x$也称为以$\alpha$为基的$\beta$的离散对数，可以正式地写作:$$x={\log }_{\alpha }\beta modp$$
  如果参数足够大的话，计算离散对数模一个素数是一个非常难的问题。因为指数运算${\alpha }^x=\beta modp$计算起来非常简单，这也形成了一个单向函数。

示例1：考虑群$Z_{47}^{\ast }$内的离散对数，其中本原元为$\alpha =5$。对$\beta =41$的离散对数问题为：找到满足下面条件的正整数$x$:$$5^x=41mod47.$$  即使使用这么小的数字，确定$x$也不是很容易。使用蛮力攻击，即系统地尝试所有可能的$x$值，可得到解$x=15$。

  在实际中，为了防止 Pohlig-Hellman攻击，群内DLP的基数最好是素数。由于群$Z_p^{\ast }$(p为素数)的基为$p-1$，而这个数显然不是素数，所以人们常会选择$Z_p^{\ast }$子群中基为素数的子群内的 DLP，而非直接使用群$Z_p^{\ast }$本身。下面将用示例2进行说明。

示例2：群$Z_{47}^{\ast }$阶为46，因此，$Z_{47}^{\ast }$中的子群对应的基有23、2和1。$\alpha =2$是拥有23个元素的子群的一个元素，因为23是一个素数，而$\alpha$是子群内的本原元。$\beta =36$(也在子群中)对应的一个可能的离散对数问题为：找到一个正整数$x(1\le x\le 23)$，使得$$2^x=36mod47.$$  利用蛮力攻击可以找到解$x=17$。

针对示例1、2中的暴力破解程序：

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * @Author Mr.Lu
 * @Date 2022/7/27 19:22
 * @ClassName DLPTest
 * @Version 1.0
 */
public class DLPTest {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("请输入群Z_n中的n: ");
        int Z_n = sc.nextInt();
        System.out.println("请输入群Z_n中的一个逆元（本原元）: ");
        int a = sc.nextInt();
        System.out.println("请输入群Z_n中的一个元素: ");
        int b = sc.nextInt();
        int[]  nums = findNums(Z_n);
        int res = findX(nums, a, b, Z_n);
        System.out.println("利用蛮力攻击找到的解为：" + res);
    }

    /**
     * 针对离散对数问题进行暴力破解，查找符合条件的x
     * @param nums
     * @param a
     * @param b
     * @param Z
     * @return
     */
    private static int findX(int[] nums, int a, int b, int Z) {
        for (int i = 0; i < nums.length; i++) {
            if(((Math.pow(a, i) - b) % Z) == 0){
                return i;
            }
        }
        return -1; // 不存在，返回-1作为结束的标志
    }

    /**
     * 求群Z内的元素
     * @param Z
     * @return
     */
    private static int[] findNums(int Z) {
        List<Integer> list = new ArrayList<>();
        for(int i = 1; i < Z; i++){
            if(gcd(i, Z) == 1){
                list.add(i);
            }
        }

        int[] nums = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            nums[i] = list.get(i);
        }
        return nums;
    }

    /**
     * 求两个数的最大公约数
     * @param num
     * @param Z
     * @return
     */
    private static int gcd(int num, int Z) {
      if(num == 1) return 1;

      int temp = num;
      num = Z % num;
      Z = temp;

      return gcd(num, Z);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

推广的离散对数问题
  DLP在密码学中有一个重要特征：它并没有限制在乘法群$Z_p^{\ast }$(p是一个素数)内，而是可以定义在任何循环群中。这也称为推广的离散对数(GDLP)问题，可以描述为:

  给定一个基为$n$的有限循环群$G$，群操作为$o$。考虑一个本原元$\alpha \in G$和另一个元素$\beta \in G$，则离散对数问题为：找到在$1\le x\le n$内的整数$x$,满足:$$\beta =\underset{x次}{\underbrace{\alpha o\alpha o...o\alpha }}={\alpha }^x$$

  与$Z_p^{\ast }$内DLP的情况一样，这样的整数$x$一定存在，因为$\alpha$是一个本原元，因此群$G$内的每个元素都可以通过$\alpha$上重复使用群操作得到。

注意：有些循环群中的DLP并不是很困难的。这样的群就不能用于公钥密码体制，因为这样的群内的DLP并不是一个单向函数。例如下面的示例：

示例：将考虑整数模素数的加法群。例如，如果选择的素数为$p=11，G=(Z_{11},+)$是本原元为$\alpha =2$的一个有限循环群。$\alpha$生成该群的过程如下：
  现在求解元素$\beta =3$的 DLP，即必须计算整数$1\le x\le 11$中，满足以下条件的$x$:$$x\ast 2=\underset{x次}{\underbrace{2+2+...+2}}\equiv 3mod11$$  针对此DLP 的攻击方式。尽管群操作为加法，但是$\alpha$, $\beta$以及离散对数$x$之间的关系可以用乘法来表示：$$x\ast 2\equiv 3mod11$$  可以将本原元$\alpha =2$求逆来求解$x$的值:$$x\equiv 2^{-1}\ast 3mod11$$  根据根据扩展的欧几里得算法可知$2^{-1}\equiv 6mod11$, 那么离散对数为：$$x\equiv 2^{-1}\ast 3\equiv 7mod11$$
  这个离散对数可以从上面给出的小表中验证。
  上面的技巧可以推广到$n$为任意值，且元素$\alpha ,\beta \in Z_n$的任何群$(Z_n,+)$中。可以得到这样一个结论: 在$Z_n$上计算推广的DLP会非常简单。这里能非常容易求解 DLP的原因在于，其中有些数学操作都不在加法群里，即乘法和逆元。

Diffie-Hellman密钥交换的安全性

  我们可以注意到使用基本 DHKE 的协议在主动攻击(攻击者可以修改消息或者生成消息)面前并不是安全的。这意味着如果攻击者Oscar可以修改消息或生成假消息，则Oscar就可以破解这个协议。这称为中间人攻击。
  目前我们只考虑消极攻击者的可能性**，即 Oscar只能监听消息但不能篡改消息**。Oscar的目的就是计算Alice与Bob之间共享的会话密钥$k_{AB}$。通过观察协议Oscar可以获得什么信息?下面分析一下：

1. Oscar知道$\alpha$和$p$，因为这两个参数在握手协议阶段是公开参数。
2. Oscar可以在密钥交换协议的执行阶段窃听信道，获得值$A=k_{pub,A}$ 和 $B=k_{pub,B}$。

  问题提出：Oscar能否从$\alpha ,p,A\equiv {\alpha }^{a}modp$ 和 $B\equiv {\alpha }^{b}modp$中计算出$k=\alpha$。这个问题也称为Diffie-Hellman问题(DHP)。与离散对数问题一样，Diffie-Hellman问题也可推广到任意的有限循环群。

  下面是DHP的正式描述:

  给定一个阶为$n$的有限循环群$G$，一个本原元$\alpha \in G$及两个 G 内的元素 $A={\alpha }^a$ 与 $B={\alpha }^b$。Diffie-Hellman问题就是找到群元素${\alpha }^{ab}$。

  求解 Diffie-Hellman 问题的一个通用方法如下。为了便于理解我们以乘法群 $Z_p^{\ast }$ 内的 DHP 作为例子。假设 Oscar 知道计算 $Z_p^{\ast }$ 内离散对数的有效方法——当然，这是一个“很大”的假设。然后，Oscar就可以通过以下两步求解出 Diffie-Hellman问题，并得到密钥 $k_{AB}$:

1. 通过求解离散对数问题: $a\equiv lo{g}_{\alpha }Amodp$ 计算出 Alice 的私钥 $a=k_{pr,A}$,
2. 计算会话密钥 $k_{AB}\equiv B^{a}modp。$

  尽管这些步骤看上去很简单，但如果p足够大，则计算离散对数问题仍然是不可行的, 即这个假设是以解决离散对数问题为前提的。

  注意：我们并不知道求解DLP是否是求解DHP的唯一方法。理论上，不用计算离散对数就能求解DHP的方法也是可能的。这个情况与RSA类似———在RSA中，因式分解是否真的是破解RSA最好的方法是未知的。然而，尽管这个结论在数学书是不可证明的，但人们通常假设有效求解DLP是有效求解DHP的唯一方法（即解决DLP是解决DHP的前提）。因此，为了保证实际中DHKE的安全性，我们必须确保对应的 DLP不能被求解。而这一点是通过选择足够大的$p$，使得 index-calculus方法不能计算 DLP而实现的。

参考资料：

一些代数知识(群、循环群和子群)：
https://blog.csdn.net/qq_43751200/article/details/125978990
公钥算法的基本数论知识(欧几里得算法、扩展欧几里得算法、欧拉函数、费马小定理与欧拉定理)：
https://blog.csdn.net/qq_43751200/article/details/125460326
《深入浅出密码学》–Christof Paar,Jan Pelzl著