Diffie-Hellman

**迪菲 - 赫爾曼密鑰交換**（英語：Diffie–Hellman key exchange，縮寫為 D-H） 是一種安全協定。它可以讓雙方在完全沒有對方任何預先資訊的條件下通過不安全信道建立起一個金鑰。這個金鑰可以在後續的通訊中作為對稱金鑰來加密通訊內容。公鑰交換的概念最早由瑞夫・墨克（Ralph C. Merkle）提出，而這個密鑰交換方法，由惠特菲爾德・迪菲（Bailey Whitfield Diffie）和馬丁・赫爾曼（Martin Edward Hellman）在 1976 年首次發表。馬丁・赫爾曼曾主張這個密鑰交換方法，應被稱為**迪菲 - 赫爾曼 - 墨克密鑰交換**（英語：Diffie–Hellman–Merkle key exchange）。

迪菲－赫爾曼金鑰交換的同義詞包括:

* **迪菲－赫爾曼金鑰協商**
* **迪菲－赫爾曼金鑰建立**
* **指數金鑰交換**
* **迪菲－赫爾曼協定**

雖然迪菲－赫爾曼金鑰交換本身是一個匿名（無認證）的金鑰交換協定，它卻是很多認證協定的基礎。

## 該協定的歷史

迪菲－赫爾曼金鑰交換是在美國密碼學家惠特菲爾德・迪菲和馬丁・赫爾曼的合作下發明的，發表於 1976 年。它是第一個實用的在非保護信道中建立共享金鑰方法。它受到了瑞夫・墨克的關於公鑰分配工作的影響。約翰・吉爾（John Gill）提出了離散對數問題的應用。該方案首先被英國 GCHQ 的馬爾科姆・J・威廉森（Malcolm J. Williamson）在稍早的幾年前發明，但是 GCHQ 直到 1997 年才決定將其公開，這時在學術界已經沒有了研究這個演算法的熱潮了。

這個方法被發明後不久出現了 RSA，另一個進行公鑰交換的演算法。它使用了非對稱加密演算法。

2002 年，馬丁・赫爾曼寫到：

> 這個系統... 從此被稱為「迪菲－赫爾曼金鑰交換」。 雖然這個系統首先是在我和迪菲的一篇論文中描述的，但是這卻是一個公鑰交換系統，是墨克提出的概念，因此如果加上他的名字，這個系統實際上應該稱為「Diffie–Hellman–Merkle 金鑰交換」。我希望這個小小的講壇可以幫助我們認識到墨克對公鑰密碼學的同等重要的貢獻。
> 
> 

> The system...has since become known as Diffie–Hellman key exchange. While that system was first described in a paper by Diffie and me, it is a public key distribution system, a concept developed by Merkle, and hence should be called 'Diffie–Hellman–Merkle key exchange' if names are to be associated with it. I hope this small pulpit might help in that endeavor to recognize Merkle's equal contribution to the invention of public key cryptography. [1]
> 
> 

描述了這個演算法的美國專利第 4,200,770 號，已經於 1997 年 4 月 29 日後過期，專利檔案表明了 Hellman、Diffie 和 Merkle 是演算法的發明者。

## 描述

迪菲－赫爾曼通過公共信道交換一個資訊，就可以建立一個可以用於在公共信道上安全通信的共享秘密。

以下解釋它的過程（包括演算法的數學部分）：

最簡單，最早提出的這個協定使用一個質數 _p_ 的整數模 n 乘法群以及其原根 _g_。下面展示這個演算法，綠色表示非秘密資訊，**紅色粗體**表示秘密資訊：

愛麗絲和鮑伯最終都得到了同樣的值，因為在模 _p_ 下 $g^{ab}$ 和 $g^{ba}$ 相等。 注意 _a_, _b_ 和 _gab = gba_ mod _p_ 是秘密的。 其他所有的值 – _p_, _g_, _ga mod p_, 以及 _gb mod p_ – 都可以在公共信道上傳遞。 一旦愛麗絲和鮑伯得出了公共秘密，他們就可以把它用作對稱金鑰，以進行雙方的加密通訊，因為這個金鑰只有他們才能得到。
當然，為了使這個例子變得安全，必須使用非常大的 _a_, _b_ 以及 _p_， 否則可以實驗所有 $g^{ab}{\bmod {23}}$ 的可能取值 (總共有最多 22 個這樣的值，就算 _a_ 和 _b_ 很大也無濟於事)。 如果 _p_ 是一個至少 300 位的質數，並且 _a_ 和 _b_ 至少有 100 位長，那麼即使使用全人類所有的計算資源和當今最好的演算法也不可能從 _g_, _p_ 和 _ga_ mod _p_ 中計算出 _a_。這個問題就是著名的離散對數問題。注意 _g_ 則不需要很大，並且在一般的實踐中通常是 2 或者 5。IETF RFC3526 文件中有幾個常用的大質數可供使用。

