椭圆曲线：曲线上的点为什么能"相加

一句话版本

在曲线 $y^2 = x^3 + ax + b$ 上，用"画直线找第三个交点再翻折"的规则可以把两个点"加"成第三个点，所有点因此构成一个阿贝尔群。把 $P$ 自己加 $k$ 次得到 $Q = kP$ 很快；反过来已知 $P, Q$ 求 $k$ 极难（椭圆曲线离散对数问题）。比特币、以太坊的私钥就是这个 $k$ 。

全文分三层：

通俗理解：弦切法、"往前走 $k$ 步"
实际用处：比特币、以太坊、Apple Pay、Signal，以及 PS3 私钥泄露事件
数学原理：群律、有限域上的曲线、ECDSA，附 $\mathbb{F}_{17}$ 上的手算例子

第一层：通俗理解

1.1 椭圆曲线长什么样

椭圆曲线和椭圆没关系（名字来自椭圆弧长积分）。它就是方程

$y^2 = x^3 + ax + b$

的图像，关于 $x$ 轴上下对称。比特币用的 secp256k1 是最简单的一条： $y^2 = x^3 + 7$ 。

1.2 弦切法："加法"是怎么定义的

拿曲线上两个点 $P$ 和 $Q$ ：

过 $P$ 、 $Q$ 画一条直线，它和曲线一定还有第三个交点 $R'$ （三次方程有三个根）；
把 $R'$ 关于 $x$ 轴翻折，得到 $R$ ；
规定 $P + Q = R$ 。

如果 $P = Q$ ，就用 $P$ 点的切线代替连线。如果直线是竖的（ $P$ 和它的翻折点），交点在"无穷远"，记作 $O$ ，它充当零元。

神奇的是，这个看起来随意的规则满足交换律、结合律，有零元，每个点有逆元（翻折点）。也就是说，曲线上的点构成一个群。

1.3 私钥和公钥

私钥：一个很大的随机整数 $k$ （比特币里是 256 位）；
公钥：把公开的基点 $G$ 自己加 $k$ 次， $Q = kG$ 。

就像在一个巨大的、乱跳的钟面上从 $G$ 出发走 $k$ 步。告诉你起点和终点，你几乎不可能推出走了多少步。用"倍加"技巧，算 $kG$ 只要约 $256$ 次倍点和加法；反过来求 $k$ ，最好的算法也要约 $2^{128}$ 步。

第二层：实际用处

场景	用的曲线 / 算法
比特币、以太坊交易签名	secp256k1 + ECDSA（比特币 Taproot 改用 Schnorr）
HTTPS 密钥交换	X25519（Curve25519 上的 ECDH）
SSH、Signal、Git 签名	Ed25519
Apple Pay、银行卡芯片、护照	NIST P-256
以太坊共识层	BLS12-381（配对友好曲线，见《双线性配对与BLS签名》）

为什么比 RSA 受欢迎：同样 128 位安全，椭圆曲线密钥 256 位，RSA 要 3072 位。密钥短、签名短、算得快，对手机、智能卡、区块链都很重要。

PS3 私钥泄露（2010）

ECDSA 签名时需要一个每次都不同的随机数 $k$ 。索尼在 PS3 上签游戏时用了一个固定的 $k$ 。黑客组织 fail0verflow 拿两份签名列个方程就解出了私钥，从此任何人都能签"官方"软件。2013 年部分安卓比特币钱包也因随机数生成器的 bug 重复使用了 $k$ ，导致比特币被盗。原因见 3.4 节。

量子威胁

Shor 算法同样能解椭圆曲线离散对数，所以 ECC 和 RSA 一样会被量子计算机攻破，见《后量子密码》。

第三层：数学原理

3.1 群律的公式

设 $P = (x_1, y_1)$ ， $Q = (x_2, y_2)$ ，先求连线斜率：

$\lambda = \begin{cases} \dfrac{y_2 - y_1}{x_2 - x_1}, & P \neq Q \\[2ex] \dfrac{3x_1^2 + a}{2y_1}, & P = Q \ (\text{切线，隐函数求导}) \end{cases}$

然后

$x_3 = \lambda^2 - x_1 - x_2,\qquad y_3 = \lambda(x_1 - x_3) - y_1.$

推导：把 $y = \lambda(x - x_1) + y_1$ 代入曲线方程，得到一个首项为 $x^3$ 、 $x^2$ 系数为 $-\lambda^2$ 的三次方程。由韦达定理，三根之和 $x_1 + x_2 + x_3 = \lambda^2$ 。

