椭圆曲线点加法

Last updated on Mar 10, 2026

本文介绍了椭圆曲线加法在实数域上的工作原理。

密码学使用有限域上的椭圆曲线，但在实数笛卡尔坐标系中更容易将椭圆曲线概念化。本文面向程序员，试图在过于偏重数学和过于笼统之间取得平衡。

椭圆曲线的集合论定义

椭圆曲线上的点集合在椭圆曲线点加法下构成一个群。

希望如果你一直关注我们的群论简介，除了“点加法”是什么之外，你应该已经理解了其中的大部分内容。但这正是抽象代数的美妙之处，对吧？你不需要知道它具体是什么，依然能看懂上面那句话。

椭圆曲线是一族具有以下公式的曲线：

y^2 = x^3 + ax + b

根据选择的 a 和 b 的值，你会得到类似下图的一些曲线：

椭圆曲线上的一个点是给定 $a$ 和 $b$ 时满足 $y² = x³ + ax + b$ 的 $(x, y)$ 坐标对。

例如，点 $(3, 6)$ 在曲线 $y² = x³ + 9$ 上，因为 $6² = 3³ + 9$ 。用群论的术语来说， $(3, 6)$ 是由 $y² = x³ + 9$ 定义的集合中的一个元素。由于我们处理的是实数，该集合的基数（cardinality）是无穷大的。

这里的思想是，我们可以从这个集合中取出两个点，进行二元运算，然后我们将得到另一个同样在该集合中的点。也就是说，它是一个同样位于曲线上的 $(x, y)$ 对。

不要把椭圆曲线单纯看作图表上的曲线，而应将其视为一个无限的点集。当且仅当这些点满足椭圆曲线方程时，它们才属于这个集合。

一旦我们将这些点视为一个集合，将它们看作一个群就不再神秘了。我们只需取出两个点，并根据群的规则生成第三个点。

具体来说，要成为一个群，这个点集需要具备：

一个满足封闭性和结合律的二元运算符，即它会生成集合中的另一个点
集合必须有一个单位元（identity element） $I$
集合中的每个点都必须有一个逆元（inverse），使得当两者通过该二元运算符结合时，结果为 $I$

椭圆曲线在加法下构成阿贝尔群

虽然我们不知道这个二元运算符是如何工作的，但我们知道它接收曲线上的两个 $(x, y)$ 点，并返回曲线上的另一个点。因为该运算符是封闭的，我们知道该点实际上将是椭圆曲线方程的有效解，而不是其他地方的某个点。

我们还知道这个二元运算符满足结合律（而且根据本节标题，也满足交换律）。

因此，给定椭圆曲线上的三个点 $A$ 、 $B$ 和 $C$ （或者如果你喜欢，可以写成 $(x_a, y_a)$ 、 $(x_b, y_b)$ 和 $(x_c, y_c)$ ），我们知道以下等式成立：

$(A ⊕ B) ⊕ C = A ⊕ (B ⊕ C)$
$A ⊕ B = B ⊕ A$

我使用 $⊕$ ，因为我们知道这个二元运算符并不是任何通常意义上的加法，而是一个二元运算符（再次回想一下集合论，二元运算符接收集合中的两个元素并返回集合中的另一个元素，至于它是如何做到的，这并不是定义的重点）。

我们还知道肯定存在某个单位元。也就是说，曲线上任何一个 $(x, y)$ 点与该单位元结合时，输出的还是同一个未改变的 $(x, y)$ 点。

又因为这是一个群而不仅仅是一个幺半群（monoid），每个点都需要有一个逆元，使得 $P ⊕ P⁻¹ = I$ ，其中 $I$ 是单位元。

单位元

直观上，我们可能会认为 $(0, 0)$ 或 $(1, 1)$ 是单位元，因为这类点经常存在于其他群中，但你可以从上面的图表中看到，这些点通常并不在曲线上。由于它们不属于 $y² = x³ + ax + b$ 上的点集，它们就不是该群的一部分。

但回想一下集合论，我们可以根据喜好在任意定义的集合上定义二元运算符。这允许我们添加一个特殊的元素，它严格来说不在曲线上，但在定义上是单位元。

我喜欢把单位元看作“无处存在的点（the point that is nowhere）”，因为如果你把“无处”与任何真实存在的点结合，什么都不会改变。令人恼火的是，数学家把这个单位元称为“无穷远点（the point at infinity）”。

嘿，等等，这个点不是应该满足 $y² = x³ + ax + b$ 吗？“无处”（或无穷大）并不是 $(x, y)$ 的有效值。

啊，但请记住，我们可以随意定义集合！我们将构成椭圆曲线的集合定义为椭圆曲线上的点加上那个“无处存在的点”。

因为二元运算符只是笛卡尔积（一种关系）的子集，而我们可以随意定义这种关系。我们可以在我们的算术中加入任意数量的巧妙的“if语句”，而依然遵循群的法则。

加法的封闭性

不失一般性，让我们以这条椭圆曲线为例：

