[科普中国]-Diffie-Hellman密钥交换算法

相关知识

离散对数的概念：

原根：如果a是素数p的一个原根，那么数值：

amodp，a^2modp，…，a^(p-1)modp

是各不相同的整数，且以某种排列方式组成了从1到p-1的所有整数。

离散对数：如果对于一个整数b和素数p的一个原根a，可以找到一个唯一的指数i，使得：

b=（a的i次方）modp其中0≦i≦p-1

那么指数i称为b的以a为基数的模p的离散对数。

Diffie-Hellman算法的有效性依赖于计算离散对数的难度，其含义是：当已知大素数p和它的一个原根a后，对给定的b，要计算i，被认为是很困难的，而给定i计算b却相对容易1。

算法原理设 A, B 两方进行通信前需要交换密钥，首先 A, B 共同选取 p 和 a 两个素数，其中 p 和 a 均公开。之后 A 选择一个自然数 Xa，计算出 Ya，Xa 保密，Ya 公开；同理，B 选择 Xb 并计算出 Yb，其中 Xb 保密，Yb 公开。之后 A 用 Yb 和 Xa 计算出密钥 K，而 B 用 Ya 和 Xb 计算密钥 K，流程如下：

+-------------------------------------------------------------------+

Global Pulic Elements

p prime number

a prime number, a

+-------------------------------------------------------------------+

User A Key Generation

Select private Xa Xa

Calculate public Ya Ya = a^Xa mod p

+-------------------------------------------------------------------+

User B Key Generation

Select private Xb Xb

Calculate public Yb Yb = a^Xb mod p

+-------------------------------------------------------------------+

Calculation of Secret Key by User A

Secret Key K K = Yb^Xa mod p

+-------------------------------------------------------------------+

Calculation of Secret Key by User B

Secret Key K K = Ya^Xb mod p

+-------------------------------------------------------------------+

下面证明，A 和 B 计算出来的密钥 K 相同。

K = Yb^Xa mod p = (a^Xb mod p)^Xa mod p = a^(Xa * Xb) mod p

根据上述求模公式 = (a^Xa mod p)^Xb mod p = Ya^Xb mod p

上面一共出现了 a, p, Xa, Ya, Xb, Yb, K 共 7 个数，其中：

公开的数：a, p, Ya, Yb

非公开数：Xa, Xb, K

通常情况下，a 一般为 2 或 5，而 p 的取值非常大，至少几百位，Xa 和 Xb 的取值也非常大，其复杂度至少为O(p^0.5)。对于攻击者来说，已知 Ya，Xa 的求解非常困难，同理 Xb 的求解也很困难，所以攻击者难以求出 K，所以 DH 能够保证通信双方在透明的信道中安全的交换密钥。下图非常形象的描述密钥交换流程：

应用DH在TLS中的应用

DH算法作为一种密钥协商机制，可以用于TLS协议当中。

如果在DH交互过程中Alice和Bob始终使用相同的私钥，就会导致后续产生的共享密钥是一样的，如果有嗅探者截获通信双方的所有数据，由于都是同一个密钥加密所得，一旦被破解，后续的通信将全部暴露。

为了保证安全性，必须引入前向保密，即Forward Secrecy。其基本实现思路就是在Alice和Bob在选择各自的私钥是引入随机性，也印证了那句话：要用发展的眼光看问题，不能一成不变2。

事实上FS在诸多加密协议中应用广泛，比如IKEv2和802.11i密钥分发中的4-way握手，无一不引入此方法。

那么问题来了，TLS中哪一个才是最安全的cipher呢？就目前而言，最安全的三个候选者如下：

TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA384_P521

TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA384_P384

TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA384_P256