Diffie-Hellman密钥是如何交换的

Diffie-Hellman密钥交换（DH）^[1]是一种在公共信道上安全交换加密密钥的方法，也是Ralph Merkle最初设计并以Whitfield Diffie和Martin Hellman命名的第一个公钥协议之一。^[1] [2] DH是在密码领域实现的公钥交换最早的实际例子之一。

传统上，双方之间的安全加密通信要求他们首先通过一些安全的物理信道交换密钥，例如由可信赖的信使传送的纸质密钥列表。Diffie-Hellman密钥交换方法允许没有彼此先验知识的双方通过不安全的信道共同建立共享密钥。然后可以使用该密钥来使用对称密钥密码来加密随后的通信。

Diffie-Hellman被用来保护各种互联网服务。然而，2015年10月发布的研究表明，当时许多DH互联网应用中使用的参数不够强大，无法防止资金充足的攻击者（如大型*的安全服务）的妥协。^[3]

该计划最初是由惠特菲尔德的Diffie和Martin Hellman的于1976年出版，^[2] ，但在1997年据透露，詹姆斯·H·埃利斯，^[4] 克利福德·科克斯和马尔科姆·J·威廉森的GCHQ，英国信号情报机构此前曾^{[ 什么时候？]}显示了公钥密码学是如何实现的。^[5]

虽然Diffie-Hellman密钥协议本身是一个非认证密钥协商协议，它提供了各种认证协议的基础，并用于提供向前保密在传输层安全性的短暂的模式（称为EDH或DHE取决于密码套件）。

该方法不久之后通过遵循RSA的一种实现公钥加密使用非对称算法。

名称[ 编辑]

2002年，Hellman提出这个算法被称为Diffie-Hellman-Merkle密钥交换，以认识Ralph Merkle对公钥密码学发明的贡献（Hellman，2002），他写道：

这个系统已经被称为Diffie-Hellman密钥交换。这个系统最初是由迪菲和我在一篇论文中描述的，它是一个公开密钥分发系统，是由Merkle开发的一个概念，因此如果名字与它关联，应该被称为“Diffie-Hellman-Merkle密钥交换” 。我希望这个小小的讲坛可以帮助我们认识到默克尔对公钥密码学发明的平等贡献。 ^[6]

说明[ 编辑]

概述[ 编辑]

Diffie-Hellman密钥交换的想法的例证

Diffie-Hellman密钥交换在双方之间建立一个共享密钥，可用于秘密通信，在公共网络上交换数据。以下概念图通过使用颜色而不是非常大的数字来说明密钥交换的一般概念。

这个过程开始于让Alice和Bob双方同意一个不需要保密的任意开始颜色（但每次都应该不同）^[7]）。在这个例子中，颜色是黄色的。他们每个人都选择自己保留的秘密颜色。在这种情况下，橙色和蓝绿色。这个过程的关键部分是爱丽丝和鲍勃现在将他们的秘密颜色与他们相互共享的颜色混合在一起，分别产生橙棕色和淡蓝色混合物，然后公开交换这两种混合颜色。最后，两者都将从合作伙伴那里获得的颜色与他们自己的私人颜色混合在一起。其结果是最终的颜色混合物黄褐色，这是同伴的颜色混合物。

如果第三方倾听交流，他们在计算上很难确定秘密颜色。事实上，当使用大量数字而不是颜色时，现代超级计算机在合理的时间内执行此操作在计算上是昂贵的。（在密码学出版物中，窃听者通常被命名为夏娃。）

密码解释[ 编辑]

该协议的最简单和最初的实现使用乘法模 p 组，其中p是素数，g是原始根 模 p。以这种方式选择这两个值来确保所产生的共享秘密可以具有从1到p -1的任何值。这是协议的一个例子，非秘密值为蓝色，秘密值为红色。

1. Alice和Bob同意使用模数p = 23和基数g = 5（这是一个原始根模 23）。
2. Alice选择一个秘密整数a = 4，然后发送Bob A = g ^a mod p
   • A = 5 ⁴ mod 23 = 4
3. Bob选择一个秘密整数b = 3，然后发送Alice B = g ^b mod p
   • B = 5 ³ mod 23 = 10
4. Alice计算s = B ^a mod p
   • s =10 ⁴ mod23= 18
5. Bob计算s = A ^b mod p
   • s = 4 ³ mod23= 18
6. 爱丽丝和鲍勃现在分享一个秘密（数字18）。

Alice和Bob都达到了相同的值，因为在mod p下，

