椭圆曲线深入解析（第一部分）

• 原文链接：medium.com/@francomango...
• 译者：AI翻译官，校对：翻译小组
• 本文链接：learnblockchain.cn/article…

前言

密码学在不断发展。

新技术始终在被开发。特别是在一些如今看似炙手可热的领域，如零知识证明 、全同态加密和后量子密码学 。

更好、更快、更安全的方法不断被研究。大量的密码技术令人不知所措。

然而，这个多样化技术世界所基于的基本数学结构却相对不变。

尽管可能有一些新的技术出现，比如多项式环和理想，以及一些关于更奇特替代方案的研究，比如 p-进数 。

我们每天使用的大多数密码方法（常常在不知不觉中）都是基于一个单一构造：椭圆曲线。

它们可能会在不久的将来变得过时。但至少在非常近的未来，它们不会消失！

我最近在密码学 101 系列中谈到过它们。说实话，那只是对这个主题的简要友好概述。作为第一次接触足够好——但远不是完整的故事。

这次，我想深入探讨椭圆曲线的世界。有很多内容要覆盖，所以我会把它分成几个部分。

椭圆曲线

自然地，首先想到的问题是椭圆曲线到底是什么？

不再多说，我向你们展示——这就是一条椭圆曲线：

你所看到的是椭圆曲线的一般魏尔斯特拉斯方程——它实际上就是一个三次（三次方）多项式。没什么可害怕的。

一般来说，我们将使用以下简化版本，在某些我们不在这里讨论的条件下是等效的：

这是在直角坐标系中绘制的椭圆曲线的样子：

看着这个图，你可能会想这些曲线有什么“椭圆”的地方。恰好这有点名字不当，如这里所解释的那样。

我们在这里表示的是满足我们之前定义的方程E的点的集合，就像抛物线满足方程y = x²一样。

现在，我们可以从一开始就说几件关于这些曲线的事情。

首先，注意它们在 x 轴上是对称的。很容易看出，罪魁祸首是 y² 项，因为对于任何正值的x³ + ax + b，都有正方根和负方根，都是y的有效解。

其次，这条曲线是光滑的。并非所有满足表达式E的曲线都是光滑的——就像这个：

这是曲线 E：y² = x³ -3x + 2

我们可以看到似乎有一个交点。如果你尝试绘制曲线y² = x³，你也会注意到一些奇怪的行为。

从技术上讲，这不是一个交点，而是曲线的两个尖尖部分相互接触。

我们称这些曲线为奇异。奇异曲线在我们尝试将它们用于我们的意图时会出现问题——因为这些点的导数是定义不清的。由于这个原因，这样的非光滑曲线不被认为是椭圆曲线。

介绍到此！这些小东西到底有什么用呢？

定义运算

这些曲线的吸引之处在于我们可以利用它们来定义一种运算。我想将本文剩余的部分用于理解该运算，并暂时不考虑它的有用性——但我们将在后续文章中讨论这个。

尽管如此，我想在继续之前提供一些背景。

我们的运算将作为数学群构造中的一个关键部分。我们稍后会讨论这些——但想法是，群是一些非常复杂的数学问题的基础，这些问题使我们都知道和喜爱的公钥密码学得以实现，还有更多。

我们将要呈现的椭圆曲线运算有一种奇怪的定义。请暂时耐心听我解释。它是这样的：

1. 选择曲线上的两个点P和Q，并画一条通过它们的线。
2. 你会发现这条线与曲线上的另一个点相交。我们称它为-R。
3. 现在，围绕 x 轴翻转 -R 。由于 -R 是曲线上的一个点，并且曲线是对称的，你将得到曲线上的另一个点：R。

整个过程看起来大致如此：

顺便说一下，这也是一个有效的椭圆曲线形状。

通过遵循这个步骤，我们计算出了一个新的点R，作为“相加”P和Q的结果。我们可以将其写为：

确实是一个奇怪的加法定义——但以这种方式思考运算是有帮助的。我们用符号⨁来区分它与“正常”加法。

不过，如果我们想将P与自己相加，会发生什么呢？

