基于ECC的数字签名算法设计与实现.doc

1、摘要：信息社会正被计算机网络及通信技术的迅猛发展推向一个新的高级阶段,政府、军事、文教、商业、金融等社会生活的各个领域都深受其影响,信息已成为一种重要的战略资源.信息安全是信息科学领域的重要新兴学科,它的核心技术是密码学,其中公钥密码由于其与生俱来的一些优势,扮演着越来越重要的角色.数字签名技术作为最近几年来公钥密码发展的一个新型分支,是安全电子商务和安全电子政务的关键技术.数字签名提供认证性、完整性和不可否认性,是信息安全的核心技术之一.基于身份的密码系统解决了传统公钥体制中利用公钥基础设施来管理公钥证书的复杂性和成本过高的问题,可与公钥证书基础设施密码体制形成牢固有利的互补.采用椭圆曲线上

2、双线性映射技术的基于身份数字签名成为近几年密码学界的热点研究问题.本文首先对密码技术的发展现状及其发展趋势进行了分析和综述,其次,论述了椭圆曲线密码体制的原理,包括椭圆曲线密码的数学基础、椭圆曲线的基本概念、椭圆曲线密码体制的构造思想、椭圆曲线上的点运算等问题,同时分析了椭圆曲线密码系统的安全性和有效性,给出了一个椭圆曲线数字签名方案,最后设计实现了一个在网络环境下使用的数字签名系统.本文给出的这种基于椭圆曲线密码的高效率的数字签名方案,不仅在算法设计时完全避免了费时的求逆运算,而且利用消息HASH值的汉明重量作为消息摘要进行签名与验证.结果在同等安全性下,该方案比通用的ECDSA等方案运行时

3、间更短.新方案可适用于网络等对签名实时性要求较高的场合1.关键词：椭圆曲线公钥密码体制,数字签名,信息安全,汉明重量The Digital Signature Algorithm Design and Implementation based on ECCAbstract:In nowadays,information society is being pushed onto a new advanced level by computer network and communication technologies,which have made great effects On gover

4、nment,military affairs,culture education,and finance,ere,Information has become an important resource in our societyInformation secIIdty is one ofthe rising subjects in information science and its core of technology is cryptologyIn eryptological area,publickey cryptosystem is playing more and more i

5、mportant roles in the world because ofits native predominanceAs a new branch ofpublickey cryptosystern,digital signature is a key technology of the sccnre B2B(Business to Business)and government affair in recent yearsAs one of the pivotal technologies of information security,digital signature provid

6、es authentication,integrality and incontestablenessIn traditional public key infrastructure (PKI) system,managing public-key certification causes problems of complexity and high cost. Fortunately,identity-based cryptography has solved these kinds of problems,and it is also a good replenisher to PKI

7、systemIdentity based signature using pairing technology on elliptical curves has become one of the pop research problemsThis paper first analyses and summarizes the current status and evolution trend of encryption,and introduces in detail the development of private-key cryptosystem and public-key cr

8、yptosystem,and provides the brief analysis of a few typical schemes.Second,the printciple of ECC is discussed,including the math foundation of ECC,operation on the elliptic curve and so on.meanwhile,the security and ECC are given.Some key algorithm ECC are implemented,including algorithm of generati

9、ng the elliptic curve,algorithm of detecting prime number and algorithm of operating between the big integers.At last design and implement a system of digital signature based on ECC for network.To offer a high efficiency digital signature based on ellip tic curve cryp tography. The design of the alg

10、orithm not only avoids timecosting inverse operation comp letely but also uses the hammingweight of HASH code of a message instead of HASH code itself as the messagedigest to participate in the signature and verifying calculation. The new scheme cost less time than the popular ECDSA. The new scheme

11、is adap ted to higher real2time needs for signature such as internet.Key Words: ECC,Digital signature,The security of information, Hamming weight目 录摘要.iAbstract:ii第一章 绪论11.1选题意义11.2 论文的内容及安排3第二章 密码学的相关知识42.1 RSA体制42.1.1 RSA算法42.1.2 RSA安全性42.2 DES体制52.2.1 DES算法52.2.2 DES安全性102.3 ECC密码体制102.3.1算法原理122

