密码学 ｜ 第六章 椭圆曲线和密码学
Chapter 6 Elliptic Curves and Cryptography
椭圆曲线这一主题包含了大量的数学知识（事实上，在椭圆曲线成为密码领域的佼佼者之前，一位著名数学家S. Lang【下面推荐的好几本书都是他的】就认为 “it is possible to write endlessly on elliptic curves!**” ）。这一章我们主要是想总结足够的用于密码学应用的基础理论。如果想进行拓展阅读的话，这里也推荐了几本关于椭圆曲线密码的综述和书籍——《Elliptic Curves in Cryptography》、《Algebraic Aspects of Cryptography》、《Elliptic Curve Public Key Cryptosystems》、《Elliptic curves and cryptography》，以及其他一些描述椭圆曲线理论的数论方面的文章和书籍——《Lectures on Elliptic Curves》、《Elliptic Curves》、《Elliptic Curves: Diophantine Analysis》、《Elliptic Functions》、《Advanced Topics in the Arithmetic of Elliptic Curves》、《The Arithmetic of Elliptic Curves》、《Rational Points on Elliptic Curves.》。【具体的书籍版本、作者信息啥的，可以去原书P299 看一下，太长了，就不记在这里了】
6.1 Elliptic Curves
这里的的椭圆曲线（椭圆曲线不是椭圆，事实上，尽管它的名字包含椭圆，但椭圆曲线和椭圆之间只有最微妙的联系）其实就是下面这条等式的解集
这条等式的形式我们称之为 Weierstrass equations，是的，以一个在十九世纪对椭圆曲线进行广泛研究的数学家命名的。图 6.1 给了两个例子
在椭圆曲线上有个很神奇的性质就是，可以很自然的，在线上取两个点，然后将他们 “相加” ，可以得到第三个点。之所以这里的 “相加” 用引号，因为我们这儿的操作是类似于加法一样去将两点组合（可交换、可结合，还有一个恒等式），但并不是我们平常用的那种加法。为了使我们对这儿的 “加法“ 描述得更自然些，也方便读者更好的理解，还是要用上几何这个工具。
设 是椭圆曲线 上两个点，如图 6.2 所示。
我们通过 做一条直线 ，这条直线与 相交于三点，分别记为 ,我们对 点根据 轴做一个对称点 （也就是将这个点的纵坐标乘以 -1）。这个过程和我们平常概念中加法很不一样，但我们称这个点 为 之和。现在，我们给这么一个奇怪的加法【我一般叫他点加】一个符号 ，写作
例 6.1 设有曲线
曲线上有点 ，连接他俩的直线 为
现在我们去找 相交的第三点，我们将 6.2 式 代入到 6.1式中消去 得到
我们需要找到这个三次多项式方程的根，一般来讲计算三次根还是比较麻烦的，但是由于我们已经知道这条方程的两个根了（ 相交于 两点），即 ,所以我们可以比较轻松的找到上式的因式分解
所以 相交的第三点的 轴坐标就是 ，然后根据 的表达式找到 轴坐标，有 ，在做一个 轴对称，得到 。
在椭圆曲线的加法上还有一些特殊情况需要考虑，首先，如果我们想用 点加上它自己呢？想象一下，如果点Q沿着曲线滑动并越来越靠近 ，连接 和 的线 会发生什么情况？在极限下，当 接近时， 将会成为 处 的切线，因此，如果我们想给 加上它自己，我们只需要如图6.3 过 做 的切线 ， 会与 相交于 ，然后像上面一样做一个 轴对称得到 。在某种意义上， 仍然与 相交于三个点，不过 重合了而已。
例 6.2 继续用 例6.1 上设定的曲线，现在我们要计算 ，曲线 在 点的斜率我们要用到隐式微分方程 6.1，因此我们有 。将点 的值代入得到斜率 ，所以 在点 处的切线为
现在我们把 6.3 式代入到 6.1 ，然后做一个因式分解可以得到
注意到点 的横坐标的值，，是三次多项式的 个根，所以我们能够很容易的对这个式子做因式分解。最后我们将 代入到等式 就可以得到 ，转换一下 轴的值我们得到
对于我们这里点加的第二个潜在的问题就是，如果我们将点 和它关于 轴对称的点 相加，连接 的即为垂线 ，并且这条线和 只相交于两个点 （见图 6.4），这里没有第三个交点，那咋办嘛？解决方法就是我们额外给他加一个点进去 ，这个点在无限远处，它不在 上，但是我假设他在这条垂线的无限远处，所以我们设 。
我们还需要解决怎么将 和普通点 相加的问题。连接 的直线是 处的垂线，所以这条线和 交于 ，我们将 相加，然后反转另一个交点 ，我们有转回来得到了 。即 ，所以 其实是在椭圆曲线加法中扮演了一个 的角色。【有时候也会叫他单位元、零点】
例 6.3 继续用 6.1 的曲线，注意到点 是在这一条曲线上的一个点。注意到点 处的切线也正好是垂线 ，所以我们给 加上它本身，得到 。
定义 椭圆曲线 是 Weierstrass equation 的解集加上一个额外的点 ，并且要求 满足 。
加法规则定义如下，设 为椭圆曲线 上的两点， 为连接 两点的直线或者是 在 处的切线（如果 ）。那么 相交于三点 ，然后通过一些计算，并且基于 是在每一条垂线上的设定，我们记 ，则 之和为，即 基于 轴的对称点。有两种写法：
除此之外，如果 ，我们定义 的reflected： ，或者直接 。随意我们定义 为 。同样的，如果重复的点加法即为给点乘以一个整数，表示为
注 6.4 为啥前面额外要求 ？ 被成为 的判别式。 意味着三次多项式 不会有 repeated roots【这里的repeated roots意思是三个根都是一样的】即，我们将式子 因式分解为 ，其中 可以是复数，那么， 当且仅当 是 distinct，【用代码表示就是，if not e1==e2=ee3】（见练习 6.3）如果 就会有奇异点（见练习6.4）加法法则在这种曲线上就不是很适用。所以我们在定义椭圆曲线的时候额外要求 。
定理 6.5 设 为一条椭圆曲线，那么这条曲线上的加法有一下性质
Identity: Inverse: Associative: Commutative:
换言之，点加使得 上的点构成了一个阿贝尔群。（可以回见 2.5一节再看看关于群的讨论和相关公理）
证明
如前文所述，Identity law 和 inverse law是正确的，因为 在所有的垂线上。commutative也很好验证，因为从 向 连接的直线 和 从 向 连接的直线是同一条。所以点的顺序没有影响。
那么我们只剩下 associate law了。可以乍一眼看过去应该不是很难证叭。到那时如果开始在纸上画图去证明它，你会发现其实还是很复杂的。有很多方法去证明 associate law，但它们都很麻烦。在我们为 上的加法给出明确的计算式之后（定理6.6），读者可以用这些公式去检验一下 associate law。如果想了解更 perspicacious 的证明，可以冲 S. Lang, Elliptic Functions. Volume 112 of Graduate Texts in Mathematics, 2nd edn. (Springer, New York, 1987). With an appendix by J. Tate。
我们的下一个任务是找到显式公式，使我们能够轻松地在椭圆曲线上进行加减运算。这些公式的推导使用了初等解析几何、微积分来寻找切线、以及一些代数运算。我们先给出结果，然后简要证明一下。
定理 6.6 （椭圆曲线加法算法）设曲线 ， 是曲线上的两点，那么有
如果 ，那么 如果 ，那么 否则设 如果 ，那么 否则 定义
然后我们就有
证明
1 和 2 是很显然的，4 的话就是垂线的情况，所以 ，对于 5，我们注意到，如果 ，那么 就是经过 和 直线的斜率表示，如果 ，那么这个 就是 点切线的斜率。我们设直线 的表达式： ，代入到 得到：
我们知道这个三次方程有两个根 ，我们设第三个根为 ，那么我们可以对上式做一个因式分解：
我们把右手边的式子打开得到 ，注意到 的系数是 ，对比一下左边可以知道这个肯定是等于 的，所以我们知道 ，有了 的坐标，因为第三个点是 的交点，所以我们再根据 的表达式计算出 就可以了，最后，我们是计算 ，我们再将得到的交点根据 轴做一个反转，也就是把纵坐标取负值我们就得到第三个点 了。