Diff-Hellman密钥交换算法

介绍

Diff-Hellman算法用于在不安全的通道上进行信息交流。他所基于的是数论中的离散对数问题。

什么是离散对数问题？

给定一个数 g、一个模 p，以及数 y，要求找出一个整数 x 使得：

​ g^x≡y(mod p)

其中，g是一个基数（通常是大素数 p的生成元），y 是给定的结果，x 是我们需要计算的离散对数。

那么为什么Diff-Hellman密钥交换算法是安全的呢？

对于给定的 g、p 和 y，计算 x （即离散对数）是一个计算上非常困难的问题。特别是，当 p 很大时（例如，几十到几百位的素数），找到 x 在现代计算机上几乎不可能通过暴力枚举来完成，除非使用一些非常高效的算法。

原理

那接下来我们从一个例子里看看原理是怎么样的。

1、选择一个公共的素数p和基数g。这两个数是公开的

2、生成私钥。每一方都要生成自己的私钥：

A 选择私钥 a（一个随机数），并计算 A=g^a (mod   p)

B 选择私钥 b（一个随机数），并计算B=g^b (mod p)

3、交换公开密钥。

A 将 A发送给 B。

B 将 B 发送给A。

4、计算共享密钥。

A接收了B给的B，然后计算共享密钥：Ka=B^a (mod p)

B接收了A给的A，然后计算共享密钥：Kb=A^b (mod p)

5、共享密钥的性质

因为Ka = B^a=(g^b)^a=g^(ab)=(g^a)^b=Kb

所以Ka=Kb

这样A和B得到了共享密钥K

例子

(g,p) = (5,23)

A这边选择 私钥a= 6

A=g^a (mod p) = 8

B这边选择 私钥b= 15

B=g^b (mod p) = 19

A将 A 发给 B ，B将 B 发给 A

双方收到后就开始计算共享素数

Ka = B^a (mod p) =2

Kb = A^b (mod p) =2

得出共享密钥 K=2