12、.3.2 ECC算法分析132.4 算法的计算复杂度15第三章 基于ECC的数字签名方案163.1数字签名163.2 数字签名方案17第四章 基于ECC数字签名方案实现194.1 算法实现194.2 数字签名实验224.3 ECC数字签名应用26第五章 总结与展望285.1 总结285.2 展望28参考文献29致谢30附录31iii安徽建筑工业学院 毕业设计（论文）第一章 绪论1.1选题意义计算机网络的建立给信息传输带来了极大的方便,实现了快速,便捷传输,但这同时也带来了隐患,有些不法分子利用掌握的计算机技术或篡改或窃取他人的信息,以达到自己的利益,因此如何实现安全传输变成为了一直以来的研究领

13、域.迄今为止,最重要的网络与通信安全自动化工具是加密.广泛使用的两种加密形式是传统加密和公钥加密.于是密码学得到了极大发展9.在公钥密码体制以前的整个密码学史中,所有的密码算法,包括原始手工计算的、由机械设备实现的以及由计算机实现的,都是基于代换和置换这两个基本工具.而公钥密码体制则为密码学的发展提供了新的理论和技术基础,一方面公钥密码算法的基本工具不再是代换和置换,而是数学函数；另一方面公钥密码算法是以非对称的形式使用两个密钥,两个密钥的使用对保密性、密钥分配、认证等都有着深刻的意义.可以说公钥密码体制的出现在密码学史上是迄今为止最大的而且唯一真正的革命.公钥密码体制的概念是在解决单钥密码体

14、制中最难解决的两个问题时提出的,这两个问题是密钥分配和数字签字.比较典型的公钥密码算法是1978年由R.Rvest,A.Shamir和L.Adleman提出的一种用数论构造的、也是迄今为止理论上最为成熟完善的公钥密码体制,该体制已得到广泛的应用.RSA的安全性是基于分解大整数的困难性假定.因此其最核心的部位在于密钥的选择上,随着计算机技术的发展为保障数据安全原本普遍采用的RSA算法的密钥长度需一再增大,使得它的运算负担越来越大.相比之下,椭圆曲线密码体制（ECC）可用短得多的密钥获得同样的安全性,具有广泛的应用前景.基于公钥密码算法的ECC 数字签名方法本质是公钥加密算法的逆运算.此时发送方用

15、自己的私钥对消息进行加密,接收方收到消息后用发送方的公钥进行解密,由于私钥由发送方自己保管且只有他本人知道,入侵者如果只知道发送方的公钥,不可能伪造签名,从而起到签名的效果,公正的第三方可以用发送方的公钥对签名的消息进行解密,从而验证消息确实来在发送方.随着通讯网络特别是INTERNET 的高速发展,利用网络作为信息交流和信息处理变得越来越普遍,社会的传统事务和业务运作模式受到前所未有的冲击目前,无论是国家政府还是企业都正融入这场网络革命中,从其原来的传统经营模式向网络模式演化未来的电子政务、电子商务、电子业务将成为不可逆转的发展趋势在与日俱增的网络活动中,人们越来越关心信息安全这个问题目前,

16、RSA 算法已广泛应用到网络安全的各个领域1985年Neil Koblitz和Victor Miller提出基于椭圆曲线理论的椭圆曲线密码系统(ECC体系),其安全性建立在椭圆曲线离散对数的难解性的基础上,在同等密钥长度的条件下其安全性远高于RSA算法目前已正式列入了IEEE 1363标准,在网络安全领域有着广阔的应用前景椭圆曲线密码（ECC）是一种高安全性、高效率的公钥密码,具有加密/解密、数字签名和密钥协商等重要的密码功能,可以安全且方便地满足各种信息网络中的用户身份识别、电子信息的真伪鉴别和保密传输等重要的信息安全需求,是信息安全领域的核心技术,并已逐渐被诸多国际和国家标准组织采纳为公钥

