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