密码学专题 - 密钥交换算法

10. 密钥交换算法

10.1 Diffie-Hellman 算法

Diffie-Hellman 算法是第一个公开密钥算法，早在 1976 年就发明了。其安全性源于在有限域上计算离散对数比计算指数更为困难。Diffie-Hellman 算法能够用于密钥分配 (Alice 和 Bob 能用它产生秘密密钥)，但是它不能用于加密或解密消息。

数学原理很简单。首先，Alice 和 Bob 协商一个大的素数 和 ， 是模 的本原元。这两个整数不必是秘密的，故 Alice 和 Bob 可以通过即使是不安全的途径协商它们。它们可在一组用户中公用。

协议如下：

1. Alice 选取一个大的随机整数 ，并发送给 Bob：。
2. Bob 选取一个大的随机整数 ，并发送给 Alice：。
3. Alice 计算 。
4. Bob计算 。

和 都等于 。即使线路上的窃听者也不可能计算出这个值，他们只知道 、、、。除非他们计算离散对数，恢复 、，否则无济于事。因此 是 Alice 和 Bob 独立计算的秘密密钥。

和 的选取对系统的安全性有很大的影响。 也应该是一个素数。最重要的是 应该很大：因为系统的安全性取决于与 同样长度的数的因子分解的难度。可以选择任何满足模 的本原元 ，没有理由不选择所能选择的最小 —— 通常只是个 1 位数 (实际上 不必是素数，但它必须能产生一个大的模 的乘法组子群)。

10.2 三方或多方 Diffie-Hellman

Diffie-Hellman 密钥交换协议很容易扩展到三人或更多的人。在下例中，Alice、Bob 和 Carol 一起产生秘密密钥。

1. Alice 选取一个大的随机整数 ，并发送给 Bob：。
2. Bob 选取一个大的随机整数 ，并发送给 Carol：。
3. Carol 选择一个大的随机整数 ，并发送给 Alice：。
4. Alice 发送给 Bob：。
5. Bob 发送给 Carol：。
6. Carol 发送给 Alice：''。
7. Alice 计算 。
8. Bob 计算 。
9. Carol 计算 。

秘密密钥 ，没有其他人能计算出 值，这个协议很容易扩展到四人或更多的人中，只是增加更多的人和增加计算的轮数。

项目源代码

项目源代码会逐步上传到 Github，地址为 https://github.com/windstamp。

Contributor

1. Windstamp, https://github.com/windstamp