17、密码标准（IEEE P1363、ANSI X9、ISO/IEC和IETF等）,成为了当今信息安全产业界使用的主流密码技术之一11.密码体制1.2 论文的内容及安排椭圆曲线属于抽象代数“代数几何学”的一个分支,自从Koblitz等人提出用来构造公钥密码以来,获得了快速发展.椭圆曲线密码体制（ECC）比RSA更有效,密钥更短而抗击能力更强.数字签名是由公钥密码体制发展而来,它在网络安全,包括身份认证、数据完整性、不可否认性以及匿名性等方面有着重要应用.本课题的主要工作是基于ECC的数字签名算法设计及实现.本课题为“基于ECC的数字签名算法设计”,其主要内容如下：（1）椭圆曲线与椭圆曲线密码体制（E

18、CC）.研究有限域上的椭圆曲线以及群性质研究基于ElGamael公钥方案的椭圆曲线密码体制.（2）数字签名与基于ECC的数字签名算法.研究数字签名特点以及在公钥密码体制下的实现.研究基于ECC的数字签名和基于RSA的数字签名算法设计.（3）基于ECC的数字签名算法实现.编程实现基于ECC的数字签名方案.第二章 密码学的相关知识计算机网络的建立,使得通信越来越便捷,人们可以利用网络快速实现远距离的通信,但网络也带来了负面影响,一些用户利用所掌握的计算机技术非法窃取、监听、篡改信息等,使得通信双方无法获取正确的信息或者双方的敏感信息得不到保证.密码学的创立为网络的安全通信提供了一种可行措施.密码体

19、制从原理上可分为两大类即单钥密码体制和双钥密码体制RSA,ECC密码体制是公钥密码体制的典型代表.2.1 RSA体制2.1.1 RSA算法 RSA算法是1978年由R.Rivest,A.Shamir和L.Adleman提出的一种用数论构造的、也是迄今为止理论上最为成熟完善的公钥密码体制,该体制已得到广泛的应用.1密钥的产生选两个保密的大素数和；计算,其中是的欧拉函数值；选一整数,满足且,；计算,满足,即是在模下的乘法逆元,因与互素,由模运算可知,它的乘法逆元一定存在；以为公开钥,为私密钥.加密加密时首先将明文比特串分组,使得每个分组对应的十进数小于,即分组长度小于.然后对每个明文分组,作加密运

20、算：解密对密文分组的解密运算为：2.1.2 RSA安全性RSA的安全性是基于分解大整数的困难性假定,之所以为假定是因为至今还未能证明分解大整数就是NP问题,也许有尚未发现的多项式时间分解算法.如果RSA的模数被成功地分解为,则立即获得,从而能够确定模的乘法逆元,即,因此攻击成功.2.2 DES体制2.2.1 DES算法13DES算法把64位的明文输入块变为64位的密文输出块,它所使用的密钥也是64位,首先,DES把输入的64位数据块按位重新组合,并把输出分为L0、R0两部分,每部分各长32位,并进行前后置换（输入的第58位换到第一位,第50位换到第2位,依此类推,最后一位是原来的第7位）,最终

21、由L0输出左32位,R0输出右32位,根据这个法则经过16次迭代运算后,得到L16、R16,将此作为输入,进行与初始置换相反的逆置换,即得到密文输出.DES算法的入口参数有三个：Key、Data、Mode.其中Key为8个字节共64位,是DES算法的工作密钥；Data也为8个字节64位,是要被加密或被解密的数据；Mode为DES的工作方式,有两种：加密或解密,如果Mode为加密,则用Key去把数据Data进行加密,生成Data的密码形式作为DES的输出结果；如Mode为解密,则用Key去把密码形式的数据Data解密,还原为Data的明码形式作为DES的输出结果.在使用DES时,双方预先约定使用

22、的”密码”即Key,然后用Key去加密数据；接收方得到密文后使用同样的Key解密得到原数据,这样便实现了安全性较高的数据传输.16轮迭代IP逆置换64位密文64位明文初始IP置换 图3 DES加密算法框图64位明文56位密钥4848Li-1Ri-1扩展/置换代换/选择置换XORLiRiCi-1Di-1Li-1Li-1置换选择2CiDiXORKi4832 32图4 DES加密算法的轮结构DES加密算法的过程:1. 对输入的密钥进行变换.用户的64bit密钥,其中第8, 16, 24, 32, 40, 48, 56, 64位是校验位, 使得每个密钥都有奇数个1.所以密钥事实上是56位.对这56位密

