上一篇博客讨论了如何利用椭圆曲线来协商一个密钥，进而用于对称加密；本篇博客讨论如何直接利用椭圆曲线，造一个公钥密码体系。

　　假设 Bob 想给 Alice 发送一条信息。他们预先约定好一条椭圆曲线 $E$，以及基点 $P \in E(\mathbb{F}_p)$. Alice 自己有私钥 $n_A$，然后把公钥 $Q_A = n_A P$ 公开。

　　Bob 手上的明文 $M$ 是椭圆曲线 $E$ 上的一个点。Bob 选择一个随机的 $k$，然后公布$$C_1 = k\cdot P,\quad C_2 = M + k\cdot Q_A$$

　　Alice 收到 $C_1, C_2$ 这两个点之后，计算$$C_2 - n_A C_1 = M+k\cdot Q_A - n_A k P = M$$

　　于是 Alice 恢复出了 Bob 给的明文。而对于攻击者 Eve，她知道这一条椭圆曲线、基点 $P$，以及 $Q_A, C_1, C_2$，现在她想得到 $M$，直觉上讲，她应该尝试找到 $k$，于是 $C_2 - k\cdot Q_A$ 就是明文。然而 $k = \log_{P} C_1$，计算起来是不现实的。

　　来看一个例子：

# ----- Alice 公开公钥 -----
E = EllipticCurve(GF(3851), [324, 1287])
P = E(920, 303)

nA = 1194
QA = nA * P

print(QA.xy())
# (2067, 2178)


# ----- Bob 发送信息 -----
M = E.lift_x(233)
k = 123

C1 = k * P
C2 = M + k * QA
C1.xy(), C2.xy()
# ((2525, 1772), (255, 2423))


# ----- Alice 接受信息 -----
msg = C2 - nA * C1
msg.xy()
# (233, 495)
▲ 一次典型的椭圆曲线 Elgamal 公钥密码体系的信息传输

　　另外，Elgamal 也可以只发送 x 坐标，但必须指明 y 是哪一个，否则计算会有误。注意到一个 x 坐标对应的两个 y 坐标，一个小于 $p/2$，另一个大于 $p/2$，故我们只需要一个 bit 的信息就可以把 y 确定下来——传输“y是否大于 p/2”即可。