MENU

迪菲-赫尔曼密钥

October 21, 2018 • Read: 4089 • 密码学阅读设置

Diffie-Hellman算法是Whitefield Diffie和Martin Hellman在1976年公布的一种秘钥交换算法,它是一种建立秘钥的方法,而不是加密方法,所以秘钥必须和其他一种加密算法结合使用。这种秘钥交换技术的目的在于使两个用户安全的交换一个秘钥一遍后面的报文加密。

颜色密钥

假设爱丽丝和鲍勃是通信的双方,而伊芙是间谍。首先,我将用颜色来讲解该技巧是如何实现的。
该技巧基于两点:

  1. 混合两种颜色得到第三种颜色很容易
  2. 得到这种混合色,想在此基础上知道原来两种颜色就难了

朝一个方向容易,朝反方向难,这就是单向函数(one-way function)

首先,他们三个人公开对某种颜色达成一致,假设是黄色。

然后爱丽丝和鲍勃随机选取私有颜色(假设爱丽丝选择红色,鲍勃选择蓝色)混入到公共的黄色中(此时爱丽丝颜色为橙色,鲍勃颜色为绿色)

爱丽丝将混合色发给鲍勃,鲍勃将自己的混合色发给爱丽丝(混合色在发送过程中被间谍伊芙窃取)。

最后就是技巧的关键了,爱丽丝和鲍勃将各自的私有色加入到另一个人的混合色中,得到一种共享的秘密颜色

此时伊芙没办法确定这种颜色,她必须有一种私有颜色才能确定

离散对数问题

将上面的例子用到实际的数值传输过程中,我们需要一种正方向易反方向难的数值过程,于是我们找到了模算术。

简单的模算数例如 $46 mod 12 \equiv 10$

下面我们考虑用质数做模数,比如17,找到17的一个原根3,它具有如下的性质:$3^x mod 17$,取不同幂x时,结果会均匀分布在0~16中。

原根的定义是,如果g是p的原根,则有$g^{p-1} mod p \equiv 1$

那么此时就产生了一个单向函数,很容易求得$3^{29} mod 17 \equiv 12$,但反向已知12,只能采用暴力试错法,求出匹配的指数。这有多难?当然数字小会很容易,但是假如不是17,而是一个100位长的数,试错法基本上是不现实的。即使假设你拥有整个星球上的计算能力,也可能需要花上千年来尝试所有的可能性.

迪菲-赫尔曼密钥

现在的解决方案是这样的,首先三个人就质模数和原根达成一致,就以17和3为例。然后爱丽丝选择一个私有的随机数15,计算$3^{15} \mod 17 \equiv 6$,鲍勃也选择一个私有的随机数13,计算$3^{13} mod 17 \equiv 12$

接下来他俩互相交换计算后的数(伊芙会截获他俩交换的数)

最后是技巧的关键,爱丽丝将从鲍勃那获取的数幂上自己私有数的次方$12^{15}$然后mod 17,即$12^{15} mod 17 \equiv 10$。鲍勃也进行同样的操作,即$6^{13} mod 17 \equiv 10$

Last Modified: October 26, 2021
Archives Tip
QR Code for this page
Tipping QR Code
Leave a Comment