23、钥进行如下表的换位.57, 49, 41, 33, 25, 17, 9, 1, 58, 50, 42, 34, 26, 18, 10, 2, 59, 51, 43, 35, 27, 19, 11, 3, 60, 52, 44, 36, 63, 55, 47, 39, 31, 23, 15, 7, 62, 54, 46, 38, 30, 22, 14, 6, 61, 53, 45, 37, 29, 21, 13, 5, 28, 20, 12, 4,表的意思是第57位移到第1位,第49位移到第2位.以此类推.变换后得到56bit数据,将它分成两部分,C028, D028.2. 计算16个子密钥,计

24、算方法Ci28 ,Di28为对前一个Ci-128, Di-128做循环左移操作.16次的左移位数如下表: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 （第i次) 1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1 (左移位数)3. 串联计算出来的Ci28 Di28 得到56位,然后对它进行如下变换得到48位子密钥Ki4814, 17, 11, 24, 1, 5, 3, 28, 15, 6, 21, 10, 23, 19, 12, 4, 26, 8, 16, 7, 27, 20, 13, 2

25、,41, 52, 31, 37, 47, 55, 30, 40, 51, 45, 33, 48, 44, 49, 39, 56, 34, 53, 46, 42, 50, 36, 29, 32,表的意思是第14位移到第1位,第17位移到第2位,以此类推.在此过程中,发现第9,18,22,25, 35,38,43,54位丢弃.4. 对64bit的明文输入进行换位变换.换位表如下:58, 50, 12, 34, 26, 18, 10, 2, 60, 52, 44, 36, 28, 20, 12, 4,62, 54, 46, 38, 30, 22, 14, 6, 64, 56, 48, 40, 32,

26、 24, 16, 8,57, 49, 41, 33, 25, 17, 9, 1, 59, 51, 43, 35, 27, 19, 11, 3,61, 53, 45, 37, 29, 21, 13, 5, 63, 55, 47, 39, 31, 23, 15, 7表的意思就是第一次变换时,第58位移到第1位,第50位移到第2位.依此类推.得到64位数据,将这数据前后分成两块L032, R032. 5. 加密过程,对Ri32进行扩展变换成48位数,方法如下, 记为E(Ri32)32, 1, 2, 3, 4, 5, 4, 5, 6, 7, 8, 9,8, 9, 10, 11, 12, 13, 12,

27、 13, 14, 15, 16, 17,16, 17, 18, 19, 20, 21,20, 21, 22, 23, 24, 25, 24, 25, 26, 27, 28, 29,28, 29, 30, 31, 32, 1,6. 将E(Ri32)与Ki48作异或运算,得到48位数,将48位数顺序分成8份,6位一份,B86.7. 使用Si替换Bi6.过程如下: 取出Bi6的第1位和第6位连成一个2位数m, m就是Si中对应的行数(0-3),取出Bi6的第2到第5位连成一个4位数n(0-15),n就是Si中对应的列数,用Simn代替Bi6.S是4行16列的对应表,里面是4位的数,一共有8个S,定义

28、如下:S1: 14,4,13,1,2,15,11,8,3,10,6,12,5,9,0,7, 0,15,7,4,14,2,13,1,10,6,12,11,9,5,3,8, 4,1,14,8,13,6,2,11,15,12,9,7,3,10,5,0, 15,12,8,2,4,9,1,7,5,11,3,14,10,0,6,13,S2: 15,1,8,14,6,11,3,4,9,7,2,13,12,0,5,10, 3,13,4,7,15,2,8,14,12,0,1,10,6,9,11,5, 0,14,7,11,10,4,13,1,5,8,12,6,9,3,2,15, 13,8,10,1,3,15,4,

29、2,11,6,7,12,0,5,14,9,S3: 10,0,9,14,6,3,15,5,1,13,12,7,11,4,2,8, 13,7,0,9,3,4,6,10,2,8,5,14,12,11,15,1, 13,6,4,9,8,15,3,0,11,1,2,12,5,10,14,7, 1,10,13,0,6,9,8,7,4,15,14,3,11,5,2,12,S4: 7,13,14,3,0,6,9,10,1,2,8,5,11,12,4,15, 13,8,11,5,6,15,0,3,4,7,2,12,1,10,14,9, 10,6,9,0,12,11,7,13,15,1,3,14,5,2,8,4,

