DH 是 Diffie-Hellman的首字母縮寫，是Whitefield與Martin Hellman在1976年提出了一個的密鑰交換協(xié)議。我個人傾向于稱DH算法為 密鑰協(xié)商協(xié)議而RSA算法是密鑰交換算法。
本篇分為幾個部分，第一個部分介紹一下密鑰交換的場景；第二部分介紹一下DH算法的的步驟，以及由該算法引出的一些問題；第三部分開始講數(shù)學(xué)原理。數(shù)學(xué)原理可能涉及到數(shù)論、抽象代數(shù)，本篇盡量在每個公式后面證明該公式的正確性。
簡單場景&簡單的密鑰協(xié)商
先從一個應(yīng)用場景說起：
Alice 和Bob想要在一個不安全的信道共享一個密鑰，該密鑰可被用來進(jìn)行后續(xù)的其他的操作，并且僅被Alice和Bob所知，第三方無法得知。
一個簡單的方法就是，現(xiàn)在全世界都是知道一個值 P=100。Alice生成隨機(jī)值5，然后乘上P，接著發(fā)送Pa = 500給Bob；通樣Bob生成隨機(jī)值6，然后乘上P，接著發(fā)送Pb = 600給Alice。
這樣，Alice 有 100，5 ，600，Bob有100，6,500。
Alice計算: 隨機(jī)值5（自己私鑰） * 600（對端的公鑰） = 3000 等式1
Bob計算 : 隨機(jī)值6（自己私鑰） * 500（對端的公鑰） = 3000 等式2
這樣 Alice就和Bob共享了一個值3000，還有誰知道3000這個值呢？我們知道Alice明文的將500發(fā)送到不安全信道，Bob明文的將600發(fā)送到不安全信道，這也就意味著第三方僅僅知道500 和 600，想要計算獲得共享密鑰，第三方要么獲取到Alice的隨機(jī)值然后拿它乘上600，要么獲取到Bob的隨機(jī)值然后拿它乘上500，這樣才能獲取到Alice和Bob的共享密鑰。
問題來了，如何獲取到Alice的隨機(jī)值呢？
第三方知道，Alice發(fā)送的500是由P乘上Alice的隨機(jī)值得到的，所以問題變成了求方程 x*100 = 500的解。一眼就能看出來，Alice的隨機(jī)值是5。
上述方法很容易被破解的原因是P太簡單了。P值再復(fù)雜點(diǎn)怎么樣？
例如P = 0x123456781234567812345678
Pa = 0xAD77D73E0BFC0E3E0BFC0E3D5E84370
Pb = 0x4EF81E05A6A0F385A6A0F38557A8D58
顯然，你不能一眼就求出方程 x*P = Pa 的解
其實(shí) Alice的隨機(jī)數(shù)為 0x98765432, Bob的隨機(jī)數(shù)為0x45681265。
但是這一切對于計算機(jī)來說還是太簡單了。例如OpenSSL、Mbedtls等眾多的開源庫都提供了大數(shù)運(yùn)算的API，計算Pa/P可能就幾毫秒甚至幾微秒的事情。
所以怎么要讓中間人難以從Pa或者Pb中分解得到Alice或Bob的隨機(jī)數(shù)，而Alice和Bob又能輕松的通過P和隨機(jī)數(shù)計算得到Pa和Pb，就成了設(shè)計這個算法的關(guān)鍵。從上面的例子可以看出，簡單的乘法運(yùn)算是不行的。
一般來說上述所說的全世界都知道的值P稱之為公鑰，為Alice和Bob的隨機(jī)數(shù)稱之為私鑰。
DH算法的一個例子
這里舉例一個DH算法的例子。
例1：
設(shè)有這么一個二元組 (q, p) = (3, 7)
我們定義Alice和Bob這么一個運(yùn)算：
（1）Alice 選擇一個范圍在[1, p-1]的隨機(jī)數(shù)，為da= 5
（2）Alice 計算Pa = q^da mod p = 3^5 mod 7 = 5
（3）Bob選擇一個范圍在[1, p-1]的隨機(jī)數(shù)，為db = 6
（4）Bob計算Pb = q^db mod p = 3^6 mod 7 = 1
（5）Alice和Bob交換Pa和Pb
（6）Alice計算共享密鑰S = Pb ^da mod p = 1^5 mod 7 = 1
（7）Bob計算共享密鑰S = Pa ^db mod p = 5^6 m 7 = 1
至此，Alice和Bob能夠共享一個密鑰為1。中間人由于只得到了Pa=5和Pb=1，如果也想要得到S，要么獲取da然后執(zhí)行步驟6中的等式計算得到結(jié)果、要么獲取db然后執(zhí)行步驟7中的等式得到結(jié)果。而要知道da或者db，需要計算
其實(shí)該算法的原理和上一部分中簡單乘法及其類似，只是獲取da或者db不是簡單的方程式了，而是涉及到對數(shù)運(yùn)算。對數(shù)運(yùn)算被認(rèn)為是“難”的，這個難建立在目前為止沒有找到一個快速計算對數(shù)的算法，數(shù)學(xué)上沒有證明這個算法是否存在。
看到這肯定有一個問題，隨便一個二元組(q, p)都可以參與運(yùn)算嗎？顯然不行。
我們來看看如果隨便一個(q, p)參與運(yùn)算，會出現(xiàn)什么情況。
例2：
假設(shè)(q, p) = (7,15)，我們讓Alice和Bob再來協(xié)商一遍
（1）Alice 選擇一個范圍在[1, p-1]的隨機(jī)數(shù)，為da= 3
（2）Alice 計算Pa = q^da mod p =7^3 mod 15 = 13
（3）Bob選擇一個范圍在[1, p-1]的隨機(jī)數(shù)，為db = 2
（4）Bob計算Pb = q^db mod p = 7^2 mod 15 = 4
（5）Alice和Bob交換Pa和Pb
（6）Alice計算共享密鑰S = Pb ^da mod p = 4^3 mod 15 = 4
（7）Bob計算共享密鑰S = Pa ^db mod p = 13^2 mod 15 = 4
看起來還是協(xié)商成功了，那問題在哪？
7^x mod 15：
7^1 mod 15 = 7
7^2 mod 15 = 4
7^3 mod 15 = 13
7^4 mod 15 = 1
7^5 mod 15 = 7
7^6 mod 15 = 4
7^7 mod 15 = 13
7^7 mod 15 = 1
......
看到規(guī)律了嗎？7^x mod 15的結(jié)果一共才4種，并且周期循環(huán)。
這也就意味著中間人獲取到了Pb = 4，中間人不一定需要知道Alice原始的隨機(jī)值（私鑰）是什么，只要在[1 , 14]中隨便選擇一個滿足7^x mod 15 = 13的值進(jìn)行計算S = 4^7 mod 15 = 4^11 mod 15 = 4 都能正確計算共享密鑰。換句話說，中間人不需要暴力遍歷[1 , 14]中的所有數(shù)就能計算共享密鑰。
所以我們選擇(b, p)的原則就是，G = b^x mod p,
當(dāng)x遍歷[1, p -1]時，G也遍歷了一遍[1, p -1]，這樣中間人即使暴力破解，在P很大的時候，暴力破解是非常難的。
DH背后的數(shù)學(xué)&DH算法證明
設(shè) 已知 二元組(q, p)
Alice 生成隨機(jī)值a，計算q^a mod p = Ga
Bob 生成隨機(jī)值b， 計算q^b mod p = Gb
Alice 計算Sa =Gb^a mod p
Bob 計算Sb = Ga^b mod p
我們需要證明Sa=Sb
Sa = Gb^a mod p
= (q^b mod p)^a mod p
令q^b mod p = T，則q^b = kp + T，也即T = q^b - kp
Sa = (q^b mod p)^a mod p
= (T)^a mod p
=(q^b - kp)^a mod p
由于對 (q^b - kp)^a展開，除了第一項為q^(ab)以及最后一項為(kp)^a，其余每一
項均存在p，所以計算(q^b - kp)^a mod p之后，只保留了第一項，即Sa = q^(ab) mod p
同理可正Sb = q^(ba) mod p = Sa
原根
我們在上一節(jié)例二中講到，我們選擇的(q, p)盡可能的使得當(dāng)x遍歷[1, p -1]時，
b^x mod p也遍歷了一遍[1, p -1]。我們就來介紹一下原根。
定義1：
當(dāng) m > 1, gcd(a, m) = 1，則使得 a^e mod m = 1成立的最小正整數(shù)e稱作整數(shù)a
對模m的階（或指數(shù)、乘法周期），記做ord(a)。若a的階
,
則a稱作為模m的原根。
例二中，7模15的階是4。
那15有原根嗎？ 顯然，根據(jù)定義，找出所有和15互素的數(shù)，然后計算他們的
階，階無一例外均不是，故15不存在原根。
現(xiàn)在我們來看看原根的另一個定理，這個定理對于我們找打合適的(q, p)很重要。
定理1：
設(shè)m>1，gcd(a,m) = 1，則
a^0, a^1, a^2, ... a^ord(a)-1 模m兩兩不同余。
證明：反證法
如若存在K,L(L<K<ord(a)) 使得
a^K = a^L mod m
由于gcd (a , m)=1，即存在a的逆a^-1，故等式兩邊乘上a^(-L)
a^(k-l) = 1 mod m
即存在k-l,使得a^(k-l) = 1 mod m等式成立，而k-l < ord(a)，與階的定義矛盾。故假設(shè)不成立。
定理1中a和m的關(guān)系，我們就可以用來當(dāng)做DH算法中的(q,p)。
RFC 3526 中給出了推薦的DH參數(shù)。
