DH算法

# 70.DH算法

DH算法是一种密钥交换算法

　‍

# DH算法的作用

之前我们说过，在实际应用中，一般公钥加密加密对称算法的密钥，密文则用对称加密算法加密传输。

例如，服务端生成一个非对称加密的密钥对，私钥自己保存，公钥发送给客户端，客户端拿到这个公钥之后，再生成一个对称加密的密钥，然后把对称加密的密钥通过公钥进行加密，加密之后发送给服务端，服务端通过私钥进行解密，这样客户端和服务端就可以通过对称加密进行通信了。

而操作系统中一般会预装了不少公钥，因此我们可以使用上面的做法来完成通信。

除此之外，还有一种方法，可以完成密钥的交换，那就是DH算法。DH算法用到了非对称加密算法，是最早的密钥交换算法之一，可以在不安全的信道上完成密钥的交换，本文简单介绍下其原理

‍

# 一些数学的背景知识

‍

# 原根

‍

原根是数论中非常重要的概念，说明如下：

若n,a为正整数，且n,a互质，那么存在整数d，使得 a^d^ ≡ 1 ( mod n )；
d 的取值可以有多个，并且至少一个，就是φ(n)。因为欧拉定理，a，n互质，则a^ φ (n) ^ mod n = 1
如果在 d 的所有取值中，φ(n)是最小的一个正整数，则称 a 是模 n 的原根。
专业一点的说法：用 δ(n,a) 表示使得 a^d^ ≡ 1 ( mod n )成立的最小正整数d，如果δ(n,a) = φ(n)，就称a为模n的原根

举个例子：令n=7，a=3，显然7、3互质， φ(7)=6，可以计算 3^6^ ≡ 1 ( mod 7)，也就是有个d的取值是6；然后我们分别尝试比6小的正整数，能否满足  a^d^ ≡ 1 ( mod n )。计算发现， 3^1^, 3^2^, 3^3^, 3^4^, 3^5 ^( mod 7) 都不等于1，因此，a=3是模n=7的原根。

同理大家可以自行验证a=5也是模n=7的原根。

令n=7，a=2，显然7、2互质，虽然 2^6^ ≡1 ( mod 7)，但我们测试在比6小的正整数中，存在 2^3^ ≡ 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，故只需要判断 3^1^, 3^2^, 3^3 ^, 3^6^( mod 7 ) 即可。

‍

# 原根的应用

举个实际的应用：请计算 7^222^的个位数字是几？其实，我们并不需要计算出7^222^这个数是多少，再取其个位数，我们只需要知道其余数就行，也就是7^222^ mod 10.

首先我们转换下公式：7^222^= 7^2^ × 7^4×55^ =7^2^ × 7^φ(10)×55^

根据模运算规律：(a * b) mod p = (a mod p * b mod p) mod p

7^2^ × 7^φ(10)×55^ mod 10 = （7^2^ mod 10 * 7^φ(10)×55^ mod 10 ) mod 10

我们分别计算7^2^ mod 10 和 7^φ(10)×55^ mod 10的值。

7^2^ mod 10 = 49 mod 10 = 9；
7^φ(10)×55^ mod 10，根据模运算规律(a^b^) mod p = ( (a mod p)^b^) mod p，可以转为（7^φ(10) ^mod 10）^55 ^mod 10。根据原根的性质，7和10是互质的，且7是10的原根，因此 7^φ(10) ^mod 10 = 1，最后7^φ(10)×55^ mod 10 = 1^55^ mod 10 = 1.

因此，7^2^ × 7^φ(10)×55^ mod 10 = 7^2^ mod 10 = 9

‍

# 离散对数难题

假设a ,p均为素数，则有以下等式：

｛a^1^ mod p，a^2^ mod p，a^3^ mod p，....., a^p-1^ mod p｝ = ｛1,2,3,......, p-1 ｝。这个式子说明，a的1次方到 a的p-1次方，结果是数字1到 p-1 的集合。

假设a = 3， p = 7，则有：

3^1^ mod 7 = 3
3^2^ mod 7 = 2
3^3^ mod 7 = 6
3^4^ mod 7 = 4
3^5^ mod 7 = 5
3^6^ mod 7 = 1

因此，我们得到了这个等式： {3^1^，3^2^，3^3^，3^4^，3^5^，3^6^} =｛1,2,3,4,5,6｝

‍

离散对数难题：对于任意一个数x，若0 < x < p，则必定存在唯一的y ( 0 < y < p)，使得 a^y^ mod p = x。当 p很大时，很难求出y，这涉及到离散对数的一些问题，这里不做多讨论，DH算法的安全性就是基于此的。

‍

# DH交换算法的基本过程

接下来，我们讲解下DH算法是如何完成密钥交换的。这里还是假设Alice要和Bob通信，攻击者为Eve

Alice首先选择一个素数p，例如97，然后选取一个p的原根5，记为g，再选取一个随机数a，例如123，然后计算A=g^a^ mod p，结果是34，然后，Alice发送p＝97，g=5，A=34给Bob。注意a没有发送。
Bob收到后，也选择一个随机数b，例如456，然后计算B = g^b^ mod p，结果是75，然后Bob把计算的B=75发给Alice，注意b没有发送。
Bob计算s = A^b^ mod p，结果是22；Alice计算s ＝ B^a^ mod p，计算结果与乙算出的结果一样，都是22。
所以最终双方协商出的密钥s是22。注意到这个密钥s并没有在网络上传输。而通过网络传输的p，g，A和B是无法推算出s的，因为离散对数难题求解困难，并且实际算法选择的素数是非常大的。

‍

为什么很难破解出来a的值？首先，A=g^a^ mod p，在知道 g,p,a的情况下，是可以很快计算出A的；

但如果反过来，知道g,p,A, 很难计算出g^a^的值，只能一个个穷举，从 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));
    }
}

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
79
80

‍