结合律是最难的部分，直接展开公式非常繁琐。更优雅的证明要用代数几何（Riemann–Roch 定理或 Cayley–Bacharach 定理），这里承认它即可。

3.2 搬到有限域上

密码学不用实数，而是用有限域 $\mathbb{F}_p$ ：上面公式里的除法全部换成模 $p$ 的乘法逆元。曲线变成一堆离散的点，但群律公式一字不改，依然是阿贝尔群。

点有多少个：Hasse 定理说 $\big|\#E(\mathbb{F}_p) - (p+1)\big| \le 2\sqrt{p}$ ，所以点数大约是 $p$ 。实际中会选点数为大素数（或大素数乘以小余因子）的曲线，这样群几乎是循环群，没有小子群可以利用（参见《Diffie–Hellman与离散对数》里的 Pohlig–Hellman）。

3.3 手算例子： $\mathbb{F}_{17}$ 上的曲线

$E: y^2 = x^3 + 2x + 2$ over $\mathbb{F}_{17}$ ，基点 $P = (5, 1)$

先检查 $P$ 在曲线上： $5^3 + 2\cdot 5 + 2 = 137 = 8\cdot 17 + 1 \equiv 1 = 1^2$ 。✓

算 $2P$ （切线）：

$\lambda = \dfrac{3\cdot 25 + 2}{2 \cdot 1} = \dfrac{77}{2}$ 。 $77 \equiv 9$ ， $2^{-1} \equiv 9 \pmod{17}$ ，所以 $\lambda = 81 \equiv 13$
$x_3 = 13^2 - 10 = 159 \equiv 6$
$y_3 = 13(5 - 6) - 1 = -14 \equiv 3$
$2P = (6, 3)$

继续加下去：

$k$	$kP$	$k$	$kP$
1	$(5, 1)$	10	$(7, 11)$
2	$(6, 3)$	11	$(13, 10)$
3	$(10, 6)$	12	$(0, 11)$
4	$(3, 1)$	13	$(16, 4)$
5	$(9, 16)$	14	$(9, 1)$
6	$(16, 13)$	15	$(3, 16)$
7	$(0, 6)$	16	$(10, 11)$
8	$(13, 7)$	17	$(6, 14)$
9	$(7, 6)$	18	$(5, 16)$

$19P = O$ （无穷远点）。所以 $P$ 的阶是 $19$ ，它生成一个 $19$ 阶循环群。注意 $18P = (5, 16) = -P$ ，正好是 $P$ 翻折过来。

离散对数问题：如果只告诉你 $Q = (0, 11)$ ，问 $Q = kP$ 中的 $k$ 是多少，你只能一个个试，查表得 $k = 12$ 。在真实曲线上，这张表有 $2^{256}$ 行。（已用 Python 验算。）

3.4 ECDSA，以及重复使用 $k$ 为什么致命

设基点 $G$ 的阶为 $n$ ，私钥 $d$ ，公钥 $Q = dG$ ，消息哈希 $h$ 。

签名：随机选 $k$ ，算 $R = kG$ ，取 $r = R_x \bmod n$ ，以及

$s = k^{-1}(h + r d) \bmod n.$

签名是 $(r, s)$ 。验证：算 $u_1 = h s^{-1}$ ， $u_2 = r s^{-1}$ ，检查 $u_1 G + u_2 Q$ 的 $x$ 坐标是否等于 $r$ 。（因为 $u_1 G + u_2 Q = s^{-1}(h + rd)G = kG$ 。）

$k$ 重复的后果：两条消息 $h_1, h_2$ 用了同一个 $k$ ，于是 $r$ 相同，而

$s_1 - s_2 = k^{-1}(h_1 - h_2) \ \Rightarrow\ k = \frac{h_1 - h_2}{s_1 - s_2},\qquad d = \frac{s_1 k - h_1}{r}.$

两行代数就拿到私钥。这就是 PS3 事件的全部数学。现代实现用 RFC 6979： $k$ 由私钥和消息哈希确定性地生成，既不依赖随机数质量，也保证不同消息的 $k$ 不同。

总结

层次	要点
直觉	连线、找第三点、翻折，就是"加法"
代数	曲线上的点构成阿贝尔群；有限域上点数约为 $p$ ；选素数阶群
安全	已知 $P$ 和 $kP$ 求 $k$ 极难（约 $\sqrt{n}$ 步）
工程	密钥短、速度快；签名随机数 $k$ 绝不能重复

椭圆曲线：曲线上的点为什么能"相加"