数学基础之椭圆曲线

椭圆曲线

本文来里聊一聊密码学当中另一个用的比较广泛的数学知识，椭圆曲线，至于为什么叫椭圆曲线，在参考资料[1]当中, 给出了一个解释。

当初人们享用微积分计算椭圆曲线的周长，通过一定的积分技巧，最终要求出以下类型的积分:

其中分母的函数项是, 如果平方以下，就得到了, 这个恰好是椭圆曲线的方程的一种形式，这种形式被称为Weierstrass型。本文也主要讨论这一种类型，当然其他类型的曲线在密码学中也有使用，由于个人水平有限，就先只讲一下Weierstrass型。

❝

友情提示: 本文后面会用到之前聊过的有限域的相关知识，如果不熟悉的读者可以自行回顾一下我之前写的文章。

❞

实数域上的椭圆曲线

先来看一下实数域上的椭圆曲线，这里推荐一个工具，cocalc, 具体链接可以再参考资料里面找，这个工具可以在线使用saga等工具，本文当中大部分图都是用这个工具绘制的，同样我也会给出绘制的代码，各位读者大佬们可以自己玩玩。

先来看几个例子:

E = EllipticCurve([-1, 0])
Ep = plot(E,-3,4,thickness=1)
show(Ep)

曲线一

上图表示的是, 这一条曲线的图。

E = EllipticCurve([-1, 1])
Ep = plot(E,-3,4,thickness=1)
show(Ep)

曲线二

上图表示的是, 这一条曲线。

其余对于a和b的改变曲线的形状，读者可以自行构建环境运行看看，这里我就不过多去截图了。

直观的看完椭圆曲线的形状，那么接下来我们来看一下有关椭圆曲线的运算，本文只是简单介绍一下运算的规则和性质，有关证明，我其实也不太熟悉，所以就不讲了，这次不给自己挖坑，证明这东西看着头大，哈哈。

考虑一个集合，满足椭圆曲线(这里的曲线目前指的是Weierstrass, 后文不做特殊说明，均为这种形式)表达式所有的点(x, y)构成的集合, 这里要加上一个无穷远点的概念，记做O, 我们记做集合E(a, b), 如果a和b不同，所对应的集合也就不同。

比如上面的图当中我绘制的两条曲线，实际体现在代码当中就是EllipticCurve([-1, 0])和EllipticCurve([-1, 1]), 分别对应a和b的值。

有了集合，自然而然的要考虑在这个集合上可以定义什么运算，我们在这个集合上定义一个加法运算"+", 可以证明，如果a和b满足如下条件:

的话，在这个加法运算和E(a, b)下，构成一个群，具体证明我也不太清楚，本文的重点还是一些结论，对于证明什么的先放到一边去吧。

首先，给出无穷远点，也就是上文提到的O是怎么来的，从几何的角度来说，如果椭圆曲线上的三个点共线，则他们的和为O, 基于这个无穷远点的定义，我们给出椭圆曲线上面具体的加法运算:

• O是加法的单位元，对于单位元的性质，具体参考有限域的的知识，这里不啰嗦了，下面假设椭圆曲线上有两个点P和Q, 其中, 并且 。
• 点P的负元是和点P当中x相同y坐标相反的点，根据椭圆曲线关于y轴对称，很容易验证，这个负元是在椭圆曲线上的，举个例子，比如P = (x, y)，那么 -P = (x, -y)。
• 如果要计算P和Q两个点的和，这肯定是不能简单的相加的，不相信的可以自己试试，如果直接横纵坐标相加，这个点大概率的不在这条曲线上了，所以定义如下规则的加法运算，连接P, Q, 显然可以得到一条直线和椭圆曲线相交于另一点R, 这个焦点是存在且唯一的，为了构成一个群，定义如下加法运算: P + Q = -R
• 考虑Q=-P的情况，这里定义 P + (-P) = O, 两点由一条垂线连接，可以假设他们相交于无穷远点O
• 最后一种情况，也就是倍点运算，也就是Q+Q的情况，这里可以画一条切线，相交曲线与S, 这里 Q + Q = 2Q = -S

通过上面的定义，可以证明在上述的加法运算下构成一个交换群。

对，作为灵魂画手的我又来手绘了，下图演示了在椭圆曲线上的加法运算，依然不接收绘图的吐槽，哈哈。

加法运算

上面是通过几何的方面对椭圆曲线上的加法运算进行了描述，但是这个几何看起来直观，但是要进行运算，还是需要给出代数描述，这里直接给出结论，对于推导过程，想了解的可以读者自行查阅相关资料。

假设P = (, ), Q = (, ), 连接它们曲线的斜率为, 这个实际上也就是两点间的斜率公式，假设P和Q的连线l与椭圆曲线相交于点R, 经过计算可得R = P + Q，即:

除此之外，P和Q重合的情况，也就是倍点运算，具体公式如下:

到这里，实数域上面的椭圆曲线就介绍完了，本文只是做了一个简单的介绍，涉及到详细的数学推导这里都没有展开，有兴趣的读者可以自行查阅相关资料，不过作为了解这个东西，只是了解一些结论方面的东西个人感觉也够用了，当然如果想在椭圆曲线上面做深入研究的话，这个还是需要更深一层的了解的。

有限域()上的椭圆曲线

对于密码学而言，定义在实数域上面的东西大概率是没法直接来用的，因为在计算机里面存在的大多不会是连续的值，都是离散的值，所以考虑一下在有限域上的椭圆曲线，这里本文只讨论下的有限域，对于GF()这个其实也相似，不过计算起来要麻烦点，毕竟多项式的运算没有数字运算简单，所以先不讨论了。

来看一下在下面的椭圆曲线的表现形式，其实也就是x和y都取整数，并且模p, 表达式如下:

同样的，这里面也是有无穷远点O的，和实数域上的椭圆曲线不同的是，这里多了一个参数p, 所以这个群记做, 同样的，要想构成一个群，也是需要满足一定条件的, 具体条件如下：

这里和实数域上的也类似，只不过多了取模的运算。

同样的，我们来看一个例子，依然用cocalc来进行绘图，假设曲线, 具体绘图代码如下：

E = EllipticCurve(GF(23),[1,1])
print(E)
graphics_array([plot(E.change_ring(GF(23)))])

E_23(1, 1)

这里，实际上他就不是连续的了，而是一个个离散的点，并且是没有什么规律的，具体的加法运算和实数域上类似，只不过要注意的是这里是在下的运算。

不过这个就没有几何方面的直观显示了，直接给出代数定义吧, 对于曲线的两个点P和Q:

其中:

这里实际上和实数域上面也是类似的，公式来源于密码编码学域网络安全一书。

小结

本文主要是介绍了一些椭圆曲线的一些运算方法和结论，并没有涉及实质性的证明，对于椭圆曲线来说，这里面用到的数学知识实际上比Elgamal和RSA多了不少，本文公式和文字比较多，也比较枯燥，希望读者见谅。