Diffie-Hellman密钥协商算法

概述#

DH算法是非对称加密算法的鼻祖，为非对称加密算法奠定了基础，主要用途是进行密钥交换，确保共享的密钥能够安全穿越不安全的网络。该算法其背后有对应数学理论做支撑，简单来讲就是构造一个复杂的计算难题，使得对该问题的求解在现实的时间内无法快速有效的求解（computationally infeasible ）。

这个机制的巧妙在于需要安全通信的双方可以用这个方法确定对称密钥。然后可以用这个对称密钥进行加密和解密。但是注意，这个密钥交换协议/算法只能用于密钥的交换，而不能进行消息的加密和解密。之所以如此，主要还是由于对称加密和非对称加密算法的特性决定的。

1. 对称加密算法和非对称加密算法#

对称加密算法

双方使用的同一个密钥，既可以加密又可以解密，这种加密方法称为对称加密，也称为单密钥加密。

优点：速度快，对称性加密通常在消息发送方需要加密大量数据时使用，算法公开、计算量小、加密速度快、加密效率高。

缺点：在数据传送前，发送方和接收方必须商定好秘钥，然后 使双方都能保存好秘钥。其次如果一方的秘钥被泄露，那么加密信息也就不安全了。另外，每对用户每次使用对称加密算法时，都需要使用其他人不知道的唯一秘钥，这会使得收、发双方所拥有的钥匙数量巨大，密钥管理成为双方的负担。

在对称加密算法中常用的算法有：DES、AES等。

AES：密钥的长度可以为128、192和256位，也就是16个字节、24个字节和32个字节。

DES：密钥的长度64位，8个字节。

非对称加密算法

一对密钥由公钥和私钥组成（可以使用很多对密钥）。私钥解密公钥加密数据，公钥解密私钥加密数据（私钥公钥可以互相加密解密）。私钥只能由一方保管，不能外泄。公钥可以交给任何请求方。

优点：安全。

缺点：速度较慢。

在非对称加密算法中常用的算法有： DH，RSA等。

两者区别

• 算法复杂度:对称密钥<非对称密钥
• 加解密速度:对称密钥>非对称密钥
• 安全性:对称密钥<非对称密钥

对称加密算法相比非对称加密算法来说，加解密的效率要高得多。但是缺陷在于对于秘钥的管理上，以及在非安全信道中通讯时，密钥交换的安全性不能保障。所以在实际的网络环境中，会将两者混合使用。因此 ，在https中(TLS\SSL)握手阶段使用非对称加密进行对称密钥的协商，而后在后续正常的数据传输时，都会使用对称加密算法进行加密传输。

数学基础#

本原根：如果使得 am≡1 (mod n)$a^m\equiv 1\left(modn\right)$ 成立的最小正幂 m$m$ 满足 m=φ(n)$m=\phi \left(n\right)$ ,则称 a$a$ 是 n$n$ 的本原根。 其中 φ(n)$\phi \left(n\right)$ 为欧拉函数。

性质：若 a$a$ 为模 n$n$ 的本原根，则 a$a$，a$a$ 的平方，a$a$ 的3次方，……，a$a$ 的 φ(n)$\phi \left(n\right)$ 次m方 模 n$n$ 的余数互不相同，而且构成一个模n的简化剩余系。

栗子(原根)：设 n=7$n=7$，则 φ(7)=7×(1−17)=6$\phi \left(7\right)=7\times (1-\frac{1}{7})=6$

• 当 n=2$n=2$ 时，我们需要找到一个 m$m$, 使得 2m%7=1$2^m\mathrm{\%}7=1$，且刚好 m==φ(7)$m==\phi \left(7\right)$，首先我们能找到当 m=3$m=3$ 时，23%7=1$2^3\mathrm{\%}7=1$，但是却不等于 φ(7)$\phi \left(7\right)$，因此不满足。
• 当 n=3$n=3$时，类比上面一点，可以发现 m=6$m=6$ 时，两点都能满足。因此 3$3$ 为 7$7$ 的一个原根。

question：找了很多资料对原本根和原根的区别，还是很含糊！有大神的话，希望能教教我，感谢啦！

算法流程及原理#

假设Alice需要与Bob协商一个秘钥（秘钥本质上就是一个比特序列，从计算的角度看就是一个大数）。

1. 首先Alice与Bob共享一个素数