以下是一個更為一般的描述:

1. 愛麗絲和鮑伯協商一個有限迴圈群 _G_ 和它的一個生成元 _g_。 （這通常在協定開始很久以前就已經規定好； _g_ 是公開的，並可以被所有的攻擊者看到。）
2. 愛麗絲選擇一個隨機自然數 _a_ 並且將 $g^{a}{\bmod {p}}$ 傳送給鮑伯。
3. 鮑伯選擇一個隨機自然數 _b_ 並且將 $g^{b}{\bmod {p}}$ 傳送給愛麗絲。
4. 愛麗絲 計算 $\left(g^{b}\right)^{a}{\bmod {p}}$ 。
5. 鮑伯 計算 $\left(g^{a}\right)^{b}{\bmod {p}}$ 。

愛麗絲和鮑伯就同時協商出群元素 $g^{ab}$ ，它可以被用作共享秘密。 $\left(g^{b}\right)^{a}$ 和 $\left(g^{a}\right)^{b}$ 因為群是乘法交換的。 (見冪.)

### 圖示

下面的圖示可以方便你理解每個資訊都只有誰知道。（伊芙是一個竊聽者 —— 她可以看到愛麗絲和鮑伯的通訊內容，但是無法改變它們）

* Let s = 共享金鑰。 s = 2
* Let a = 愛麗絲的私鑰。如 a = 6
* Let A = 愛麗絲的公鑰。如 A = ga mod p = 8
* Let b = 鮑伯的私鑰。如 b = 15
* Let B = 鮑伯的公鑰。如 B = gb mod p = 19
* Let g = 公共原根。如 g=5
* Let p = 公共質數。如 p = 23

注意：對愛麗絲來說解開鮑伯的私鑰或鮑伯要解開愛麗絲的私鑰應該都很困難。如果對愛麗絲來說解開鮑伯的私鑰不難的話（反之亦然），伊芙可以輕易地替換掉她自己的私鑰 / 公鑰對，把鮑伯的公鑰插到她自己的私鑰，產生出一個假的共享密鑰，並解開鮑伯的私鑰（然後用這個解開共享私鑰。伊芙可以試著選擇一個能讓她輕鬆解開鮑伯的私鑰的公鑰 / 私鑰對）。

## 安全性

在選擇了合適的 _G_ 和 _g_ 時，這個協定被認為是竊聽安全的。偷聽者（"Eve"）可能必須通過求解迪菲－赫爾曼問題來得到 _g_ab。在當前，這被認為是一個困難問題。如果出現了一個高效的解決離散對數問題的演算法，那麼可以用它來簡化 _a_ 或者 _b_ 的計算，那麼也就可以用來解決迪菲－赫爾曼問題，使得包括本系統在內的很多公鑰密碼學系統變得不安全。

_G_ 的階應當是一個素數，或者它有一個足夠大的素因子以防止使用 Pohlig–Hellman 演算法來得到 _a_ 或者 _b_。由於這個原因，一個索菲熱爾曼素數 _q_ 可以用來計算素數 _p=2q+1_，這樣的 _p_ 稱為安全素數，因為使用它之後 _G_ 的階只能被 2 和 _q_ 整除。_g_ 有時被選擇成 _G_ 的 _q_ 階子群的生成元，而不是 _G_ 本身的生成元，這樣 _ga_ 的勒讓德符號將不會顯示出 _a_ 的低位。

如果 Alice 和 Bob 使用的亂數生成器不能做到完全隨機並且從某種程度上講是可預測的，那麼 Eve 的工作將簡單的多。

臨時 DH（D-H Ephemeral，DHE）能夠提供前向安全性。

### 身分驗證

