密码学专题

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

2020-05-10 本文已影响0人 furnace

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

10. 密钥交换算法

10.1 Diffie-Hellman 算法

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

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

协议如下：

Alice 选取一个大的随机整数 $x$ ，并发送给 Bob： $X=g^x \ mod \ n$ 。
Bob 选取一个大的随机整数 $y$ ，并发送给 Alice： $Y=g^y \ mod \ n$ 。
Alice 计算 $k = Y^x \ mod \ n$ 。
Bob计算 $k' = X^y \ mod \ n$ 。

$k$ 和 $k'$ 都等于 $g^{xy} \ mod \ n$ 。即使线路上的窃听者也不可能计算出这个值，他们只知道 $n$ 、 $g$ 、 $X$ 、 $Y$ 。除非他们计算离散对数，恢复 $x$ 、 $y$ ，否则无济于事。因此 $k$ 是 Alice 和 Bob 独立计算的秘密密钥。

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

10.2 三方或多方 Diffie-Hellman

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

Alice 选取一个大的随机整数 $x$ ，并发送给 Bob： $X=g^x \ mod \ n$ 。
Bob 选取一个大的随机整数 $y$ ，并发送给 Carol： $Y=g^y \ mod \ n$ 。
Carol 选择一个大的随机整数 $z$ ，并发送给 Alice： $Z=g^z \ mod \ n$ 。
Alice 发送给 Bob： $Z' = Z^x \ mod \ n$ 。
Bob 发送给 Carol： $X' = X^y \ mod \ n$ 。
Carol 发送给 Alice：' $Y' = Y^z \ mod \ n$ '。
Alice 计算 $k = Y'^x \ mod \ n$ 。
Bob 计算 $k = Z'^y \ mod \ n$ 。
Carol 计算 $k = X'^z \ mod \ n$ 。

秘密密钥 $k = g^{xyz} \ mod \ n$ ，没有其他人能计算出 $k$ 值，这个协议很容易扩展到四人或更多的人中，只是增加更多的人和增加计算的轮数。

项目源代码

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

Contributor

Windstamp, https://github.com/windstamp

上一篇下一篇

猜你喜欢

热点阅读