椭圆曲线ECC加密算法入门介绍

法则详解:

▲这里的+不是实数中普通的加法,而是从普通加法中抽象出来的加法,他具备普通加法的一些性质,但具体的运算法则显然与普通加法不同。

▲根据这个法则,可以知道椭圆曲线无穷远点O∞与椭圆曲线上一点P的连线交于P’,过P’作y轴的平行线交于P,所以有 无穷远点 O∞+ P = P 。这样,无穷远点 O∞的作用与普通加法中零的作用相当(0+2=2),我们把无穷远点 O∞ 称为 零元。同时我们把P’称为P的负元(简称,负P;记作,-P)。(参见下图)

▲根据这个法则,可以得到如下结论 :如果椭圆曲线上的三个点A、B、C,处于同一条直线上,那么他们的和等于零元,即A+B+C= O∞

▲k个相同的点P相加,我们记作kP。如下图:P+P+P = 2P+P = 3P。

下面,我们利用P、Q点的坐标(x1,y1),(x2,y2),求出R=P+Q的坐标(x4,y4)。

例4.1:求椭圆曲线方程y2+a1xy+a3y=x3+a2x2+a4x+a6上,平常点P(x1,y1),Q(x2,y2)的和R(x4,y4)的坐标。

解:(1)先求点-R(x3,y3)

因为P,Q,-R三点共线,故设共线方程为y=kx+b,其中

若P≠Q(P,Q两点不重合) 则

直线斜率k=(y1-y2)/(x1-x2)

若P=Q(P,Q两点重合) 则直线为椭圆曲线的切线,故由例3.1可知:

k=(3x2+2a2x+a4 -a1y) /(2y+a1x+a3)

因此P,Q,-R三点的坐标值就是方程组:

y2+a1xy+a3y=x3+a2x2+a4x+a6 -----------------[1] y=(kx+b) -----------------[2]

的解。

将[2],代入[1] 有

(kx+b)2+a1x(kx+b)+a3(kx+b) =x3+a2x2+a4x+a6 --------[3]

对[3]化为一般方程,根据三次方程根与系数关系(当三次项系数为1时;-x1x2x3 等于常数项系数, x1x2+x2x3+x3x1等于一次项系数,-(x1+x2+x3)等于二次项系数。)

所以-(x1+x2+x3)=a2-ka1-k2

x3=k2+ka1+a2+x1+x2;---------------------求出点-R的横坐标

因为k=(y1-y3)/(x1-x3) 故

y3=y1-k(x1-x3);-------------------------------求出点-R的纵坐标

(2)利用-R求R

显然有 x4=x3= k2+ka1+a2+x1+x2; ------------求出点R的横坐标

而y3 y4 为 x=x4时 方程y2+a1xy+a3y=x3+a2x2+a4x+a6的解

化为一般方程y2+(a1x+a3)y-(x3+a2x2+a4x+a6)=0 , 根据二次方程根与系数关系得: -(a1x+a3)=y3+y4

故y4=-y3-(a1x+a3)=k(x1-x4)-y1-(a1x4+a3); ---------------求出点R的纵坐标

即:

x4=k2+ka1+a2+x1+x2;

y4=k(x1-x4)-y1-a1x4-a3;

本节的最后,提醒大家注意一点,以前提供的图像可能会给大家产生一种错觉,即椭圆曲线是关于x轴对称的。事实上,椭圆曲线并不一定关于x轴对称。如下图的y2-xy=x3+1

五、密码学中的椭圆曲线

我们现在基本上对椭圆曲线有了初步的认识,这是值得高兴的。但请大家注意,前面学到的椭圆曲线是连续的,并不适合用于加密;所以,我们必须把椭圆曲线变成离散的点。

让我们想一想,为什么椭圆曲线为什么连续?是因为椭圆曲线上点的坐标,是实数的(也

就是说前面讲到的椭圆曲线是定义在实数域上的),实数是连续的,导致了曲线的连续。因此,我们要把椭圆曲线定义在有限域上(顾名思义,有限域是一种只有由有限个元素组成的域)。

域的概念是从我们的有理数,实数的运算中抽象出来的,严格的定义请参考近世代数方面的数。简单的说,域中的元素同有理数一样,有自己得加法、乘法、除法、单位元(1),零元(0),并满足交换率、分配率。

下面,我们给出一个有限域Fp,这个域只有有限个元素。

Fp中只有p(p为素数)个元素0,1,2 …… p-2,p-1;

Fp 的加法(a+b)法则是 a+b≡c (mod p);即,(a+c)÷p的余数 和c÷p的余数相同。 Fp 的乘法(a×b)法则是 a×b≡c (mod p);

Fp 的除法(a÷b)法则是 a/b≡c (mod p);即 a×b-1≡c (mod p);(b-1也是一个0到p-1之间的整数,但满足b×b-1≡1 (mod p);具体求法可以参考初等数论,或我的另一篇文章)。

Fp 的单位元是1,零元是 0。

同时,并不是所有的椭圆曲线都适合加密。y2=x3+ax+b是一类可以用来加密的椭圆曲线,也是最为简单的一类。下面我们就把y2=x3+ax+b 这条曲线定义在Fp上:

选择两个满足下列条件的小于p(p为素数)的非负整数a、b

4a3+27b2≠0 (mod p)

则满足下列方程的所有点(x,y),再加上 无穷远点O∞ ,构成一条椭圆曲线。 y2=x3+ax+b (mod p)

其中 x,y属于0到p-1间的整数,并将这条椭圆曲线记为Ep(a,b)。 我们看一下y2=x3+x+1 (mod 23)的图像

是不是觉得不可思议?椭圆曲线,怎么变成了这般模样,成了一个一个离散的点? 椭圆曲线在不同的数域中会呈现出不同的样子,但其本质仍是一条椭圆曲线。举一个不太恰当的例子,好比是水,在常温下,是液体;到了零下,水就变成冰,成了固体;而温度上升到一百度,水又变成了水蒸气。但其本质仍是H2O。

Fp上的椭圆曲线同样有加法,但已经不能给以几何意义的解释。不过,加法法则和实数域上的差不多,请读者自行对比。

1. 无穷远点 O∞是零元,有O∞+ O∞= O∞,O∞+P=P

2. P(x,y)的负元是 (x,-y),有P+(-P)= O∞

3. P(x1,y1),Q(x2,y2)的和R(x3,y3) 有如下关系:

x3≡k2-x1-x2(mod p) y3≡k(x1-x3)-y1(mod p)

其中若P=Q 则 k=(3x2+a)/2y1 若P≠Q,则k=(y2-y1)/(x2-x1)

例5.1 已知E23(1,1)上两点P(3,10),Q(9,7),求1)-P,2)P+Q,3) 2P。 解 1) –P的值为(3,-10)

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4