DH(Diffie–Hellman)算法简介

本文最后更新于:2022年5月1日 晚上

〇、前言

DH 是 Diffie-Hellman 的首字母缩写,是 Whitefield 与 Martin Hellman 在 1976 年提出了一个的密钥协商协议,其安全性源于在有限域上计算离散对数。该算法可以使两个用户之间安全地交换一个密钥,但不能用于加密或解密信息

一、原理

维基百科:DH 算法

  1. Alice 和 Bob 首先约定好公开的一种颜色,比如黄色
  2. Alice 和 Bob 各自挑选出一种私密的颜色,比如橙色和青色
  3. Alice 和 Bob 各自将两种颜色混合起来
  4. 双方交换混合后的颜色
  5. Alice 和 Bob 各自将自己的私密颜色再次混入得到的颜色中
  6. 现在 Alice 和 Bob 得到了一种相同的颜色,这种颜色是由一份黄色、一份橙色、一份青色混合而来,但外界无法得知

颜色混合是一种 “不可逆” 的操作,当双方交换颜色时,尽管我们知道他们交换的颜色都是由一份黄色和另一份其他颜色混合得到的,但我们还是无法或者很难得到他们的私密颜色

DH 秘钥交换算法的原理非常相似,也是利用了数学上的一个“不可逆”的运算,就是离散对数

二、离散对数

乘方得逆运算称为对数运算,比如已知 $7^x = 49$,那么可知 $x = log_749 = 2$。即使在数字很大的时候,对数运算也非常容易

但如果是计算 $7^x\ mod\ 13 = 8$,求 $x$,那就不那么容易了,这个过程称为 “离散对数”。离散对数的运算在数字很大时几乎是不可能的,DH 算法就是利用了这种特性来设计的

公式里的 mod 是取模运算,取模运算有几条基本的定律如下:

$$(a+b)\ mod\ P = (a\ mod\ P + b\ mod\ P)\ mod\ P $$

$$(a*b)\ mod\ P = (a\ mod\ P * b\ mod\ P)\ mod\ P$$

$$(a^b)\ mod\ P = ((a\ mod\ P)^b)\ mod\ P$$

根据上面的公式,可以推导出一个非常重要的公式:

$$(G^{a*b})\ mod\ P = (G^a\ mod\ P)^b\ mod\ P = (G^b\ mod\ P)^a\ mod\ P$$

三、DH 算法

根据离散对数的知识,我们可以向上面交换颜色那样设计出一个秘密交换数字的流程出来

  1. A 和 B 首先约定两个公开的质数 p 和 g

  2. A 和 B 各自随机产生两个数 a, b,作为自己的私钥

  3. 各自计算出自己的公钥 A, B

    $A = g^a\ mod\ p$

    $B = g^b\ mod\ p$

  4. 交换公钥 A, B

  5. 计算出加密用的密钥S

    $S_a=B^a\ mod\ p=(g^b\ mod\ p)^a\ mod\ p=g^{a*b}\ mod\ p$

    $S_b=A^b\ mod\ p=(g^a\ mod\ p)^b\ mod\ p=g^{a*b}\ mod\ p$

最终两个人得到的秘密数字都是 $g^{ab}\ mod\ p$,窃听者仅从 p、g、A、B 四个公开信息中,无法计算出这个秘密数字

举个例子,假如 $p=23$,$g=5$,Alice 选取的秘密数字 $a=6$,那么 $A=5^6\ mod\ 23=8$,Bob 选取的秘密数字是 $b=15$,那么 $B=5^{15}\ mod\ 23=19$,交换 A 和 B 后,Alice 计算出的密钥 $S_a=19^6\ mod\ 23=2$,Bob计算出的密钥 $S_b=8^{15}\ mod\ 23=2$

实际运算中如果需要生成 128bit 的密钥,那么 p 的值必需是 128bit 的质数。由于有模运算的存在,最终获得的密钥并不会大于 p,所以 p 值通常取 128bit 数字中最大的一个质数,g 可以随便设置为一个小的质数

需要注意的是,为了防止应用优化算法计算上述问题,质数 p 不是随便选择 的,需要符合一定的条件。

随机数 a、b 的生成算法也应当使结果尽可能随机,不能出现可预测的规律,否则会使破解变的容易。

通过上述计算过程也可以看出 DH 算法不仅可以应用在 2 方通信的情况,如果 多方通信,也可以使用该算法

四、缺点

DH 密钥交换算法 无法验证对方身份,所以 DH 密钥交换算法 不能抵御中间人攻击

DH 算法中间人攻击原理:

从其原理之中可以看出,a、b 值并没有什么关系,a、b 不能证明通信双方 Alice 与 Bob 的身份,这使得中间人攻击可以轻易产生。

假设一个攻击者 Tom,当 Alice 向 Bob 发送 g、p、A 时,Tom 截获了信息,并(假装自己是 Bob)向 Alice 发送了 $T=g^t\ mod\ p$,其中 t 是 Tom 的私钥。同时 Tom(假装自己是 Alice)向 Bob 发送 g、p,$T=g^t\ mod\ p$,这样 Bob 以为这是 Alice 发过来的,就向 T 发送了 $B=g^b\ mod\ p$

在 Alice 与 Tom 之间,创建的密钥就是 $S_{ta}=g^{at}\ mod\ p$,两方密钥相同

在 Tom 与 Bob 之间,创建的密钥就是 $S_{tb}=g^{tb}\ mod\ p$,两方密钥相同

这样,密钥创建完成,Alice 与 Bob 都认为自己与对方分享了只有他们两人所知的密钥,实际上并不是。当 Alice 想要发信息给 Bob 时,Alice 就会将信息用 $S_{ta}=g^{at}\ mod\ p$ 加密后发出,消息 Bob 无法解密,但会被 Tom 收到并解密。Tom 可以选择扣留信息,也可以篡改信息后使用 $S_{tb}=g^{tb}\ mod\ p$ 加密后发给 Bob,Bob 会认为这是 Alice 发来的消息

解决:

可以采用数据签名技术解决中DH密钥交换过程中可能存在的中间人攻击

五、参考链接

  1. DH密钥交换(Diffie–Hellman key exchange)算法笔记
  2. 一个简单的DH密钥协商算法的实现
  3. Diffie–Hellman key exchange
  4. 关于Diffie-Hellman密钥协商机制以及中间人攻击

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!