Diffie-Hellman

N1Key2023/5/12大约 2 分钟

Diffie-Hellman算法

背景： Diffie-Hellman 算法由 Whitfield Diffie 和 Martin Hellman 提出，该算法的安全性也是基于一般有限域上的离散对数问题的难解性。

算法描述：

（1）假设Alice和Bob之间要建立一个共享密钥 $k$ 。Alice和Bob首先选定一个大素数 $p$ ，并选 $g$ 为乘法群 $F_{p}^{*}$ 中的一个生成元。

（2） Alice 选取一个私钥 $a$ (整数)： $1 ⩽ a ⩽ p - 2$ ，计算 $A = g^{a} m o d p$ 。发送 $A$ 给Bob。

（3） Bob选取一个私钥 b(整数)： $1 ⩽ b ⩽ p - 2$ ，计算 $B = g^{b} m o d p$ 。发送 $B$ 给 Alice。

（4） Alice 计算 $k = B^{a}$ $m o d$ $p$

（5） Bob 计算 $k = A^{b}$ $m o d$ $p$

因为 $B^{a} = (g^{b})^{a} = g^{a b} = (g^{a})^{b} = A^{b}$ $m o d$ $p$ ，Alice 与 Bob 计算得到的 $k$ 是相同的。这样的 $k$ 可以作为通信的共享密钥

由于 $a$ 与 $b$ 是保密的，所以即使攻击者知道了 $p 、 g 、 A 、 B$ ，也很难获得 Alice 与 Bob 的共享密钥 $k$ 。因为攻击者要想获得 $k$ ，则需要先解决离散对数问题 $A = g^{x}$ $m o d$ $p$ 或 $B = g^{x}$ $m o d$ $p$ ,而这是困难的。

椭圆曲线上的Diffie-Hellman算法

(1) Alice 和 Bob 之间要建立一个共享密钥。

选取公共参数：取 $q > 3$ 是某个素数幂， $E 是 F_{q}$ 上的椭圆曲线， $E (F_{q})$ 是相应的 Abel 群，G 是 $E (F_{q})$ 中的一个具有较大素数阶 $n$ 的点。

(2) Alice 选取一个私钥 a(整数)： $1 ⩽ a ⩽ n - 2$ ，计算 $A = a G$ 。发送 A 给 Bob。

(3) Bob 选取一个私钥 b(整数)： $1 ⩽ b ⩽ n - 2$ ，计算 $B = b G$ 。发送 B 给 Alice。

(4) Alice 计算 $K = a B$

(5) Bob 计算 $K = b A$

显然 Alice 与 Bob 计算得到的 $K$ 是相同的：

$a B = a (b G) = (a b) G = b (a G) = b A$

$K$ 即为 Alice 与 Bob 之间的共享密钥。

椭圆曲线上的 Diffie-Hellman 密钥交换算法的安全性基于椭圆曲线上离散对数问题的难解性。