查看“︁迪菲-赫爾曼密鑰交換”︁的源代码

<!-- {{unreferenced|time=2012-12-05T04:00:19+00:00}}-->{{Nofootnotes|time=2015-10-02}}
{{NoteTA
|G1 = IT
|G2 = Math
}}
'''迪菲-赫爾曼密鑰交換'''（{{lang-en|Diffie–Hellman key exchange}}，縮寫為D-H） 是一种[[安全协议]]。它可以让双方在完全没有对方任何预先信息的条件下通过不安全[[信道]]建立起一个[[密钥]]。这个密钥可以在后续的通讯中作为[[对称密钥]]来[[加密]]通讯内容。公鑰交換的概念最早由[[瑞夫·墨克]]（{{lang|en|Ralph C. Merkle}}）提出，而這個密鑰交換方法，由[[惠特菲爾德·迪菲]]（{{lang|en|Bailey Whitfield Diffie}}）和[[馬丁·赫爾曼]]（{{lang|en|Martin Edward Hellman}}）在1976年首次發表。馬丁·赫爾曼曾主張這個密鑰交換方法，應被稱為'''迪菲-赫爾曼-墨克密鑰交換'''（{{lang-en|Diffie–Hellman–Merkle key exchange}}）。

迪菲－赫尔曼密钥交换的同义词包括:
*'''迪菲－赫尔曼密钥协商'''
*'''迪菲－赫尔曼密钥建立'''
*'''指数密钥交换'''
*'''迪菲－赫尔曼协议'''

虽然迪菲－赫尔曼密钥交换本身是一个匿名（无认证）的[[密钥交换]]协议，它却是很多认证协议的基础。

==该协议的历史==
迪菲－赫尔曼密钥交换是在美國密碼學家[[惠特菲爾德·迪菲]]和[[馬丁·赫爾曼]]的合作下发明的，發表於1976年。它是第一个实用的在非保护信道中建立[[共享密钥]]方法。它受到了[[瑞夫·墨克]]的关于[[公开密钥加密|公钥分配]]工作的影响。{{tsl|en|John Gill (climber)|約翰·吉爾 (攀岩)|約翰·吉爾}}（{{lang|en|John Gill}}）提出了[[离散对数]]问题的应用。该方案首先被[[英国]][[GCHQ]]的{{tsl|en|Malcolm J. Williamson|馬爾科姆·J·威廉森}}（Malcolm J. Williamson）在稍早的几年前发明，但是GCHQ直到1997年才决定将其公开，这时在学术界已经没有了研究这个算法的热潮了。

这个方法被发明后不久出现了[[RSA加密演算法|RSA]]，另一个进行公钥交换的算法。它使用了[[公开密钥加密|非对称加密算法]]。

2002年，馬丁·赫爾曼写到：
<blockquote>这个系统...从此被称为「迪菲－赫尔曼密钥交换」。 虽然这个系统首先是在我和迪菲的一篇论文中描述的，但是这却是一个公钥交换系统，是墨克提出的概念，因此如果加上他的名字，这个系统实际上应该称为「Diffie–Hellman–Merkle密钥交换」。我希望这个小小的讲坛可以帮助我们认识到墨克对公钥密码学的同等重要的贡献。</blockquote>

