DH密鑰交換非對稱加密

迪菲－赫爾曼密鑰交換（diffie–hellman key exchange，簡稱“d–h”） 是一種安全協定。

它可以讓雙方在完全沒有對方任何預先資訊的條件下通過不安全信道建立起一個密鑰。這個密鑰可以在後續的通訊中作為對稱密鑰來加密通訊内容。

離散對數的概念：

原根：如果a是素數p的一個原根，那麼數值：

            amodp，a^2 modp，…，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 卻相對容易。

diffie-hellman算法：

假如使用者a和使用者b希望交換一個密鑰。

取素數p和整數a，a是p的一個原根，公開a和p。

a選擇随機數xa<p，并計算ya=a^xa mod p。

b選擇随機數xb<p，并計算yb=a^xb mod p。

每一方都将x保密而将y公開讓另一方得到。

a計算密鑰的方式是：k=(yb) ^xa modp

b計算密鑰的方式是：k=(ya) ^xb modp

證明：

                     (yb)^ xa mod p = (a^xb modp)^ xa mod p

                         = (a^xb)^ xa mod p = (a^xa) ^xb mod p   

(<-- 密鑰即為 a^(xa*xb) mod p)

                         =(a^xa modp)^ xb mod p= (ya) ^xb mod p

由于xa和xb是保密的，而第三方隻有p、a、yb、ya可以利用，隻有通過取離散對數來确定密鑰，但對于大的素數p，計算離散對數是十分困難的。

例子：

假如使用者alice和使用者bob希望交換一個密鑰。

取一個素數p =97和97的一個原根a=5。

alice和bob分别選擇秘密密鑰xa=36和xb=58，并計算各自的公開密鑰：

ya=a^xa mod p=5^36 mod 97=50

yb=a^xb mod p=5^58 mod 97=44

alice和bob交換了公開密鑰之後，計算共享密鑰如下：

alice：k=(yb) ^xa mod p=44^36 mod 97=75

bob：k=(ya) ^xb mod p=50^58 mod 97=75 

當然，為了使這個例子變得安全，必須使用非常大的xa, xb 以及p， 否則可以實驗所有的可能取值。(總共有最多97個這樣的值, 就算xa和xb很大也無濟于事)。

如果 p 是一個至少 300 位的質數，并且xa和xb至少有100位長， 那麼即使使用全人類所有的計算資源和當今最好的算法也不可能從a, p和a^(xa*xb) mod p 中計算出 xa*xb。

這個問題就是著名的離散對數問題。注意g則不需要很大, 并且在一般的實踐中通常是2或者5。

在最初的描述中，迪菲－赫爾曼密鑰交換本身并沒有提供通訊雙方的身份驗證服務，是以它很容易受到中間人攻擊。 

一個中間人在信道的中央進行兩次迪菲－赫爾曼密鑰交換，一次和alice另一次和bob，就能夠成功的向alice假裝自己是bob，反之亦然。

而攻擊者可以解密（讀取和存儲）任何一個人的資訊并重新加密資訊，然後傳遞給另一個人。是以通常都需要一個能夠驗證通訊雙方身份的機制來防止這類攻擊。

有很多種安全身份驗證解決方案使用到了迪菲－赫爾曼密鑰交換。例如當alice和bob共有一個公鑰基礎設施時，他們可以将他們的傳回密鑰進行簽名。