从01开始 从01开始
首页
  • 计算机科学导论
  • 数字电路
  • 计算机组成原理

    • 计算机组成原理-北大网课
  • 操作系统
  • Linux
  • Docker
  • 计算机网络
  • 计算机常识
  • Git
  • JavaSE
  • Java高级
  • JavaEE

    • Ant
    • Maven
    • Log4j
    • Junit
    • JDBC
    • XML-JSON
  • JavaWeb

    • 服务器软件
    • Servlet
  • Spring
  • 主流框架

    • Redis
    • Mybatis
    • Lucene
    • Elasticsearch
    • RabbitMQ
    • MyCat
    • Lombok
  • SpringMVC
  • SpringBoot
  • 学习网课的心得
  • 输入法
  • 节假日TodoList
  • 其他
  • 关于本站
  • 网站日记
  • 友人帐
  • 如何搭建一个博客
GitHub (opens new window)

peterjxl

人生如逆旅,我亦是行人
首页
  • 计算机科学导论
  • 数字电路
  • 计算机组成原理

    • 计算机组成原理-北大网课
  • 操作系统
  • Linux
  • Docker
  • 计算机网络
  • 计算机常识
  • Git
  • JavaSE
  • Java高级
  • JavaEE

    • Ant
    • Maven
    • Log4j
    • Junit
    • JDBC
    • XML-JSON
  • JavaWeb

    • 服务器软件
    • Servlet
  • Spring
  • 主流框架

    • Redis
    • Mybatis
    • Lucene
    • Elasticsearch
    • RabbitMQ
    • MyCat
    • Lombok
  • SpringMVC
  • SpringBoot
  • 学习网课的心得
  • 输入法
  • 节假日TodoList
  • 其他
  • 关于本站
  • 网站日记
  • 友人帐
  • 如何搭建一个博客
GitHub (opens new window)
  • JavaSE

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

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

    • Java核心类

    • IO

    • Java与时间

    • 异常处理

    • 哈希和加密算法

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

    • 网络编程

    • Java
  • JavaSenior

  • JavaEE

  • JavaWeb

  • Spring

  • 主流框架

  • SpringMVC

  • SpringBoot

  • Java并发

  • Java源码

  • JVM

  • 韩顺平

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

DH算法

# 70.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^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

  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));
    }
}
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)

‍

在GitHub上编辑此页 (opens new window)
上次更新: 2023/4/17 11:03:59
Java中的RSA算法
数字签名

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

Theme by Vdoing | Copyright © 2022-2023 粤ICP备2022067627号-1 粤公网安备 44011302003646号
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式