椭圆曲线数字签名算法(ECDSA)

摘要椭圆曲线数字签名算法（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首先由Scott和Vanstone在1992年为了响应NIST对数字签名标准（DSS）的要求而提出。ECDSA于1998年作为ISO标准被采纳，在1999年作为ANSI标准被采纳，并于2000年成为IEEE和FIPS标准。包含它的其他一些标准亦在ISO的考虑之中。本文中我们将介绍ANSIX9.62标准。也将介绍一些签名的基础知识以及协议、安全性、实现、互操作性方面的问题。本文其他部分的安排如下：第二节中我们将回顾数字签名方案和DSA，第三节和第四节将分别介绍有限域和椭圆曲线，第五节将讲述域参数的产生和参数有效性的验证，第六节将讲述密钥对的产生和公钥有效性的验证，第七节的内容是ECDSA的签名和验证过程。第八章论证ECDSA的安全性，第九节和第十节讲述的是ECDSA协议和实现方面的问题。2、数字签名方案2.1背景知识数字签名的目的是提供一个手写签名的数字化副本。签名是一个依赖于签名者私钥和被签名一段消息的比特串。签名必须是可验证的，即如果对签名的真实性存在疑问，必须由一个中立的第三方作出公正的裁决，并且无需知道签名者的私钥。对签名的抵赖以及伪造签名应该能被发现。本文论述的是非对称摘要数字签名。“非对称”即用户的密钥对各不相同。用户的私钥用于签名，其他用户用他的公钥来检验签名的真实性。摘要是指对一段消息先用哈希函数进行摘要计算，尔后再对消息摘要进行签名，而不是消息。安全性：从理论上讲，在选择消息攻击下，数字签名应该是不可伪造的。这一概念由Goldwasser，Micali和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，满足。2、在有限域中寻找q阶循环子群的生成元g，具体方法是在选取元素h计算g=modp，当g≠1时即找到满足要求的g。3、域参数就是p，q和g。DSA密钥对的产生：每个拥有域参数p，q和g进行如下操作：1、选择随机或伪随机数x满足1xp-1。2、计算。3、用户的私钥是x，公钥是y。DSA签名过程：1、选择随机或伪随机数k满足1kp-1。2、计算，若r=0则返回第一步。K-13、计算。4、计算e=SHA-1(m)。5、计算，若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、计算。4、计算和5、计算及。6、如果则认可此签名。安全性分析：由于r和s均小于q，故DSA签名长度小于320比特。DSA的安全性依赖于两个方面，它们都基于离散对数问题的难解性，一个是Zp*上的离散对数问题，目前已有数域筛算法去加以解决，这是一种亚指数级的算法。其平均运算时间为：其中c约为1.923，若p是1024比特的素数，则上式的计算量是无法接受的。因此目前1024比特的DSA可以应付现有攻击。另一个是q阶子群上的离散对数问题，给定p，q，g和y，，要寻找x，目前昀好的算法是Pollard’sRho算法，大约要做步。若q是160比特的，则该算法在计算上不可行，因此DSA是很安全的。DSA的安全性主要取决于p和q的尺寸。增加其中一个的尺寸而不增加另一个的尺寸对安全性的提高并无益处。此外，对两种离散对数问题解决算法的提高都会削弱DSA。安全参数的产生：DSA的早期版本受到了一些批评，因此FIPS186推出了一种新模式以产生素数p和q以及“可证明的随机性”。它可以防止用户故意构造一个利于破译的素数（例如可以由CA来产生域参数并发送给用户）。FIPS指定了两个模式，分别使用SHA-1和DES，产生伪随机私钥x。FIPS186指定使用这两种模式以及其他经过FIPS认可的安全模式。3、有限域我们将简要介绍有限域的知识，更多详细内容请参看其他书籍。有限域由一个有限集合F和F上的两个二元运算组成，这两个运算满足某种运算规则，分别称为加法和乘法。有限域的阶即域中元素的个数。当仅当q是素数的幂次时存在一个q阶有限域，这个有限域是唯一的，记作。有很多方法可以描述的元素，有些描述方式可以使域上的软件及硬件运算更加高效。若q=pm，其中p为素数，m为正整数，则p称为的特征，m称为的度。至于椭圆曲线密码，一般基于素域或是多项式域。在3.1和3.2中我们将分别介绍这两种有限域上的元素和运算以及多项式域的两种表示方法：多项式表示方法和正规基表示方法。3.1有限域FpP为素数，有限域称为素域，由整数集{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是中的非零元素，a的逆是唯一的，记作，有例1．，全部元素为{1,2,……,22}，其上三种运算：12+20=9，8*9=3，8-1=3。3.2有限域称之为特征为2的有限域或者一个二进制有限域，可以看做是上的m维向量空间。中存在m个不同的元素，任一个ß∈均可写为以下形式：集合{}称为在上的基。有这样一个基，域中所有元素就可以用一个比特串(a0,a1,……am-1)来表示。这样，加法就可以用向量的逐比特异或运算来表示，乘法运算则依赖于基的选择。基的选择方式是多种多样的。一些基可以使运算变得高效。ANSIX9.62给出了两种基，分别是多项式基和正规基。多项式基是上的m次本原多项式，那么f（x）定义了一个多项式基。域元素有限域由上的所有不多于m次的多项式组成。域元素可以写为比特串形式。因此的元素可以写为长度为m的比特串。乘法单位元是(0,0,…,0,1)，加法零元是全零串(0,0,……,0)。域运算：加法：乘法：求逆运算：选择不可约多项式ANSIX9.62的两条标准如下：1.如果在上有m次三项本原多项式，则模多项式应在这些多项式中选取k昀小的那个。2.若不存在那样的多项式，则f(x)应为m次5项本原多项式。这时有三条原则：(1)应尽量小。(2)确定时k2应尽量小。(3),确定时，应尽量小。正规基表示的正规基有着如下形式：。正规基总是存在的。任何元素，能够写成如下的形式：。正规基表示使得元素的平方运算效率很高。另一方面，不同元素的乘积通常来说会显得效率很低。因此，ANSIX9.62采用了高斯正规基，它的乘法运算更简单和有效率。高斯正规基正规基的T值表示正规基乘法运算的复杂度。通常来说，T值越小，表示乘法运算更有效。给定m，T，，至多有一个GNB的T值为T。高斯正规基的存在性高斯正规基总是存在的，当m不能被8整除。一个Type为T的高斯正规基存在的充分必要条件：p是素数且p=Tm+1，(Tm/k,m)=1其中k为在模p下乘法阶为2.域元素域中的任意元素a可以表示为：.故有：。零元素表示为0=（0，0，...0）,乘法单位元表示1=（1，1，...,1）.域运算加法与多项式基表示类似。平方运算就是对向量表示的域元素做一次简单循环移位。乘法运算p=Tm+1,,阶为T。定义序列T为偶数和奇数的两种情况。求逆运算跟多项式基表示类似。高斯正规基的选取ANSIX9.62给定了下列原则：1.如果存在Type值为2的，必须使用。2.如果不存在Type值为2的，若存在Type值为1的，必须使用。3.如果上面两个条件都不满足，则选择Type值昀小的高斯正规基5、ECDSA域参数ECDSA的域参数包括一条合适的椭圆曲线和其上一个基点G。域参数可以全局公开，也可以只对单个用户公开。5.1部分讲述域参数应该满足的要求，5.2部分讲解如何产生随机曲线，5.3部分介绍了一种产生域参数的方法，5.4部分给出了验证域参数是否符合要求的方法。5.1域参数为了提高实现效率，基域尺寸和参数的选择都有限制：另外，为了抵抗已知的攻击方式，曲线的选择和基点的阶都有一定的限制。对域的要求基域的阶要么q等于p,要么等于。前者模一个大素数p，后者模一个多项式或正规基。对曲线的要求为了抵抗Pollard’srho和PohligHellman攻击。E上的点的个数应能被一个大素数n整除。ANSIX9.62规定n应大于和。应选择E使得为素数或近似素数。定义辅因子，其中n为素数，h非常小。选择曲线时应注意的一些其他事项为了抵抗MOV和FR攻击，曲线应是非超奇异（即要求p不能整除）的。更一般的，应当满足n不能整除，1≤k≤C，一般取C为20。昀后，为了抵抗SSSA对反常曲线的攻击，不得取反常曲线（即不得等于q）。为了抵御上面提到的和将来可能出现的对这些特殊曲线的攻击，应使用随机方式选取一条椭圆曲线满足能被一个大素数整除，满足上述一系列条件的随机曲线不甚可能被这些攻击方式所攻破。可以使用随机数发生器（如SHA-1一类的单向函数）来产生曲线的系数。5.2中介绍了一种类似FIPS-186的模式以产生随机曲线。域参数的概述1.域尺寸q，q=p或。2.域的表示方法FR和其中元素的表示方法。3.至少160比特长度的随机比特串。4.两个域参数a和b。5.基点G(xG,yG)。6.