椭圆曲线数字签名算法

椭圆曲线数字签名算法（ECDSA）原文TheEllipticCurveDigitalSignatureAlgorithm(ECDSA)CERTICOM公司李鹤帅译（部分内容有删节）摘要椭圆曲线数字签名算法（ECDSA）是使用椭圆曲线对数字签名算法（DSA）的模拟。ECDSA于1999年成为ANSI标准，并于2000年成为IEEE和NIST标准。它在1998年既已为ISO所接受，并且包含它的其他一些标准亦在ISO的考虑之中。与普通的离散对数问题（discretelogarithmproblemDLP）和大数分解问题（integerfactorizationproblemIFP）不同，椭圆曲线离散对数问题（ellipticcurvediscretelogarithmproblemECDLP）没有亚指数时间的解决方法。因此椭圆曲线密码的单位比特强度要高于其他公钥体制。本文将详细论述ANSIX9.62标准及其协议和实现方面的问题。1、介绍数字签名算法（DSA）在联邦信息处理标准FIPS中有详细论述。它的安全性基于素域上的离散对数问题。椭圆曲线密码（ECC）由NealKoblitz和VictorMiller于1985年发明。它可以看作是椭圆曲线对先前基于离散对数问题（DLP）的密码系统的模拟，只是群元素由素域中的数换为有限域上的椭圆曲线上的点。椭圆曲线密码体制的安全性基于椭圆曲线离散对数问题（ECDLP）的难解性。椭圆曲线离散对数问题远难于离散对数问题，椭圆曲线密码系统的单位比特强度要远高于传统的离散对数系统。因此在使用较短的密钥的情况下，ECC可以达到于DL系统相同的安全性。这带来的好处就是计算参数更小，密钥更短，运算速度更快，签名也更加短小。因此椭圆曲线密码尤其适用于处理器速度、带宽及功耗受限的场合。ECDSA是椭圆曲线对DSA的模拟。ECDSA首先由ScottVanstone在1992年为了响应NIST对数字签名标准（DSS）的要求而提出。ECDSA于1998年作为ISO标准被采纳，在1999年作为ANSI标准被采纳，并于2000年成为IEEE和FIPS标准。包含它的其他一些标准亦在ISO的考虑之中。本文中我们将介绍ANSIX9.62标准。也将介绍一些签名的基础知识以及协议及实现方面的问题。本文其他部分的安排如下：第二节中我们将回顾数字签名方案和DSA。第三节和第四节将分别介绍有限域和椭圆曲线。第五节将讲述域参数的产生，第六节将讲述密钥对的产生。第七节的内容是ECDSA的签名和验证过程。第八章论证ECDSA的安全性。第九节和第十节讲述的是ECDSA协议和实现方面的问题。2、数字签名方案2.1背景知识数字签名的目的是提供一个手写签名的数字化副本。签名是一个依赖于签名者私钥和一段消息的比特串。签名必须是可验证的，即如果对签名的真实性存在疑问，必须由一个中立的第三方作出公正的裁决，并且无需知道签名者的私钥。对签名的抵赖以及伪造签名应该能被发现。本文论述的是非对称摘要数字签名。“非对称”即用户的密钥对各不相同。用户的私钥用于签名，其他用户用他的公钥来检验签名的真实性。摘要是指对一段消息先用哈希函数进行摘要计算，尔后再对消息摘要进行签名。安全性。从理论上讲，在选择消息攻击下，数字签名应该是不可伪造的。这一概念由GoldwasserMicali和Rivest提出。更一般的讲就是攻击者获得用户A的摘要和签名，但他无法用其他的摘要来伪造这样一个签名。应用。数字签名方案用于以下一些用途：数据完整性（确保数据没有被未知或未授权的中间人改变），数据源认证（确保数据的来源是可信的），不可否认性（确保用户不能对自己的行为进行抵赖）。数字签名是密码学协议的基本组成部分，并且可以提供其他一些服务如：身份认证（FIPS196，ISO/IEC9798-3），密钥传递前的认证（ANSIX9.63，ISO/IEC11770-3），经验证的密钥协商（ISO/IEC11770-3）。分类。数字签名方案可以根据所基于的数学难题进行分类：1、基于大整数分解（IF）的方案，安全性基于大整数分解的难度。实例有RSA方案和Rabin方案。2、基于离散对数（DL）的方案，安全性基于有限域上普通的离散对数问题。实例包括ElGamal，Schnorr，DSA和Nyberg-Rueppel方案。3、基于椭圆曲线（EC）的方案，安全性基于椭圆曲线离散对数问题。2.2数字签名算法DSA于1991年由NIST提出，并在FIPS186中得到确认。DSA可以看作是ElGamal签名方案的一个变形。其安全性建立在素域上的离散对数问题的困难性之上。DSA参数的产生。每个用户的安全参数产生如下：1、选择160比特的素数q和1024比特的素数p，满足q|p-1。2、在有限域Zp*中寻找q阶循环子群的生成元g，具体方法是在Zp*选取元素h计算g=h(p-1)/qmodp，当g≠1时即找到满足要求的g。3、域参数就是p，q和g。DSA密钥对的产生。每个拥有域参数p，q和g进行如下操作：1、选择伪随机数x满足1<x<p-1。2、计算y=gxmodp。3、用户的私钥是x，公钥是y。DSA签名过程：1、选择伪随机数k满足1<k<p-1。2、计算X=gkmodp，r=Xmodq，若r=0则返回第一步。3、计算k-1modq。4、计算e=SHA-1(m)。5、计算s=k-1(e+xr)modq，若s=0则返回第一步。6、对消息m的签名就是(r,s)。DSA签名的验证。为了验证(r,s)是对m的签名，需要使用签名者的域参数(p,q,g)和公钥y进行如下运算：1、验证r，s在区间[1,q-1]中。2、计算e=SHA-1(m)。3、计算ω=s-1modq。4、计算u1=ωemodq和u2=rωmodq5、计算X=gu1yu2modp及v=Xmodq。6、如果v=r则认可此签名。安全性分析。由于r和s均小于q，故DSA签名长度小于320比特。DSA的安全性依赖于两个方面，它们都基于离散对数问题的难解性，一个是Zp*上的离散对数问题，目前已有数域筛算法去加以解决，这是一种亚指数级的算法。其平均运算时间为：O(exp((c+o(1))(lnp)1/3(lnlnp)2/3))其中c约为1.923，若p是1024比特的素数，则上式的计算量是无法接受的。因此目前1024比特的DSA可以应付现有攻击。另一个是q阶子群上的离散对数问题，给定p，q，g和y，y=gxmodp，要寻找x，目前最好的算法是Pollard’sRho算法，大约要做sqrt(пq/2)步。若q是160比特的，则该算法在计算上不可行，因此DSA是很安全的。DSA的安全性主要取决于p和q的尺寸。增加其中一个的尺寸而不增加另一个的尺寸对安全性的提高并无益处。此外，对两种离散对数问题解决算法的提高都会削弱DSA。安全参数的产生。DSA的早期版本受到了一些批评，因此FIPS186推出了一种新模式以产生素数以及“可证明的随机性”。它可以防止用户故意构造一个利于破译的素数（例如可以由CA来产生域参数并发送给用户）。FIPS指定了两个模式，分别使用SHA-1和DES，产生伪随机私钥x。FIPS186指定使用这两种模式以及其他经过FIPS认可的安全模式。3、有限域我们将简要介绍有限域的知识。更多详细内容请参看其他书籍。有限域由一个有限集合F和F上的两个二元运算组成，这两个运算满足某种运算规则，分别称为加法和乘法。有限域的阶即域中元素的个数。当仅当q是素数时存在一个q阶有限域，这个有限域是唯一的，记作Fq。有很多方法可以描述Fq的元素，有些描述方式可以使域上的软件及硬件运算更加高效。若q=pm，其中p为素数，m为正整数，则p称为Fq的特征，m称为Fq的度。至于椭圆曲线密码，一般基于素域或是多项式域。在3.1和3.2中我们将分别介绍这两种有限域上的元素和运算以及多项式域的两种表示方法：多项式表示方法和正规基表示方法。3.1有限域FpP为素数，有限域Fp称为素域，由整数集{1,2,……,p-1}和其上的符合下列规则的运算组成：1、加法。a,b∈p，a+b=r，r为a与b的和模p所得的值。2、乘法。a,b∈p，a*b=s，s为a与b的积模p所得的值。3、求逆运算。a是Fp中的非零元素，a的逆是唯一的，记作a-1，有a*a-1=1modp例1．F23，全部元素为{1,2,……,22}，其上三种运算：12+20=9，8*9=3，8-1=3。3.2有限域F2mF2m称之为特征为2的有限域，可以看做是F2上的m维向量空间。F2m中存在m个不同的元素ß0,ß1……,ßm-1，任一个ß∈F2m均可写为以下形式：ß=a0ß0+a1ß1+……+am-1ßm-1ai∈{0,1}集合{ß0,ß1……,ßm-1}称为F2m在F2上的基。有这样一个基，域中所有元素就可以用一个比特串(a0,a1,……am-1)来表示。这样，加法就可以用向量的逐比特异或运算来表示，乘法运算则依赖于基的选择。基的选择方式是多种多样的。一些基可以使运算变得高效。ANSIX9.62给出了两种基，分别是多项式基和正规基。多项式基f(x)=xm+fm-1xm-1+……f2x2+f1x+f0（fi∈{0,1}）是F2上的m次本原多项式。域元素。有限域F2m由F2上的所有不多于m次的多项式组成。F2m={am-1xm-1+……+a1x+a0|ai∈{0,1}}域元素am-1xm-1+……+a1x+a0可以写为比特串(am-1,……a1,a0)形式。因此F2m的元素可以写为长度为m的比特串。乘法单位元是(0,0,…,0,1)，加法零元是全零串(0,0,……,0)。域运算。加法。a=(am-1,……a1,a0)，b=(bm-1,……,b1,b0)，a+b=c=(cm-1,……,c1,c0)，ci=aiXORbi。乘法。a=(am-1,……a1,a0)，b=(bm-1,……,b1,b0)，a*b=r=(rm-1,……,r1,r0)，多项式rm-1xm-1+……+r1x+r0由(am-1xm-1+……+a1x+a0)*(bm-1xm-1+……+b1x+b0)模f(x)而来。求逆运算。a是F2m中的非零元素，a-1满足a-1*a=1例2.有限域F24,模多项式为f(x)=x4+x+1，有限域中16个元素分别为：0(0000)1(0001)x(0010)x+1(0011)x2(0100)x2+1(0101)x2+x(0110)x2+x+1(0111)x3(1000)x3+1(1001)x3+x(1010)x3+x+1(1011)x3+x2(1100)x3+x2+1(1101)x3+x2+x(1110)x3+x2+x+1(1111)F2^4上的运算举例：(1101)+(1001)=(0100)(1101)*(1001)=(1111)(x3+x2+1)*(x3+1)=x6+x5+x2+1(x6+x5+x2+1)mod(x4+x+1)=x3+x2+x+1(1101)-1=(0100)x=(0010)是F24的生成元x1=(0010)x2=(0100)x3=(1000)x4=(0011)x5=(0110)x6=(1100)x7=(1011)x8=(0101)x9=(1010)x10=(0111)x11=(1110)x12=(1111)x13=(1101)x14=(1001)x15=(0001)模多项式的确定。ANSIX9.62的两条标准如下：1.如果在F2上有m次三项本原多项式xm+xk+1，则模多项式应在这些多项式中选取k最小的那个。2.若不存在那样的多项式，则f(x)应为m次5项本原多项式xm+xk3+xk2+xk1+1。这时有三条原则：(1)k3应尽量小。(2)k3确定时k2应尽量小。(3)k3,k2确定时，k1应尽量小。正规基（略）4、有限域上的椭圆曲线本节我们将给出椭圆曲线的简要介绍，更详细的内容请参见其他书目。4.1Fp上的椭圆曲线P为大于3的奇素数，定义在Fp上的椭圆曲线有如下形式：y2=x3+ax+b，a,b∈Fp，4a3+27b2≠0modp。集合E(Fp)包括所有满足方程的(x,y)，x∈Fp,y∈Fp，另外还包括一个无穷远点O。例4.F23上的椭圆曲线y2=x3+x+4，4a3+27b2=22mod23，下面是E(F23)上的除无穷远点之外的所有点：(0,2)(0,21)(1,11)(1,12)(4,7)(4,16)(7,3)(7,20)(8,8)(8,15)(9,11)(9,12)(10,5)(10,18)(11,9)(11,14)(13,11)(13,12)(14,5)(14,18)(15,6)(15,17)(17,9)(17,14)(18,9)(18,14)(22,5)(22,19)加法公式。椭圆曲线上点的加法遵循的规则称之为“弦切规则”。椭圆曲线上的点及其运算规则即构成椭圆曲线密码系统的基本结构。加法规则最好用几何方法来描述。P=(x1,y1)，Q=(x2,y2)是曲线E上两个不同的点，P与Q的和R(x3,y3)用以下方法求得：作过P和Q的割线，这条线与曲线交于第三点，这个点的共轭即是R。在进行倍点运算时，只需把割线改成切线即可。由上面的几何描述，可以导出下面的点加和倍点公式。1.任意P∈E(Fp)，P+O=O+P=P。2.P=(x,y)∈E(Fp)，(x,y)+(x,-y)=O。（点(x,-y)称为-P）3.P=(x1,y1)∈E(Fp)，Q=(x2,y2)∈E(Fp)，P≠±Q，P+Q=R=(x3,y3)。x3=((y2-y1)/(x2-x1))2-x1-x2y3=((y2-y1)/(x2-x1))(x1-x3)-y14.P=(x1,y1)∈E(Fp)，P≠-P，2P=(x3,y3)x3=((3x12+a)/2y1)2-2x1y3=((3x12+a)/2y1)(x1-x3)-y1想要完成这些计算，就需要定义在Fp上的一系列运算，包括加法、减法、乘法和求逆运算。例5.例4中椭圆曲线上的点加和倍点。P=(4,7)，Q=(13,11)P+Q=(15,6)2P=(10,18)4.2F2m上的椭圆曲线F2m上的椭圆曲线形式如下：y2+xy=x3+ax2+b，a,b∈F2m，b≠0。集合E(F2m)包括所有满足方程的(x,y)，x∈F2m,y∈F2m，另外还包括一个无穷远点O。例6.有限域F24，模多项式f(x)=x4+x+1。曲线E:：y2+xy=x3+ß4x2+1。下面是曲线上的除无穷远点之外的所有点：(0,1)(1,ß6)(1,ß13)(ß3,ß8)(ß3,ß13)(ß5,ß3)(ß5,ß11)(ß6,ß8)(ß6,ß14)(ß9,ß10)(ß9,ß13)(ß10,ß)(ß10,ß8)(ß12,0)(ß12,ß12)加法公式。几何描述与Fp上的椭圆曲线一致。点加和倍点公式如下：1.任意P∈E(F2m)，P+O=O+P=P。2.P=(x,y)∈E(F2m)，(x,y)+(x,x+y)=O，(x,x+y)称为-P。3.P=(x1,y1)∈E(F2m)，Q=(x2,y2)∈E(F2m)，P≠±Q，P+Q=R=(x3,y3)。x3=((y2+y1)/(x2+x1))2+(y2+y1)/(x2+x1)+x1+x2+ay3=((y2+y1)/(x2+x1))(x1+x3)+x3+y14.P=(x1,y1)∈E(F2m)，P≠-P，2P=(x3,y3)x3=x12+b/x12y3=x12+(x1+y1/x1)x3+x3例7.例6中椭圆曲线上的点加和倍点。P=(ß6,ß8)，Q=(ß3,ß13)P+Q=(1,ß13)2P=(ß10,ß8)4.3基本性质群的阶。E是Fq上的椭圆曲线。Hasse定理指出椭圆曲线上的点（包括无穷远点）个数为#E(Fq)=q+1-t，|t|≤2sqrt(q)，#E(Fq)就是E的阶，t称为E的迹。也就是说曲线的阶大致等于基域的尺寸q。群结构。E(Fq)是一个秩为1或2的阿贝尔群。E(Fq)同构于Zn1×Zn2，n2整除n1。Zn是n阶循环群。另外n2整除q-1，若n2=1，则E(Fq)是循环群。此时E(Fq)同构于Zn1，存在P∈E(Fq)，使E(Fq)={kP|0≤k≤n1-1}，这个点叫作E(Fq)的生成元。例8.循环椭圆曲线。例4中的椭圆曲线E(F23)。#E(F23)=29，曲线的阶为素数，E(F23)是一个循环群并且除O外的其他点都是生成元。选取P=(0,2)。1=(0,2)2=(13,12)3=(11,9)4=(1,12)5=(7,20)6=(9,11)7=(15,6)8=(14,5)9=(4,7)10(22,5)11(10,5)12(17,9)13(8,15)14(18,9)15(18,14)16(8,8)17(17,14)18(10,18)19(22,18)20(4,16)21(14,18)22(15,17)23(9,12)24(7,3)25(1,11)26(11,14)27(13,11)28(0,21)29O5、ECDSA域参数ECDSA的域参数包括一条合适的椭圆曲线和其上一个基点G。域参数可以全局公开，也可以只对单个用户公开。5.1部分讲述域参数应该满足的要求，5.2部分讲解如何产生随机曲线，5.3部分介绍了一种产生域参数的方法，5.4部分给出了验证域参数是否符合要求的方法。5.1域参数为了提高实现效率，基域尺寸和参数的选择都有限制：另外，为了抵抗已知的攻击方式，曲线的选择和基点的阶都有一定的限制。对域的要求。基域的阶要么q等于p,要么等于2m。前者模一个大素数p，后者模一个多项式或正规基。对曲线的要求。为了抵抗Pollard’srho和PohligHellman攻击。E上的点的个数应能被一个大素数n整除。ANSIX9.62规定n应大于2160和4sqrt(q)。定义辅因子h=#E(Fq)/n。选择曲线时应注意的一些其他事项。为了抵抗MOV和FR攻击，曲线应是非超奇异（即要求p不能整除q+1-#E(Fq)）的。更一般的，应当满足n不能整除qk-1，1≤k≤C，一般取C为20。最后，为了抵抗SSSA对反常曲线的攻击，不得取反常曲线（即#E(Fq)不得等于q）。为了抵御上面提到的和将来可能出现的对这些特殊曲线的攻击，应使用随机方式选取一条椭圆曲线满足#E(Fq)能被一个大素数整除，满足上述一系列条件的随机曲线不甚可能被这些攻击方式所攻破。可以使用随机数发生器（如SHA-1一类的单向函数）来产生曲线的系数。5.2中介绍了一种类似FIPS-186的模式以产生随机曲线。概述。域参数的概述。1.域尺寸q，q=p或2m。2.域的表示方法FR和其中元素的表示方法。3.至少160比特长度的随机比特串。4.两个域参数a和b。5.基点G(xG,yG)。6.点G的阶n>160bit，n>4sqrt(q)。7.辅因子h=#E(Fq)/n。5.2用随机方法产生椭圆曲线本节讲述如何用随机方法产生椭圆曲线。随机参数使用SHA-1来产生。使用这种方法产生的椭圆曲线具有良好的随机性，可以避免性质较差的曲线的产生。q=p的情况下面要使用到这些参数：t=┌㏒p┐，s=└(t-1)/160┘，v=t-160s算法1.产生一条随机椭圆曲线。输入：域尺寸p。输出：至少160比特的比特串，参数a，b，它们确定了一条Fp上的椭圆曲线。1．选择一个长度g大于160比特的随机比特串SeedE。2.计算H=SHA-1(SeedE)，c0表示H的右起v长比特串。3.W0是H的左起v长比特串。4.z是比特串SeedE所表示的整数。5.forifrom1tosdo(1)si是(z+i)mod2g的比特串。(2)计算Wi=SHA-1(si)。6.W是比特串W0||W1||……||Ws。7.r是比特串W所表示的整数。8.若r=0或4r+27=0modp则返回第一步。9.选择随机整数a,b∈Fp，不能同时为0，要求rb2=a3modp（可以让a,b同时为r）。10.选定的曲线为y2=x3+ax+b。11.输出SeedE，a，b。Fp上的椭圆曲线同构类。两条定义在Fp上的椭圆曲线E1:y2=x3+a1x+b1和E2:y2=x3+a2x+b2在Fp上同构的充要条件是存在u∈Fp使得a1=u4a2，b1=u6b2（同构的椭圆曲线可以认为是相同的，若E1同构于E2，则E1(Fp)同构于E2(Fp)）。若E1同构于E2且b1不为0，则有a13/b12=a23/b22。奇异椭圆曲线：曲线E:y2=x3+ax+b，4a3+27b2=0modp，要么是a,b同时为0，要么是a3/b2=-27/4。若r∈Fp，r≠0，r≠-27/4，则存在两个曲线同构群E:y2=x3+ax+b，a3/b2=rmodp。算法1的第9步中(a,b)就只有两种选择。第8步中的限制条件确保曲线不是异常曲线。另外我们注意到算法1产生的曲线不会发生a,b有一个为0而另一个不为0的情况，这无关紧要因为这些曲线只是所有曲线中微不足道的一部分，任何算法都不可能完全随机地来产生曲线。Fp上的扭曲线。两条非同构曲线：E1:y2=x3+ax+b，E2:y2=x3+ac2x+bc3，c∈Fp，是一个非模p二次剩余，则称E1,E2相互扭转。它们的r是相等的。它们的阶满足：#E1(Fp)+#E2(Fp)=2p+2，若能计算出其中一条曲线的阶，另一条曲线的阶可轻易得出。算法2.证明一条曲线是在Fp上随机产生的。输入：域尺寸p，长度g≥160bit的比特串SeedE，域参数a,b。1.计算H=SHA-1(SeedE)，c0是H的右起v长比特串。2.W0是H的左起v长比特串。3.z是比特串SeedE所表示的整数。4.forifrom1tosdo(1)si是(z+i)mod2g的比特串。(2)计算Wi=SHA-1(si)。5.W是比特串W0||W1||……||Ws。6.r是比特串W所表示的整数。7.验证rb2=a3modp是否成立，成立则接受，反之则拒绝。q=2m的情况下面要使用到这些参数：s=└(t-1)/160┘，v=m-160s算法3：产生F2m上的一条随机椭圆曲线。输入：域尺寸2m。输出：至少160比特的比特串，参数a，b，它们确定了一条F2m上的椭圆曲线。1.选择一个长度g大于160比特的随机比特串SeedE。2.计算H=SHA-1(SeedE)，b0表示H的右起v长比特串。3.z是比特串SeedE所表示的整数。4.forifrom1tosdo(1)si是(z+i)mod2g的比特串。(2)计算bi=SHA-1(si)。5.b是比特串b0||b1||……||bs。6.若b=0则返回第一步。7.a是F2m上的随机数。8.F2m上的椭圆曲线E:y2+xy=x3+ax2+b。9.输出SeedE，a，b。F2m上的椭圆曲线同构类。F2m上的两条曲线E1:y2+xy=x3+a1x2+b1，E2:y2+xy=x3+a2x2+b2在F2m上同构的充要条件是b1=b2且TR(a1)=TR(a2)，TR(ß)=ß+ß2+ß4+……+ß2^(m-1)。同构的椭圆曲线可以认为是相同的，若E1同构于E2，则E1(F2m)同构于E2(F2m)。下面是F2m上的一个典型的椭圆曲线同构类{y2+xy=x3+ax2+b|b∈F2m,b≠0,a∈{0,ß}}，其中ß∈F2m，是一个满足TR(ß)=1的固定元素（若m是奇数，则令ß=1）。因此对于已经选定的b，算法3中的步骤7中a只有两种选择。F2m上的扭曲线。两条不同构的曲线E1:y2+xy=x3+a1x2+b，E2:y2+xy=x3+a2x2+b，TR(a1)≠TR(a2)，则这两条曲线互称为扭曲线。它们的阶满足#E1(F2m)+#E2(F2m)=2p+2，若能计算出其中一条曲线的阶，另一条曲线的阶可轻易得出。F2m上的椭圆曲线的阶总是偶数，若TR(a1)=0，则#E1(F2m)=0mod4，若TR(a1)=1，则#E1(F2m)=2mod4。算法4.证明一条曲线是在F2m上随机产生的。输入：域尺寸2m，长度g≥160bit的比特串SeedE，域参数a,b。输出：判断算法3产生的曲线是否是随机的。1.计算H=SHA-1(SeedE)，b0表示H的右起v长比特串。2.z是比特串SeedE所表示的整数。3.forifrom1tosdo(1)si是(z+i)mod2g的比特串。(2)计算bi=SHA-1(si)。4.b’是比特串b0||b1||……||bs。5.若b=b’，则接受反之则拒绝。5.3域参数的产生下面是产生安全参数的方法：1.利用算法1或算法3产生曲线E:y2=x3+ax+b或y2+xy=x3+ax2+b。2.计算N=#E(Eq)。3.验证N是否有一个长度大于160bit且大于4sqrt(q)的因子n，若没有，则返回第一步。4.验证n是否能整除qk-1(1≤k≤20)，若能，则返回第一步。5.验证n是否等于q，若等于，则返回第一步。6.随机选择点G’∈E(Eq)，计算G=(N/n)G’，重复这一步，直至G≠O，G就是基点。曲线阶的计算。1985年Schoof提出了一个多项式时间的算法以计算素域上椭圆曲线的阶，后来Koblitz使其也能用于F2m。在q较大时Schoof的算法效率较低。经过若干年的改进，形成了Schoof-Elkies-Atkin算法，即SEA算法（算法细节详见其他资料）。有了SEA算法，在工作站上用若干个小时就可以产生大约200bit左右尺寸的随机曲线。Satoh提出了针对F2m上曲线的新算法，在一台高速PC上若干秒就可以产生一条大约200bit尺寸的曲线。复乘模式（CM）。（略）Koblitz曲线。这种曲线是多项式域上的一种反常曲线，首先由Koblitz提出。这种曲线定义在F2m上，而它的系数在F2中取值。因此有两种Koblitz曲线：y2+xy=x3+x+1和y2+xy=x3+1。Koblitz曲线上的标量乘法效率很高。Koblitz曲线在ECDSA中的应用前景广阔。5.4域参数的验证域参数的验证确保选定的域参数具有必须的算术性质。这一步骤的必要性包括两点：(1)防止攻击者利用较弱的参数进行攻击。(2)防止在传递参数时出现偶然的编码或传输错误。使用较弱的参数将达不到安全要求。验证域参数的方法。判断D={q,FR,a,b,G,n,h}是否合用可使用下面之一的算法：1.使用算法5进行验证。2.D是由一个可靠的系统产生的。3.D由可靠的组织提供且经过算法5验证。4.D由可靠的组织提供且由一个可靠的系统产生的。算法5.椭圆曲线域参数的验证。输入：D={q,FR,a,b,G,n,h}。输出：判断参数是否合乎要求。1.验证q=p或2m。2.验证FR是合乎要求的。3.验证G≠O。4.验证a,b,xG,yG在p或模多项式所规定的范围内。5.若随机曲线是用户自己用5.2的算法1或算法3产生的，验证a,b确由SeedE生成。6.q=p时，验证4a3+27b2≠0modp；q=2m时，验证b≠0。7.将G代人曲线方程，证明其确在曲线上。8.验证n是素数。9.验证n>2160且n>4sqrt(q)。10.验证nG=O。11.计算h’=└(sqrt(q)+1)2/n┘，验证h=h’。12.验证n不整除qk-1(1≤k≤20)。13.验证n≠q。14.通过上述验证的D才是合格的。求椭圆曲线的阶。由Hasse定理可知(sqrt(q)-1)2≤#E(Fq)≤(sqrt(q)+1)2。由于n>4sqrt(q)，故n不可能整除#E(Fq)，因此E(Fq)只有一个n阶子群。另外由于(sqrt(q)+1)2-(sqrt(q)-1)2=4sqrt(q)存在唯一整数h使(sqrt(q)-1)2≤nh≤(sqrt(q)-1)2，即h=└(sqrt(q)+1)2/n┘。算法5的9，10，11步就是验证nh=#E(Fq)。正如5.2所指出的，计算椭圆曲线的阶是件异常费时的工作。实际应用中用户可以购买厂家的软件计算曲线的阶，不过这样的软件必须是经过认证的。6、ECDSA密钥对ECDSA密钥对的选择与域参数的选择有关。私钥是一个随机整数，公钥是私钥与基点的乘积。6.1介绍如何产生密钥对，6.2讲述怎样验证公钥是否满足要求，6.3将讨论CA的重要性。6.1密钥对的产生用户A的密钥对与参数D={q,FR,a,b,G,n,h}有关。在生成密钥对前用户必须确保域参数是安全可靠的（见5.4）。ECDSA密钥对的产生：1.在区间[1,n-1]中选定一个随机数d。2.计算Q=dG。3.私钥为d，公钥为Q。6.2公钥的验证公钥的验证最早由Johnson提出，其目的在于确保公钥具有良好的算术性质。公钥的验证并不关心用户私钥的情况，甚至不管私钥是否存在。进行公钥的验证出于以下两个理由：(1)防止攻击者利用性质较差的公钥进行攻击。(2)避免偶然的编码或传输错误。使用性质较差的公钥会使其他安全措施无效。这方面的攻击实例可参见Lim和Lee的文献。公钥的验证方法。可使用以下方法之一进行验证：1.用户A使用算法6进行验证。2.Q由可靠的系统产生。3.Q由可靠的组织提供且经过算法6验证。4.Q由可靠的组织提供且由一个可靠的系统产生的。算法6.ECDSA公钥的验证。输入：公钥Q=(xQ,yQ)，参数D={q,FR,a,b,G,n,h}。输出：是否接受公钥Q。1.验证Q≠O。2.验证xQ,yQ在p或模多项式所规定的范围内。3.验证xQ,yQ在曲线上。4.验证nQ=O。5.若Q通过上述验证，则接受之。6.3持有私钥的证明若干用户C能够确认A的公钥确系其本人的，C就可以要求A签名。为了做到这一点，在CA确定每个用户A对其私钥的所有权之前，CA需要每个A证明他们对其公钥的所有权。对所有权的认证有多种形式，如对一段由CA选定的消息的签名，也可以用一些所谓的“零知识”方法。私钥所有权的认证和公钥所有权认证所起的作用是不一样的。同时进行这两种验证提供了高水平的安全保障。7、ECDSA签名的产生和认证本节介绍ECDSA签名产生和认证的方法。ECDSA签名的产生。有参数D={q,FR,a,b,G,n,h}和密钥对{d,Q}的用户A使用以下方法对消息m进行签名：1.产生随机或伪随机数k，1≤k≤n-1。2.计算kG=(x1,y1)。3.计算r=x1modn，若r=0则返回第一步。4.计算k-1modn。5.计算e=SHA-1(m)。6.计算s=k-1(e+dr)modn，若s=0则返回第一步。7.对消息m的签名为(r,s)。ECDSA签名的验证。为了验证A对消息m的签名(r,s)，B需要A的公钥Q和A的公开参数D=(q,FR,a,b,G,n,h)。B最好对D和Q也进行确认（见5.4和6.2）。B进行如下操作：1.验证r和s在区间[1,n-1]中。2.计算e=SHA-1(m)。3.计算ω=s-1modn。4.计算u1=ωemodn，u2=rωmodn。5.计算X=u1G+u2Q。6.若X=O，则签名非法，x1为X的x坐标，v=x1modn。7.若v=r则接受签名。签名验证的根据。若对消息m的签名(r,s)确为A所为，则s=k-1(e+dr)modn。将其化简可得：k=s-1(e+dr)=s-1e+s-1dr=ωe+ωdr=u1+u2dmodn。因此u1G+u2Q=(u1+u2d)G=kG，因此v=r时认可签名。数据类型的转换。ANSIX9.62规定了一个将域参数转换为整数的规则，它用在产生签名的第二步和验证签名的第六步，在计算x1modn之前将x1转换为整数。ANSIX9.62也规定了一个将比特串转换为整数的规则，它用于将SHA-1产生的比特串转换为整数。公钥证书。在验证A的签名之前B需要一份A的公开参数D和公钥Q的副本，ANSIX9.62对此未作详细说明。实践中可靠的公钥一般由证书来分配。A的公钥证书应包括能唯一标识他的信息（如姓名，住址等），公开参数D，公钥Q，以及CA对这些信息的签名。B可以利用CA对A的证书来可靠地获得A的公开参数D和公钥Q的副本。在签名验证中对r和s进行验证的基本原理。在签名验证的第1步中验证r和s是否在区间[1,n-1]中，这一操作是高效且极有必要的，ElGamal签名方案不进行这一操作，有一些攻击方法可以利用这一点进行攻击。下面是一个在ECDSA不验证r≠0modn时可以采用的攻击方式，A使用Fp上的椭圆曲线：y2=x3+ax+b，b是模p的二次剩余，并且假设A使用的基点是G(0,sqrt(b))（这是有可能的，用户可能会选择一个x坐标为0的点作为基点，这样可以使参数组D变得短小），攻击者可以对任意消息m伪造A的签名，签名是(r=0,s=e)。DSA和ECDSA的比较。单从概念上讲，ECDSA和DSA的区别仅在于DSA的子群是Zp*上由g上生成的，而ECDSA的子群是椭圆曲线点群上由G生成的。在实现上，ECDSA和DSA的唯一重要区别是r的产生，DSA的r是通过计算X=g-1modp再模q，而ECDSA的r是取kG的x坐标而来。8、安全方面的考虑ECDSA在安全性方面的目标是能抵抗选择明文（密文）攻击。而攻击A的攻击者的目标是在截获A的签名后，可以生成对任何消息的合法签名。尽管ECDSA的理论模型很坚固，但是人们仍研究很多措施以提高ECDSA的安全性。在ECDLP不可破解及哈希函数足够强的前提下，DSA和ECDSA的一些变形已被证明可以抵抗现有的任何选择明文（密文）攻击。在椭圆曲线所在群是一般群并且哈希函数能够抗碰撞攻击的前提下，ECDSA本身的安全性已经得到证明。ECDSA可能面临的攻击：1.对ECDLP的攻击。2.对哈希函数的攻击。3.其他攻击。本阶将介绍目前对ECDSA的攻击方式及防御它们的方法。8.1椭圆曲线离散对数问题若攻击者能由A的公钥和公开参数计算出A的私钥，则攻击者就可以随心所欲地伪造A的签名。问题的定义。椭圆曲线离散对数问题（ECDLP）：一条定义在有限域Fq上的椭圆曲线E，E(Fq)上的一个n阶点P，Q=lP，1≤l≤n-1，求l。已知的攻击这一部分将介绍一些已知的对ECDLP的攻击方式，并将论证它们在实际中是不可行的。1.穷尽搜索法。依次计算P,2P,3P,4P……直到与Q匹配为止，最差情况下要作n次。2.Pohlig-Hellman算法。该算法由Pohlig和Hellman发明，利用P的阶n的因子分解。该算法将模n条件下求l的问题转化为求模每个n的因子条件下求l的问题。利用中国剩余定理即可求得l。为了抵抗这种攻击，椭圆曲线的阶应被一大素数n整除，或者曲线的阶就是素数或近乎是一个素数（即由一个大素数和一个小整数相乘而来）。在本节的剩余部分我们假定曲线的阶是素数。3.小步-大步算法。该算法是一种需要很大存储空间的穷尽搜索算法，在最差情况下，需要存储sqrt(q)个点，运算sqrt(q)步。4.Pollard’sRho算法。该算法由Pollard发明，这是小步-大步算法的一种随机化版本。它大约需要sqrt(пn/2)步，但其所需要的存储空间几乎可以忽略不计。Gallant,Lambert,Vanstone和Wiener,Zuccherato的文章向我们介绍了Pollard’sRho算法的改进。改进后的算法效率提高了sqrt(2)倍，即算法只需sqrt(пn)/2步。5.并行Pollard’sRho算法。VanOorschot和Wiener的文章告诉我们在使用r个处理器并行运算时，Pollard’sRho算法的时间复杂度为sqrt(пn)/2r，即使用r个处理器时，运算效率提高了r倍。6.Pollard’sLambda算法。这也是小步-大步算法的一种随机化版本，在并行化时速度也有线性提高。并行Pollard’sLambda比并行Pollard’sRho要略慢一些。不过，如果已知离散对数在[0,b]，b<0.39n时Pollard’sLambda算法要快一些。7.多重对数算法。R.Silverman和Stapleton注意到若一个ECDLP被（并行）Pollard’sRho算法解决，那么已进行的工作对解决另一个ECDLP（曲线和基点不变）大有好处。更精确地说，若解决第一个ECDLP耗时t=sqrt(пn)/2r，则第二个耗时(sqrt(2)-1)t≈0.41t，第三个耗时需(sqrt(3)-sqrt(2))≈0.32t，第四个耗时(sqrt(4)-sqrt(3))≈0.27t……以此类推。这样对于一条特定的曲线和一个特定的点，ECDLP会越来越易于解决。从另一方面看，解决k个ECDLP（曲线和基点不变）只需sqrt(k)倍解决单个ECDLP所需代价。这里的分析没有考虑存储方面的问题。为了避免这种情况的出现，最好的办法就是使得密码系统足够强使得首次破解不可能。8.超奇异椭圆曲线。Menezes,Okamoto,Vanstone,Frey和Ruck的研究表明，在某些适当的条件下，定义在有限域Fq上的椭圆曲线E上的ECDLP可以化为某个扩域Fqk（k≥1）上的普通乘法群上的DLP，从而可以使用数域筛法加以解决。这样的转化算法只有在k较小时才有实用价值，因此对绝大多数椭圆曲线都不适用。为了抵抗这种攻击方式，在选择安全曲线时必须检验基点P的阶n不整除qk-1，1≤k≤20。这样可以使上述攻击方式在计算上不可行。若E的迹t能够被Fq的特征p所整除，则称E是超奇异椭圆曲线。对于这类曲线，它们的k≤6，使用上面的方法就可以产生解决ECDLP的亚指数算法。因此ECDSA严禁使用超奇异椭圆曲线。更一般地讲，在选择安全曲线时检验基点P的阶n不整除qk-1可以剔除那些可以将ECDLP转化为Fq上的DLP的曲线，不仅包括超奇异椭圆曲线，也包括迹为2的椭圆曲线。9.素域反常椭圆曲线。定义在Fp上，且#E(Fp)=p的曲线称为素域反常曲线。其上ECDLP存在高效攻击方式SSSA。这种攻击方式不能用于其他曲线，因此只要确保#E(Fp)≠p即可使这种攻击无效。10.小域上的椭圆曲线。E是一条定义在F2e上的椭圆曲线。Gallant,Lambert,Vanstone,Wiener和Zuccherato的研究表明Pollard’sRho算法在E(F2ed)上的效率可以提高sqrt(d)倍。即运算步骤变为sqrt(пn/d)/2步。如果E是Koblitz曲线，Pollard’sRho算法在F2m上的效率提高了sqrt(m)倍。为避免这种情况的发生，在进行曲线安全性分析时应避免曲线方程的系数在一小子域中。11.定义在F2m（m为合数）的椭圆曲线。Galbraith和Smart论述了当曲线定义在F2m（m为合数）（这样的域称为合域）时，Weil变换可以用于解决ECDLP。后来，Gaudry,Hess和Smart证明了当m有一个小因子l，如l=4时，存在比Pollard’sRho算法更高效的算法。Menezes和Qu也做了类似的分析。根据这样的结论，椭圆曲线密码不应使用合域上的曲线。现有的各种标准均禁止使用这种曲线。12.不适用于ECDLP的Index-Calculus方法。ECDLP是否存在普适性的亚指数算法是一个重要但却又尚不明确的问题，而ECDSA的安全性又与此密切相关。现在还没有人能够证明ECDLP不存在亚指数算法。然而，对DLP的分析进行了24年，对ECDLP的分析进行了16年，至今未发现解决ECDLP的普适性亚指数算法。Miller,J.Silverman和Suzuki已经证明了用于解决DLP的Index-Calculus方法不适用于ECDLP。13.Xedni-Calculus攻击。一种很有趣的攻击方式，由J.Silverman提出，它不仅可以解决ECDLP，还可以解决DLP和IFP。但后来它被证明在实际应用中并不可行。14.超椭圆曲线。超椭圆曲线是一类任意亏格的代数曲线，椭圆曲线就是其中亏格为1的一种。对于大亏格的超椭圆曲线上的ECDLP，Adleman,DeMarrais和Huang提出了一种亚指数算法，不过对于椭圆曲线，这种方法比穷举法还要差。15.与ECDLP等价的DLP。Stein和Zuccherato证明了亏格为1的二次同余函数域上的DLP等价于ECDLP。对于这类问题亦无亚指数算法，这从另一个方面证明了ECDLP的困难性。试验结果目前解决ECDLP最好的普适性算法是并行Pollard’sRho算法，大约需要sqrt(пn)/2r步，n是基点P的阶，r是处理器个数。Certicom的ECC挑战。Certicom公司于1997年启动了一项ECC挑战项目，旨在鼓励与促进对ECC的研究。他们的挑战由下面的一系列椭圆曲线的ECDLP组成，ECCp-k表示Fp上的椭圆曲线，ECC2-k表示F2m上的椭圆曲线，ECC2k-k表示F2m上的Koblitz曲线，k表示n的尺寸。这些曲线的基域的阶等于或略大于n（或者说这些曲线的阶是素数或近似是素数）。1.Fp上的椭圆曲线，ECCp-79，ECCp-89，ECCp-97，ECCp-109，ECCp-131，ECCp-163，ECCp-191，ECCp-239，ECCp-359。2.F2m（m为素数）上的椭圆曲线，ECC2-79，ECC2-89，ECC2-97，ECC2-109，ECC2-131，ECC2-163，ECC2-191，ECC2-238，ECC2-353。3.F2m（m为素数）上的Koblitz曲线，ECC2k-95，ECC2k-108，ECC2k-130，ECC2k-163，ECC2k-238，ECC2k-358。挑战的结果。1998年Escott介绍了一种经过Teske改进的并行Pollard’sRho算法，他们所解决的最困难的ECDLP是ECCp-97，使用了至少16个国家的1200台机器，耗时53天。执行椭圆曲线点加运算的次数约为2*1014次，与理论值很接近（理论值为sqrt(пn)/2≈3.5*1014，n≈297）。他们估计要解决ECCp-109大约需要50000台200MHz的奔腾机运行3个月。硬件攻击VanOorschot和Wiener研究了利用专用硬件实现并行Pollard’sRho算法的可能性。他们估计花1000万美元制造一个有330000个处理器的机器可以在32天内解决n≈2120的ECDLP。由于ANSIX9.62规定n应大于2160，故在现有条件下，这样的硬件攻击不可行。8.2对哈希函数的攻击定义。哈希函数H是一种将任意长度比特串映射为定长t比特串的函数，满足下列条件：1.H的计算足够高效。2.（不可逆）对于所有的y∈{0,1}t，寻找比特串x使H(x)=y在计算上不可行。3.（抗碰撞）寻找比特串x1和x2使得H(x1)=H(x2)在计算上不可行。SHA-1的安全需要。下面显示了若SHA-1不能满足不可逆及抗碰撞条件时，攻击者可以这些问题成功攻破ECDSA。1.若SHA-1是可求逆的，则攻击者E可以这样伪造A的签名：E可以选取一个随机整数l，尔后计算r等于Q+lG的横坐标模n的值。E令s=r，计算e=rlmodn。若E能找到e=SHA-1(m)的逆m，则可构造m的合法签名(r,s)。2.若SHA-1不能抗碰撞，则用户A可以这样否认自己的签名：A构造两个消息m和m’满足SHA-1(m)=SHA-1(m’)，这样的一对消息称为SHA-1的碰撞。A可以对m签名却声称自己对m’签名。理想的安全性。一个t比特长度哈希函数满足下面两个条件时则有理想的安全性：1.寻找原象大约需要2t步操作。2.寻找哈希碰撞大约需要2t/2步操作。SHA-1是160比特哈希函数，具有良好的安全性。攻击SHA-1最高效的方法是寻找哈希碰撞，大约需要280步，因此通过哈希函数攻击ECDSA在计算上是不可行的。这里只是单纯讨论哈希函数的输出长度，而未讨论与之紧密相关的椭圆曲线基点阶尺寸。现在得到广泛使用的哈希函数并不多，只有SHA-1和RIPEMD-160（另一种160比特哈希函数）两种。哈希函数的可变输出长度。在不久的将来，SHA-1将被一个可变长度哈希函数族Hl所代替，Hl是一个l可变比特长度的具有理想安全性的哈希函数。若椭圆曲线基点的阶为n，则l应等于└logn┘。这样的话，通过攻击ECDLP和攻击哈希函数来攻破ECDSA所需代价基本一样。新的哈希函数开始使用256，384，512比特的输出长度。8.3其他攻击方式随机数k的保密要求。在ECDSA中随机数k与私钥d有同样的保密要求。因为攻击者E若获知了用户A的随机数k，则他可以计算出A的私钥d=r-1(ks-e)modn。因此必须确保随机数k安全地产生，存储，销毁。随机数k的重复使用问题。用于对多个消息签名的随机数必须是互不依赖的。每次签名时k都必须不同，否则d可被恢复出来。实际中一般使用伪随机数发生器来产生，这样基本不可能产生相同的k。下面展示的是两次使用相同的k分别对m1和m2进行签名导致私钥d被计算出来的过程：两次签名分别为(r,s1)与(r,s2)；s1=k-1(e1+dr)modn，s2=k-1(e2+dr)modn；ks1=e1+drmodn，ks2=e2+drmodn；k(s1-s2)=(e1-e2)modn，由于s1与s2几乎不可能相当，因此可以计算出k=(e1-e2)(s1-s2)-1modn，从而可以进一步求得d。Vaudenay攻击。Vaudenay发现了DSA中的一个漏洞：SHA-1的值要模q，q和SHA-1的输出都是160比特长度的，有时候SHA-1的输出大于q，因此有时SHA-1(m)≠SHA-1(m)modn。这个缺点使得攻击者可能伪造签名。在ECDSA中这个问题是不存在的，因为ECDSA标准要求n大于2160。签名副本密钥选取攻击。对于一个签名方案S，如果给出A的公钥PA和对消息M的签名sA，攻击者E可以找到一个合法的密钥对(PE,SE)使之对M签名仍得到sA，则称这个签名方案具有签名副本密钥选取（DSKS）的性质。使用这种攻击方式的前提是E必须要知道SE，Blake-Wilson和Menezes在他们的文献中详述了如何用这种方式去攻击一个签名体制。他们还论述了如果用户可以自行选择域参数，则ECDSA会面临DSKS的问题。例子如下：假如用户A的域参数DA=(q,FR,a,b,G,n,h)，A的密钥对为(QA,dA)，(r,s)是A对M的签名。攻击者E选择随机整数c，1≤c≤n-1，令t=((s-1e+s-1rc)modn)≠0，计算X=s-1eG+s-1rQ（e=SHA-1(M)）以及G’=(t-1modn)X，尔后E就有了自己的域参数DE=(q,FR,a,b,G’,n,h)，QE=cG’。易于验证DE和QE是合法的，并且(r,s)亦是E对M的签名。具有DSKS性质的签名方案是不可靠的，设计签名方案的目标之一是能抵抗住这种选择消息攻击。对抗DSKS很简单，确保域参数选取的随机性即可。同时，我们也看到了域参数和公钥的选取是多么的重要。实现方面的攻击。ANXI9.62没有提到ECDSA实现方面的攻击，比如计时攻击，差分攻击，能量攻击以及针对伪随机数的弱随机性的攻击。9、实现方面的考虑在实现ECDSA之前，必须进行一些基本的选择：1.基域的选择，Fp或F2m。2.若选取F2m上的曲线，要决定使用正规基表示方法还是多项式表示方法。3.曲线的类型，一般曲线还是Koblitz曲线。4.曲线点的表示，仿射坐标还是投射坐标。在进行选择时由很多影响因素，总的来说就是针对不同的应用进行不同的选择已取得最好的结果，这些影响因素包括：1.安全性方面的考虑。2.有限域运算高效性方面的考虑（包括加法，平方，乘法，求逆运算）。3.椭圆曲线算术高效性方面的考虑（点加和倍点）。4.应用环境（软件，硬件，嵌入式系统）。5.计算环境的考虑（速度，存储空间，处理器位数，门运算，能耗）。6.通信环境的考虑（带宽，时延）。参考文献。目前最详细并且得到广泛应用的椭圆曲线标准是IEEE1363-2000。10、通用性方面的考虑一个加密标准要达到的目标包括两方面：1.密码系统的健壮性。2.在不同系统间的通用性。影响通用性的因素。通用性可以通过规范密码系统的步骤和格式来实现数据的共享，如共享域参数，密钥，交换消息等；也可以通过对实现密码体制的设备的种类来实现。对于椭圆曲线密码学，特别是ECDSA来说，影响通用性的因素包括：1.可使用的有限域的个数和类型。2.有限域中元素的表示方式。3.有限域上椭圆曲线的条数。4.域元素，曲线上的点，曲线参数，公钥，签名的表示方式。10.1ECDSA标准ECDSA的标准和标准草案有很多，其中已经过颁发部门批准的有：ANSIX9.62,FIPS186-2,IEEE1363-2000,ISO14888-3。ECDSA也被密码标准化组织（SECG，这是一个从事密码标准通用性潜力研究的组织）加以标准化。首先我们将简要介绍这些标准，然后对它们进行比较，最后还会提到一些其他ECDSA标准。主要的ECDSA标准。1.ANSIX9.62。该项目始于1995年，并于1999年正式作为ANSI标准颁布。ANSIX9.62具有高安全性和通用性。它的基域可以是Fp，也可以是F2m。F2m中的元素可以以多项式形式或正规基形式来表示。若用多项式形式，ANSIX9.62要求模多项式为不可约三项式，标准中提供了一些不可约三项式，另外还给出了一个不可约五项式。为了提高通用性，针对每一个域提供了一个模多项式。若使用正规基表示方法，ANSIX9.62规定使用高斯正规基。椭圆曲线最主要的安全因素是n，即基点阶，ANSIX9.62的n大于2160。椭圆曲线是使用随机方法选取的。ANSIX9.62规定使用以字节为单位的字符串形式来表示曲线上的点，ASN.1语法可以清楚地描述域参数，公钥和签名。2.FIPS186-2。1997年，NIST开始制定包括椭圆曲线和RSA签名算法的FIPS186标准。1998年，NIST推出了FIPS186，它包括RSA与DSA数字签名方案，这个方案也称为FIPS186-1。1999年NIST又面向美国G0vment推出了15种椭圆曲线。这些曲线都遵循ANSIX9.62和IEEE1363-2000的形式。2000年，包含ANSIX9.62中说明的ECDSA，使用上述曲线的FIPS186-2问世。3.IEEE1363-2000。该标准于2000年作为IEEE标准问世。IEEE1363的覆盖面很广，包括公钥加密，密钥协商，基于IFP、DLP、ECDLP的数字签名。它与ANSIX9.62和FIPS186完全不同，它没有最低安全性限制（比如不再对基点阶进行限制），用户可以有充分的自由。因此IEEE1363-2000并不是一个安全标准，也不具有良好的通用性，它的意义在于给各种应用提供参照。它的基域可以是Fp，也可以是F2m。F2m中的元素可以以多项式形式或正规基形式来表示。Fp中元素表示形式是整数，F2m中元素表示形式是字符串。这与ANSIX9.62和FIPS186是一致的。4.ISO/IEC14888-3。这个标准包含若干签名算法，其中ECDSA部分与ANSIX9.62一致。5.SEC1和SEC2。SEC1描述了ECDSA，椭圆曲线加密算法，椭圆曲线密钥交换协议。而SEC2给出了具体的椭圆曲线。SEC1的ECDSA遵从ANSIX9.62，但对域的尺寸未作限制。比较。这些标准的关系如下图：其他的ECDSA标准。ECDSA还有其他很多标准，它们包括：1.ISO/IEC15946。该标准草案包括多种椭圆曲线密码技术，包括公钥加密，数字签名，密钥产生等。与ANSIX9.62，FIPS186-2，IEEE1363-2000中曲线基域必须是素域或多项式域不同，ISO/IEC15946对基域类型未作限制。其在ECDSA描述方面与ANSIX9.62一致。2.IETFPKIX。供X.509证书使用的一个标准，其格式与ANSIX9.62一致。3.LETFTLS。这是IETF为SSL制定的标准，将会包含ANSIX9.62的ECDSA。4.WAPWTLS。为移动通信工具提供传输层安全保障，使之能够安全地浏览网页，其认证使用ANSIX9.62的ECDSA。10.2NIST推荐的曲线这部分内容给出了NIST向美国G0vment推荐（而非强制规定）的15条曲线。推荐的有限域，共十个：1.素域Fp，p=2192-264-1，p=2224-296+1，p=2256-2224+2192+296-1，p=2384-2128-296+232-1，p=2521-1。2.多项式域F2163，F2233，F2283，F2409，F2571。选择这些域的原因在于：1.点的阶长度至少应该二倍于分组密码的密钥长度，这是因为一般认为使用穷尽法破译密钥长度为k的分组密码的代价大致相当于使用Pollard’sRho方法破译阶为2k的椭圆曲线密码。它们的对比如下：2.对于素域Fp，模数p应该是伪梅森素数或类梅森素数，这样可以使模乘运算效率更高。3.对于多项式域F2m，选择m的原则是使得F2m上存在有大素因子的阶的Koblitz曲线。由于当l整除m时，#E(F2l)也整除#E(F2m)，因此需要m是素数。推荐的椭圆曲线，它们分为三种类型：1.Fp上的随机曲线。2.F2m上的Koblitz曲线。3.F2m上的随机曲线。下面就是推荐曲线的参数，用十进制和十六进制表示。Fp上的随机曲线各种参数的含义如下：P：基域Fp的阶。Seed：使用算法1来随机产生曲线参数过程中要用到的系数。R：算法1中SHA-1的输出。a，b：曲线方程的参数，其中a取-3，这样可以提高运算效率。xG，yG：基点G的坐标。n：G的阶。h：辅因子h=#E(Fq)/n。CurveP-192p=6277101735386680763835789423207666416083908700390324961279n=6277101735386680763835789423176059013767194773182842284081seed=3045ae6fc8422f64ed579528d38120eae12196d5r=3099d2bbbfcb2538542dcd5fb078b6ef5f3d6fe2c745de65a=-3b=64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1Gx=188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012Gy=07192b95ffc8da78631011ed6b24cdd573f977a11e794811h=1CurveP-224p=26959946667150639794667015087019630673557916260026308143510066298881n=26959946667150639794667015087019625940457807714424391721682722368061seed=bd71344799d5c7fcdc45b59fa3b9ab8f6a948bc5r=5b056c7e11dd68f40469ee7f3c7a7d74f7d121116506d031218291fba=-3b=b4050a850c04b3abf54132565044b0b7d7bfd8ba270b39432355ffb4Gx=b70e0cbd6bb4bf7f321390b94a03c1d356c21122343280d6115c1d21Gy=bd376388b5f723fb4c22dfe6cd4375a05a07476444d5819985007e34h=1CurveP-256P=115792089210356248762697446949407573530086143415290314195533631308867097853951n=115792089210356248762697446949407573529996955224135760342422259061068512044369seed=c49d360886e704936a6678e1139d26b7819f7e90r=7efba1662985be9403cb055c75d4f7e0ce8d84a9c5114abcaf3177680104fa0da=-3b=5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604bGx=6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296Gy=4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5h=1CurveP-384p=39402006196394479212279040100143613805079739270465446667948293404245721771496870329047266088258938001861606973112319n=39402006196394479212279040100143613805079739270465446667946905279627659399113263569398956308152294913554433653942643seed=a335926aa319a27a1d00896a6773a4827acdac73r=79d1e655f868f02fff48dcdee14151ddb80643c1406d0ca10dfe6fc52009540a495e8042ea5f744f6e184667cc722483a=-3b=b3312fa7e23ee7e4988e056be3f82d19181d9c6efe8141120314088f5013875ac656398d8a2ed19d2a85c8edd3ec2aefGx=aa87ca22be8b05378eb1c71ef320ad746e1d3b628ba79b9859f741e082542a385502f25dbf55296c3a545e3872760ab7Gy=3617de4a96262c6f5d9e98bf9292dc29f8f41dbd289a147ce9da3113b5f0b8c00a60b1ce1d7e819d7a431d7c90ea0e5fh=1CurveP-521p=6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151n=6864797660130609714981900799081393217269435300143305409394463459185543183397655394245057746333217197532963996371363321113864768612440380340372808892707005449seed=d09e8800291cb85396cc6717393284aaa0da64bar=0b48bfa5f420a34949539d2bdfc264eeeeb077688e44fbf0ad8f6d0edb37bd6b533281000518e19f1b9ffbe0fe9ed8a3c2200b8f875e523868c70c1e5bf55bad637a=-3b=051953eb9618e1c9a1f929a21a0b68540eea2da725b99b315f3b8b489918ef109e156193951ec7e937b1652c0bd3bb1bf073573df883d2c34f1ef451fd46b503f00Gx=c6858e06b70404e9cd9e3ecb662395b4429c648139053fb521f828af606b4d3dbaa14b5e77efe75928fe1dc127a2ffa8de3348b3c1856a429bf97e7e31c2e5bd66Gy=11839296a789a3bc0045c8a5fb42c7d1bd998f54449579b446817afbd17273e662c97ee72995ef42640c550b9013fad0761353c7086a272c24088be94769fd16650h=1F2m上的Koblitz曲线与F2m上的随机曲线尺寸为163的多项式域。T=4p(t)=t163+t7+t6+t3+1CurveK-163a=1n=5846006549323611672814741753598448348329118574063多项式表示法：Gx=2fe13c0537bbc11acaa07d793de4e6d5e5c94eee8Gy=289070fb05d38ff58321f2e800536d538ccdaa3d9正规基表示法：Gx=05679b353caa46825fea2d3713ba450da0c2a4541Gy=235b7c6710050689906bac3d9dec76a835591edb2CurveB-163n=5846006549323611672814742442876390689256843201587多项式表示法：b=20a601907b8c953ca1481eb10512f78744a3205fdGx=3f0eba16286a2d57ea0991168d4994637e8343e36Gy=0d51fbc6c71a0094fa2cdd545b11c5c0c797324f1正规基表示法：s=85e25bfe5c86226cdb12016f7553f9d0e693a268b=6645f3cacf1638e139c6cd13ef61734fbc9e3d9fbGx=0311103c17167564ace77ccb09c681f886ba54ee8Gy=333ac13c6447f2e67613bf7009daf98c87bb50c7f尺寸为233的多项式域T=2p(t)=t233+t74+1CurveK-233a=0n=3450873173395281893717377931138512760570940988862252126328087024741343多项式表示法：Gx=17232ba853a7e731af129f22ff4149563a419c26bf50a4c9d6eefad6126Gy=1db537dece819b7f70f555a67c427a8cd9bf18aeb9b56e0c11056fae6a3正规基表示法：Gx=0fde76d9dcd26e643ac26f1aa901aa129784b71fc0722b2d05614d650b3Gy=0643e317633155c9e0447ba8020a3c43177450ee036d633501434cac978CurveB-2