椭圆曲线密码算法

椭圆曲线密码算法(ECC)椭圆曲线是由NeilKoblitz(Koblitz,1985)和VictorMiller(Miller,1985)两位学者分别于1985年首先提出大多数的椭圆曲线密码系统是在模p或F2n下运算。此密码系统仍是存有RSA或ElGamal常见的弱点(e.g.同模数攻击、低指数攻击)。RSA与ElGamal系统中需要使用长度为

1024位的模数，才能达到足够的安全等级而ECC只需使用长度为160位的模数即可，且传送密文或签章所需频宽较少，并已正式列入IEEE1363标准椭圆曲线密码系统基于椭圆曲线离散对数问题(EllipticCurveDiscreteLogarithmProblem,ECDLP)。即在有限域K之下，给定椭圆曲线E上的两相异点P及Q，其中当点P的秩(order)若够大时(大于160位)，要找出一整数l使得Q=lP是很难的计算难题。在实数域中，椭圆曲线可定义成所有满足方程式的点(x,y)所构成的集合。若方程式没有重复的因式或，则能成为群(group)。例如，椭圆曲线的图形如图1-1所示。若，则此曲线将会形成退化(某些数的逆元素(inverse)将不存在)。椭圆曲线的图形如图1-1所示。椭圆曲线密码系统在模p(或Fp)下定义为椭圆曲线

其中模F2n下定义为椭圆曲线其中，此曲线称为nonsuper-singular。椭圆曲线有一个特殊的点，记为O，它并不在椭圆曲线E上，此点称为无穷远点(thepointatinfinity)两个相异的点相加：假设P和Q是椭圆曲线上两个相异的点，而且P不等于-Q

。若P+Q=R

，则点R是经过P、Q两点的直线与椭圆曲线相交之唯一交点的负点。如图1-2所示。双倍的点：令P+P=2P

，则点2P是经过P的切线与椭圆曲线相交之唯一交点的负点。如图1-3所示。椭圆曲线运算规则椭圆曲线在模p下的运算规则

加法规则：对所有的点P

E(Fp)，则P+O=O+P，

P+(-P)=O(ii)

令及且，则，其中(iii)

如果，则对所有的点而言，乘法规则：如果，则对所有的点而言，kP=P+P+…+P(k个P相加)如果，则对所有的点而言，例子1：有限域F23之下，点是椭圆曲线的生成数。请计算2P和3P的值

P=(0,1)2P=(13,13)3P=(5,5)4P=(3,15)5P=(6,17)6P=(19,2)7P=(17,9)8P=(18,0)9P=(17,14)

10P=(19,21)11P=(6,6)12P=(3,8)13P=(5,18)14P=(13,10)15P=(0,22)请在坐标上画出各个点，并观察图像特点注：其实还要加上一个无穷远点，故E上的点共有16个，点P的秩n=16。例2：在有限域F23之下，取椭圆曲线

上的两点及若则R=?

解：例3：条件同例2，若，

则R=?解：椭圆曲线在下的运算规则加法规则：对所有的点则，令及，且。则，其x3,y3分别为：(iii)

如果，则对所有的点而言，例子4：在有限域之下，取椭圆曲线

y2+xy=x3+g8x2+g2

上的两点P=(g3,g9)及Q=(g,g5)，其中g=(0010)为的生成数，且不可约多项式为f(x)=x4+x+1。若P+Q=R=(x3,y3)

则R=?解：注：g的乘幂如下例5条件同例4，若则R=?解：椭圆曲线密钥生成令E是FP上的椭圆曲线，P是E(FP)上的点，设P的阶是素数n，则集合

<P>={∞,P,2P,3P,…,(n-1)P}

是由P生成的椭圆曲线循环子群。素数p，椭圆曲线方程E，点P和阶n构成公开参数组。私钥在区间[1,n-1]内随机选择的正整数d，相应的公钥是Q=dP。由公开参数组和公钥Q求私钥d的问题是椭圆曲线离散对数问题(ECDLP)密钥对生成

输入：椭圆曲线参数组(p,E,P,n)

输出：公钥Q和私钥d选择d[1，n]计算Q=dP返回(Q,d)基本椭圆曲线加密输入：椭圆曲线参数组(