基于椭圆曲线的 Diffie-Hellman 密钥交换

椭圆曲线 Diffie-Hellman 算法概述

　　和常规的 Diffie-Hellman 密钥交换算法一样，现在 Alice 和 Bob 想要协商出一个整数，且信道是不安全的，有各种各样的窃听者。

　　首先，他们需要约定好一个椭圆曲线 $E(\mathbb{F}_p)$，以及一个基点 $P$. 现在 Alice 找一个 $n_A$，Bob 找一个 $n_B$，接下来 Alice 计算 $Q_A = n_A P$，Bob 计算 $Q_B = n_B P$.

　　完成之后，Alice 与 Bob 交换 $Q_A$ 和 $Q_B$，接下来 Alice 计算 $n_A Q_B$，Bob 计算 $n_BQ_A$，于是他俩算出了相同的点：$$n_A Q_B = (n_An_B)P = n_BQ_A$$

　　接下来，他们可以拿着这个点的 x 坐标，作为对称加密的密钥了。

一个例子

　　我们实际操作一个例子。假设 Alice 和 Bob 约定好使用椭圆曲线：$$p=3851, \quad E:Y^2 = X ^ 3 + 324 X + 1287, \quad P=(920, 303)$$

　　现在 Alice 选取了 $n_A = 1194$，BoB 选取了 $n_B = 1759$，分别计算 $Q_A, Q_B$:

E = EllipticCurve(GF(3851), [324, 1287])
P = E(920, 303)

nA = 1194
QA = nA * P
nB = 1759
QB = nB * P

QA.xy(), QB.xy()
# ((2067, 2178), (3684, 3125))

　　于是 Alice 公布 $Q_A = (2067, 2178)$，Bob 公布 $Q_B = (3684, 3125)$. 接下来他们算出密钥协商的结果：

print((nA * QB).xy())
# (3347, 1242)
print((nB * QA).xy())
# (3347, 1242)

　　从而 Alice 和 Bob 协商了点 $(3347, 1242)$. 现在来考虑攻击者 Eve。她知道椭圆曲线 $E$，知道基点 $P$，知道两人公布的  $Q_A$ 和 $Q_B$. 她的目标是计算出 $n_A n_B P$，这是很困难的，目前看来最可行的方式是计算出 $n_A$ 或者 $n_B$. 这就是椭圆曲线上的离散对数问题，需要 $\sqrt{p}$ 次运算才能完成。

　　当然，也许可能有其他更好的方法来攻破椭圆曲线 Diffie-Hellman，但我们还没有发现。

消息传输的简化

　　我们刚刚说过，密钥交换完成后，Alice 和 Bob 将会利用协商好的点的 x 坐标，而抛弃 y 坐标。由于一个 x 坐标只对应两个 y 坐标，能不能不传输 y 坐标，以节省传输的信息量呢？

　　Alice 公布 $Q_A$ 的 x 坐标，Bob 公布 $Q_B$ 的 $x$ 坐标。那么 Alice 会计算出 Bob 那个点的 y 坐标（二次剩余，很容易算）——可能是 $Q_B$，或者猜错了，得到 $-Q_B$. 同样地，Bob 计算出的 Alice 点坐标可能是 $\pm Q_A$. 无论他们选择什么点（两人一共有四种选择方式），都会计算出$$\pm n_BQ_A = \pm n_AQ_B = \pm (n_An_B)P$$

　　抛弃掉 y 轴坐标，x 轴坐标仍然是正确的。例子：

print((nA * QB).xy())
# (3347, 1242)
print((nA * -QB).xy())
# (3347, 2609)
print((nB * QA).xy())
# (3347, 1242)
print((nB * -QA).xy())
# (3347, 2609)

　　因此，我们传输 $Q_A, Q_B$ 的时候，确实可以省略掉 y 轴坐标，而不用担心协商错误。