椭圆曲线密码算法的研究与实现
|
摘要
随着信息技术的不断发展和应用，信息的安全性变得越来越重要。现在广泛使用的RSA公钥密码系统已很难满足未来人们对信息高安全性的需求。椭圆曲线密码系统(Elliptic Curve Cryptosystem)是迄今为止每比特具有最高安全强度的密码系统。与其他公钥密码系统相比，椭圆曲线密码系统除了安全性高外，还具有计算负载小，密码尺寸短，占用带宽少等优点。因此，椭圆曲线密码系统被认为是最有希望成为下一代通用的公钥密码系统。
本文首先对密码技术的发展现状及其发展趋势进行了分析和综述，详细的介绍了私钥密码系统和公钥密码系统的发展，并给出了一些典型的加密体制的简要分析。其次，探讨了椭圆曲线密码体制的原理，包括椭圆曲线密码的数学基础、椭圆曲线的基本概念、椭圆曲线密码体制的构造思想、椭圆曲线上点的运算等问题，同时分析了椭圆曲线密码系统的安全性和有效性，给出了安全椭圆曲线应该符合的三个标准。第三，给出了一个基于CM算法的安全椭圆曲线产生算法，利用这个算法产生的椭圆曲线的阶是两个大素数的乘积，并对其的正确性进行了理论上证明。第四，实现了椭圆曲线密码系统中的一些关键性算法，包括椭圆曲线生成算法、椭圆曲线密码中的KP运算、素性检测算法以及大整数间的运算。第五，提出了一种基于ECC的ElGamal数字签名方案，将经典的ElGamal数字签名方案移植到椭圆曲线密码系统之上，并验证了该方案的正确性。最后，对ECC的发展趋势和研究方向进行了探讨。
With the development and application of information technology, the problem of information security becomes more and more important. RS A cryptosystem, a public-key cryptosystem being used widely today, seems to have difficulty in meeting the users' need of higher security. So far, the Elliptic Curve Cryptosystem (ECC) provides the highest strength-per-bit of any cryptosystem known.In addition to its high security, ECC also has many other merits over other public-key cryptosystems such as less computation overheads,shorter key size, considerable bandwidth savings,and so on. All of these merits have made it the best public-key cryptosystem that is suitable for current use in future.
This paper first analyses and summarizes the ststus quo and evolution trend of encryption, and introduces in detail the development of private-key cryptosystem and public-key cryptosystem, and provides the brief analysis of a few typical schemes. Second, the principle of ECC is discussed, including the math foundation of ECC, basic conception of elliptic curve, constructing idea of ECC, operation on the elliptic curve and so on. Meanwhile, the security and efficiency of ECC are analyzed and thus three conditions required by ECC are given. Third, an efficient algorithm to generate the secure elliptic curves which bases on the CM algorithm is presented. According to this algorithm, the rank of elliptic curve constructed is the product of two large prime numbers. And its correctness is proved in theory. Fourth, some key algorithms in ECC are implemented, including algorithm of generating the elliptic curve,algorithm of computing the kP of the ECC, algorithm of detecting prime number and lgorithm of operating be
tween the big integers. Fifth, the variation of Elgamal signature scheme based on ECC is presented and its validity is proved.And the new scheme transplates the typical Elgamal signature scheme int ECC. At last, the evolution trend and reseach direction are discussed.
本文首先对密码技术的发展现状及其发展趋势进行了分析和综述，详细的介绍了私钥密码系统和公钥密码系统的发展，并给出了一些典型的加密体制的简要分析。其次，探讨了椭圆曲线密码体制的原理，包括椭圆曲线密码的数学基础、椭圆曲线的基本概念、椭圆曲线密码体制的构造思想、椭圆曲线上点的运算等问题，同时分析了椭圆曲线密码系统的安全性和有效性，给出了安全椭圆曲线应该符合的三个标准。第三，给出了一个基于CM算法的安全椭圆曲线产生算法，利用这个算法产生的椭圆曲线的阶是两个大素数的乘积，并对其的正确性进行了理论上证明。第四，实现了椭圆曲线密码系统中的一些关键性算法，包括椭圆曲线生成算法、椭圆曲线密码中的KP运算、素性检测算法以及大整数间的运算。第五，提出了一种基于ECC的ElGamal数字签名方案，将经典的ElGamal数字签名方案移植到椭圆曲线密码系统之上，并验证了该方案的正确性。最后，对ECC的发展趋势和研究方向进行了探讨。
With the development and application of information technology, the problem of information security becomes more and more important. RS A cryptosystem, a public-key cryptosystem being used widely today, seems to have difficulty in meeting the users' need of higher security. So far, the Elliptic Curve Cryptosystem (ECC) provides the highest strength-per-bit of any cryptosystem known.In addition to its high security, ECC also has many other merits over other public-key cryptosystems such as less computation overheads,shorter key size, considerable bandwidth savings,and so on. All of these merits have made it the best public-key cryptosystem that is suitable for current use in future.
This paper first analyses and summarizes the ststus quo and evolution trend of encryption, and introduces in detail the development of private-key cryptosystem and public-key cryptosystem, and provides the brief analysis of a few typical schemes. Second, the principle of ECC is discussed, including the math foundation of ECC, basic conception of elliptic curve, constructing idea of ECC, operation on the elliptic curve and so on. Meanwhile, the security and efficiency of ECC are analyzed and thus three conditions required by ECC are given. Third, an efficient algorithm to generate the secure elliptic curves which bases on the CM algorithm is presented. According to this algorithm, the rank of elliptic curve constructed is the product of two large prime numbers. And its correctness is proved in theory. Fourth, some key algorithms in ECC are implemented, including algorithm of generating the elliptic curve,algorithm of computing the kP of the ECC, algorithm of detecting prime number and lgorithm of operating be
tween the big integers. Fifth, the variation of Elgamal signature scheme based on ECC is presented and its validity is proved.And the new scheme transplates the typical Elgamal signature scheme int ECC. At last, the evolution trend and reseach direction are discussed.
引文
[1] 卿斯汉．密码学与计算机网络安全．北京：清华大学出版社，2001，4．31～69
[2] 冯登国．计算机通信网络安全．北京：清华大学出版社，2001，3．23～169
[3] [美]Bruce Schneier著．吴世雄等译．应用密码学．北京：机械工业出版社，2002，5．135～279
[4] 段云所，陈钟．信息网络安全的目标、技术和方法．网络安全技术与应有，2001，1(1)．60～64
[5] 吴文玲，贺也平等．欧洲21世纪数据加密标准候选算法简评．软件学报，2001，(1)．35～37
[6] 冯登国．国内外信息安全研究现状及其发展趋势．网络安全技术与应有，2001，1(1)．8～13
[7] Miyaji A. Elliptic curves over F_n suitable for cryptosystems. In: Seberry J, Zheng Y ed. Advances in Cryptology-AUSCRYPT'92 Proceedings. Berlin: Spring-Verlag, 1993. 479～491
[8] 庞栓琴．椭圆曲线公钥密码体制．西安矿业学院学报，1999，19(3)．84～87
[9] 李学俊，敬忠良，张骏等．基于椭圆曲线离散对数问题的公钥密码．计算机工程与应用，2000(6)．20～22
[10] 徐秋亮，李大兴．椭圆曲线密码体制．计算机研究与发展，1999，36(11)．128l～1288
[11] 张引，王潮，潘云鹤．椭圆曲线密码体制研究与并行实现．遥测遥控，1999，18(1)．49～53
[12] 张龙军，赵霖，沈钧毅．基于有限域的椭圆曲线密码体制的建立研究．小型微型计算机系统，2000，21(10)．1039～1041
[13] Vanstone S A, Zuccherato R J. Elliptic curve cryptosystems using curves of smooth orderthe ring Z_n. IEEE TIT, 1997, 43(7). 1231～1237
[14] 杨君辉，戴宗铎，杨栋毅等．关于椭圆曲线密码的实现．通信技术，2001，117(6)．1～3．
[15] 卢开澄．计算机密码学．北京：清华大学出版社，1998．196～277
[16] 李岚．基于椭圆曲线离散对数问题的密码系统的研究与实现：学位论文．合肥：合肥工业大学，2002，3．1～30
[17] 张方国．超椭圆曲线密码体制的研究：学位论文．西安：西安电子科技大学，2001，10．13～46
[18] 卢忱，周秦武，卞正中等．椭圆曲线密码体制基点选取算法的设计与实现．西安交通大学学报，2000，34(6)．27～30
[19] 王晖．椭圆曲线密码及其在宽带无线IP中的应有：学位论文．西安：西安电子科技大学，2002，4．21～40
[20] Koblitz N. Elliptic curve Cryptosystems. Mathematics of Computation, 1987, 48(177).203～209
[21] 肖立国．椭圆曲线密码算法及其应用研究：学位论文．广西：广西大学，2002．1～40
[22] 张龙军，沈钧毅，赵霖．适于构建密码体制的椭圆曲线上的快速点加算法研究．计算机工程与应用，2000(6)．28～30
[23] Miyaji A. On Secure and Fast Elliptic curve cryptosystems over F_p. IEICE TransFundamentals, 1994(4). 630～635
[24] Eseott A E, Sager J C. Attacking Elliptic Curve Cryptosustem Using the Parallel Pollard's Method. RSA Laboratories CryptoBytes, 1999(2). 79～90
[25] 张龙军，沈钧毅，赵霖．椭圆曲线密码体制安全性研究．西安交通大学学报，2001，35(10)．1038～1041
[26] 王张宜，杨寒涛，张焕国．椭圆曲线密码的安全性分析．计算机工程，2002，28(5)．161～163
[27] 李琼芳．椭圆曲线密码体制及其在智能卡上的应有：学位论文．西安：西安电子科技大学，2001，1．13～46
[28] Menezes A, Okamato T, Vanstone S. Reducing elliptic curve logarithms to logarithms in a finite field. IEEE Transaction on Information Theory, 1993, 39(5). 1639～1646
[29] Menezes A,Vanstone S. The implementation of elliptic curve cryptosystems. In: Seberry J, Pieprzyk J ed. Advances in Cryptology-AUSCRYPT'90 Proceedings. Berlin: Springer-Verlag, 1990. 2～13
[30] Certicom Corp. Current Public-Key Cryptographic Systems. http://www.certicom.com
[31] 陈兴容．椭圆曲线加密系统的设计与实现：学位论文．成都：成都电子科技学，2002，3．1～49
[32] 秦玉荣，王新梅．椭圆曲线密码体制(ECC)的应有．电信快报，2001(1)．134～35
[33] Certicom Corp. ECC Standards. http://www.certicom.com/research
[34] 张龙军，李长虹，沈钧毅．基于有限域Fp上的安全椭圆曲线密码体制研究．小型微型计算机系统，2001，22(12)．1452～1455．
[35] Schoof R. Elliptic curves over finite fields and computation of square roots mod p. Mathematics of computation, 1985, 44(170). 483～494
[36] 杨文锋．Schoof算法及其在椭圆曲线密码体制中的应用．通信技术，2001，11，(6)．10～12
[37] Lercier R, Morain F. Counting the number of points of on elliptic curves over finite fields: strategies and performances. In: Guillou L C, Quisquater J ed. Advances in Cryptolog-EUROCRYPT'95Proceedings. Berlin: Springer-Verlag, 1995.79～94
[38] Atkin A, Marain F. Elliptic curves and pfimality proving. Mathematics of Computation, 1996, 61(203). 29～68
[39] Lay G J, Zimmer H G. Constructing elliptic curves with given group order over large finite fields. In: Adlernan L M, Huang D ed. Algorithmic Number Theory Proceedings. Berlin: Spring-Verlag, 1994. 250～263
[40] 白国强．椭圆曲线密码及其算法研究：学位论文．西安：西安电子科技大学，2000．10～53
[41] Morain F. Building cyclic elliptic curves modulo large primes. In: Davis D W ed. Advan-Ces in Cryptology-EUROCRYPT'91Proceedings. Berlin: Springer-Verlag, 1991. 328～336
[42] 周长缨，Kwok-Yan Lam，周正欧．产生安全椭圆曲线的一种有效方法．通信学报，2001，22(12)．94～98
[43] Anderson R, Vaudenay S. Minding your p's and q's. In: Kim K, Matsumoto Ted. Advances in Cryptology-ANSIACRYPT'96 Proceeding. Berlin: Springer Verlag. 1996. 26～35
[44] 徐秋亮，李大兴．适用于建立密码体制的椭圆曲线的构造方法及实现．计算机学报， 1998，21(12)．1059～1065
[45] 王宇洁．计算机网络通信中数据安全与保密方法的研究：学位论文．沈阳：沈阳工业大学，2001，6．2-23
[46] 郭庆平，金庆华，徐凯声．数字签名技术及其应用．武汉交通大学学报，1999(5)．508～512
[47] 杨义先，孙伟，钮心忻．现代密码新理论．北京：科学出版社，2002，8．23～46
[48] 张龙军，皱涛，沈钧毅．一种基于椭圆曲线密码体制的盲数字签名方案．计算机应用，2001，21(3)．17～19
[2] 冯登国．计算机通信网络安全．北京：清华大学出版社，2001，3．23～169
[3] [美]Bruce Schneier著．吴世雄等译．应用密码学．北京：机械工业出版社，2002，5．135～279
[4] 段云所，陈钟．信息网络安全的目标、技术和方法．网络安全技术与应有，2001，1(1)．60～64
[5] 吴文玲，贺也平等．欧洲21世纪数据加密标准候选算法简评．软件学报，2001，(1)．35～37
[6] 冯登国．国内外信息安全研究现状及其发展趋势．网络安全技术与应有，2001，1(1)．8～13
[7] Miyaji A. Elliptic curves over F_n suitable for cryptosystems. In: Seberry J, Zheng Y ed. Advances in Cryptology-AUSCRYPT'92 Proceedings. Berlin: Spring-Verlag, 1993. 479～491
[8] 庞栓琴．椭圆曲线公钥密码体制．西安矿业学院学报，1999，19(3)．84～87
[9] 李学俊，敬忠良，张骏等．基于椭圆曲线离散对数问题的公钥密码．计算机工程与应用，2000(6)．20～22
[10] 徐秋亮，李大兴．椭圆曲线密码体制．计算机研究与发展，1999，36(11)．128l～1288
[11] 张引，王潮，潘云鹤．椭圆曲线密码体制研究与并行实现．遥测遥控，1999，18(1)．49～53
[12] 张龙军，赵霖，沈钧毅．基于有限域的椭圆曲线密码体制的建立研究．小型微型计算机系统，2000，21(10)．1039～1041
[13] Vanstone S A, Zuccherato R J. Elliptic curve cryptosystems using curves of smooth orderthe ring Z_n. IEEE TIT, 1997, 43(7). 1231～1237
[14] 杨君辉，戴宗铎，杨栋毅等．关于椭圆曲线密码的实现．通信技术，2001，117(6)．1～3．
[15] 卢开澄．计算机密码学．北京：清华大学出版社，1998．196～277
[16] 李岚．基于椭圆曲线离散对数问题的密码系统的研究与实现：学位论文．合肥：合肥工业大学，2002，3．1～30
[17] 张方国．超椭圆曲线密码体制的研究：学位论文．西安：西安电子科技大学，2001，10．13～46
[18] 卢忱，周秦武，卞正中等．椭圆曲线密码体制基点选取算法的设计与实现．西安交通大学学报，2000，34(6)．27～30
[19] 王晖．椭圆曲线密码及其在宽带无线IP中的应有：学位论文．西安：西安电子科技大学，2002，4．21～40
[20] Koblitz N. Elliptic curve Cryptosystems. Mathematics of Computation, 1987, 48(177).203～209
[21] 肖立国．椭圆曲线密码算法及其应用研究：学位论文．广西：广西大学，2002．1～40
[22] 张龙军，沈钧毅，赵霖．适于构建密码体制的椭圆曲线上的快速点加算法研究．计算机工程与应用，2000(6)．28～30
[23] Miyaji A. On Secure and Fast Elliptic curve cryptosystems over F_p. IEICE TransFundamentals, 1994(4). 630～635
[24] Eseott A E, Sager J C. Attacking Elliptic Curve Cryptosustem Using the Parallel Pollard's Method. RSA Laboratories CryptoBytes, 1999(2). 79～90
[25] 张龙军，沈钧毅，赵霖．椭圆曲线密码体制安全性研究．西安交通大学学报，2001，35(10)．1038～1041
[26] 王张宜，杨寒涛，张焕国．椭圆曲线密码的安全性分析．计算机工程，2002，28(5)．161～163
[27] 李琼芳．椭圆曲线密码体制及其在智能卡上的应有：学位论文．西安：西安电子科技大学，2001，1．13～46
[28] Menezes A, Okamato T, Vanstone S. Reducing elliptic curve logarithms to logarithms in a finite field. IEEE Transaction on Information Theory, 1993, 39(5). 1639～1646
[29] Menezes A,Vanstone S. The implementation of elliptic curve cryptosystems. In: Seberry J, Pieprzyk J ed. Advances in Cryptology-AUSCRYPT'90 Proceedings. Berlin: Springer-Verlag, 1990. 2～13
[30] Certicom Corp. Current Public-Key Cryptographic Systems. http://www.certicom.com
[31] 陈兴容．椭圆曲线加密系统的设计与实现：学位论文．成都：成都电子科技学，2002，3．1～49
[32] 秦玉荣，王新梅．椭圆曲线密码体制(ECC)的应有．电信快报，2001(1)．134～35
[33] Certicom Corp. ECC Standards. http://www.certicom.com/research
[34] 张龙军，李长虹，沈钧毅．基于有限域Fp上的安全椭圆曲线密码体制研究．小型微型计算机系统，2001，22(12)．1452～1455．
[35] Schoof R. Elliptic curves over finite fields and computation of square roots mod p. Mathematics of computation, 1985, 44(170). 483～494
[36] 杨文锋．Schoof算法及其在椭圆曲线密码体制中的应用．通信技术，2001，11，(6)．10～12
[37] Lercier R, Morain F. Counting the number of points of on elliptic curves over finite fields: strategies and performances. In: Guillou L C, Quisquater J ed. Advances in Cryptolog-EUROCRYPT'95Proceedings. Berlin: Springer-Verlag, 1995.79～94
[38] Atkin A, Marain F. Elliptic curves and pfimality proving. Mathematics of Computation, 1996, 61(203). 29～68
[39] Lay G J, Zimmer H G. Constructing elliptic curves with given group order over large finite fields. In: Adlernan L M, Huang D ed. Algorithmic Number Theory Proceedings. Berlin: Spring-Verlag, 1994. 250～263
[40] 白国强．椭圆曲线密码及其算法研究：学位论文．西安：西安电子科技大学，2000．10～53
[41] Morain F. Building cyclic elliptic curves modulo large primes. In: Davis D W ed. Advan-Ces in Cryptology-EUROCRYPT'91Proceedings. Berlin: Springer-Verlag, 1991. 328～336
[42] 周长缨，Kwok-Yan Lam，周正欧．产生安全椭圆曲线的一种有效方法．通信学报，2001，22(12)．94～98
[43] Anderson R, Vaudenay S. Minding your p's and q's. In: Kim K, Matsumoto Ted. Advances in Cryptology-ANSIACRYPT'96 Proceeding. Berlin: Springer Verlag. 1996. 26～35
[44] 徐秋亮，李大兴．适用于建立密码体制的椭圆曲线的构造方法及实现．计算机学报， 1998，21(12)．1059～1065
[45] 王宇洁．计算机网络通信中数据安全与保密方法的研究：学位论文．沈阳：沈阳工业大学，2001，6．2-23
[46] 郭庆平，金庆华，徐凯声．数字签名技术及其应用．武汉交通大学学报，1999(5)．508～512
[47] 杨义先，孙伟，钮心忻．现代密码新理论．北京：科学出版社，2002，8．23～46
[48] 张龙军，皱涛，沈钧毅．一种基于椭圆曲线密码体制的盲数字签名方案．计算机应用，2001，21(3)．17～19