DH算法原理

DH算法原理

DH 是 Diffie-Hellman的首字母缩写，是Whitefield与Martin Hellman在1976年提出了一个的密钥交换协议。我个人倾向于称DH算法为 密钥协商协议而RSA算法是密钥交换算法。

本篇分为几个部分，第一个部分介绍一下密钥交换的场景；第二部分介绍一下DH算法的的步骤，以及由该算法引出的一些问题；第三部分开始讲数学原理。数学原理可能涉及到数论、抽象代数，本篇尽量在每个公式后面证明该公式的正确性。

简单场景&简单的密钥协商

先从一个应用场景说起：

Alice 和Bob想要在一个不安全的信道共享一个密钥，该密钥可被用来进行后续的其他的操作，并且仅被Alice和Bob所知，第三方无法得知。

一个简单的方法就是，现在全世界都是知道一个值 P=100。Alice生成随机值5，然后乘上P，接着发送Pa = 500给Bob；通样Bob生成随机值6，然后乘上P，接着发送Pb = 600给Alice。

这样，Alice 有 100，5 ，600，Bob有100，6,500。

Alice计算: 随机值5（自己私钥） * 600（对端的公钥） = 3000 等式1

Bob计算 : 随机值6（自己私钥） * 500（对端的公钥） = 3000 等式2

    这样 Alice就和Bob共享了一个值3000，还有谁知道3000这个值呢？我们知道Alice明文的将500发送到不安全信道，Bob明文的将600发送到不安全信道，这也就意味着第三方仅仅知道500 和 600，想要计算获得共享密钥，第三方要么获取到Alice的随机值然后拿它乘上600，要么获取到Bob的随机值然后拿它乘上500，这样才能获取到Alice和Bob的共享密钥。

    问题来了，如何获取到Alice的随机值呢？

    第三方知道，Alice发送的500是由P乘上Alice的随机值得到的，所以问题变成了求方程 x*100 = 500的解。一眼就能看出来，Alice的随机值是5。

上述方法很容易被破解的原因是P太简单了。P值再复杂点怎么样？

例如P = 0x123456781234567812345678

Pa  = 0xAD77D73E0BFC0E3E0BFC0E3D5E84370

Pb  = 0x4EF81E05A6A0F385A6A0F38557A8D58

显然，你不能一眼就求出方程 x*P = Pa 的解

    其实 Alice的随机数为 0x98765432, Bob的随机数为0x45681265。

但是这一切对于计算机来说还是太简单了。例如OpenSSL、Mbedtls等众多的开源库都提供了大数运算的API，计算Pa/P可能就几毫秒甚至几微秒的事情。

    所以怎么要让中间人难以从Pa或者Pb中分解得到Alice或Bob的随机数，而Alice和Bob又能轻松的通过P和随机数计算得到Pa和Pb，就成了设计这个算法的关键。从上面的例子可以看出，简单的乘法运算是不行的。

    一般来说上述所说的全世界都知道的值P称之为公钥，为Alice和Bob的随机数称之为私钥。

DH算法的一个例子

这里举例一个DH算法的例子。

例1：

设有这么一个二元组 (q, p) = (3, 7)

我们定义Alice和Bob这么一个运算：

（1）Alice 选择一个范围在[1, p-1]的随机数，为da= 5

（2）Alice 计算Pa = q^da mod p = 3^5 mod 7 = 5

（3）Bob选择一个范围在[1, p-1]的随机数，为db = 6

（4）Bob计算Pb = q^db mod p = 3^6 mod 7 = 1

（5）Alice和Bob交换Pa和Pb

（6）Alice计算共享密钥S = Pb ^da mod p = 1^5 mod 7 = 1

（7）Bob计算共享密钥S = Pa ^db mod p = 5^6 m 7 = 1

    至此，Alice和Bob能够共享一个密钥为1。中间人由于只得到了Pa=5和Pb=1，如果也想要得到S，要么获取da然后执行步骤6中的等式计算得到结果、要么获取db然后执行步骤7中的等式得到结果。而要知道da或者db，需要计算

    其实该算法的原理和上一部分中简单乘法及其类似，只是获取da或者db不是简单的方程式了，而是涉及到对数运算。对数运算被认为是“难”的，这个难建立在目前为止没有找到一个快速计算对数的算法，数学上没有证明这个算法是否存在。

    看到这肯定有一个问题，随便一个二元组(q, p)都可以参与运算吗？显然不行。

