DH算法

DH 算法

DH 是Diff-Hellman首字母的缩写,是由Whitefield与Martin Hellman在1976年提出的一个密钥交换协议。它可以确保共享KEY穿越不安全的网络,共享的KEY可以用于后续的加密操作。最初了解到这个方法是在IPsec的IKE流程中。

简单的场景

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。

1
2
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值再复杂点怎么样?

1
2
3
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算法的例子

设有这么一个二元组 (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) = (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很大的时候,暴力破解是非常难的。

数学基础

首先是为什么通过这种方法最后双方能够协商出相同的结果

算法证明

设 已知 二元组(q, P)

Alice 生成随机值a,计算
$$
g^{a}modp=Ga
$$

Bob 生成随机值b, 计算
$$
g^{b}modp=Gb
$$

Alice 计算Sa
$$
S_{a}=G^{a}_{b}modP
$$

Bob 计算
$$
S_{b}=G^{b}_{a}modP
$$

我们需要证明
$$ Sa=Sb $$

$$
\begin{aligned}S_{a}=G^{a}_{b}modP\
=\left( q^{b}modP\right) ^{a}\
=\left( q^{b}-kP\right) ^{a}modP\end{aligned}
$$

对于$ \left( q^{b}-kP\right) ^{a} $展开,除去第一项和其他都含P,所以 $S_{a}=q^{ba}$。同理可以求的Sb,两个值都是 $q^{ba}$

原根

参考

原文链接