30、 3,15,0,6,10,1,13,8,9,4,5,11,12,7,2,14, S5: 2,12,4,1,7,10,11,6,8,5,3,15,13,0,14,9, 14,11,2,12,4,7,13,1,5,0,15,10,3,9,8,6, 4,2,1,11,10,13,7,8,15,9,12,5,6,3,0,14, 11,8,12,7,1,14,2,13,6,15,0,9,10,4,5,3, S6: 12,1,10,15,9,2,6,8,0,13,3,4,14,7,5,11, 10,15,4,2,7,12,9,5,6,1,13,14,0,11,3,8, 9,14,15,5,2,8,12,3

31、,7,0,4,10,1,13,11,6, 4,3,2,12,9,5,15,10,11,14,1,7,6,0,8,13, S7: 4,11,2,14,15,0,8,13,3,12,9,7,5,10,6,1, 13,0,11,7,4,9,1,10,14,3,5,12,2,15,8,6, 1,4,11,13,12,3,7,14,10,15,6,8,0,5,9,2, 6,11,13,8,1,4,10,7,9,5,0,15,14,2,3,12, S8: 13,2,8,4,6,15,11,1,10,9,3,14,5,0,12,7, 1,15,13,8,10,3,7,4,12,5,6,11,0,14,9,2

32、, 7,11,4,1,9,12,14,2,0,6,10,13,15,3,5,8, 2,1,14,7,4,10,8,13,15,12,9,0,3,5,6,11,8. 将从Bi6经过S得到的8个4位数连起来得到32位数.对这个数进行如下变换: 16,7,20,21,29,12,28,17, 1,15,23,26, 5,18,31,10, 2,8,24,14,32,27, 3, 9,19,13,30, 6,22,11, 4,25,得到的结果与Li32作异或运算,把结果赋给Ri32.9. 把Ri-132的值赋给Li,从5开始循环.直到K1648结束.10. 将最后的L,R合并成64位,然后进行如下转化

33、得到最后的结果.这是对第4步的一个逆变化. 40, 8, 48, 16, 56, 24, 64, 32, 39, 7, 47, 15, 55, 23, 63, 31, 38, 6, 46, 14, 54, 22, 62, 30, 37, 5, 45, 13, 53, 21, 61, 29, 36, 4, 44, 12, 52, 20, 60, 28, 35, 3, 43, 11, 51, 19, 59, 27, 34, 2, 42, 10, 50, 18, 58, 26, 33, 1, 41, 9, 49, 17, 57, 25解密过程同样,只需要把16个子密钥Ki48的顺序颠倒过来就可以了.

34、2.2.2 DES安全性DES算法具有极高安全性,到目前为止,除了用穷举搜索法对DES算法进行攻击外,还没有发现更有效的办法.而56位长的密钥的穷举空间为256,这意味着如果一台计算机的速度是每一秒种检测一百万个密钥,则它搜索完全部密钥就需要将近2285年的时间,可见,这是难以实现的,当然,随着科学技术的发展,当出现超高速计算机后,我们可考虑把DES密钥的长度再增长一些,以此来达到更高的保密程度.由上述DES算法介绍我们可以看到：DES算法中只用到64位密钥中的其中56位,而第8、16、24、.64位8个位并未参与DES运算,这一点,向我们提出了一个应用上的要求,即DES的安全性是基于除了8,

35、16,24,.64位外的其余56位的组合变化256才得以保证的.因此,在实际应用中,我们应避开使用第8,16,24,.64位作为有效数据位,而使用其它的56位作为有效数据位,才能保证DES算法安全可靠地发挥作用.如果不了解这一点,把密钥Key的8,16,24,. .64位作为有效数据使用,将不能保证DES加密数据的安全性,对运用DES来达到保密作用的系统产生数据被破译的危险,这正是DES算法在应用上的误区,留下了被人攻击、被人破译的极大隐患.2.3 ECC密码体制椭圆曲线13：一条椭圆曲线是在射影平面上满足威尔斯特拉斯方程（Weierstrass）所有点的集合.椭圆曲线一般方程：其中是满足某些

