DH & RSA 原理

在 https 建立连接过程中，会进行秘钥协商。双方会各自给出一个随机数 rc, rs，再加上一个 pre-master。最后根据 rc + rs + pre-master 三个随机数计算出最终的主密钥。

这里我们要介绍的 pre-master 的生成算法，就是 DH 秘钥交换的变种，ECDHE。下面我们先来介绍一下 DH 算法。

DH 算法

DH，全称是 Diffe-Hellman，它的原理很简单。

双方预先知道两个公共参数 g 和 p，然后各自给定一个数，最后根据一个数学公式，则可计算出相同的秘钥。

这是建立模幂运算的基础上，先求幂，后取模，称为模幂计算。如下所示，其中 p 是质数，a、b、p 都取很大的数，g 可以取较小的数。

gᵃᵇ mod p = (gᵃ mod p)ᵇ mod p = (gᵇ mod p)ᵃ mod p

秘钥交换过程

假设 Alice 与 Bob 通信，协商秘钥，计算过程如下：

1. Alice 随机生成一个数，作为自己的秘钥 a，计算公钥 A = gᵃ mod p，然后将 A 告诉 Bob。
2. Bob 随机生成一个数，作为自己的秘钥 b，计算公钥 B = gᵇ mod p，然后将 B 告诉 Alice。
3. Bob 根据 A 和 b，计算出秘钥 k1 = Aᵇ mod p = (gᵃ mod p)ᵇ mod p 。
4. Alice 根据 B 和 a，计算出秘钥 k2 = Bᵃ mod p = (gᵇ mod p)ᵃ mod p。

最终得到 k1 == k2。

私钥 a，b 不被外部所知，只有 A、B、g、p 是公开的。而仅仅知道这几个数，是很难求出 a、b 的。因为涉及到对数运算问题。

公式特性

对于下面这个模幂公式来说：

gᵃ mod p = A

它满足如下特性：

1. 已知 g、a、p，求 A 容易。
2. 已知 g、p、A，求 a 困难。
3. 已知 a、p、A，求 g 困难。

该算法就是利用了 1、2 特性。

RSA

非对称加密算法，用公钥加密，可以用私钥解密；用私钥加密，可以用公钥解密。

假设 g 是原始数据，套用如下公式，经过公钥 a 加密后变为了 A。

gᵃ mod p = A

那么如何解出 g 呢？假设我们也根据上面的公式套用一下，用同样的方式解密，如下所示。其中 d 是私钥，将 A 进行解密得到 g。

Aᵈ mod p = g

将 A 代入，可得到：

gᵃᵈ mod p = g

那么 a、d、g 之间的关系就建立起来了。

同样，如果用私钥 d 加密，公钥 a 来解密，也是成立的。

g^d mod p = A
A^a mod p = g

// 同样可得出一样的等式
gᵃᵈ mod p = g

欧拉函数

欧拉函数 φ(x) 表示，≤ x 的正整数中，有多少个数与其互质。比如 x = 4，比 4 小的数有 1、2、3、4，其中 1、3 是质数，所以 φ(4) = 2。

它满足如下特性：

• 当 x 为质数时，与其互质的数有 x - 1 个。
• 当 x 可分解为两个质数乘积时，x = m * n，那么 φ(x) = (m-1)*(n-1)。

欧拉定理

欧拉定理如下，g 的 φ(p) 次幂，再模上 p，结果为 1。其中 g，p 互质。

g^φ(p) mod p = 1 

推导过程

下面我们将欧拉定理做如下处理：

1. 两边同时做 k 次幂运算，即 gᵏᵠ⁽ᴾ⁾ mod p = 1。
2. 两边同时乘以 g，得到 gᵏᵠ⁽ᴾ⁾⁺¹ mod p = g。
3. 再根据上面我们得出的公式 gᵃᵈ mod p = g，可得出 d = (kφ(p)+1)/a。这就是公私钥之间的关系。

当我们有了公钥 a，要计算出私钥 d，就很容易了，只需知道 φ(p)。而又要让 φ(p) 不易被破解，根据欧拉公式中提到的 φ(x) = (m-1)*(n-1)，可以取用很大的质数 m 和 n，p = m * n，这样破解起来就很困难了。

因为外部知道的是公钥 a、非常大的数 p，求出 d 需要将 p 进行质因数分解。而对超大数进行分解非常困难，当 p 的位数越长，安全性就越好。现在一般采用 2048 位，1024 位已经不太安全了。

加密数据必须是整数，且需小于 p。如果遇到字符串，可将其先进行编码分段来加密。