在最初的描述中，迪菲－赫爾曼金鑰交換本身並沒有提供通訊雙方的身分驗證服務，因此它很容易受到中間人攻擊。 一個中間人在信道的中央進行兩次迪菲－赫爾曼金鑰交換，一次和 Alice 另一次和 Bob，就能夠成功的向 Alice 假裝自己是 Bob，反之亦然。而攻擊者可以解密（讀取和儲存）任何一個人的資訊並重新加密資訊，然後傳遞給另一個人。因此通常都需要一個能夠驗證通訊雙方身分的機制來防止這類攻擊。

有很多種安全身分驗證解決方案使用到了迪菲－赫爾曼金鑰交換。當 Alice 和 Bob 共有一個公鑰基礎設施時，他們可以將他們的返回金鑰進行簽章，也可以像 MQV 那樣簽章 _g_a 和 _g_b；STS 以及 IPsec 協定的 IKE 組件已經成為了 Internet 協定的一部分；當 Alice 和 Bob 共享一個口令時，他們還可以從迪菲－赫爾曼演算法使用口令認證金鑰協商，類似於 ITU-T 的建議 X.1035。這已經被用作了 G.hn 的家庭網路標準。

## 參見

* 密碼學首頁
* 模算術
* 橢圓曲線迪菲 - 赫爾曼
* 公鑰密碼學
* ElGamal 加密演算法
* 迪菲－赫爾曼問題
* MQV
* 口令認證金鑰協商
* 前向安全性

## 參照

* Dieter Gollmann (2006). _Computer Security Second Edition_ West Sussex, England: John Wiley & Sons, Ltd.
* Non-Secret Encryption Using a Finite Field MJ Williamson, January 21, 1974.
* Thoughts on Cheaper Non-Secret Encryption （頁面存檔備份，存於網際網路檔案館） MJ Williamson, August 10, 1976.
* New Directions in Cryptography （頁面存檔備份，存於網際網路檔案館） W. Diffie and M. E. Hellman, IEEE Transactions on Information Theory, vol. IT-22, Nov. 1976, pp: 644–654.
* Cryptographic apparatus and method Martin E. Hellman, Bailey W. Diffie, and Ralph C. Merkle, U.S. Patent #4,200,770, 29 April 1980
* The History of Non-Secret Encryption JH Ellis 1987 (28K PDF file) (HTML version)
* The First Ten Years of Public-Key Cryptography （頁面存檔備份，存於網際網路檔案館） Whitfield Diffie, Proceedings of the IEEE, vol. 76, no. 5, May 1988, pp: 560–577 (1.9MB PDF file)
* Menezes, Alfred; van Oorschot, Paul; Vanstone, Scott (1997). _Handbook of Applied Cryptography_ Boca Raton, Florida: CRC Press. ISBN 0-8493-8523-7. (Available online （頁面存檔備份，存於網際網路檔案館）)
* Singh, Simon (1999) _The Code Book: the evolution of secrecy from Mary Queen of Scots to quantum cryptography_ New York: Doubleday ISBN 0-385-49531-5
* An Overview of Public Key Cryptography Martin E. Hellman, IEEE Communications Magazine, May 2002, pp:42–49. (123kB PDF file)

## 外部連結

* Oral history interview with Martin Hellman, Charles Babbage Institute, University of Minnesota. Leading cryptography scholar Martin Hellman discusses the circumstances and fundamental insights of his invention of public key cryptography with collaborators Whitfield Diffie and Ralph Merkle at Stanford University in the mid-1970s.
* RFC 2631 – _Diffie–Hellman Key Agreement Method_ E. Rescorla June 1999.
* _Summary of ANSI X9.42: Agreement of Symmetric Keys Using Discrete Logarithm Cryptography_ (64K PDF file) (Description of ANSI 9 Standards)
* Diffie–Hellman explained visually （頁面存檔備份，存於網際網路檔案館）
* Diffie–Hellman Key Exchange – A Non-Mathematician’s Explanation by Keith Palmgren
* Crypt::DH （頁面存檔備份，存於網際網路檔案館） Perl module from CPAN
* Hands-on Diffie–Hellman demonstration （頁面存檔備份，存於網際網路檔案館）
* C implementation using GNU Multiple Precision Arithmetic Library
* Diffie Hellman in 2 lines of Perl （頁面存檔備份，存於網際網路檔案館） (using dc)
* Smart Account Management (SAcct) （頁面存檔備份，存於網際網路檔案館） (using DH key exchange to derive session key)