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

五、密码学中的椭圆曲线

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

　　让我们想一想，为什么椭圆曲线为什么连续？是因为椭圆曲线上点的坐标，是实数的（也就是说前面讲到的椭圆曲线是定义在实数域上的），实数是连续的，导致了曲线的连续。因此，我们要把椭圆曲线定义在有限域上（顾名思义，有限域是一种只有由有限个元素组成的域）。

　　域的概念是从我们的有理数，实数的运算中抽象出来的，严格的定义请参考近世代数方面的数。简单的说，域中的元素同有理数一样，有自己得加法、乘法、除法、单位元(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)
　　　 2) k=(7-10)/(9-3)=-1/2，2的乘法逆元为12 因为2*12≡1 (mod 23)
　　　　　k≡-1*12 (mod 23) 故 k=11。
　　　　　x=112-3-9=109≡17 (mod 23);
　　　　　y=11[3-(-6)]-10=89≡20 (mod 23)
　　　　　故P+Q的坐标为(17,20)
　　　 3) k=[3(32)+1]/(2*10)=1/4≡6 (mod 23)
　　　　　x=62-3-3=30≡20 (mod 23)
　　　　　y=6(3-7)-10=-34≡12 (mod 23)
　　　　　故2P的坐标为(7,12)

　　最后，我们讲一下椭圆曲线上的点的阶。
　　如果椭圆曲线上一点P，存在最小的正整数n，使得数乘nP=O∞，则将n称为P的 阶，若n不存在，我们说P是无限阶的。
　　事实上，在有限域上定义的椭圆曲线上所有的点的阶n都是存在的（证明，请参考近世代数方面的书）

练习：
　　1． 求出E11(1,6)上所有的点。
　　2．已知E11(1,6)上一点G(2,7)，求2G到13G所有的值。