狼爱上狸

我胡汉三又回来了

有趣的椭圆曲线加密

一、概述

椭圆曲线加密算法依赖于椭圆曲线理论,后者理论涵盖的知识比较深广,而且涉及数论中比较深奥的问题。经过数学家几百年的研究积累,已经有很多重要的成果,一些很棘手的数学难题依赖椭圆曲线理论得以解决(比如费马大定理)。

本文涉及的椭圆曲线知识只是抽取与密码学相关的很小的一个角落,涉及到很浅的理论的知识,同时也是一点比较肤浅的总结和认识,重点是利用椭圆曲线结合数学技巧阐述加密算法的过程和原理。

本文特意构造有比较多的实例方便理解其过程和原理。

二、椭圆曲线

椭圆曲线方程来源于椭圆积分,后者来最初来源于计算椭圆周长的问题,有一段时间的历史了,在欧拉时期就开始研究。椭圆周长没有精确的初等函数的公式表示,只有近似的公式表示,精确的椭圆周长可以用不定积分表示。

现在一般将形如如下形式的积分定义为椭圆积分:

(x)=cxR[t,P(t)]dt" role="presentation">

其中

是其两个参数的有理函数,是一个无重根的3或4阶多项式,而是一个常数。椭圆曲线方程与(t)" role="presentation">

表现形式比较相像。

数学上的椭圆曲线一般由如下形式给出:

,其中判别式Δ(E)=4a3c+a2b24b327c2+18abc0" role="presentation">

椭圆曲线都是关于X轴对称的曲线。

典型的椭圆曲线如:

,其图像为:

更多的椭圆曲线图像:

 限定Δ" role="presentation">

不为零有特殊的意义。如果判别式Δ(E)" role="presentation">等于零,由三次方程判别式判定理可知,方程

存在二重根或者三重根,曲线表现为"自相交"或者有“尖点”。

两个典型的例子是:

有三重根,表现为有"尖点";

有二重根,表现为“自相交”,它们都不是椭圆曲线,其图像分别如下:

                          

在密码学中用到的椭圆曲线方程一般限定为:

,其中

也即是这里的二次项系数为0。

三、椭圆曲线算术

椭圆曲线上可以定义一些很有意思的特殊运算规则。一般来说会定义两种运算:加法和数乘运算。加法运算是点与点之间的运算;数乘运算基于加法运算,重复的加法运算就是数乘。

1、实数域的加法运算

1.1、加法运算的几何解释

已知椭圆曲线上两个不同的点

,则这两个点之和可以通过如下操作得到:过两点做直线,与椭圆曲线相交于第三点,该点关于X轴的对称点即是所求的

点。椭圆曲线的这种加法运算有比较明确的几何含义。如下所示:

以这种比较奇特的规则来定义加法运算会让人觉得比较怪异,其思想很可能是借鉴于求椭圆曲线有理解的方法(没有去严格考据)。

求椭圆曲线有理解考虑的问题是寻找有理点(x,y)" role="presentation">

使其满足椭圆曲线方程。其求解过程是在有限的已知有理点的集合中,选两个点,作直线与椭圆曲线相交与第三点个有理点。此时如果再利用三个点中的任意两点作直线不能在产生新的有理解(因为他们本身是已经在一条直线上,不会产生新的交点),但是考虑关于X轴对称的点必定也是有理点,于是可以利用或者

继续做直线与椭圆曲线相交得到新的有理解,对新的交点再取对称点,以此迭代下去。由此利用交点的对称点作直线来生成新的交点,进而可逐步求解满足椭圆曲线的有理解。

椭圆曲线加法运算的规则中“取交点的对称点”正是与上述求解过程及其相似。

对于加法运算也有另外一种描述:若椭圆曲线上三个点在同一直线上,则他们的和为

,也即是,其中的

是无穷远点或者零点。

更完整的椭圆曲线加法运算规则如下:

1、

,对任意的,有

看做零点,对加法运算没有实际贡献(类似于四则运算加法运算中的0)。

2、(x,y)" role="presentation">

的负元是关于X中对称的点(x,y)" role="presentation">(而不是关于原点对称),(P)=O" role="presentation">。过的直线与X轴垂直,实际上可以看做它与椭圆曲线相交于无穷远点(射影平面,也即是在欧式平面上添加了无穷远点和无穷远直线的平面),因此将也将

视作无穷远点。

3、计算

的和是通过做过两点的直线,与椭圆曲线相交于第三点,再取该点关于X轴的对称点以此作为

之和,正如上面的几何图形展示的那样。

4、计算

点()的两倍时,是做该点的切线,再取交点关于X轴的对称点,也即是

容易验证,对于椭圆曲线上的点和

点组成的集合,以及集合上定义的二元加法运算,构成一个Abel群。单位元是点,(x,y)" role="presentation">的逆元是(x,y)" role="presentation">

,封闭性,结合性以及交换性也是显然满足的。

1.2、加法运算的代数解释

几何解释更直观,代数解释更有利于数值计算。

过曲线上(xp,yp)" role="presentation">

(xQ,yQ)" role="presentation">两点(

不互为负元)做直线,求与曲线的第三个交点的问题是很容易用代数的方法来描述的。

也即是求:

y2=x3+ax+b(1)yyp=k(xxp)(2)" role="presentation">

其中斜率

将(2)代入(1)再利用次数对齐的方式容易求得第三个交点的对称点也即

之和(xR,yR)" role="presentation">

为:

(xPxR)" role="presentation">

如果需要计算倍乘,可以让多个点自身重复相加得到。例如

,当

时,代数描述为:

(xPxR)yP" role="presentation">

2、模素数P的加法运算

密码学中普遍采用的是有限域上的椭圆曲线,也即是变元和系数均在有限域中取值的椭圆曲线。使用模素数

的有限域,将模运算引入到椭圆曲线算术中,变量和系数从集合

中取值而非是在实数上取值。

此时讨论椭圆曲线形式如下:

modp=(x3+ax+b)modp" role="presentation">

其中(4a3+27b2)modp0modp" role="presentation">

,变量和系数均在

中取值。

将满足上式的所有非负整数对和