椭圆曲线点加法

这篇文章描述了椭圆曲线在实数上的加法是如何工作的。

加密技术使用有限域上的椭圆曲线，但在实数的笛卡尔平面上理解椭圆曲线要简单得多。本文面向程序员，力求在较多数学内容与较轻松讨论之间找到一个平衡。

椭圆曲线的集合论定义

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

希望如果你已经阅读了我们的群论介绍，你实际上能够理解大部分内容，除了“点加法”是什么。但这就是抽象代数的美妙之处，对吧？你无需知道那是什么，依然可以理解上述句子。

椭圆曲线是一类具有如下公式的曲线：

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

根据你选择的 a 和 b 的值，你将得到如以下的一些曲线：

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

例如，点 $(3, 6)$ 在曲线 $y² = x³ + 9$ 上，因为 $6² = 3³ + 9$。在群论的术语中，$(3, 6)$ 是由 $y² = x³ + 9$ 定义的集合的一个成员。因为我们处理的是实数，这个集合具有无限的基数。

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

不要试图将椭圆曲线视为图上的一个图形，而是将其视为一个无限的点集。只有当且仅当满足椭圆曲线方程时，点才在这个集合中。

一旦我们将这些点视为一个集合，以群的形式看待它并不神秘。我们只需取两个点，并根据群的规则生成第三个。

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

• 一个闭合和结合的二元运算，即它会在该集合中生成另一个点
• 该集合必须有一个单位元素 $I$
• 集合中的每个点必须有一个逆元素，使得当两者与二元运算结合时，结果是 $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)$ 点。

而且因为这是一个群而不是一个幺半群，所以每个点都需要有一个逆元素，使得 $P ⊕ P⁻¹ = I$，其中 $I$ 是单位元素。

单位元素

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

但是请记住，根据集合论，我们可以任意定义二元运算。这使我们能够添加一个技术上不在曲线上的特殊元素，但根据定义它是单位元素。

我喜欢将单位元素视为“无处的点”，因为如果你将无处与任何实数点结合，则什么都不会改变。恼人的是，数学家将这个点，称为“无穷远的点”。

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

啊，但请记住，我们可以任意定义集合！我们将构成椭圆曲线的集合定义为椭圆曲线上的点和无处点。

因为二元运算仅仅是笛卡尔乘积的子集（一种关系），我们可以随意定义这个关系。我们可以在我们的算术中有任意多的“如果语句”，并且仍然遵循群法则。

加法是封闭的

不失一般性，让我们取椭圆曲线

$$ y² = x³ + 10 $$

以说明直线如何与椭圆曲线相交，让我们绘制一条几乎竖直的直线 $y = 10x$

（它可以是 1000x 以使其更加竖直，但我们会得到数值不稳定性，正如你将在后面看到的那样）

我们得到以下的一组图示。

事实证明，即使看起来紫色线条（$y = 10x$）的上升速度比蓝色曲线（$y² = x³ + 10$）快，但它们总会相交。

如果我们放大到足够的程度，我们可以看到交点。这在一般情况下是成立的。

只要 x 不是“完全竖直”的，只要它与曲线的两个点交叉，它总会再次交叉第三个点。 那两个点如果是切点，则这两个点可能是同一个点。

“如果我们与两个点相交”很重要。如果我们将紫线向左移动，以便它不穿过椭圆曲线的“U型”，那么它只会在一个点相交。

理解这一点的另一种方法：

如果一条直线在椭圆曲线上恰好相交两个点，并且没有交点是切线交点，那么它必须是完全竖直的。

你可以从上面的公式中进行代数证明，但我认为几何上的论述更直观。

我建议你停下来并绘制一些椭圆曲线和直线，以视觉上说服自己。

我们对垂直线的例外实际上会使逆元素和单位元素完美契合。

椭圆曲线上一个点的逆是该对的 y 值的负值。 也就是说，$(x, y)$ 的逆是 $(x, -y)$，反之亦然。通过这样的点绘制一条直线会形成一条完美的竖直线。

我们之前提到的“无穷远”的点就是我们之前提到的单位元素，当我们绘制一条垂直线时，它就是“高高在上”的点。

阿贝尔群

椭圆曲线点在我们的“2 个点总是产生一个第三个点，除非是单位”的背景下，显然具有可交换性质。

当我们选择两个点时，只有一个唯一的第三个点。你不能在椭圆曲线上得到四个交点。因为我们只得到一个可能的解，所以显然 $A ⊕ B = B ⊕ A$。

为什么椭圆曲线加法在$x$轴上翻转

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

在目前的形式下，如果我们两点相加而相交在中间，它就存在缺陷。

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

$$ \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$ 不是单位元（只有单位元素才可能是其自身的逆），因此我们有了一个矛盾。

幸运的是，我们可以通过一种方法来挽救这一点。只需将点加法定义为第三点 翻转到 y 轴。再次强调，我们 被允许这样做，因为二元运算可以以我们喜欢的方式定义，我们只需要确保我们的定义满足群法则。

因此，正确的方式来添加椭圆曲线点在图上表示如下：

加法公式

通过一些代数，给定两个点

$$ \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$，我们会得到一个零除错误，但这意味着它们是同一个点，这显然是可交换的。

我们可以用类似的技术来证明结合性，但不幸的是，这非常麻烦，所以我们将感兴趣的读者参考另一篇结合性证明。

椭圆曲线满足阿贝尔群属性

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

1. 二元运算是封闭的。它要么与曲线上的第三个点相交，要么与无穷远的点（单位）相交。我们可以保证当两个点相交时，会得到一个第三个有效点。二元运算是结合的。
2. 该群有一个单位元素。
3. 每个点都有一个逆。
4. 该群是阿贝尔的，因为 $A ⊕ B = B ⊕ A$

一个二元运算必须接受集合中的每一个可能的元素对。如果这个元素对是同一个元素，即 $A ⊕ A$ 怎么办？

点乘法：与自身相加

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

因此，将一个点与自身相加实际上是在该点处取导数，获得交点，然后翻转 $y$ 轴。

以下图像以图形化方式演示了 $A ⊕ A = 2A$。

点乘法的捷径

如果我们想要计算 $1000A$ 而不是 $2A$ 呢？这看似是一个 $\mathcal{O}(n)$ 操作，但事实并非如此。

由于结合性，我们可以将 $1000A$ 写为

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

$512A$（及其他项）可以迅速计算，因为512只是 $A$ 经过9次加倍。

因此，与其执行1000次操作，不如在14次内完成（9次计算512，缓存中间结果，之后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)$ 次。因为结合律的缘故，我们执行它的顺序并不重要。

所以当你看到像那样的操作时，我们的群并没有突然拥有乘法二元运算，它只是一个误导性的标记而已。

在有限域中的椭圆曲线

如果我们要在实际应用中使用实数上的椭圆曲线，则由于交点可能需要大量的小数位来计算，因此在数值上会非常不稳定。

因此实际上，我们使用的是模运算。

但通过这样做我们并没有失去之前获得的直觉。

通过RareSkills进一步学习

这部分内容来自我们的零知识课程，查看那里以获取更多的学习内容。

最初发布于2023年9月1日

• 原文链接： rareskills.io/post/ellip...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～