椭圆曲线密码算法.ppt

*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,椭圆曲线密码算法,(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),