相反，假设我们有一个在曲线上与P非常接近的点——我们称之为P'。随着P’逐渐接近P，通过它们的直线慢慢靠近P处的切线。很自然地，我们可以推断出找到P ⨁ P是用之前相同的过程，但在第一步中使用P的切线。

这就是为什么拥有良好定义的导数是重要的！

毫无疑问，我们遵循的步骤被称为弦与切线规则。但是它总是有效的吗？有没有什么边界情况可能会有问题？

交点

在我们的弦与切线规则的第一步，一个重要的假设是我们可以找到一个第三个交点。这总是可能吗？让我们仔细看看——该进行一些替换了！

直线l的方程是非常简单的：

有趣的是，我们可以将该表达式直接代入我们的椭圆曲线方程，生成这个关于x的三次多项式等式：

三次多项式就像这个，在最多情况下有三个根。正如你可能猜到的，那些根将是我们直线与曲线相交的点的 x 坐标，如果确实存在任何交点的话。

让我们尝试在弦切线法则的情况下查看这个表达式会发生什么。

弦（Chord）

如果我们的多项式有三个根，那么我们可以将其因式分解为形如 (x - r) 的乘积。经过一些重新排列，我们最终得到：

我们还没有弄清楚m和n的值——但它们对于通过两个点 (P 和 Q) 的直线来说是相对容易计算的，所以我把这部分留给你。

扩展上面表达式的左侧是有用的，结果是：

看看这个：比较方程两边的 x² 项，我们得到：

通过将几个项移到右边，我们得到了这个第三交点的 x 坐标的表达式。为了找到 y，我们只需将其代入直线方程，然后翻转得到的值。我们得到：

这就是所有的内容！

切线

找到 R 就有点棘手了，因为我们需要找到通过 P 的与曲线的切线。切线就是通过 P 的那条直线，其斜率等于该曲线关于 x 的一阶导数。

由于我们没有 E(x) 形式的显式公式，所以我们必须拿出我们的微积分技能，并利用一个名为 链规则 的小把戏，将 E(x) 视为一个 隐函数：

将 P 的坐标代入上述表达式，我们可以找到在 P 点上与 E 的切线的斜率——这就是我们在前一步中得到的 m 值。

然后，我们照常继续。我们只需小心考虑 xₚ 作为一个具有 重数 = 2 的根。考虑到这一点，我们几乎可以得到相同的结果：

将 P 加到自己身上就像是将它加倍。因此，我们将其写作 [2]P，我们称之为——你猜对了——点加倍！

边缘案例

很好！到目前为止，一切都运转良好。

现在我们可以尝试将 P 和 -P（其在 x 轴上的反射）相加。然而，经过它们的直线是一个竖直线，由 x = xₚ 定义。这意味着我们将得到：

对于给定的 xₚ 值，这意味着我们得到了两个有效的 yₚ 值，而不是三个。不是很好——我们过程的第一步要求存在第三个交点。或者说，不是吗？

显然，为了使我们的操作明确，我们需要能够执行 P ⨁ (-P)。如果这只是简单的加法，当然会导致零。本质上，我们需要定义零对于我们的操作意味着什么。

那么，这就是了：我向你展示 无穷远点：

这不是很直观，但想象一下蓝线在无穷远处“截取”曲线。当然不是。

我请你此时发挥一点想象力。如果有什么的话，想象一下这是一个“特殊点”。每当我们需要加 P ⨁ (-P) 时，我们知道常规的弦法则不适用，相反，我们知道结果是无穷远点 𝒪。

当我们谈论投影空间时，我们会对此作更多解释。

快速加法

我们定义的这个操作还有一个特别酷的方面，那就是有一个快速加法算法。这是说，如果我们想加：

我们可以一步一步地进行，将 P 加到每个后续和的结果，因为我们已经知道如何去做。

令人惊讶的是，我们可以做得更好。因为这个操作是结合性的，所以可以“批处理”加法，以一种可能方便我们的方法。例如， [5]P 可以写成：

请注意，最终的表达式需要两次加倍和一次加法，而不是最初设置中所需的四次加法。节省一次操作可能看起来不算太多，但当我们乘以更大的 m 时，节省就显著了。

乘法的一般算法按加倍加的方式工作。对于我们想要乘以的任何正整数 m，我们首先需要找到它的二进制表示，并进行如下过程：

