DH 算法
# DH 算法
DH 算法是一种密钥交换算法
# DH 算法的作用
之前我们说过,在实际应用中,一般公钥加密加密对称算法的密钥,密文则用对称加密算法加密传输。
例如,服务端生成一个非对称加密的密钥对,私钥自己保存,公钥发送给客户端,客户端拿到这个公钥之后,再生成一个对称加密的密钥,然后把对称加密的密钥通过公钥进行加密,加密之后发送给服务端,服务端通过私钥进行解密,这样客户端和服务端就可以通过对称加密进行通信了。
而操作系统中一般会预装了不少公钥,因此我们可以使用上面的做法来完成通信。
除此之外,还有一种方法,可以完成密钥的交换,那就是 DH 算法。DH 算法用到了非对称加密算法,是最早的密钥交换算法之一,可以在不安全的信道上完成密钥的交换,本文简单介绍下其原理
# 一些数学的背景知识
# 原根
原根是数论中非常重要的概念,说明如下:
- 若 n,a 为正整数,且 n,a 互质,那么存在整数 d,使得 ad ≡ 1 ( mod n );
- d 的取值可以有多个,并且至少一个,就是 φ(n)。因为欧拉定理,a,n 互质,则 aφ (n) mod n = 1
- 如果在 d 的所有取值中,φ(n)是最小的一个正整数,则称 a 是模 n 的原根。
- 专业一点的说法:用 δ(n,a) 表示 使得 ad ≡ 1 ( mod n )成立的最小正整数 d,如果 δ(n,a) = φ(n),就称 a 为模 n 的原根
举个例子:令 n=7,a=3,显然 7、3 互质, φ(7)=6,可以计算 36 ≡ 1 ( mod 7),也就是 有个 d 的取值是 6;然后我们分别尝试比 6 小的正整数,能否满足 ad ≡ 1 ( mod n )。计算发现, 31, 32, 33, 34, 35( mod 7) 都不等于 1, 因此,a=3 是模 n=7 的原根。
同理大家可以自行验证 a=5 也是模 n=7 的原根。
令 n=7,a=2,显然 7、2 互质,虽然 26 ≡1 ( mod 7),但我们测试在比 6 小的正整数中,存在 23 ≡ 1 ( mod 7 ),显然 3 < φ(7) = 6,不满足原根的定义,故 a=2 并不是模 n=7 的原根。
原根有几个性质,其中一条:δ(n,a) 一定能整除 φ(n)。因此如果判断 a 是不是模 n 的原根时,只需要检验 a 的 φ(n)的约数次方模 n 的值即可。如:n=7,a=3, φ(7)=6 , 6 的约数只有 1,2,3,故只需要判断 31, 32, 33, 36( mod 7 ) 即可。
# 原根的应用
举个实际的应用:请计算 7222 的个位数字是几? 其实,我们并不需要计算出 7222 这个数是多少,再取其个位数,我们只需要知道其余数就行,也就是 7222 mod 10.
首先我们转换下公式:7222= 72 × 74×55 =72 × 7φ(10)×55
根据模运算规律:(a * b) mod p = (a mod p * b mod p) mod p
72 × 7φ(10)×55 mod 10 = (72 mod 10 * 7φ(10)×55 mod 10 ) mod 10
我们分别计算 72 mod 10 和 7φ(10)×55 mod 10 的值。
- 72 mod 10 = 49 mod 10 = 9;
- 7φ(10)×55 mod 10,根据模运算规律(ab) mod p = ( (a mod p)b) mod p,可以转为 (7φ(10)mod 10)55mod 10。根据原根的性质,7 和 10 是互质的,且 7 是 10 的原根,因此 7φ(10)mod 10 = 1,最后 7φ(10)×55 mod 10 = 155 mod 10 = 1.
因此,72 × 7φ(10)×55 mod 10 = 72 mod 10 = 9
# 离散对数难题
假设 a ,p 均为素数,则有以下等式:
{a1 mod p,a2 mod p,a3 mod p,....., ap-1 mod p} = {1,2,3,......, p-1 }。这个式子说明,a 的 1 次方到 a 的 p-1 次方,结果是数字 1 到 p-1 的集合。
假设 a = 3, p = 7,则有:
- 31 mod 7 = 3
- 32 mod 7 = 2
- 33 mod 7 = 6
- 34 mod 7 = 4
- 35 mod 7 = 5
- 36 mod 7 = 1
因此,我们得到了这个等式: {31,32,33,34,35,36} ={1,2,3,4,5,6}
离散对数难题:对于任意一个数 x,若 0 < x < p,则必定存在唯一的 y ( 0 < y < p),使得 ay mod p = x。当 p 很大时,很难求出 y,这涉及到离散对数的一些问题,这里不做多讨论,DH 算法的安全性就是基于此的。
# DH 交换算法的基本过程
接下来,我们讲解下 DH 算法是如何完成密钥交换的。这里还是假设 Alice 要和 Bob 通信,攻击者为 Eve
- Alice 首先选择一个素数
p
,例如 97,然后选取一个p
的原根 5,记为g
,再选取一个随机数a
,例如 123,然后计算 A=ga mod p,结果是 34,然后,Alice 发送p=97
,g=5
,A=34
给 Bob。注意 a 没有发送。 - Bob 收到后,也选择一个随机数
b
,例如 456,然后计算 B = gb mod p,结果是 75,然后 Bob 把计算的B=75
发给 Alice,注意 b 没有发送。 - Bob 计算 s = Ab mod p,结果是 22;Alice 计算 s = Ba mod p,计算结果与乙算出的结果一样,都是 22。
- 所以最终双方协商出的密钥
s
是 22。注意到这个密钥s
并没有在网络上传输。而通过网络传输的p
,g
,A
和B
是无法推算出s
的,因为离散对数难题求解困难,并且实际算法选择的素数是非常大的。
为什么很难破解出来 a 的值?首先,A=ga mod p,在知道 g,p,a 的情况下,是可以很快计算出 A 的;
但如果反过来,知道 g,p,A, 很难计算出 ga 的值,只能一个个穷举,从 a = 0 开始尝试,然后再取模(就是离散对数难题)
更确切地说,DH 算法是一个密钥协商算法,双方最终协商出一个共同的密钥,而这个密钥不会通过网络传输。
如果我们把 a
看成 Alice 的私钥,A
看成 Alice 的公钥,b
看成 Bob 的私钥,B
看成 Bob 的公钥,DH 算法的本质就是双方各自生成自己的私钥和公钥,私钥仅对自己可见,然后交换公钥,并根据自己的私钥和对方的公钥,生成最终的密钥 secretKey
,DH 算法通过数学定律保证了双方各自计算出的 secretKey
是相同的。
# Java 中实现 DH 算法
使用 Java 实现 DH 算法的代码如下:
package chapter12Hash;
import javax.crypto.KeyAgreement;
import java.math.BigInteger;
import java.security.*;
import java.security.spec.*;
public class EncryptDemo6DH {
public static void main(String[] args) {
// Bob和Alice:
Person2 bob = new Person2("Bob");
Person2 alice = new Person2("Alice");
// 各自生成KeyPair:
bob.generateKeyPair();
alice.generateKeyPair();
// 双方交换各自的PublicKey:
// Bob根据Alice的PublicKey生成自己的本地密钥:
bob.generateSecretKey(alice.publicKey.getEncoded());
// Alice根据Bob的PublicKey生成自己的本地密钥:
alice.generateSecretKey(bob.publicKey.getEncoded());
// 检查双方的本地密钥是否相同:
bob.printKeys();
alice.printKeys();
// 双方的SecretKey相同,后续通信将使用SecretKey作为密钥进行AES加解密...
}
}
class Person2 {
public final String name;
public PublicKey publicKey;
private PrivateKey privateKey;
private byte[] secretKey;
public Person2(String name) {
this.name = name;
}
// 生成本地KeyPair:
public void generateKeyPair() {
try {
KeyPairGenerator kpGen = KeyPairGenerator.getInstance("DH");
kpGen.initialize(512);
KeyPair kp = kpGen.generateKeyPair();
this.privateKey = kp.getPrivate();
this.publicKey = kp.getPublic();
} catch (GeneralSecurityException e) {
throw new RuntimeException(e);
}
}
public void generateSecretKey(byte[] receivedPubKeyBytes) {
try {
// 从byte[]恢复PublicKey:
X509EncodedKeySpec keySpec = new X509EncodedKeySpec(receivedPubKeyBytes);
KeyFactory kf = KeyFactory.getInstance("DH");
PublicKey receivedPublicKey = kf.generatePublic(keySpec);
// 生成本地密钥:
KeyAgreement keyAgreement = KeyAgreement.getInstance("DH");
keyAgreement.init(this.privateKey); // 自己的PrivateKey
keyAgreement.doPhase(receivedPublicKey, true); // 对方的PublicKey
// 生成SecretKey密钥:
this.secretKey = keyAgreement.generateSecret();
} catch (GeneralSecurityException e) {
throw new RuntimeException(e);
}
}
public void printKeys() {
System.out.printf("Name: %s\n", this.name);
System.out.printf("Private key: %x\n", new BigInteger(1, this.privateKey.getEncoded()));
System.out.printf("Public key: %x\n", new BigInteger(1, this.publicKey.getEncoded()));
System.out.printf("Secret key: %x\n", new BigInteger(1, this.secretKey));
}
}
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
79
80
# 小结
DH 算法是一种密钥交换协议,通信双方通过不安全的信道协商密钥,然后进行对称加密传输。
但是 DH 算法并未解决中间人攻击,即甲乙双方并不能确保与自己通信的是否真的是对方。消除中间人攻击需要其他方法。
# 参考
密钥交换算法 - 廖雪峰的官方网站 (opens new window)
Diffle-Hellman-密钥交换过程描述_Zetaa 的博客-CSDN 博客 (opens new window)
Diffie-Hellman 密钥交换算法 | 公钥加密 | DH 算法 | 密码学 | 信息安全_哔哩哔哩_bilibili (opens new window)
【不懂数学没关系】DH 算法 | 迪菲-赫尔曼 Diffie–Hellman 密钥交换_哔哩哔哩_bilibili (opens new window)