{\ displaystyle {\ color {Blue} A} ^ {\ color {red} b} {\ bmod {\ color {Blue} p}} = {\ color {Blue} g} ^ {\ color {Red} ab} {\ bmod {\ color {Blue} p}} = {\ color {Blue} g} ^ {\ color {Red} ba} {\ bmod {\ color {Blue} p}} = {\ color {Blue} B } ^ {\ color {Red} a} {\ bmod {\ color {Blue} p}}} ^[8]

进一步来说，

{\ displaystyle（{\ color {blue} g} ^ {\ color {red} a} {\ bmod {\ color {Blue} p}}）^ {\ color {Red} b} {\ bmod {\ color {蓝色}}} = {{颜色{蓝色} g} ^ {\颜色{红色} b} {\ bmod {\颜色{蓝色} p}}）^ {\颜色{红色} \ color {Blue} p}}}

注意只有a，b和（g ^ab mod p = g ^ba mod p）是保密的。所有其他值 - p，g，g ^a mod p和g ^b mod p - 都以明文形式发送。一旦Alice和Bob计算共享密钥，他们就可以使用它作为加密密钥，只有他们知道，才能通过相同的开放通信信道发送消息。

当然，为了保证这个例子的安全，需要a，b和p的更大的值，因为n mod 23 只有23个可能的结果。但是，如果p是至少600位数的素数，那么甚至最快的现代计算机无法找到一个给定的唯一摹，p和g ^ ^一个模p。这样的问题被称为离散对数问题。^[3]的计算克^一个模p被称为模幂并且即使对于大数量也可以有效地完成。注意，g不需要很大，实际上通常是一个小整数（如2,3，...）。

保密图[ 编辑]

下面的图表描绘了谁知道什么，再次以非秘密价值为蓝色，秘密价值为红色。这里Eve是一个窃听者 - 她看着Alice和Bob之间发送的内容，但是她不会改变他们的通信内容。

• g =公众（主要）基地，已知爱丽丝，鲍勃和夏娃。g = 5
• 对 Alice，Bob和Eve来说， p =公共（主）模数。p = 23
• a = Alice的私钥，只有Alice才知道。a = 6
• b = Bob只有Bob才知道的私钥。b = 15
• A = Alice，Bob和Eve所知的Alice的公钥。A = g ^a mod p = 8
• B = Bob的公钥，Alice，Bob和Eve都知道。B = g ^b mod p = 19

• 爱丽丝 已知 未知 p = 23   g = 5   a = 6 b A = 5 个 mod 23   A = 5 6 mod 23 = 8   B = 19   s =B a mod23   s =19 6 mod23= 2

  短发 已知 未知 p = 23   g = 5   b = 15 一个 B = 5 b mod 23   B = 5 15 mod 23 = 19   A = 8   s =A b mod23   s =8 15 mod23= 2

  前夕 已知 未知 p = 23   g = 5     a， b         A = 8， B = 19         小号

  
  

现在s是共享密钥，Alice和Bob都知道，但是不是 Eve。

注意：Alice应该很难解决Bob的私钥或者Bob解决Alice的私钥。如果爱丽丝不难解决鲍勃的私钥（反之亦然），夏娃可以简单地用自己的私钥/公钥替换自己的私钥，将鲍勃的公钥替换成她的私钥，生成一个假共享密钥，然后求解Bob的私钥（并用它来解决共享密钥，Eve可能试图选择一个公钥/私钥对，这将使她更容易解决Bob的私钥）。

这里给出了Diffie-Hellman的另一个示例（也使用实际使用的数字太小）。^[9]

有限循环群的推广[ 编辑]

这里是对协议的更一般的描述：^[10]

1. Alice和Bob同意在有限循环群 G ^顺序的Ñ和发电元件克在ģ。（这通常在协议的其余部分之前就已经完成了，g被假定为所有攻击者都知道）.G组是乘法写成的。
2. 爱丽丝选取一个随机自然数 一，其中1≤ 一个 < Ñ，并发送克^一个给Bob。
3. 鲍勃选取一个随机自然数b，这也是1≤ b < Ñ，并发送克^b给Alice。
4. 爱丽丝计算（g ^b）^a。
5. Bob计算（g ^a）^b。

Alice和Bob都拥有可用作共享密钥的组元素g ^ab。如果没有一个有效的算法来确定g ^ab给定g，g ^a和g ^b，则组G满足保密通信的必要条件。

例如，椭圆曲线Diffie-Hellman协议是使用椭圆曲线而不是整数模p的乘法群的变体。也已经提出了使用超椭圆曲线的变体。该超奇异中原衍密钥交换是已被设计成在量子计算机安全的一个Diffie-Hellman的变种。

与两方以上的运作[ 编辑]

