迪菲-赫爾曼密鑰交換

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

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

迪菲－赫爾曼密鑰協商
迪菲－赫爾曼密鑰建立
指數密鑰交換
迪菲－赫爾曼協議

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

該協議的歷史

迪菲－赫爾曼密鑰交換是在美國密碼學家惠特菲爾德·迪菲和馬丁·赫爾曼的合作下發明的，發表於1976年。它是第一個實用的在非保護信道中建立共享密鑰方法。它受到了瑞夫·墨克的關於公鑰分配工作的影響。約翰·吉爾（英語：John Gill (climber)）（John Gill）提出了離散對數問題的應用。該方案首先被英國 GCHQ的馬爾科姆·J·威廉森（英語：Malcolm J. Williamson）（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是算法的發明者。

描述

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

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

Diffie–Hellman 密鑰交換

最簡單，最早提出的這個協議使用一個質數p的整數模n乘法群以及其原根g。下面展示這個算法，綠色表示非秘密信息，紅色粗體表示秘密信息：

愛麗絲
秘密	非秘密	計算
	p, g
a
		g^a mod p
	…
	(g^b mod p)^a mod p

$\rightarrow$

$\leftarrow$

=

鮑伯
計算	非秘密	秘密
	p, g
		b
	…
g^b mod p
	(g^a mod p)^b mod p

愛麗絲與鮑伯協定使用 p=23以及base g=5.
愛麗絲選擇一個秘密整數a=6，計算A = g^a mod p並發送給鮑伯。
- A = 5⁶ mod 23 = 8.
鮑伯選擇一個秘密整數b=15，計算B = g^b mod p並發送給愛麗絲。
- B = 5¹⁵ mod 23 = 19.
愛麗絲計算s = B ^a mod p
- 19⁶ mod 23 = 2.
鮑伯計算s = A ^b mod p
- 8¹⁵ mod 23 = 2.

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

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

愛麗絲和鮑伯協商一個有限循環群 G 和它的一個生成元 g。（這通常在協議開始很久以前就已經規定好； g是公開的，並可以被所有的攻擊者看到。）
愛麗絲選擇一個隨機自然數 a 並且將 $g^{a}{\bmod {p}}$ 發送給鮑伯。
鮑伯選擇一個隨機自然數 b 並且將 $g^{b}{\bmod {p}}$ 發送給愛麗絲。
愛麗絲計算 $\left(g^{b}\right)^{a}{\bmod {p}}$ 。
鮑伯計算 $\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 = g^a mod p = 8
Let b = 鮑伯的私鑰。如 b = 15
Let B = 鮑伯的公鑰。如 B = g^b mod p = 19
Let g = 公共原根。如 g=5

Let p = 公共質數. 如 p = 23

愛麗絲
知道	不知道
p = 23
base g = 5
a = 6
	b = 15
A = 5⁶ mod 23 = 8
B = 5^b mod 23 = 19
s = 19⁶ mod 23 = 2
s = 8^b mod 23 = 2
s = 19⁶ mod 23 = 8^b mod 23
s = 2

鮑伯
知道	不知道
p = 23
base g = 5
	a = 6
b = 15
B = 5¹⁵ mod 23 = 19
A = 5^a mod 23 = 8
s = 8¹⁵ mod 23 = 2
s = 19^a mod 23 = 2
s = 8¹⁵ mod 23 = 19^a mod 23
s = 2

伊芙
知道	不知道
p = 23
base g = 5
	a = 6
	b = 15
A = 5^a mod 23 = 8
B = 5^b mod 23 = 19
s = 19^a mod 23
s = 8^b mod 23
s = 19^a mod 23 = 8^b mod 23
	s = 2

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

安全性

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

G的階應當是一個素數，或者它有一個足夠大的素因子以防止使用Pohlig–Hellman算法來得到a或者b。由於這個原因，一個索菲熱爾曼素數 q可以用來計算素數p=2q+1，這樣的p稱為安全素數，因為使用它之後G的階只能被2和q整除。g有時被選擇成G的q階子群的生成元，而不是G本身的生成元，這樣g^a的勒讓德符號將不會顯示出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的家庭網絡標準。

參見

引用

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)