单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,椭圆曲线密码算法(ECC),椭圆曲线是由,Neil Koblitz(Koblitz,1985),和,Victor Miller(Miller,1985),两位学者分别于1985年首先提出,大多数的椭圆曲线密码系统是在模,p,或,F,2,n,下运算此密码系统仍是存有RSA或ElGamal常见的弱点(e.g.同模数攻击、低指数攻击)RSA与ElGamal系统中需要使用长度为,1024位的模数,，,才能达到足够的安全等,级,而ECC只需使用长度为160位的模数即可,，,且传送密文或签章所需频宽较少,，,并已正式列入IEEE 1363标准,椭圆曲线密码系统基于椭圆曲线离散对数问题(Elliptic Curve Discrete Logarithm Problem,ECDLP)即在有限域,K,之下,，,给定椭圆曲线,E,上的两相异点,P,及,Q,，,其中当点,P,的秩(order)若够大时(大于160位),，,要找出一整数,l,使得,Q,=,lP,是很难的计算难题在实数域中，椭圆曲线可定义成所有满足方程式,的点,(,x,y,),所构成的集合。
若方程式没有重复的因式或 ，则,能成为群(group)例如，椭圆曲线 的图形如图1-1所示若 ，则此曲线将会形成退化(某些数的逆元素(inverse)将不存在)椭圆曲线 的图形如图1-1所示椭圆曲线密码系统在模,p,(或,Fp,)下定义为椭圆曲线,其中,模,F,2,n,下定义为椭圆曲线,其中 ，此曲线称为nonsuper-singular椭圆曲线有一个特殊的点，记为,O,，它并不在椭圆曲线,E,上，此点称为无穷远点(the point at infinity),两个相异的点相加：假设,P,和,Q,是椭圆曲线上两个相异的点，而且,P,不等于-,Q,若,P,+,Q=R,，则点,R,是经过,P,、,Q,两点的直线与椭圆曲线相交之唯一交点的负点如图1-2所示双倍的点：令,P,+,P=2P,，则点2,P,是经过,P,的切线与椭圆曲线相交之唯一交点的负点如图1-3所示椭圆曲线运算规则,椭圆曲线在模,p,下的运算规则,加法规则：,对所有的点,P,E,(,F,p,),，则,P+O=O+P,，,P,+(-,P,)=,O,(ii),令 及 且 ，则 ，其中,(iii),如果 ，则对所有的点 而言，,乘法规则：,如果 ，则对所有的点 而言，,kP=P+P+,+P,(,k,个,P,相加),如果 ，则对所有的点 而 言，,例子1：,有限域,F,23,之下，点 是椭圆曲线,的生成数。
请计算2P和3P的值,P,=(0,1),2,P,=(13,13),3,P,=(5,5),4,P,=(3,15),5,P,=(6,17),6,P,=(19,2),7,P,=(17,9),8,P,=(18,0),9,P,=(17,14),10,P,=(19,21),11,P,=(6,6),12,P,=(3,8),13,P,=(5,18),14,P,=(13,10),15,P,=(0,22),请在坐标上画出各个点，并观察图像特点,注：其实还要加上一个无穷远点，故,E,上的点共有16个，点,P,的秩,n,=16例2：,在有限域,F,23,之下，取椭圆曲线,上的两点 及 若,则,R,=?,解：,例3：条件同,例2,，,若,，,则,R,=?,解：,椭圆曲线在 下的运算规则,加法规则：,对所有的点 则 ，,令 及,，,且 则 ，其,x,3,y,3,分别为：,(iii),如果 ，则对所有的点 而言，,例子4：,在有限域 之下，取椭圆曲线,y,2,+xy=x,3,+g,8,x,2,+g,2,上的两点P=(g,3,g,9,)及Q=(g,g,5,)，其中,g=(0010)为 的生成数，且不可约多项式为 f(x)=x,4,+x+1。
若 P+Q=R=(x,3,y,3,),则,R,=?,解：,注：,g,的乘幂如下,例5 条件同例4，若,则,R,=?,解：,椭圆曲线密钥生成,令,E,是,F,P,上的椭圆曲线，,P,是,E,(,F,P,)上的点，设P的阶是素数n，则集合,=,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,),基本椭圆曲线加密,输入：椭圆曲线参数组,(,p,E,P,n,)，公钥,Q，,明文,m,输出：密文(,C,1,C,2,),将明文,m,表示为,E,(,F,P,),上的点,M,选择,k,1,，,n,计算,C,1,=,kP,计算,C,2,=,M,+kQ,返回,(,C,1,C,2,),基本椭圆曲线解密,输入：椭圆曲线参数组,(,p,E,P,n,)，私钥,d，,密文(,C,1,C,2,),输出：明文,m,计算,M=?,，并从点,M,取出明文,m,返回,(m),。