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

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

椭圆曲线的集合论定义

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

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

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

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

<aside> 💡 💡 打个比方:这个方程就像一张『入场资格表』。平面上有无数个 $(x,y)$ 点,但只有把坐标代进去、左右两边真的相等的点,才算『在曲线上』。比如取 $a=0,b=9$,点 $(3,6)$ 代进去:左边 $6^2=36$,右边 $3^3+9=36$,相等,所以它有资格;而 $(3,5)$ 算出来 $25\ne36$,就被挡在门外。$a$ 和 $b$ 只是调节曲线胖瘦弯曲程度的两个旋钮。

</aside>

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

不同 a、b 取值下的几条椭圆曲线

不同 a、b 取值下的几条椭圆曲线

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

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

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

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

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

具体来说,要成为一个群,这个点集需要具备:

<aside> 💡 💡 一句话理解这三条要求:把『群』想象成一台规规矩矩的机器。第一条说『塞两个零件进去,吐出来的还是同款零件』(不会冒出曲线外的怪东西);第二条说『有个万能占位符 $I$,谁碰它都原样返回』,就像乘法里的 $1$、加法里的 $0$;第三条说『每个零件都有专属搭档,两个一合就还原成占位符 $I$』,就像 $5$ 和 $-5$ 相加回到 $0$。

</aside>