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

如果我们只能用目前所包含的内容来定义什么是椭圆曲线，我们可能会说：

它们是具有特定表达式的三次多项式，定义在有限域上，并结合了一种特殊的点加法方式。

虽然从技术上讲，这是准确的，但这并没有很好地展现椭圆曲线的价值。特别是因为它们存在的整个理由是被应用于加密算法中——到目前为止，我们并没有提到任何使椭圆曲线作为加密基础的吸引人的特性。

显然，我们漏掉了一些重要的信息。

公平地说，谈论 椭圆曲线 最终是有点误导的。因为实际上，实际上在加密中使用的椭圆曲线其实并不是 曲线，而是 群。

它们是什么？

没错，群。仅仅“椭圆曲线”这个名字并没有讲述完整的故事。称它们为椭圆曲线 群 更为合适，但更短的版本被广泛接受。

现在，群 是 对加密很有趣的。而我们对它们还没有太多介绍，所以我们从这里开始吧！

群（Groups ）

原则上，群是非常简单的结构。它们仅由两个简单的元素定义：一个 集合，和一个 二元 运算。有效的二元运算需要生成一个也属于该集合的结果。换句话说，它应该是如下形式的函数：

通常，我们不区分群 𝔾 和基础集合。通常将该集合称为“群”本身！

我们稍后将看到群为什么重要。但首先，让我们来看一个重要的例子。

我们在 早先的讨论 中花了很多时间讨论 有限域。这些域的基础集合仅是 模 p 的整数：

因为在 p 范围内，加法、减法、乘法和除法（模倒数）都是定义清晰的，所以这 behaves like a field。现在我们将 零 去掉：

那么我就问：这仍然是一个域吗？

答案是 不。原因在于它在加法下并不 封闭：当我们将 1 和 p - 1 相加时，会得到 0，而 0 不属于我们的集合。

不过，在 乘法 的情况下，情况是可以成立的。

在这个群中，当两个数 a 和 b 相乘时，唯一能得到 0 的方式是结果是 p 的倍数——也就是说，p 是 a.b 的因子中的一部分。但如果 p 是 素数，那么这是不可能的——p 不可能仅仅出现在 a 和 b 的因数组合中。

因此，集合 ℤₚ* 的元素相乘绝不会得 0（模 p，且当 p 为素数时）。

我们看到，ℤₚ* 像一个群一样运作，因为它只支持一种操作（乘法）。称这个为 乘法群 也不奇怪。

有人可能会争辩说，它支持两种操作，因为我们可以计算乘法逆元。我们暂时就不深入讨论这一点。

群不一定是 有限 的——实际上，确实存在无限群。但由于与我们在 之前的帖子中提到的 相似的原因，我们希望使用有限群。通常，这被称为具有有限 阶 的群，而你可能猜测，这个 阶 是指群中的元素数量，或其 大小，或 基数。

Identity 与生成元（Generators）

群中的某些元素具有独特的性质，使它们显得特别。这就是群的 身份元素（identity） 的情况。

从概念上讲，身份元素非常简单。它是一个在群的二元运算中具有 完全无效 效果的元素。例如，在我们的 整数乘法群 中，我们可以很容易地看到 1 是身份元素，因为对于群中的任何数字 a：

每个群必须有一个身份元素。不过，有些可能不那么显而易见。

然后，我们有 生成元。这个想法同样相当简单：取群中的一个元素 g，并与 它自己 执行群运算。

为了简单起见，暂时假设群是乘法群。因此，结果是 g² 而不是 2g。

拿结果，再次乘以 g，得到 g³。重复这个过程，直到结果再次为 g。

模 p 的整数乘法群是 循环的——不仅是有限的，经过足够多次运算后，你会回到同一个生成元。就像时钟上的数字一样！

如果在这个迭代过程中你看到群中的 每个元素，然后才重新获得 g，那么我们说它 生成 该群，或者说它是该群的一个 生成元。通常用以下符号表示：

并非所有群中的元素必然是生成元。更多时候，我们会发现 𝔾 的一个 子序列。恰好这个子序列也表现得像一个群——实际上，这些生成的子集被称为 子群。

为什么是群？

此时你可能想知道，群有什么特别之处。与我们到目前为止观察到的事物相比，它们似乎并不特别花哨。

然而，表象可能会产生误导。尽管它们看起来简单，但它们是许多加密算法的 支柱！

至少在环和基于格的加密变得更普及之前！

在现代加密的早期，像 Diffie-Hellman 密钥交换 和 Rivest-Shamir-Adleman（RSA）等算法彻底改变了信息共享和保护的方式。这两者都是基于一个简单的操作：模指数运算。换句话说，像这样操作：

看看这个——y 是由 g 生成的乘法群的一个元素。这就是说明 g 是一个群生成元，这也意味着它不能是群的身份元素。

确实存在 快速模指数运算 的算法。但反向过程——在我们的例子中，寻找 x —并没有那么简单，因为模运算引入了非线性。

反转指数运算的问题被称为 离散对数问题，或 DLP。尽管 确实存在算法 可以解决这个问题，但它们的效率远不如快速的指数运算。随着群规模的增大，问题的难度也随之增加——对于足够大的群，该问题在常规模计算能力下是 不可行 的。

为了正确起见，我必须澄清，RSA 不是基于 DLP，而是基于 整数因式分解问题 _。

所以，没错，群 是 有用的！但是这与椭圆曲线有什么关系？

嗯……

椭圆曲线群

嗯，我在文章开头就有点剧透了。

椭圆曲线，加上我们定义的加（和翻倍）点的操作，形成 群。