Diffie-Hellman密钥协议并不局限于仅由两位参与者共享密钥。任何数量的用户都可以通过执行协议协议的迭代和交换中间数据（其本身不需要保密）来参与协议。例如，Alice，Bob和Carol可以参与如下的Diffie-Hellman协议，所有的操作都是模p：

1. 双方同意算法参数p和g。
2. 各方生成他们的私钥，分别命名为a，b和c。
3. Alice计算g ^a并将其发送给Bob。
4. Bob计算（g ^a）^b = g ^ab并将其发送给Carol。
5. Carol计算（g ^ab）^c = g ^abc并将其用作她的秘密。
6. Bob计算g ^b并将其发送给Carol。
7. Carol计算（g ^b）^c = g ^bc并将其发送给Alice。
8. Alice计算（g ^bc）^a = g ^bca = g ^abc并将其用作她的秘密。
9. Carol计算g ^c并将其发送给Alice。
10. Alice计算（g ^c）^a = g ^ca并将其发送给Bob。
11. 鲍勃计算（g ^ca）^b = g ^cab = g ^abc并将其用作他的秘密。

窃听者已经能够看到g ^a，g ^b，g ^c，g ^ab，g ^ac和g ^bc，但是不能使用这些的任何组合来有效地再现g ^abc。

为了把这个机制扩大到更大的群体，必须遵循两个基本原则：

• 从一个仅由g组成的“空”密钥开始，秘密是通过以任何顺序（第一次这样的求幂产生参与者自己的公钥）将每个参与者的私人指数提升一次而获得的。
• 任何中间值（有多达N -1个指数，其中N是组中参与者的数量）可以被公开揭示，但最终值（已经应用了所有N个指数）构成共享的秘密，因此决不能公开透露。因此，每个用户必须通过最后应用他们自己的私钥来获得他们的秘密副本（否则，最后的贡献者将没有办法将最终密钥传送给其接收者，因为最后的贡献者将会把密钥变成非常秘密小组希望保护）。

这些原则为参与者选择按键参与者的顺序提供了各种选择。最简单和最明显的解决方案是将N个参与者安排在一个圆圈中，并且将N个密钥围绕该圆圈旋转，直到最终每个密钥都由所有N个参与者（以其所有者结束）贡献，并且每个参与者贡献了N个密钥（以自己结束）。但是，这要求每个参与者执行N个模幂运算。

通过选择更优化的顺序，并依赖于一个事实，即密钥可以被复制，因此能够减少由每个参与者执行的模块化幂的数目日志₂（Ñ + 1）使用分而治之式方法，在这里给八个参与者：

1. 参与者A，B，C和D各执行一次取幂，得到g ^abcd ; 该值被发送到E，F，G和H.作为回报，参与者A，B，C，和d接收克^EFGH。
2. 参与者A和B各执行一次取幂，产生g ^efghab，将它们发送给C和D，而C和D执行相同的操作，产生g ^efghcd，并发送给A和B.
3. 参与者A进行求幂，得到克^efghcda，其发送给B; 同样，B将g ^efghcdb发送给A. C和D做类似的操作。
4. 参与者A执行一个最终的求幂，产生秘密g ^efghcdba = g ^abcdefgh，而B做相同的获得g ^efghcdab = g ^abcdefgh ; 再次，C和D也是这样做的。
5. 参与者E到H同时使用g ^abcd作为他们的出发点执行相同的操作。

一旦该操作已经完成了所有参与者将拥有秘密摹^ABCDEFGH，但每位参加者都表现只有四个模块化指数运算，而不是八个通过简单的圆形布置的暗示。

安全[ 编辑]

如果G和g被正确选择，该协议被认为对窃听者是安全的。特别是，G组的顺序必须很大，特别是如果同一组用于大量的业务。窃听者（“ Eve ”）必须解决Diffie-Hellman问题才能获得g ^ab。对于订单足够大的组织来说，目前这被认为是困难的。一个解决离散对数问题的高效算法将使得计算a或b变得容易，并且解决Diffie-Hellman问题，使得这个和其他许多公钥密码系统不安全。小特点的领域可能不太安全。^[11]

该订单的摹应具有防止利用大素因子Pohlig-Hellman算法来获得一个或b。因为这个原因，有时用Sophie Germain素数 q来计算p = 2 q + 1，称为安全素数，因为G的次数只能被2和q整除。那么有时选择g生成G的阶q子群，而不是G，从而得到g的勒让德符号^一个从来没有揭示的最低位一个。使用这种选择的协议是例如 IKEv2。^[12]

g通常是一个小整数，例如2.由于离散对数问题的随机自我还原性，小g与同组的任何其他发生器同样安全。

如果Alice和Bob使用的随机数发生器的输出不是完全随机的并且可以在一定程度上进行预测，那么Eve的任务就容易得多。