36、简单条件的实数.定义中包括一个称为无穷远点的元素,记为.图5 椭圆曲线椭圆曲线上的加法运算定义如下：如果其上的3个点位于同一直线上,那么它们的和是.进一步可如下定义椭圆曲线上的加法律：为加法单位元,即对椭圆曲线上任一点,即+=.设是椭圆曲线上的一点,它的加法逆元定义为这是因为的连线延长到无穷远时,得到椭圆曲线上的另一个点,即椭圆曲线上的3点,共线,所以,即设和是椭圆曲线上坐标不同的两点,的定义如下：画一条通过的直线与椭圆曲线交于点.由得点的倍数定义如下：在点做椭圆曲线的一条切线,设切线与椭圆曲线交于点,定义.类似地定义等.密码学中普遍采用的是有限域上的椭圆曲线,有限域上的椭圆曲线是指曲线方程定

37、义为,所有系数都是某一有限域中的元素.其中最为常用的是由方程定义的曲线.因为是方程的判别式,当时,方程有重根,设为,则点是方程的重根.令则,所以在点无定义,即曲线在点的切线无定义,因此点的倍数运算无定义.加法定义如下：设则.如果,那么,即是的加法逆元,表示为设,则由以下规则确定：其中2.3.1算法原理（1）消息嵌入到椭圆曲线点在使用椭圆曲线构造密码体制前,需要将明文消息镶嵌到椭圆曲线上,作为椭圆曲线上的点.设明文消息是,椭圆曲线为,是一个足够大的整数,使得将明文消息镶嵌到椭圆曲线上时,错误概率是.实际情况中,可3050在之间取值.不妨取,对明文消息,如下计算一系列：直到是平方根,即得到椭圆曲线

38、上的点.因为在0到的整数中,有一半是模的平方剩余.所以次找到使得是平方根的概率不下于.反过来,为了从椭圆曲线上的点得到明文消息,只需求.（2）ELGamal密码体制的原理密钥产生过程：首先选择一素数以及两个小于的随机数g和x,计算.以作为公开密钥,作为秘密密钥.加密过程：设欲加密明文消息M,随机选一与p-1互素的整数,计算,密文为.解密过程：这是因为（3）利用椭圆曲线实现ELGamal密码体制首先选取一条椭圆曲线,并得,将明文消息m嵌入到曲线上得点,再对点做加密变换.取的一个生成元G,和G作为公开参数.用户A选作为秘密钥,并以作为公开钥.任一用户B若想向A发送消息,可选取一随机正整数k,产生以

39、下点对作为密文： A解密时,以密文点对中的第二个点减去用自己的秘密钥与第一个点的倍乘,即 攻击者若想由得到,就必须知道.而要得到,只有通过椭圆曲线上的两个已知点G和kG,这意味着必须求椭圆曲线上的离散对数,因此不可行.2.3.2 ECC算法分析根据椭圆曲线的数量乘的定义,可以找到一个点,满足, (共有个)若存在椭圆曲线上的另一点,满足方程椭圆曲线离散对数问题就是在已知,的情况下求屉的过程.即在数学上,离散对数(DLP)求解是非常困难的,必须通过附加结构亚指数时间的索引计算方法求解而有限域上的椭圆曲线的代数对象由一个基本运算构成,没有此类的附加结构,所以不能由索引的方法求得对于有限域上的大素数因

40、子椭圆离散对数问题,目前还没有有效的攻击方法,也构成了椭圆曲线密码体制的数学基础 随着计算机技术的发展为保障数据安全原本普遍采用的RSA算法的密钥长度需一再增大,使得它的运算负担越来越大.相比之下,椭圆曲线密码体制ECC可用短得多的密钥获得同样的安全性,具有广泛的应用前景.与基于有限域上离散对数问题的公钥体制如RSA相比,椭圆曲线密码体制有如下优点：(1) 安全性高目前主流的数字签名方案是基于大整数因子分解问题的RSA 算法,其特点是数学原理简单.在应用过程中容易实现,但其单位安全强度相对较低,目前用国际上公认的对于RSA 算法最有效的攻击方法一般数域筛选(NFS)方法去破译和攻击RSA算法,