y² = x³ + 10

为了说明直线如何在椭圆曲线上相交，让我们画一条几乎垂直的直线 $y = 10x$

（也可以是 1000x 使其更垂直，但正如你稍后将看到的，我们会遇到数值不稳定的问题）

我们得到了下面这组图表。

结果表明，尽管看起来紫色的线（ $y = 10x$ ）比蓝色的曲线（ $y² = x³ + 10$ ）上升得快，但它们最终总是会相交。

如果我们缩小得足够多，就可以看到交点。一般来说，这是成立的。

只要直线不是“完全垂直”的，如果它穿过曲线上的两个点，就一定会穿过第三个点。 如果其中一个交点是切点，这几个点中的两个可能是同一个点。

“如果它与两个点相交”这一前提很重要。如果我们把紫色的线向左移，使其不穿过椭圆曲线的“U型转弯”，那么它将只在一点相交。

另一种理解方式是：

如果一条直线与椭圆曲线恰好相交于两点，且这两个交点都不是切点，那么它必定是完全垂直的。

你可以从上面的公式推导出一个代数证明，但我认为几何论证更直观。

我建议你在此暂停，画一些椭圆曲线和直线，通过视觉来验证这一点。

我们对垂直直线的例外处理实际上使得逆元和单位元完美地归位。

椭圆曲线点的逆元是该坐标对 y 值的负数。 也就是说， $(x, y)$ 的逆元是 $(x, -y)$ ，反之亦然。穿过这样两个点的直线会形成一条完全垂直的线。

单位元就是我们前面提到的“无穷远点”，它仅仅是当我们画一条垂直线时，那个“在无限高处”的点。

阿贝尔群

椭圆曲线点在我们的“2个点结合总是产生第3个点（单位元除外）”的规则下构成一个群，这一事实使其交换律特性变得显而易见。

当我们选取两个点时，只存在唯一一个第三点。你不可能在椭圆曲线上得到四个交点。既然我们只有唯一的可能解，那么很明显 $A ⊕ B = B ⊕ A$ 。

为什么椭圆曲线加法需要沿 x 轴翻转

在上一节中，我们忽略了一个非常重要的细节，因为它确实值得单设一节来讨论。

在其当前的形式中，如果我们将相交点位于中间的两个点相加，就会出现一个 bug。

根据我们上面的定义，以下公式必须成立：

\begin{align*} A ⊕ B &= C \\ A ⊕ C &= B \\ B ⊕ C &= A \end{align*}

稍微运用一些代数知识，我们会得出一个矛盾：

\begin{align*} (B ⊕ C) ⊕ B &= C \\ B ⊕ C &= \mathsf{inv}(B) ⊕ C \\ B &= \mathsf{inv}(B) \end{align*}

这表明 $B$ 等于它的逆元。但 $B$ 并不是单位元（单位元是唯一等于其自身逆元的元素），因此我们得到了一个矛盾。

谢天谢地，有办法挽救这个问题。只需将点加法定义为沿 x 轴翻转后的第三个点即可。再说一次，我们被允许这样做，因为二元运算符可以随心所欲地定义，我们只关心我们的定义是否满足群论法则。

因此，椭圆曲线点加法的正确方式如下面的图表所示：

加法公式

利用一些代数知识，给定两个点：

\begin{align*} P₁ &= (x₁, y₁) \\ P₂ &= (x₂, y₂) \end{align*}

可以使用以下公式推导出如何计算 $P₃ = (x₃, y₃)$ ，其中 $P₃ = P₁ ⊕ P₂$ 。

\begin{align*} \lambda &= \frac{y₂ - y₁}{x₂ - x₁} \\ x₃ &= \lambda² - x₁ - x₂ \\ y₃ &= \lambda(x₁-x₃) - y₁ \end{align*}

用代数方法证明交换律和结合律

由于我们有一个封闭形式的方程，给定点 $T$ 和 $U$ ，我们可以用代数方法证明 $T⊕U = U⊕T$ 。

我们这样做：

\begin{align*} P &= T ⊕ U \\ Q &= U ⊕ T \\ P &= Q \end{align*}

var('y_t', 'y_u', 'x_t', 'x_u')
lambda_p = (y_u - y_t)/(x_u - x_t)
x_p = lambda_p^2 - x_t - x_u
y_p = (lambda_p*(x_t - x_p) - y_t)

lambda_q = (y_t - y_u)/(x_t - x_u)
x_q = lambda_q^2 - x_u - x_t
y_q = (lambda_q*(x_u - x_q) - y_u)

下面是在 Jupyter notebook 中运行上述代码并格式化输出的截图。计算机代数系统需要一点点调试，但我们可以清楚地看到 x_q == x_p 和 y_q == y_p。

对于所有 $(x_t, y_t)$ 和 $(x_u, y_u)$ 的值， $P = Q$ 。如果 $x_t = x_u$ ，我们会遇到除以零的错误，但这意味它们是同一个点，这显然是满足交换律的。

