专业信息安全工程师网站|培训机构|服务商(2018信息安全工程师学习QQ群:327677606,客服QQ:270019001)

软题库 培训课程
当前位置:信管网 >> 信息安全工程师 >> 综合知识 >> 文章内容
椭圆曲线的基本概念-信息安全工程师知识点
来源:信管网  2018年10月11日  【信管网:项目管理师专业网站所有评论

信息安全工程师知识点:椭圆曲线的基本概念

椭圆曲线并不是椭圆,之所以称为椭圆曲线是因为它们与计算椭圆属长的方程相似。椭圆曲线可以定义在不同的有限域上,对我们最有用的是定义在GF(p) 上的椭圆曲线和定义在GF(2m)上的椭圆曲线。下面介绍GF(p)上的椭圆曲线。

定义2.1设p是大于3的素数,且4a3+27b2≠0 mod p,称曲线

y2=x3+αx+b,α,b∈GF(p)          (2-51)

为GF(p)上的椭圆曲线。

由椭圆曲线可得到一个同余方程:

y2=x3+αx+b  mod  p                  (2-52)

其解为一个二元组(x,y) ,其中x,y∈GF(p),将此二元组描画到椭圆曲线上便为一个点,于是又称其为解点。

为了利用解点构成交换群,需要引进一个0元素,并定义如下的加法运算:

①引进一个无穷点O(∞,∞),简记为O,作为O元素。

O(∞,∞)十O(∞,∞)=0+0=0            (2-53)

并定义对于所有的解点P(X , y) ,

P(x,y) +O=O+P(x,y) =P (x,y)       (2-54)

②设P(x1,y1) 和Q (x2,y2) 是解点,如果x1=x1且y1=-y2,则

P(x1,y1) +Q(x2,y2) =0                   (2-55)

这说明任何解点R(x,y) 的逆就是R (x,-y) 。

③设P(x1,y1) 和Q(x2,y2) 是解点,如果P≠±Q,则

P(x1,y1) 十Q(x2,y2)=R(x3,y3)

其中

(4) 当P(x1,y1) =Q(x2,y2)时,

P(x1,y1) 十Q(x2,y2)=2P(x1,y1)=R(x3,x3)

其中

作集合E={全体解点,无穷点O} 。

可以验证,如上定义的集合E 和加法运算构成加法交换群。

椭圆曲线及其解点的加法运算的几何意义如图2-35所示。

设P(x1,y1)和Q(x2,y2)是椭圆曲线的两个点,则连接P(x1,y1) 和Q(x2,y2)的直线与椭匾曲线的另一交点关于横轴的对称点即为P(x1,y1)十Q(x2,y2)点。

例2-4取p=11,,椭圆曲线y2=x3+x+6。由于p较小,使GF(p)也较小,故可以利用穷举的方法根据式(2-54)求出所有解点。穷举过程如表2-12所示。

①根据表2-12 可知全部解点集为{ (2 ,4), (2,7) ,(3,5), (3,6), (5,2),(5,9), (7, 2), (7,9) ,(8, 3) ,(8, 8),(10,2) ,(10, 9) }。再加上无穷远点O,共13的点构成一个加法交换群。

②由于群的元素个数为13 ,而13为素数,所以此群是循环群,而且任何一个非O元素都是生成元。

③由于是加法群n个元素G相加,G+G+...+G=nG。我们取G= (2, 7) 为生成元,具体计算加法表如下:

2G= (2,7) + (2,7) = (5,2),这是因为λ= (3x22+1) (2x7) -1 mod 11 =2x3-1 mod 11=2x4 mod 11=8 。于是,x3=82-2-2 mod 11=5,y3=8 (2-5) -7 mod 11=2 。

经过类似计算,最后得:

G= (2, 7) , 2G= (5 , 2)

3G= (8, 3) , 4G=(10, 2)

5G= (3, 6), 6G= (7, 9)

7G= (7, 2) , 8G= (3, 5)

9G=(10, 9), 10G= (8 , 8)

11G= (5, 9) , 12G= (2, 4)

13G=12G+G= (2, 4) + (2, 7) =0

由此显然可知,全部解点加上无穷远点O的集合{O,G,2G,3G,4G,5G,6G,7G, 8G, 9G, 10G,11G, 12G} 构成循环群,其中任何一个非零元素都是生成元。



例2-5 p=5时,GF(p)上的一些椭圆曲线的解点数(包含无穷远点)如表2-13所示。

在以上例中,由于参数p较小,使得有限域GF(p)也较小,故可以利用穷举的方法求出所有解点。但是,对于一般情况要确切计算椭圆曲线解点数N 的准确值比较困难。研究表明, N满足以下不等式
P+1-2P1/2≤N≤P+1+2P1/2 (2-58)
式(2-58)给出椭圆曲线解点数N的计数范围。
虽然确切计算椭圆曲线解点数N 的准确值比较困难,但是已有一个比较有效的算法来计算它。吕前已经能够有效计算p大到10409的GF(p)上的椭圆曲线解点数和m大到601的GF(2m)上的椭圆曲线解点数。
为了能够利用椭圆曲线构成安全的椭匮曲线密码,必须选用好的椭匾曲线。所谓好的椭圆曲线是指,据此曲线构成的椭睦曲线密码是安全的,而且运算是快速的。



分享到: 新浪微博 腾讯朋友 收藏本页
发表评论  查看完整评论  

相关内容

推荐文章
合作网站内容