41、它的破译或求解难度是亚指数级的,其复杂度 而对于ECC算法,目前最有效的攻击方法其破译和求解的难度是指数级的,其复杂度,其中是ECC交换群的阶的最大素因子,也就是在相同的密钥长度条件下,ECC算法的安全性要远远超过RSA 算法ECC算法的计算量小并且处理速度快在一定的相同的计算资源条件下,虽然在RSA 中可以通过选取较小的公钥(可以小到3)的方法提高公钥处理速度,即提高加密和签名验证的速度,使其在加密和签名验证速度上与ECC有可比性但在私钥的处理速度上(解密和签名),ECC远比RSA、DSA 快得多 同时ECC系统的密钥生成速度比RSA 快百倍以上以163位的ECC算法与1024位的RSA 算

42、法比较ECC算法的签名时间为3.0ms,密钥对生成时间为3.8ms,但RSA 算法却分别高达228.4ms和47O8.3ms,因此在相同条件下,ECC则有更高的加密性能ECC算法的存储空间占用小：ECC 的密钥尺寸和系统参数与RSA 相比耍小得多160位ECC与1024位RSA具有相同的安全强度210位ECC则与2048位RSA 具有相同的安全强度,意味着它所占的存贮空间要小得多5RSA密钥长度ECC密钥长度RSA/ECC(密钥长度比)5121065:17681326:110241607:1204821010:12100060035:1表1 ECC与RSA安全模长的比较(2) 密钥量小由攻击两

43、者的算法复杂度可知,在实现相同的安全性能条件下,ECC体制所需的密钥量远比基于有限域上的离散对数问题的公钥体制的密钥量小.(3)灵活性好有限域一定的情况下,其上的循环群（即）就定了.而上的椭圆曲线可以通过改变曲线参数,得到不同的曲线,形成不同的循环群.因此,椭圆曲线具有丰富的群结构和多选择性.ECC算法的带宽要求低,当对长消息进行加解密时,两类密码系统有相同的带宽要求,但应用于短消息时ECC带宽要求却低得多而数字签名正是基于短消息的通讯传输,因此基于ECC体制的数字签名系统带宽要求比RSA低很多,易于在各种网络环境下推广应用此外,ECC算法的灵活性要高于RSA算法,它可以通过改变参数设置获得不

44、同的曲线,具有丰富的群结构和多选择性2.4 算法的计算复杂度DES：从子密钥的生成过程中,可以知道实际上只有56位有效,因为8、16、32、64这8位作为奇偶校验位从穷举攻击的角度来 图4 产生子密钥的过程说,这56位长度的密钥是远远不够的,由于DES的互补性,穷举攻击时,仅需搜索其一半只要攻击者掌握若干密文c和对应的明文m用一切可能的密钥 来加密M,直到得到E(m)=C,那么就是破译的密钥同时利用穷举攻击的时间复杂度是ECC：攻击有限域上的离散对数问题可用指数积分法,其运算复杂度为,其中是模数,为素数.而它对椭圆曲线上的离散对数问题并不有效.目前攻击椭圆曲线上的离散对数问题只有适合攻击任何循

45、环群上离散对数问题的大不小步法,其运算复杂度为,其中是椭圆曲线所形成的Abel群的阶的最大素因子.因此,ECC密码体制比基于有限域上的离散对数问题的公钥体制更安全.第三章 基于ECC的数字签名方案3.1数字签名消息加密可以保护信息交换双方不受第三方的攻击,但是它不能处理通信双方自身发生的攻击,这种攻击可以有多种形式.在收发双方不能完全信任的情况下,就需要除加密外其他的方法来解决这些问题.数字签名是解决这个问题的最好方法,它的作用相当于手写签名.数字签名,就是只有信息的发送者才能产生的别人无法伪造的一段数字串,这段数字串同时也是对信息的发送者发送信息真实性的一个有效证明.简单地说,所谓数字签名就是附加在数据单元上的一些数据,或是对数据单元所作的密码变换.这种数据或变换允许数据单元的接收者用以确认数据单元的来源和数据单元的完整性并保护数据,防止被人(例如接收者)进行伪造.它是对电子形式的消息进行签名的一种方法,一个签名消息能在一个通信网络中传输.基于公钥密码体制和私钥密码体制都可以获得数字签名