DH 算法

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

DH 算法的作用

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

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

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

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

一些数学的背景知识

原根

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

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

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

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

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

原根的应用

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

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

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

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

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

• 7² 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）⁵⁵mod 10。根据原根的性质，7 和 10 是互质的，且 7 是 10 的原根，因此 7^φ(10)mod 10 = 1，最后 7^φ(10)×55 mod 10 = 1⁵⁵ mod 10 = 1.

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

离散对数难题

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

｛a¹ mod p，a² mod p，a³ 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¹ mod 7 = 3
• 3² mod 7 = 2
• 3³ mod 7 = 6
• 3⁴ mod 7 = 4
• 3⁵ mod 7 = 5
• 3⁶ mod 7 = 1

因此，我们得到了这个等式： {3¹，3²，3³，3⁴，3⁵，3⁶} =｛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

1. Alice 首先选择一个素数 p，例如 97，然后选取一个 p 的原根 5，记为 g，再选取一个随机数 a，例如 123，然后计算 A=g^a mod p，结果是 34，然后，Alice 发送 p＝97，g=5，A=34 给 Bob。注意 a 没有发送。
2. Bob 收到后，也选择一个随机数 b，例如 456，然后计算 B = g^b mod p，结果是 75，然后 Bob 把计算的 B=75 发给 Alice，注意 b 没有发送。
3. Bob 计算 s = A^b mod p，结果是 22；Alice 计算 s ＝ B^a mod p，计算结果与乙算出的结果一样，都是 22。
4. 所以最终双方协商出的密钥 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));
    }
}

小结

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)

离散对数为什么是难题？ - 知乎 (opens new window)