模指数运算的等价物是点标量乘法：我们取一个整数 x，计算：

这是将 G 加在一起 x 次的简写。

同样，G 是一个 生成元，不同于 群的身份。

在椭圆曲线群中，身份点是无穷远点 𝒪。

使这些群与整数乘法群不同的，是计算二元运算所需的成本要 高得多。将两个整数相乘相对简单而迅速，而增加椭圆曲线点则涉及多个乘法。

这很重要，因为这使得解决 DLP 困难得多。正如我们之前提到的，大多数现代加密依赖于这一问题的困难性或类似问题。问题越困难，安全性越高。

至少，对于类似的密钥大小。你可以在 这里 找到关于此的有趣讨论。

群大小

只要我们处理的是 大型群，这一切都是好的。如果不是，那么我们的努力将付之东流。

任何依赖 DLP 作为安全基础的问题都可以转换为椭圆曲线群——我们存在椭圆曲线离散对数问题，即 ECDLP。

确实存在小的椭圆曲线群的例子——我们在 上一篇文章 中见过一个。那些对于加密目的并没有什么用处。

此外，仅通过查看其仿射方程，立即看出椭圆曲线的大小也并不明显。因此你可能想知道：我们如何知道给定椭圆曲线群的大小？

我们可以首先尝试简单的方法：字面上就是 计数每一个点。

考虑例子曲线 y² = x³ + x + 1 在 𝔽₇ 上。为了找到曲线上的所有点，我们只需检查所有坐标在 𝔽₇ 中的组合 (x, y)——满足上述方程的组合将是曲线上的点。当然还有 𝒪。

一个稍微更快的方法是利用曲线的对称性，这将把我们的搜索域缩小一半。

在这个小例子中，我们总共发现了 9 个点。还不算太糟，对吧？

但当曲线定义在一个 大型素数 的 𝔽ₚ 上时，我们就遇到了问题。如果 p 是一个 256 位整数，即使现代超级计算机也将花费过多的时间来计算曲线中的所有点。真是长得可以一直到宇宙热寂。

仍在等待。

大致来说，大多数实际使用的椭圆曲线是在大小约为 2²⁵⁶（这是一个 77 位数字）的域上定义的。

这是不切实际的，至少可以说。

当然，更有效的方法已经被开发出来。一个最著名的算法是 Schoof 算法，它利用了一些我们尚未介绍的概念，如 Hasse 界限 和 Frébenius 同态。我们也许会在后面讨论这些。

Schoof 算法在多项式时间内运行，还有一些更快的替代方案，如 Schoof-Elkies-Atkin (SEA) 算法。

在处理群大小时，还有一个需要注意的点是其 素因式分解。椭圆曲线群的大小通常是一个 合数（即不是素数）。也就是说，群的大小 #E(𝔽ₚ) 将是：

其中 pᵢ 是素数。

我们为什么要关注这一点？因为有一个叫 拉格朗日 的家伙。

拉格朗日定理 在群论中揭示，如果 q 是某个群 G 的阶，则该群将具有 阶为 pᵢ 的 循环子群——这是 q 的因子。

这很棘手，因为另一个定理： 中国剩余定理（简称 CRT）。长话短说，通过寻找每个阶 pᵢ 的子群，可以解决 DLP 在每个子群上，然后将结果结合起来。

如果我们分析这个过程，我们会发现这些子 DLP 中最困难的是与最大的 pᵢ 相关的。

所有这一切是说：我们不仅要找一个 大的 椭圆曲线群——我们真正需要的是一个具有 大素因子的 大型群。

谢谢你，拉格朗日。

更深的联系

最后，我想花点时间来讨论一个非常有趣的话题。计算椭圆曲线上的点在加密中有实际应用，正如我们刚刚看到的。但它也与数学中一个最深刻的未解难题相关： Birch 和 Swinnerton-Dyer（BSD）猜想。

这个猜想是6个未解的千年难题之一。如果你感到特别激动，可以试着阅读问题陈述，看看是否能引起你的兴趣！解决此问题将获得百万美元奖金。

BSD 猜想是关于寻找椭圆曲线上的 有理点——其坐标为 分数 的点，例如 (1/2, -3/4)。某些曲线可以具有无限数量的有理点，而其他曲线只能有有限的数量。该猜想是关于理解一个椭圆曲线属于这两种类别的哪一种。

虽然在实数域上的椭圆曲线可以形成无限群，但当我们在有限域上定义它们时，它们会自动变成有限群。这是因为我们的坐标仅能取自有限域中的值——每个坐标只有 p 个可能的值。这种有限性质更适合于加密目的。

弄清这一点是一个复杂的任务。确实——它涉及使用一种称为 L-函数 的东西，这个函数定义在复数域上。计算这个 L-函数与点计数紧密相关，这正是我们刚才的目标。

理解 BSD 猜想需要一些时间。如果你感兴趣，这里有 克雷数学研究所的讲座，以及另一段精彩的视频（用西班牙语，带有字幕）对其进行了详细的解释和动画。

但那是另一个时代的兔子洞。我们回到现实。

总结

在阅读完这篇文章后，如果我们再次被问到什么是椭圆曲线，我们现在可以谈论 椭圆曲线群，并且我们现在知道这些是对加密有用的结构。

椭圆曲线群的应用非常广泛。我建议查看加密101系列，以获取关于涉及椭圆曲线的算法的长（但不完整）列表。

但故事并没有到此结束。有关椭圆曲线还有很多要说的内容。关于如何使计算更快的提示，以及如何选择“好的椭圆”曲线等等——前方还有很多乐趣。

• 原文链接： medium.com/@francomangon...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，在这里修改，还请包涵～