不安全信道下的 Diffie-Hellman 密钥交换协议

作者: , 共 1320 字 , 共阅读 0

迪菲-赫尔曼密钥交换( Diffie–Hellman key exchange ,简称「D–H」) 是一种安全协议。它可以让双方在完全没有对方任何预先信息的条件下通过不安全信道建立起一个密钥。这个密钥可以在后续的通讯中作为对称密钥来加密通讯内容。

1. 离散对数的数学概念

协议基于离散对数的概念:

如果\( a\)是素数\( p\)的一个原根,那么数值:

$$ a \mod p , a^2 \mod p, \cdots, a^{p-1} \mod p $$

是各不相同的整数,且以某种排列方式组成了从 1 到 p-1 的所有整数。

如果对于一个整数\( b\)和素数\( p\)的一个原根\( a\),可以找到一个唯一的指数\(i\),使得:

$$ b = a^i \mod p, 0 \leq i \leq p - 1 $$

那么指数\( i\)称为\( b\)的以\( a\)为基数的模\( p\)的离散对数。

Diffie-Hellman 算法的有效性依赖于计算离散对数的难度,其含义是:当已知大素数\( p\)和它的一个原根\( a\)后,对给定的\( b\),要计算 \( i\) ,被认为是很困难的,而给定\( i\) 计算\( b\) 却相对容易 。

2. 具体的 Diffie-Hellman 算法

假如用户 A 和用户 B 希望交换一个密钥。取素数\( p\)和整数\( a\)\( a\)\( p\) 的一个原根,公开\( a\)\( p\)

  • A 选择随机数\( X_A<p\),并计算\( Y_A=a^{X_A} \mod p\)
  • B 选择随机数\( X_B<p\),并计算\( Y_B=a^{X_B} \mod p\)

每一方都将 X 保密而将 Y 公开让另一方得到。

  • A 计算密钥:\( K=Y_B^{X_A} \mod p\)
  • B 计算密钥:\( K=Y_A^{X_B} \mod p\)

密钥的有效性:

$$K_B = Y_B^{X_A} = a^{X_BX_A} = a^{X_AX_B} = Y_A^{X_B} = K_A \mod p$$

由于\( X_A\)\( X_B\)是保密的,而第三方只有\( p\), \( a\), \( Y_B\)\( Y_A\)可以利用,只有通过取离散对数来确定密钥,但对于大的素数\( p\),计算离散对数是十分困难的。

3. 优势和缺陷

DH 协议可以让通信双方平等地协商密钥,而且可以很简单地扩充到多方协商。

该协议可以防止中间人偷窥,恶意中间人对数据流的截获并不会计算出双方协商出的密钥。但该协议无法完全防止中间人攻击。如果中间人仿冒 A ,和 B 协商一份密钥\( K_{AB}\);再仿冒 B 和 A 协商一份密钥\( K_{BA}\)。然后 A 发送给 B 的信息用\( K_{AB}\)加密,中间人截获解密后再用\( K_{BA}\)加密发送给 B ,此时 B 无法意识到信息被人查看。

因此,现代密码学中, DH 协议通常配合公钥体系( RSA 或者DSA)共同使用。协议双方会使用私钥签名,对方可以验证,从而防范中间人攻击。

Q. E. D.

类似文章:
比特币协议里使用了 ECDSA (椭圆曲线签名算法),我之前以为它和基于大数分解的 RSA 公钥密码体系差不多。这两天看了下维基百科,才发现它们之间的差异挺大。
现在越来越多的软件支持端到端加密,服务器和第三方即使获取所有网络流量,也无法查看具体数据内容,从数学和工程上提供安全性。
Tox 是一个开源的实时通信协议,不需要中央服务器,提供多种跨平台的客户端。
机器统治世界提到,随着科技的发展,我们可以直接用机器来替代政府。所谓机器统治世界,并不意味着机器是世界的主人。机器还是听命于人类,只不过以一种无法被干预的民主投票的方式。所以,机器统计世界的第一要解决的问题就是投票协议。
想起比多中心的匿名投票协议,有一种很简单的使用盲签名的投票协议,可以做到匿名投票。
机器统治世界,其中一个重要的部分便是安全计算。而这一领域的开创性工作便是姚期智先生的「姚氏百万富翁问题」。相关的工作发表于 1982 年 FOCS 上的的《Protocols for secure computations》
IT » 比特币
最近 bitcoin 很火,我也是最先从云风那里了解到的,后来发现李笑来&霍炬对其都有涉及。不过他们对其具体技术原理的描述还是不够细致,所以我自己把bitcoin wiki又重新看了一遍。 看完之后,疑惑挺多,我对这个体系远没有前面三位这么乐观。诚然,它会成为"Geeks "手中的玩物甚至灰色交易的工具,但要说的达到「一出天下反」的程度,那还需要解决一些技术和金融方面的问题。
英文是 communication complexity ,不知道该翻译成通信复杂性,还是通讯复杂性呢。这里先用通讯复杂性吧。这是一个理论计算机的子领域,在过去 30 年衍生了很多东西。它是我的研究的主要内容,这里简略介绍一下。
最近在配置 matrix synapse 时,才注意到现在配置一个 https 网站已经非常简单,而且 nginx 也非常好用。
现在越来越多的软件支持端到端加密,服务器和第三方即使获取所有网络流量,也无法查看具体数据内容,从数学和工程上提供安全性。