离散对数问题
基于 Z p ∗ Z^*_p Zp∗的离散对数问题(DLP)
给定一个阶为 p − 1 p-1 p−1 的有限循环群 Z p ∗ Z^*_p Zp∗，一个本原元 α ∈ Z p ∗ α \in Z^*_p α∈Zp∗和另一个元素 β ∈ Z p ∗ {\beta} \in Z^*_p β∈Zp∗。DLP是确定满足以下条件的整数 x x x(其中 1 ≤ x ≤ p − 1 1≤x≤p-1 1≤x≤p−1)的问题: α x = β m o d p α^x ={\beta}mod p αx=βmodp
有群 Z p ∗ Z^*_p Zp∗的性质可知这样的整数 x x x肯定存在，因为 α α α是一个本原元，而每个群元素可以表示为任何本原元的幂值。这个整数 x x x也称为以 α α α为基的 β β β的离散对数，可以正式地写作: x = log α β m o d p x = {\log}_{\alpha}{\beta} mod p x=logαβmodp
如果参数足够大的话，计算离散对数模一个素数是一个非常难的问题。因为指数运算 α x = β m o d p α^x ={\beta}mod p αx=βmodp计算起来非常简单，这也形成了一个单向函数。
示例1：考虑群 Z 47 ∗ Z^*_{47} Z47∗内的离散对数，其中本原元为 α = 5 α =5 α=5。对 β = 41 β=41 β=41的离散对数问题为：找到满足下面条件的正整数 x x x: 5 x = 41 m o d 47. 5^x = 41 mod 47. 5x=41mod47. 即使使用这么小的数字，确定 x x x也不是很容易。使用蛮力攻击，即系统地尝试所有可能的 x x x值，可得到解 x = 15 x= 15 x=15。
在实际中，为了防止 Pohlig-Hellman攻击，群内DLP的基数最好是素数。由于群 Z p ∗ Z^*_p Zp∗(p为素数)的基为 p − 1 p-1 p−1，而这个数显然不是素数，所以人们常会选择 Z p ∗ Z^*_p Zp∗子群中基为素数的子群内的 DLP，而非直接使用群 Z p ∗ Z^*_p Zp∗本身。下面将用示例2进行说明。
示例2：群 Z 47 ∗ Z^*_{47} Z47∗阶为46，因此， Z 47 ∗ Z^*_{47} Z47∗中的子群对应的基有23、2和1。 α = 2 α = 2 α=2是拥有23个元素的子群的一个元素，因为23是一个素数，而 α α α是子群内的本原元。 β = 36 β=36 β=36(也在子群中)对应的一个可能的离散对数问题为：找到一个正整数 x ( 1 ≤ x ≤ 23 ) x(1≤x≤23 ) x(1≤x≤23)，使得 2 x = 36 m o d 47. 2^x = 36 mod 47. 2x=36mod47. 利用蛮力攻击可以找到解 x = 17 x= 17 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);
}
}
推广的离散对数问题
DLP在密码学中有一个重要特征：它并没有限制在乘法群 Z p ∗ Z^*_{p} Zp∗(p是一个素数)内，而是可以定义在任何循环群中。这也称为推广的离散对数(GDLP)问题，可以描述为:
给定一个基为 n n n的有限循环群 G G G，群操作为 o o o。考虑一个本原元 α ∈ G \alpha \in G α∈G和另一个元素 β ∈ G \beta \in G β∈G，则离散对数问题为：找到在 1 ≤ x ≤ n 1≤ x ≤ n 1≤x≤n内的整数 x x x,满足: β = α o α o . . . o α ⏟ x 次 = α x \beta = \underbrace{{\alpha} o {\alpha} o ...o {\alpha}}_{x次} = {\alpha}^x β=x次 αoαo...oα=αx
与 Z p ∗ Z^*_{p} Zp∗内DLP的情况一样，这样的整数 x x x一定存在，因为 α α α是一个本原元，因此群 G G G内的每个元素都可以通过 α α α上重复使用群操作得到。
注意：有些循环群中的DLP并不是很困难的。这样的群就不能用于公钥密码体制，因为这样的群内的DLP并不是一个单向函数。例如下面的示例：
示例：将考虑整数模素数的加法群。例如，如果选择的素数为 p = 11 ， G = ( Z 11 , + ) p = 11，G = (Z_{11}, +) p=11，G=(Z11,+)是本原元为 α = 2 α =2 α=2的一个有限循环群。 α α α生成该群的过程如下：
现在求解元素 β = 3 β=3 β=3的 DLP，即必须计算整数 1 ≤ x ≤ 11 1 ≤ x ≤ 11 1≤x≤11中，满足以下条件的 x x x: x ∗ 2 = 2 + 2 + . . . + 2 ⏟ x 次 ≡ 3 m o d 11 x*2 = \ \underbrace{2 + 2 + ... + 2}_{x次} \equiv 3 mod 11 x∗2= x次
2+2+...+2≡3mod11 针对此DLP 的攻击方式。尽管群操作为加法，但是 α \alpha α, β \beta β以及离散对数 x x x之间的关系可以用乘法来表示： x ∗ 2 ≡ 3 m o d 11 x*2 \equiv 3 mod 11 x∗2≡3mod11 可以将本原元 α = 2 α=2 α=2求逆来求解 x x x的值: x ≡ 2 − 1 ∗ 3 m o d 11 x \equiv 2^{-1}*3 mod 11 x≡2−1∗3mod11 根据根据扩展的欧几里得算法可知 2 − 1 ≡ 6 m o d 11 2^{-1}\equiv 6 mod 11 2−1≡6mod11, 那么离散对数为： x ≡ 2 − 1 ∗ 3 ≡ 7 m o d 11 x \equiv 2^{-1}*3 \equiv 7mod 11 x≡2−1∗3≡7mod11
这个离散对数可以从上面给出的小表中验证。
上面的技巧可以推广到 n n n为任意值，且元素 α , β ∈ Z n \alpha, \beta \in Z_n α,β∈Zn的任何群 ( Z n , + ) (Z_n,+) (Zn,+)中。可以得到这样一个结论: 在 Z n Z_n Zn上计算推广的DLP会非常简单。这里能非常容易求解 DLP的原因在于，其中有些数学操作都不在加法群里，即乘法和逆元。
Diffie-Hellman密钥交换的安全性
我们可以注意到使用基本 DHKE 的协议在主动攻击(攻击者可以修改消息或者生成消息)面前并不是安全的。这意味着如果攻击者Oscar可以修改消息或生成假消息，则Oscar就可以破解这个协议。这称为中间人攻击。
目前我们只考虑消极攻击者的可能性**，即 Oscar只能监听消息但不能篡改消息**。Oscar的目的就是计算Alice与Bob之间共享的会话密钥 k A B k_{AB} kAB。通过观察协议Oscar可以获得什么信息?下面分析一下：
- Oscar知道 α α α和 p p p，因为这两个参数在握手协议阶段是公开参数。
- Oscar可以在密钥交换协议的执行阶段窃听信道，获得值 A = k p u b , A A = k_{pub, A} A=kpub,A 和 B = k p u b , B B = k_{pub, B} B=kpub,B。
问题提出：Oscar能否从 α , p , A ≡ α a m o d p α, p ,A \equiv {\alpha}^a mod p α,p,A≡αamodp 和 B ≡ α b m o d p B \equiv {\alpha}^b mod p B≡αbmodp中计算出 k = α k= α k=α。这个问题也称为Diffie-Hellman问题(DHP)。与离散对数问题一样，Diffie-Hellman问题也可推广到任意的有限循环群。
下面是DHP的正式描述:
给定一个阶为 n n n的有限循环群 G G G，一个本原元 α ∈ G α \in G α∈G及两个 G 内的元素 A = α a A = {\alpha}^a A=αa 与 B = α b B = {\alpha}^b B=αb。Diffie-Hellman问题就是找到群元素 α a b {\alpha}^{ab} αab。
求解 Diffie-Hellman 问题的一个通用方法如下。为了便于理解我们以乘法群 Z p ∗ Z^*_p Zp∗ 内的 DHP 作为例子。假设 Oscar 知道计算 Z p ∗ Z^*_p Zp∗ 内离散对数的有效方法——当然，这是一个“很大”的假设。然后，Oscar就可以通过以下两步求解出 Diffie-Hellman问题，并得到密钥 k A B k_{AB} kAB:
- 通过求解离散对数问题: a ≡ l o g a A m o d p a \equiv log_aAmod p a≡logaAmodp 计算出 Alice 的私钥 a = k p r , A a = k_{pr, A} a=kpr,A,
- 计算会话密钥 k A B ≡ B a m o d p 。 k_{AB} \equiv B^a mod p 。 kAB≡Bamodp。
尽管这些步骤看上去很简单，但如果p足够大，则计算离散对数问题仍然是不可行的, 即这个假设是以解决离散对数问题为基础的。
注意：我们并不知道求解DLP是否是求解DHP的唯一方法。理论上，不用计算离散对数就能求解DHP的方法也是可能的。这个情况与RSA类似———在RSA中，因式分解是否真的是破解RSA最好的方法是未知的。然而，尽管这个结论在数学书是不可证明的，但人们通常假设有效求解DLP是有效求解DHP的唯一方法（即解决DLP是解决DHP的前提）。因此，为了保证实际中DHKE的安全性，我们必须确保对应的 DLP不能被求解。而这一点是通过选择足够大的 p p 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著