Diffie-Hellman密钥是如何交换的

时间:2022-02-06 18:22:31

Diffie-Hellman密钥交换DH[1]是一种在公共信道上安全交换加密密钥的方法,也是Ralph Merkle最初设计并以Whitfield DiffieMartin 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密钥交换的想法的例证

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

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

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

密码解释编辑]

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

  1. Alice和Bob同意使用模数p = 23和基数g = 5(这是一个原始根模 23)。
  2. Alice选择一个秘密整数a = 4,然后发送Bob A = a mod p
    • A = 5 4 mod 23 = 4
  3. Bob选择一个秘密整数b = 3,然后发送Alice B = b mod p
    • B = 5 3 mod 23 = 10
  4. Alice计算s = a mod p
    • s =10 4 mod23= 18
  5. Bob计算s = b mod p
    • s = 4 3 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}}}Diffie-Hellman密钥是如何交换的 [8]

进一步来说,

{\ displaystyle({\ color {blue} g} ^ {\ color {red} a} {\ bmod {\ color {Blue} p}})^ {\ color {Red} b} {\ bmod {\ color {蓝色}}} = {{颜色{蓝色} g} ^ {\颜色{红色} b} {\ bmod {\颜色{蓝色} p}})^ {\颜色{红色} \ color {Blue} p}}}Diffie-Hellman密钥是如何交换的

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

当然,为了保证这个例子的安全,需要abp的更大的值,因为n mod 23 只有23个可能的结果。但是,如果p是至少600位数的素数,那么甚至最快的现代计算机无法找到一个给定的唯一pg ^ 一个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. 爱丽丝计算(ba
  5. Bob计算(ab

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

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

与两方以上的运作编辑]

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

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

窃听者已经能够看到abcabacbc,但是不能使用这些的任何组合来有效地再现abc

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

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

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

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

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

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

安全编辑]

如果Gg被正确选择,该协议被认为对窃听者是安全的特别是,G组的顺序必须很大,特别是如果同一组用于大量的业务。窃听者(“ Eve ”)必须解决Diffie-Hellman问题才能获得ab对于订单足够大的组织来说,目前这被认为是困难的。一个解决离散对数问题的高效算法将使得计算ab变得容易,并且解决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 9[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)}Diffie-Hellman密钥是如何交换的给她发消息,Bob选择一个随机b,然后发送Alice{\ displaystyle g ^ {b} {\ bmod {p}}}Diffie-Hellman密钥是如何交换的 (未加密)以及用对称密钥加密的消息 {\ displaystyle(g ^ {a})^ {b} {\ bmod {p}}}Diffie-Hellman密钥是如何交换的只有Alice可以确定对称密钥,并因此解密消息,因为只有她有一个(私钥)。预先共享的公钥还可以防止中间人攻击。

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