我们可以使用类似的方法来证明结合律，但遗憾的是这极其繁杂，因此我们建议有兴趣的读者参考另一篇结合律证明。

椭圆曲线满足阿贝尔群的性质

让我们看看椭圆曲线是如何满足群性质的。

二元运算符是封闭的。它要么与曲线上的第3个点相交，要么与无穷远点（单位元）相交。当我们让两点相交时，必定能得到第三个有效的点。该二元运算符满足结合律。
该群拥有一个单位元。
每个点都有一个逆元。
该群是阿贝尔群，因为 A ⊕ B = B ⊕ A

一个二元运算符必须能接受集合中所有可能的点对。如果点对是相同的元素，即 A ⊕ A 呢？

点乘法：将一个点与其自身相加

让我们用极限的概念来思考这个问题。将一个点加到它自己身上，就像把两个点无限靠近，直到它们变成同一个点。当这种收敛发生时，直线的斜率将与曲线相切。

因此，将一个点与其自身相加仅仅是在该点处求导，求出交点，然后翻转 $y$ 轴。

下图通过图表展示了 $A ⊕ A = 2A$ 。

点乘法的捷径

如果我们想计算 $1000A$ 而不是 $2A$ 该怎么办？这看起来像是一个 $\mathcal{O}(n)$ 的操作，但实际上并非如此。

基于结合律，我们可以将 $1000A$ 写为

1000A = 512A ⊕ 256A ⊕ 128A ⊕ 64A ⊕ 32A ⊕ 8A

$512A$ （及其他项）可以快速计算出来，因为 512A 就是将 $A$ 翻倍（doubled）9 次。

因此，我们不需要进行 1000 次运算，只需 14 次即可（9 次用于计算 512A 并缓存中间结果，然后再进行 5 次加法）。

当我们涉及密码学时，这实际上是一个非常重要的性质：

我们可以高效地将椭圆曲线上的点与一个大整数相乘。

加法的实现细节

使用简单的代数知识推导点加法的公式并不太难。当我们让两个点相交时，我们知道斜率和直线经过的点，因此我们就可以计算出交点。

我不想在这里做这种推导，因为我不想陷入一堆符号操作中。

群论的全部威力就在于，我们根本不在乎符号操作的具体过程是什么样的。我们只需要知道，如果我们对两个点执行二元运算，就会得到集合中的另一个点，并且我们的集合遵循群法则。

如果你用这种方式思考，椭圆曲线就容易理解得多。

我们不应该试图从零开始孤立地理解椭圆曲线，而应该学习一堆其他的代数群，然后将这些知识和直觉转移到椭圆曲线上。

加法下的有理数是一个群。模素数的整数在乘法下是一个群。非零行列式的矩阵在乘法下是一个群。

执行二元运算后，你会得到集合中的另一个元素。群拥有单位元，并且每个元素都有逆元。结合律也成立。记住这些后，你就不应该在意运算符 ⊕ 在幕后究竟是怎么运作的了。

在我看来，如果你试图脱离群论的第一性原理来孤立地理解椭圆曲线数学，那你就是在自找麻烦。把它放在与之相关的数学体系中去理解要容易得多。

这样能带来更顺畅的学习体验。

代数操作实际上只是结合加法。

设 $P$ 为一个椭圆曲线点。如果我们将进行如下操作会发生什么？

(a + b)P + cP = aP + (b + c)P

起初，能够这样做可能看起来很奇怪，因为如果我们试图想象在椭圆曲线上到底发生了什么，我们肯定会一头雾水。

请记住，上面看起来像乘法的操作，实际上只是一个点不断与自身相加，因此当我们把它看作群时，其背后的实际过程如下：

\underbrace{(a + b)P + cP}_{((a + b + c)P)} = \underbrace{aP + (b + c)P}_{(a + b + c)P}

\begin{align*} (a + b + c)P &= (a + b + c)P \\ (aP + bP) + cP &= aP + (bP + cP) \\ (a + b)P + cP &= aP + (b + c)P \end{align*}

标量“乘法”并不像我们对普通代数所理解的那样具有“分配律”。它只是重新排列将 P 与自身相加的顺序的一种简写。

在底层，我们其实只是将 $P$ 与自身相加了 $(a + b + c)$ 次。得益于结合律，操作的顺序并不重要。

所以，当你看到这样的推导操作时，我们的群并没有突然多出一个乘法二元运算符，那只是一种具有误导性的简写方式。

有限域上的椭圆曲线

如果我们要在实际应用中在实数域上计算椭圆曲线，它们的数值稳定性会非常差，因为交点的计算可能需要非常多的小数位。

因此在现实中，我们的一切操作都是通过模算术（modular arithmetic）完成的。

但是，我们通过将实数作为可视化示例所获得的直觉，在模算术中并不会丢失。

通过 RareSkills 了解更多

此材料摘自我们的零知识证明课程，详情请见此处以了解更多信息。本文是零知识证明（Zero Knowledge Proofs）系列文章的一部分。

首发于 2023 年 9 月 1 日