迪菲-赫尔曼密钥交换

最近因研究端到端加密,需要研究迪菲-赫尔曼密钥交换算法,特此记录。

迪菲-赫尔曼密钥交换(英语:Diffie–Hellman key exchange,缩写为D-H) 是一种安全协议。它可以让双方在完全没有对方任何预先信息的条件下通过不安全信道创建起一个密钥。这个密钥可以在后续的通讯中作为对称密钥加密通讯内容。

详细的请参考:维基百科

核心测试代码参考

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
public static void main(String args[]){

//生成一个随机安全质数
BigInteger g = generateSafeBigPrime();
System.out.println("生成一个随机质数:"+g);


//查找此随机安全质数的原根
BigInteger a = getOriginalRoot(g);


//客户端A生成随机整数a
BigInteger randomA = BigInteger.valueOf(new Random().nextInt(100000));
System.out.println("A随机生成一个整数:"+randomA);

//客户端B生成随机整数b
BigInteger randomB = BigInteger.valueOf(new Random().nextInt(100000));
System.out.println("B随机生成一个整数:"+randomB);

//客户端A 执行 g_a := pow(g, a) mod dh_prime
BigInteger g_a = a.modPow(randomA,g);
System.out.println("A运算并发给B的g_a:"+g_a);

//客户端B 执行 g_b := pow(g, b) mod dh_prime
BigInteger g_b = a.modPow(randomB,g);
System.out.println("B运算并发送给A的g_b:"+g_b);


BigInteger keyForA = g_b.modPow(randomA,g);
System.out.println("A计算出的密钥:"+keyForA);

BigInteger keyForB = g_a.modPow(randomB,g);
System.out.println("B计算出的密钥:"+keyForB);

}

经过数次运算,得出的结果为:

1
2
3
4
5
6
7
8
生成一个随机质数:880133
880133找到最小原根:2
A随机生成一个整数:92500
B随机生成一个整数:31761
A运算并发给B的g_a:808849
B运算并发送给A的g_b:298160
A计算出的密钥:435943
B计算出的密钥:435943
1
2
3
4
5
6
7
8
生成一个随机质数:968819
968819找到最小原根:2
A随机生成一个整数:25635
B随机生成一个整数:80842
A运算并发给B的g_a:391986
B运算并发送给A的g_b:346766
A计算出的密钥:59727
B计算出的密钥:59727
1
2
3
4
5
6
7
8
生成一个随机质数:536377
536377找到最小原根:10
A随机生成一个整数:40984
B随机生成一个整数:42138
A运算并发给B的g_a:147842
B运算并发送给A的g_b:228293
A计算出的密钥:340401
B计算出的密钥:340401
1
2
3
4
5
6
7
8
生成一个随机质数:694987
694987找到最小原根:2
A随机生成一个整数:60050
B随机生成一个整数:18125
A运算并发给B的g_a:486303
B运算并发送给A的g_b:160261
A计算出的密钥:27136
B计算出的密钥:27136

附录

此交换算法的安全性在于,需要进行双方交换或传输的只有 安全质数p ,原根g, g_a, g_b 几个,而a,b随机整数只在本机设备有,无法被获取

(当然,前提是设备是足够安全的,如果说设备的内容可以随便被获取,那这个算法的安全性就消失了)

而且由于安全质数p, a,b这几个数都是2048 bit的,足够大,所以使得当前的计算量无法破解。