<blockquote>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. [https://web.archive.org/web/20050118031258/http://www.comsoc.org/livepubs/ci1/public/anniv/pdfs/hellman.pdf]</blockquote>

描述了这个算法的{{US patent|4,200,770}}，已经於1997年4月29日後过期，專利文件表明了Hellman、Diffie和Merkle是算法的发明者。

==描述==

迪菲－赫尔曼通过公共信道交换一个信息，就可以建立一个可以用于在公共信道上安全通信的[[共享密鑰|共享秘密]]。

以下解释它的过程（包括算法的数学部分）：

[[Image:Diffie-Hellman-Schlüsselaustausch.svg|center|thumb|400px|Diffie–Hellman 密鑰交換]]

最简单，最早提出的这个协议使用一个[[素数|質數]]''p''的[[模n乘法群|整數模n乘法群]]以及其[[原根]]''g''。下面展示这个算法，<span style="color:green">绿色</span>表示非秘密信息，'''<span style="color:red">红色粗体</span>'''表示秘密信息：
{| border="0" cellspacing="0" cellpadding="2"
|
{| class="wikitable"
! colspan="3" | 愛麗絲
|-
| align="center" bgcolor="#D0D0D0" style="font-size: 90%;" | 秘密
| align="center" bgcolor="#D0D0D0" style="font-size: 90%;" | 非秘密 
| align="center" bgcolor="#D0D0D0" style="font-size: 90%;" | 计算
|-
| align="center" |
| align="center" | '''p, g'''
| align="center" |
|-
| align="center" | '''a'''
| align="center" | 
| align="center" |
|-
| align="center" | 
| align="center" | 
| align="center" | '''g<sup>a</sup>''' mod p
|-
| align="center" |
| align="center" | …
| align="center" |
|-
| align="center" | 
| align="center" | ('''g<sup>b</sup>''' mod p)'''<sup>a</sup>''' mod p
| align="center" |
|}
| valign="bottom" |
{| border="0" cellspacing="1" cellpadding="5"
| align="center" |
|-
| align="center" |
|-
| align="center" |
|-
| align="center" |
|-
| align="center" |
|-
| align="center" | '''<math>\rightarrow</math>'''
|-
| align="center" | '''<math>\leftarrow</math>'''
|-
| align="center" | '''='''
|}
|
{| class="wikitable"
! colspan="3" | 鮑伯
|-
| align="center" bgcolor="#D0D0D0" style="font-size: 90%;" | 计算
| align="center" bgcolor="#D0D0D0" style="font-size: 90%;" | 非秘密
| align="center" bgcolor="#D0D0D0" style="font-size: 90%;" | 秘密
|-
| align="center" |
| align="center" | '''p, g'''
| align="center" |
|-
| align="center" |
| align="center" | 
| align="center" | '''b'''
|-
| align="center" | 
| align="center" | …
| align="center" |
|-
| align="center" | '''g<sup>b'''</sup> mod p
| align="center" | 
| align="center" |
|-
| align="center" | 
| align="center" | ('''g<sup>a</sup>''' mod p)'''<sup>b</sup>''' mod p
| align="center" |
|}
|
# [[愛麗絲與鮑伯]]协定使用 ''<span style="color:green">p</span>''=<span style="color:green">23</span>以及base ''<span style="color:green">g</span>''=<span style="color:green">5</span>.
# 愛麗絲选择一个秘密整数'''''<span style="color:red">a</span>'''''='''<span style="color:red">6</span>'''，计算<span style="color:green">A</span> = ''<span style="color:green">g</span><sup>'''<span style="color:red">a</span>'''</sup>'' mod ''<span style="color:green">p</span>''并发送给鮑伯。
#* <span style="color:green">A</span> = <span style="color:green">5</span><sup>'''<span style="color:red">6</span>'''</sup> mod <span style="color:green">23</span> = <span style="color:green">8</span>.
# 鮑伯选择一个秘密整数'''''<span style="color:red">b</span>'''''='''<span style="color:red">15</span>'''，计算<span style="color:green">B</span> = ''<span style="color:green">g</span><sup>'''<span style="color:red">b</span>'''</sup>'' mod ''<span style="color:green">p</span>''并发送给愛麗絲。
#* <span style="color:green">B</span> = <span style="color:green">5</span><sup>'''<span style="color:red">15</span>'''</sup> mod <span style="color:green">23</span> = <span style="color:green">19</span>.
# 愛麗絲计算'''<span style="color:red">s</span>''' = ''<span style="color:green">B</span>'' ''<sup>'''<span style="color:red">a</span>'''</sup>'' mod ''<span style="color:green">p</span>''
#*<span style="color:green">19</span><sup>'''<span style="color:red">6</span>'''</sup> mod <span style="color:green">23</span> = '''<span style="color:red">2</span>'''.
# 鮑伯计算'''<span style="color:red">s</span>''' = ''<span style="color:green">A</span>'' ''<sup>'''<span style="color:red">b</span>'''</sup>'' mod ''<span style="color:green">p</span>''
#*<span style="color:green">8</span><sup>'''<span style="color:red">15</span>'''</sup> mod <span style="color:green">23</span> = '''<span style="color:red">2</span>'''.
|}
愛麗絲和鮑伯最终都得到了同样的值，因为在模''p''下<math>g^{ab}</math>和<math>g^{ba}</math> 相等。 注意''a'', ''b'' 和 ''g<sup>ab</sup> = g<sup>ba</sup>'' mod ''p'' 是秘密的。  其他所有的值 – ''p'', ''g'', ''g<sup>a</sup> mod p'', 以及 ''g<sup>b</sup> mod p'' – 都可以在公共信道上传递。 一旦愛麗絲和鮑伯得出了公共秘密，他们就可以把它用作对称密钥，以进行双方的加密通讯，因为这个密钥只有他们才能得到。当然，为了使这个例子变得安全，必须使用非常大的''a'', ''b'' 以及 ''p''， 否则可以实验所有<math>g^{ab} \bmod{23}</math>的可能取值（总共有最多22个这样的值，就算''a''和''b''很大也无济于事）。 如果 ''p'' 是一个至少 300 位的质数，并且''a''和''b''至少有100位长，那么即使使用全人类所有的计算资源和当今最好的算法也不可能从''g'', ''p''和''g<sup>a</sup>'' mod ''p'' 中计算出 ''a''。这个问题就是著名的[[离散对数|离散对数问题]]。注意''g''则不需要很大，并且在一般的实践中通常是2或者5。IETF RFC3526 文档中有几个常用的大质数可供使用。

以下是一个更为一般的描述:

# 愛麗絲和鮑伯协商一个有限[[循环群]] ''G'' 和它的一个[[群的生成集|生成元]] ''g''。  （这通常在协议开始很久以前就已经规定好； ''g''是公开的，并可以被所有的攻击者看到。） 
# 愛麗絲选择一个[[随机数生成器|随机]][[自然数]] ''a'' 并且将<math>g^{a} \bmod{p}</math>发送给鮑伯。
# 鮑伯选择一个随机自然数 ''b'' 并且将<math>g^{b} \bmod{p}</math>发送给愛麗絲。
# 愛麗絲 计算<math>\left ( g^{b} \right )^{a} \bmod{p}  </math>。
# 鮑伯 计算<math>\left ( g^{a} \right )^{b} \bmod{p}  </math>。

愛麗絲和鮑伯就同时协商出群元素<math>g^{ab}</math>，它可以被用作共享秘密。<math>\left ( g^{b} \right )^{a}</math>和<math>\left ( g^{a} \right )^{b}</math>因为群是[[乘法交换律|乘法交换]]的。 (见[[幂]].)

===图示===

下面的图示可以方便你理解每个信息都只有谁知道。（[[爱丽丝与鲍伯|伊芙]]是一个窃听者——她可以看到愛麗絲和鮑伯的通讯内容，但是无法改变它们）

* Let s = 共享密钥。 s = 2

* Let a = 愛麗絲的私钥。如 a = 6
* Let A = 愛麗絲的公钥。如 A = g<sup>a</sup> mod p = 8
* Let b = 鮑伯的私钥。如 b = 15
* Let B = 鮑伯的公钥。如 B = g<sup>b</sup> mod p = 19
* Let g = 公共原根。如 g=5

* Let p = 公共质数. 如 p = 23

{| border="0" cellspacing="0" cellpadding="2"
| valign="top" |
{| class="wikitable"
! colspan="2" | 愛麗絲
|-
| align="center" | 知道
| align="center" | 不知道
|-
| p = 23
|
|-
| base g = 5
|
|-
| a = 6
| 
|-
|
| b = 15
|-
| A = 5<sup>6</sup> mod 23 = 8
|
|-
| B = 5<sup>b</sup> mod 23 = 19
|
|-
| s = 19<sup>6</sup> mod 23 = 2
|
|-
| s = 8<sup>b</sup> mod 23 = 2
|
|-
| s = 19<sup>6</sup> mod 23 = 8<sup>b</sup> mod 23
|
|-
| s = 2
|
|}
| valign="top" | 
{| class="wikitable"
! colspan="2" | 鮑伯
|-
| align="center" | 知道
| align="center" | 不知道
|-
| p = 23
|
|-
| base g = 5
|
|-
|
| a = 6
|-
| b = 15
| 
|-
| B = 5<sup>15</sup> mod 23 = 19
|
|-
| A = 5<sup>a</sup> mod 23 = 8
|
|-
| s = 8<sup>15</sup> mod 23 = 2
|
|-
| s = 19<sup>a</sup> mod 23 = 2
|
|-
| s = 8<sup>15</sup> mod 23 = 19<sup>a</sup> mod 23
|
|-
| s = 2
|
|}
| valign="top" | 
{| class="wikitable"
! colspan="2" | 伊芙
|-
| align="center" | 知道
| align="center" | 不知道
|-
| p = 23
|
|-
| base g = 5
|
|-
|
| a = 6
|-
|
| b = 15
|-
| A = 5<sup>a</sup> mod 23 = 8
| 
|-
| B = 5<sup>b</sup> mod 23 = 19
|
|-
| s = 19<sup>a</sup> mod 23
|
|-
| s = 8<sup>b</sup> mod 23
|
|-
| s = 19<sup>a</sup> mod 23 = 8<sup>b</sup> mod 23
|
|-
|
| s = 2
|}
|}

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

==安全性==
在选择了合适的''G''和''g''时，这个协议被认为是窃听安全的。偷听者伊芙可能必须通过求解[[迪菲－赫尔曼问题]]来得到''g''<sup>''ab''</sup>。在当前，这被认为是一个困难问题。如果出现了一个高效的解决[[离散对数问题]]的算法，那么可以用它来简化''a''或者''b''的计算，那么也就可以用来解决迪菲－赫尔曼问题，使得包括本系统在内的很多公钥密码学系统变得不安全。

''G''的[[群论|阶]]应当是一个素数，或者它有一个足够大的素因子以防止使用[[Pohlig–Hellman算法]]来得到''a''或者''b''。由于这个原因，一个[[索菲热尔曼素数]] ''q''可以用来计算素数''p=2q+1''，这样的''p''称为[[安全素数]]，因为使用它之后''G''的阶只能被2和''q''整除。''g''有时被选择成''G''的''q''阶子群的生成元，而不是''G''本身的生成元，这样''g<sup>a</sup>''的[[勒让德符号]]将不会显示出''a''的低位。

如果Alice和Bob使用的[[随机数生成器]]不能做到完全随机并且从某种程度上讲是可预测的，那么Eve的工作将简单的多。

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

===身份验证===
在最初的描述中，迪菲－赫尔曼密钥交换本身并没有提供通讯双方的[[身份验证]]服务，因此它很容易受到[[中间人攻击]]。 一个中间人在信道的中央进行两次迪菲－赫尔曼密钥交换，一次和Alice另一次和Bob，就能够成功的向Alice假装自己是Bob，反之亦然。而攻击者可以解密（读取和存储）任何一个人的信息并重新加密信息，然后传递给另一个人。因此通常都需要一个能够验证通讯双方身份的机制来防止这类攻击。

有很多种安全身份验证解决方案使用到了迪菲－赫尔曼密钥交换。当Alice和Bob共有一个[[公钥基础设施]]时，他们可以将他们的返回密钥进行签名，也可以像[[MQV]]那样签名''g''<sup>''a''</sup>和''g''<sup>''b''</sup>；[[Station-to-Station protocol|STS]]以及[[IPsec]]协议的[[因特网密钥交换|IKE]]组件已经成为了[[Internet协议]]的一部分；当Alice和Bob共享一个口令时，他们还可以从迪菲－赫尔曼算法使用[[口令认证密钥协商]]，类似于[[ITU-T]]的建议[[X.1035]]。这已经被用作了[[G.hn]]的家庭网络标准。

==参见==
* [[Portal:密码学|密码学主页]]
* [[模算术]]
* [[椭圆曲线迪菲-赫尔曼]]
* [[公钥密码学]]
* [[ElGamal加密算法]]
* [[迪菲－赫尔曼问题]]
* [[MQV]]
* [[口令认证密钥协商]]
* [[前向安全性]]

==引用==
* Dieter Gollmann (2006).  ''Computer Security Second Edition'' West Sussex, England: John Wiley & Sons, Ltd.
* [https://web.archive.org/web/20080906162911/http://www.mirrors.wiretapped.net/security/info/reference/cesg-publications/History/secenc.pdf Non-Secret Encryption Using a Finite Field] MJ Williamson, [[January 21]], 1974.
* [http://www.fi.muni.cz/usr/matyas/lecture/paper3.pdf Thoughts on Cheaper Non-Secret Encryption] {{Wayback|url=http://www.fi.muni.cz/usr/matyas/lecture/paper3.pdf |date=20170810081436 }} MJ Williamson, [[August 10]], 1976.
* [http://citeseer.ist.psu.edu/340126.html New Directions in Cryptography] {{Wayback|url=http://citeseer.ist.psu.edu/340126.html |date=20080627023651 }} W. Diffie and M. E. Hellman, IEEE Transactions on Information Theory, vol. IT-22, Nov. 1976, pp: 644–654.
* {{US patent|4200770|Cryptographic apparatus and method}} Martin E. Hellman, Bailey W. Diffie, and Ralph C. Merkle, U.S. Patent #4,200,770, [[29 April]] 1980
* [https://web.archive.org/web/20080807183435/http://www.cesg.gov.uk/site/publications/media/ellis.pdf The History of Non-Secret Encryption] [[James H. Ellis|JH Ellis]] 1987 (28K PDF file) ([https://web.archive.org/web/20101127035626/http://jya.com/ellisdoc.htm HTML version])
* [http://cr.yp.to/bib/1988/diffie.pdf The First Ten Years of Public-Key Cryptography] {{Wayback|url=http://cr.yp.to/bib/1988/diffie.pdf |date=20110514094708 }} Whitfield Diffie, Proceedings of the IEEE, vol. 76, no. 5, May 1988, pp: 560–577 (1.9MB PDF file)
* [[Alfred Menezes|Menezes, Alfred]]; [[Paul van Oorschot|van Oorschot, Paul]]; [[Scott Vanstone|Vanstone, Scott]] (1997).  ''[[Handbook of Applied Cryptography]]'' Boca Raton, Florida: CRC Press. ISBN 0-8493-8523-7. ([http://www.cacr.math.uwaterloo.ca/hac/ Available online] {{Wayback|url=http://www.cacr.math.uwaterloo.ca/hac/ |date=20050307081354 }})
* [[Simon Singh|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
* [https://web.archive.org/web/20050118031258/http://www.comsoc.org/livepubs/ci1/public/anniv/pdfs/hellman.pdf An Overview of Public Key Cryptography] Martin E. Hellman, IEEE Communications Magazine, May 2002, pp:42–49. (123kB PDF file)

==外部链接==
*[http://www.cbi.umn.edu/oh/display.phtml?id=353 Oral history interview with Martin Hellman]{{dead link|date=2018年1月 |bot=InternetArchiveBot |fix-attempted=yes }}, [[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.
* [http://csrc.nist.gov/encryption/kms/summary-x9-42.pdf ''Summary of ANSI X9.42: Agreement of Symmetric Keys Using Discrete Logarithm Cryptography'']{{dead link|date=2018年4月 |bot=InternetArchiveBot |fix-attempted=yes }} (64K PDF file) ([https://web.archive.org/web/20040816210145/http://www.rsasecurity.com/rsalabs/node.asp?id=2306 Description of ANSI 9 Standards])
* [http://www.xml-dev.com/blog/2009/04/diffie-hellman-key-exchange.html Diffie–Hellman explained visually] {{Wayback|url=http://www.xml-dev.com/blog/2009/04/diffie-hellman-key-exchange.html |date=20120113201111 }}
* [https://web.archive.org/web/20100324054439/http://www.netip.com/articles/keith/diffie-helman.htm Diffie–Hellman Key Exchange – A Non-Mathematician’s Explanation] by Keith Palmgren
* [http://search.cpan.org/search?query=Crypt%3A%3ADH&mode=module Crypt::DH] {{Wayback|url=http://search.cpan.org/search?query=Crypt%3A%3ADH&mode=module |date=20170305002204 }} [[Perl]] module from [[CPAN]]
* [http://ds9a.nl/tmp/dh.html Hands-on Diffie–Hellman demonstration] {{Wayback|url=http://ds9a.nl/tmp/dh.html |date=20190625142720 }}
* [https://web.archive.org/web/20080627113318/http://oldpiewiki.yoonkn.com/cgi-bin/moin.cgi/DiffieHellmanKeyExchange C implementation using GNU Multiple Precision Arithmetic Library]
* [http://www.cypherspace.org/adam/rsa/perl-dh.html Diffie Hellman in 2 lines of Perl] {{Wayback|url=http://www.cypherspace.org/adam/rsa/perl-dh.html |date=20191102010221 }} (using [[dc (computer program)|dc]])
* [http://code.google.com/p/sacct/ Smart Account Management (SAcct)] {{Wayback|url=http://code.google.com/p/sacct/ |date=20170411011722 }} (using DH key exchange to derive session key)

{{密碼學|public-key}}

[[Category:密鑰合意協議]]
[[Category:公钥密码学]]