从 01 开始 从 01 开始
首页
  • 📚 计算机基础

    • 计算机简史
    • 数字电路
    • 计算机组成原理
    • 操作系统
    • Linux
    • 计算机网络
    • 数据库
    • 编程工具
    • 装机
  • 🎨 前端

    • Node
  • JavaSE
  • Java 高级
  • JavaEE

    • 构建、依赖管理
    • Ant
    • Maven
    • 日志框架
    • Junit
    • JDBC
    • XML-JSON
  • JavaWeb

    • 服务器软件
    • 环境管理和配置管理-科普篇
    • Servlet
  • Spring

    • Spring基础
  • 主流框架

    • Redis
    • Mybatis
    • Lucene
    • Elasticsearch
    • RabbitMQ
    • MyCat
    • Lombok
  • SpringMVC

    • SpringMVC 基础
  • SpringBoot

    • SpringBoot 基础
  • Windows 使用技巧
  • 手机相关技巧
  • 最全面的输入法教程
  • 最全面的浏览器教程
  • Office
  • 图片类工具
  • 效率类工具
  • 最全面的 RSS 教程
  • 码字工具
  • 各大平台
  • 校招
  • 五险一金
  • 职场规划
  • 关于离职
  • 杂谈
  • 自媒体
  • 📖 读书

    • 读书工具
    • 走进科学
  • 🌍 英语

    • 从零开始学英语
    • 英语兔的相关视频
    • Larry 想做技术大佬的相关视频
  • 🏛️ 政治

    • 反腐
    • GFW
    • 404 内容
    • 审查与自我审查
    • 互联网
    • 战争
    • 读书笔记
  • 💰 经济

    • 关于税
    • 理财
  • 💪 健身

    • 睡眠
    • 皮肤
    • 口腔健康
    • 学会呼吸
    • 健身日志
  • 🏠 其他

    • 驾驶技能
    • 租房与买房
    • 厨艺
  • 电影

    • 电影推荐
  • 电视剧
  • 漫画

    • 漫画软件
    • 漫画推荐
  • 游戏

    • Steam
    • 三国杀
    • 求生之路
  • 小说
  • 关于本站
  • 关于博主
  • 打赏
  • 网站动态
  • 友人帐
  • 从零开始搭建博客
  • 搭建邮件服务器
  • 本站分享
  • 🌈 生活

    • 2022
    • 2023
    • 2024
    • 2025
  • 📇 文章索引

    • 文章分类
    • 文章归档

晓林

程序猿,自由职业者,博主,英语爱好者,健身达人
首页
  • 📚 计算机基础

    • 计算机简史
    • 数字电路
    • 计算机组成原理
    • 操作系统
    • Linux
    • 计算机网络
    • 数据库
    • 编程工具
    • 装机
  • 🎨 前端

    • Node
  • JavaSE
  • Java 高级
  • JavaEE

    • 构建、依赖管理
    • Ant
    • Maven
    • 日志框架
    • Junit
    • JDBC
    • XML-JSON
  • JavaWeb

    • 服务器软件
    • 环境管理和配置管理-科普篇
    • Servlet
  • Spring

    • Spring基础
  • 主流框架

    • Redis
    • Mybatis
    • Lucene
    • Elasticsearch
    • RabbitMQ
    • MyCat
    • Lombok
  • SpringMVC

    • SpringMVC 基础
  • SpringBoot

    • SpringBoot 基础
  • Windows 使用技巧
  • 手机相关技巧
  • 最全面的输入法教程
  • 最全面的浏览器教程
  • Office
  • 图片类工具
  • 效率类工具
  • 最全面的 RSS 教程
  • 码字工具
  • 各大平台
  • 校招
  • 五险一金
  • 职场规划
  • 关于离职
  • 杂谈
  • 自媒体
  • 📖 读书

    • 读书工具
    • 走进科学
  • 🌍 英语

    • 从零开始学英语
    • 英语兔的相关视频
    • Larry 想做技术大佬的相关视频
  • 🏛️ 政治

    • 反腐
    • GFW
    • 404 内容
    • 审查与自我审查
    • 互联网
    • 战争
    • 读书笔记
  • 💰 经济

    • 关于税
    • 理财
  • 💪 健身

    • 睡眠
    • 皮肤
    • 口腔健康
    • 学会呼吸
    • 健身日志
  • 🏠 其他

    • 驾驶技能
    • 租房与买房
    • 厨艺
  • 电影

    • 电影推荐
  • 电视剧
  • 漫画

    • 漫画软件
    • 漫画推荐
  • 游戏

    • Steam
    • 三国杀
    • 求生之路
  • 小说
  • 关于本站
  • 关于博主
  • 打赏
  • 网站动态
  • 友人帐
  • 从零开始搭建博客
  • 搭建邮件服务器
  • 本站分享
  • 🌈 生活

    • 2022
    • 2023
    • 2024
    • 2025
  • 📇 文章索引

    • 文章分类
    • 文章归档
  • JavaSE

    • 我的 Java 学习路线
    • 安装 Java
    • Java 数据类型

    • Java 多版本配置
    • 面向对象

    • Java 核心类

    • IO

    • Java 与时间

    • 异常处理

    • 哈希和加密算法

      • 什么是哈希算法
      • 第三方库的哈希算法
      • MAC 算法
      • 加密算法介绍
      • 对称加密算法
      • 口令加密算法
      • 非对称加密算法介绍
      • RSA 算法原理(一):数学知识
      • RSA算法原理(二):概述
      • RSA 算法原理(三):补充知识
      • Java 中的 RSA 算法
      • DH 算法
        • DH 算法的作用
        • 一些数学的背景知识
        • DH 交换算法的基本过程
        • Java 中实现 DH 算法
        • 小结
        • 参考
      • 数字签名
      • SSL 和 TLS 协议介绍
    • Java8 新特性

    • 网络编程

  • JavaSenior

  • JavaEE

  • JavaWeb

  • Spring

  • 主流框架

  • SpringMVC

  • SpringBoot

  • Java
  • JavaSE
  • 哈希和加密算法
2023-03-20
目录

DH 算法

# DH 算法

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

# DH 算法的作用

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

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

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

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

# 一些数学的背景知识

# 原根

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

  1. 若 n,a 为正整数,且 n,a 互质,那么存在整数 d,使得 ad ≡ 1 ( mod n );
  2. d 的取值可以有多个,并且至少一个,就是 φ(n)。因为欧拉定理,a,n 互质,则 aφ (n) mod n = 1
  3. 如果在 d 的所有取值中,φ(n)是最小的一个正整数,则称 a 是模 n 的原根。
  4. 专业一点的说法:用 δ(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

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

# 小结

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)

上次更新: 2025/6/3 09:31:54
Java 中的 RSA 算法
数字签名

← Java 中的 RSA 算法 数字签名→

最近更新
01
学点统计学:轻松识破一本正经的胡说八道
06-05
02
2025 年 5 月记
05-31
03
《贫穷的本质》很棒,但可能不适合你
05-27
更多文章>
Theme by Vdoing | Copyright © 2022-2025 | 粤 ICP 备 2022067627 号 -1 | 粤公网安备 44011302003646 号 | 点击查看十年之约
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式