1. 将结果的初始值设为 W = P。
2. 然后，从第二个最重要的位开始，赋值 W = [2]W。
3. 如果当前位是 1，那么还要加上 W = W ⨁ P。
4. 向右移动一位，并从步骤 2 重新开始。

例如，11 的二进制是 1011。这个过程总共会有 3 次迭代：

- 初始化： W = P
- 第一个数字： W = [2]W = [2]P
- 第二个数字： W = [2]W ⨁ P = [5]P
- 最后一个数字： W = [2]W ⨁ P = [11]P

总共 3 次乘法 和 2 次加法——已经是如果我们一次加一个 P 所需的 10 次加法的一半。

通常，这被称为乘以 m，而不是“快速加法”。不过，我们确实有一个快速算法——重要的是，逆问题 根本不快。

我所说的，给定两个点 G 和 Q，使得 Q = [m]G，没有快速算法可以回推 m 的值。

这种简单性使我们所知和喜爱的许多公共密钥密码学成为可能！

但为什么是椭圆曲线？

哦，天哪。又来了这个火辣的问题。

我们仍然不太清楚椭圆曲线从密码学角度如何有用。我们知道的只是如何将点相加，遵循的过程在我们目前的知识下，似乎非常任意，而且老实说，有点强迫。

当然，还有很多关于椭圆曲线的内容可以讨论——但我们至少可以尝试想象几件事。

有一个叫做 Bézout 定理 的定理，笼统地说，一条直线会在 3 个点处拦截一个三次曲线（包括无穷远点之类的）。因此，我们的操作是相当自然的——给定曲线中的两个点，画出一条经过它们的直线可以保证我们会找到第三个，这对于得到唯一的结果是有用的。

我们如果尝试使用更高阶的曲线会怎样？根据贝祖定理，我们不仅有_3_个交点。这意味着，如果我们想要将曲线上的两个点_P_和_Q_相加，我们将会有多个候选结果。我们该选择哪一个？

曲线 y² = x⁵ - 4x³ + 3x 和一条直线在 5 个不同点相交。

这使得在这些类型的曲线上定义运算变得有些复杂。

使用一个叫做除数的概念是可能的。但现在谈论这个还为时尚早。

如果我们能以某种方式在更高阶曲线上定义运算，另一个问题就是不实用性。在我们可靠的椭圆曲线上寻找交点表达式很简单，但在更复杂的曲线中可能会变得一团糟。显式公式可能根本不可用，这要归因于阿贝尔-鲁菲尼定理 。

我们刚才说过我们会使用魏尔斯特拉斯形式，但这并不意味着没有其他三阶曲线可以使用。例如，还有蒙哥马利曲线和爱德华曲线，它们在密码学中也很有用，但可能并不是最广泛采用的曲线。

此外，我们可以考虑稍微复杂一些的三阶曲线，例如这个：

曲线 -5x³+ 4x²y + 14x - y³+ 12y = 0

无论你多么努力，你会发现一条直线最多与这条曲线相交三次。但这并不意味着使用起来非常实用——事实上，推导显式公式并不容易，并且可能比我们的简单魏尔斯特拉斯结果更具计算复杂性。

在这个意义上，我们的椭圆曲线定义处于一种“合适”的区域，平衡了操作的低计算成本，同时提供了足够的复杂性以在密码学中有用。

而关于我一直提到的那些显式公式，如果我们想从我们的曲线中构建任何算法，我们肯定是需要它们的。你看，这些可视化在建立初步理解方面很棒，但无法真实地表示椭圆曲线在我们眼中的样子，更接近于这个：

我感觉你可能刚刚想了：

别担心——这一切很快就会变得明了！

总结

在这一系列希望能短小的文章的第一部分中，我们介绍了关于椭圆曲线的基础知识。

如果你已经阅读过这篇文章 ，或者你对这个主题有先前的了解，你可能会觉得这个介绍非常简单。

但我们才刚刚开始！我们还有很多有趣的内容要覆盖——从百万美元的问题，到“高维度”的曲线。

敬请期待，我们下次再见于下一篇文章 !

我是 AI 翻译官，为大家转译优秀英文文章，如有翻译不通的地方，在这里修改，还请包涵～