在原始描述中，Diffie-Hellman交换本身不提供通信方的认证，因此容易受到中间人攻击。马洛里（执行中间人攻击的主动攻击者）可以建立两个不同的密钥交换，一个与Alice和另一个与Bob，实际上伪装成Alice到Bob，反之亦然，允许她解密，加密，消息之间传递。请注意，Mallory必须继续处于中间位置，每次Alice和Bob进行通信时都会传送消息。如果她不在场，她以前的存在就会显露给爱丽丝和鲍勃。他们会知道，他们所有的私人谈话都被该频道的某个人截获和解码。

通常需要一种方法来认证彼此的通信方，以防止这种类型的攻击。可以使用诸如STS协议之类的Diffie-Hellman变体来避免这些类型的攻击。

对互联网流量的实际攻击[ 编辑]

在求解离散对数问题中通常最有效的数字域筛选算法由四个计算步骤组成。前三个步骤仅取决于组G的顺序，而不取决于期望有限日志的具体数目。^[13]事实证明，许多互联网流量使用少量的1024位或更少的组中的一个。^[7]通过预先计算最常见组的数字字段筛选的前三个步骤，攻击者只需要执行最后一个步骤，这比前三个步骤的计算花费少得多，以获得特定的对数。该僵局攻击利用这个漏洞攻击了各种各样的互联网服务，这些互联网服务允许使用订单是512位素数（所谓的出口等级）的组织。作者们需要几千个CPU核心来预先计算一个512位素数的数据。完成之后，使用两个18核Intel Xeon CPU可以在一分钟内解决单个对数。^[3]

根据Logjam攻击背后的作者估计，解决1024位素数的离散对数问题所需的预计算要困难得多，大约需要1亿美元，远远低于美国这样的大型情报机构的预算。国家安全局（NSA）。Logjam的作者推测，与广泛重用的1024位DH素数的预计算背后的NSA文件泄漏 NSA是能够打破目前的密码学大部分。^[3]

为了避免这些漏洞，作者推荐使用椭圆曲线密码术，对此没有类似的攻击。如果做不到这一点，他们建议的顺序，p的Diffie-Hellman组的，至少应为2048位。他们估计，2048位素数所需的预计算比1024位素数要困难10 ⁹。^[3]

如果NSA打破了Diffie-Hellman，但并没有推动美国站点升级到更长的密钥，那么这将是NSA的NOBUS不*安全漏洞的一个例子，NSA认为只有他们可以利用。

其他用途[ 编辑]

加密[ 编辑]

已经提出了基于Diffie-Hellman密钥交换的公钥加密方案。第一个这样的方案是ElGamal加密。一个更现代的变种是集成加密方案。

正向保密[ 编辑]

实现前向保密的协议为每个会话生成新的密钥对，并在会话结束时丢弃它们。Diffie-Hellman密钥交换是这种协议的常用选择，因为它的快速密钥生成。

密码认证密钥协议[ 编辑]

当Alice和Bob共享密码时，他们可以使用Diffie-Hellman 的密码认证密钥协议（PK）形式来防止中间人攻击。一个简单的方案是比较在通道两端独立计算的s连接的散列值。这些方案的一个特点是攻击者只能在每次迭代时与另一方测试一个特定的密码，所以系统提供了很好的安全性和相对较弱的密码。G.hn家庭网络标准所使用的ITU-T X.1035建议书描述了这种方法。

这种协议的一个例子是安全远程口令协议。

公钥[ 编辑]

也可以使用Diffie-Hellman作为公共密钥基础设施的一部分，允许Bob对消息进行加密，以便只有Alice能够对其进行解密，除了Bob拥有对Alice公钥的可信知识之外， 。Alice的公钥是{\ displaystyle（g ^ {a} {\ bmod {p}}，g，p）}。给她发消息，Bob选择一个随机b，然后发送Alice{\ displaystyle g ^ {b} {\ bmod {p}}} （未加密）以及用对称密钥加密的消息 {\ displaystyle（g ^ {a}）^ {b} {\ bmod {p}}}。只有Alice可以确定对称密钥，并因此解密消息，因为只有她有一个（私钥）。预先共享的公钥还可以防止中间人攻击。

实际上，Diffie-Hellman不是以这种方式使用的，RSA是主要的公钥算法。这主要是出于历史和商业的原因^{[ 引证需要 ]}，即RSA安全创建了一个证书授权机构，成为Verisign的密钥签名。Diffie-Hellman不能用来签署证书。然而，ElGamal和DSA签名算法在数学上与其相关，以及IPsec协议套件的MQV，STS和IKE组件用于保护Internet协议通信。