我们来看看如果随便一个(q, p)参与运算，会出现什么情况。

例2：

假设(q, p) = (7,15)，我们让Alice和Bob再来协商一遍

（1）Alice 选择一个范围在[1, p-1]的随机数，为da= 3

（2）Alice 计算Pa = q^da mod p =7^3 mod 15 = 13

（3）Bob选择一个范围在[1, p-1]的随机数，为db = 2

（4）Bob计算Pb = q^db mod p = 7^2 mod 15 = 4

（5）Alice和Bob交换Pa和Pb

（6）Alice计算共享密钥S = Pb ^da mod p = 4^3 mod 15 = 4

（7）Bob计算共享密钥S = Pa ^db mod p = 13^2 mod 15 = 4

看起来还是协商成功了，那问题在哪？

7^x mod 15：

7^1 mod 15 = 7

7^2 mod 15 = 4

7^3 mod 15 = 13

7^4 mod 15 = 1

7^5 mod 15 = 7

7^6 mod 15 = 4

7^7 mod 15 = 13

7^7 mod 15 = 1

......

    看到规律了吗？7^x mod 15的结果一共才4种，并且周期循环。

这也就意味着中间人获取到了Pb = 4，中间人不一定需要知道Alice原始的随机值（私钥）是什么，只要在[1 , 14]中随便选择一个满足7^x mod 15 = 13的值进行计算S = 4^7 mod 15 = 4^11 mod 15 = 4 都能正确计算共享密钥。换句话说，中间人不需要暴力遍历[1 , 14]中的所有数就能计算共享密钥。

    所以我们选择(b, p)的原则就是，G = b^x mod p,

当x遍历[1, p -1]时，G也遍历了一遍[1, p -1]，这样中间人即使暴力破解，在P很大的时候，暴力破解是非常难的。

DH背后的数学&DH算法证明

设 已知 二元组(q, p)

Alice 生成随机值a，计算q^a mod p = Ga

Bob  生成随机值b， 计算q^b mod p = Gb

Alice 计算Sa =Gb^a mod p

Bob 计算Sb = Ga^b mod p

我们需要证明Sa=Sb

Sa = Gb^a mod p

     = (q^b mod p)^a mod p

令q^b mod p = T，则q^b = kp + T，也即T = q^b - kp

Sa = (q^b mod p)^a mod p

= (T)^a mod p

=(q^b - kp)^a mod p

    由于对 (q^b - kp)^a展开，除了第一项为q^(ab)以及最后一项为(kp)^a，其余每一

项均存在p，所以计算(q^b - kp)^a mod p之后，只保留了第一项，即Sa = q^(ab) mod p

同理可正Sb = q^(ba) mod p = Sa

原根

    我们在上一节例二中讲到，我们选择的(q, p)尽可能的使得当x遍历[1, p -1]时，

b^x mod p也遍历了一遍[1, p -1]。我们就来介绍一下原根。

定义1：

当 m > 1, gcd(a, m) = 1，则使得 a^e mod m = 1成立的最小正整数e称作整数a

对模m的阶（或指数、乘法周期），记做ord(a)。若a的阶

,

则a称作为模m的原根。

例二中，7模15的阶是4。

那15有原根吗？ 显然，根据定义，找出所有和15互素的数，然后计算他们的

阶，阶无一例外均不是，故15不存在原根。

现在我们来看看原根的另一个定理，这个定理对于我们找打合适的(q, p)很重要。

定理1：

设m>1，gcd(a,m) = 1，则

a^0, a^1, a^2, ... a^ord(a)-1 模m两两不同余。

证明：反证法

如若存在K,L(L<K<ord(a)) 使得

a^K = a^L mod m

由于gcd (a , m)=1，即存在a的逆a^-1，故等式两边乘上a^(-L)

a^(k-l) = 1 mod m

即存在k-l,使得a^(k-l) = 1 mod m等式成立，而k-l < ord(a)，与阶的定义矛盾。故假设不成立。

定理1中a和m的关系，我们就可以用来当做DH算法中的(q,p)。