椭圆曲线密码研究与实现
|
摘要
椭圆曲线密码体制是目前公钥体制中每比特密钥安全强度最高的一种密码体制，在相同安全强度条件下，椭圆曲线密码体制具有较短的密钥长度，较少的计算量、存储量、带宽等优点，而且椭圆曲线密码体制已经被许多国际标准化机构作为标准化文件向全球颁布，被认为是下一代最通用的公钥密码系统。
本文首先介绍并分析了椭圆曲线密码体制的优点及研究现状；其次研究了椭圆曲线密码体制的基本理论；第三，分析了椭圆曲线密码的安全性并介绍了密钥共享，加密，数字签名等椭圆曲线密码体制；第四，深入研究了特征为2的有限域F_2m中的元素在多项式基和最优正规基表示下的乘法运算和乘法逆运算的快速算法，并对Hankerson等人提出的多项式基下的乘法运算的快速算法作了改进，而且在实验的基础上不仅分析研究了F_2m域中元素在多项式基和最优正规基表示下的乘法和乘法逆运算的性能，还对这两种基表示下的F_2m域中元素运算效率的优劣作了比较和研究，所得的结论可供在实现椭圆曲线密码体制时参考；第五，研究了目前流行的计算椭圆曲线标量乘法的快速算法，同时改进了固定基点梳形法，提高了整个系统的速度，并在实验的基础上分析研究了流行算法的优劣；第六，实现了基于F_2m的椭圆曲线密码体制的算法库，在我们的算法库中只需稍微改变便能实现基于任意尺寸的F_2m上的ECDH，ECES，ECDSA等椭圆曲线密码体制；第七，实现了两条安全椭圆曲线上的椭圆曲线密码体制，包括ECDH，ECES，ECDSA。一条是ANSIX9.62中的191bit的安全曲线，F_2m中的元素用多项式基表示，一条是我们安全曲线库中的148bit的安全曲线，F_2m中的元素用最优正规基表示；最后对本文进行总结和展望了以后的工作。
The highest safety strength of private key per bit in the Public-Key Cryptography systems is the Elliptic Curve Cryptography at present. Under similar secure conditions, the ECC has the advantages such as: less computation amounts, shorter length of private key, smaller storing and bandwidth. Moreover, it has been declared as standard documents adopted by many international standard institutions and regarded as the most universally used public key system.
Firstly, we generalize and analyze the advantages and present research of Elliptic Curve Cryptography; secondly, we study the basic theory of the ECC; thirdly, we illustrate the safety of the ECC and discuss the Elliptic Curve Key Agreement Scheme, Elliptic Curve Encryption Scheme and Elliptic Curve Digital Signature Algorithm; fourthly, we study fast algorithms of the multiplication and inversion multiplication of the element of in the underlying finite field F2m whose characteristic is two represented by the two basis of optimal normal basis and polynomial basis. We make improvements to the fast algorithm of the polynomial basis multiplication by Hankerson and base on the experiments, we describe the properties and compare the advantages of the multiplication and inversion multiplication of the elements in F2m field under optimal normal bases and polynomial basis .Results concluding from the study car be used as references in the realization of the elliptic curve cryptosystem; fifthly, we overview the current fast algorithm of point multiplication, improve the fix base point comb algorithm, advance the speed of the whole system and remark the advantages and disadvantages of the popular algorithms based upon the experimental datas; sixthly we realize the algorithm library of elliptic curve cryptography based on the F2m. Only change slightly in our algorithm library can we realize the ECDH, ECES, ECDSA based onF2m of anysize; seventhly, we realize the ECC on two secure elliptic curves, including ECDH, ECES, ECDSA. One is the 191 bits secure curve of ANSI X9.62 , elements in F2m field represented by polynomial basis, the other is the 148bits secure curve in our secure curve library elements in F2m field represented by optimal normal basis; the conclusion summarizes the whole paper and preview the the further developments of the work we have done.
本文首先介绍并分析了椭圆曲线密码体制的优点及研究现状；其次研究了椭圆曲线密码体制的基本理论；第三，分析了椭圆曲线密码的安全性并介绍了密钥共享，加密，数字签名等椭圆曲线密码体制；第四，深入研究了特征为2的有限域F_2m中的元素在多项式基和最优正规基表示下的乘法运算和乘法逆运算的快速算法，并对Hankerson等人提出的多项式基下的乘法运算的快速算法作了改进，而且在实验的基础上不仅分析研究了F_2m域中元素在多项式基和最优正规基表示下的乘法和乘法逆运算的性能，还对这两种基表示下的F_2m域中元素运算效率的优劣作了比较和研究，所得的结论可供在实现椭圆曲线密码体制时参考；第五，研究了目前流行的计算椭圆曲线标量乘法的快速算法，同时改进了固定基点梳形法，提高了整个系统的速度，并在实验的基础上分析研究了流行算法的优劣；第六，实现了基于F_2m的椭圆曲线密码体制的算法库，在我们的算法库中只需稍微改变便能实现基于任意尺寸的F_2m上的ECDH，ECES，ECDSA等椭圆曲线密码体制；第七，实现了两条安全椭圆曲线上的椭圆曲线密码体制，包括ECDH，ECES，ECDSA。一条是ANSIX9.62中的191bit的安全曲线，F_2m中的元素用多项式基表示，一条是我们安全曲线库中的148bit的安全曲线，F_2m中的元素用最优正规基表示；最后对本文进行总结和展望了以后的工作。
The highest safety strength of private key per bit in the Public-Key Cryptography systems is the Elliptic Curve Cryptography at present. Under similar secure conditions, the ECC has the advantages such as: less computation amounts, shorter length of private key, smaller storing and bandwidth. Moreover, it has been declared as standard documents adopted by many international standard institutions and regarded as the most universally used public key system.
Firstly, we generalize and analyze the advantages and present research of Elliptic Curve Cryptography; secondly, we study the basic theory of the ECC; thirdly, we illustrate the safety of the ECC and discuss the Elliptic Curve Key Agreement Scheme, Elliptic Curve Encryption Scheme and Elliptic Curve Digital Signature Algorithm; fourthly, we study fast algorithms of the multiplication and inversion multiplication of the element of in the underlying finite field F2m whose characteristic is two represented by the two basis of optimal normal basis and polynomial basis. We make improvements to the fast algorithm of the polynomial basis multiplication by Hankerson and base on the experiments, we describe the properties and compare the advantages of the multiplication and inversion multiplication of the elements in F2m field under optimal normal bases and polynomial basis .Results concluding from the study car be used as references in the realization of the elliptic curve cryptosystem; fifthly, we overview the current fast algorithm of point multiplication, improve the fix base point comb algorithm, advance the speed of the whole system and remark the advantages and disadvantages of the popular algorithms based upon the experimental datas; sixthly we realize the algorithm library of elliptic curve cryptography based on the F2m. Only change slightly in our algorithm library can we realize the ECDH, ECES, ECDSA based onF2m of anysize; seventhly, we realize the ECC on two secure elliptic curves, including ECDH, ECES, ECDSA. One is the 191 bits secure curve of ANSI X9.62 , elements in F2m field represented by polynomial basis, the other is the 148bits secure curve in our secure curve library elements in F2m field represented by optimal normal basis; the conclusion summarizes the whole paper and preview the the further developments of the work we have done.
引文
[1] 张龙军，沈钧毅，赵霖．椭圆曲线密码体制安全性研究．西安交通大学学报，2000，35(10)：1038—1041
[2] William Stallings著，杨明等译．密码编码学与网络安全：原理与实践．第二版．北京：电子工业出版社，2001
[3] 孟春岩，范辉，余雪丽．椭圆曲线用于加密的安全性讨论．微型机与应用，2001，6(6)：59—60
[4] 罗涛，易波．基于WAP的移动电子商务的安全．无线电工程，2003，33(1)：45—48
[5] 卢开澄．计算机密码学：计算机网络中的数据保密与安全．第二版．北京：清华大学出版社，1998
[6] 胡冠章．应用近世代数．第二版．北京：清华大学出版社，1999
[7] 张禾瑞．近世代数基础．1978年修订本．北京：高等教育出版社，2001
[8] 王新梅，肖国镇．纠错码—原理与方法．第一版．西安：西安电子科技大学出版社，1991
[9] ANSI X9.62-1998, Public key Cryptography For The Financial Services Industry: The Elliptic Curve Digital Signature Algorithm(ECDSA). Working Draft, 1998
[10] ANSI X9.63-199x, Public key Cryptograph for the Financial Services Industry: Key Agreement and Key Transport Using Elliptic Curve Cryptography. Working Draft, 1999
[11] A.Menezes,T.Okamoto. Reducing elliptic curve logarithms to logarithms in a finite field.http://www.cacr.math.uwaterloo.ca ,2003
[12] M.Brown, D,Hankerson,J.Lopez. Software Implementation of the NIST Elliptic Curve Over Prime Fields. http://www.cacr.math.uwatedoo.ca,2003
[13] R.Gallant,R.Lambert and S.Vanstone. Faster Point Multiplication on Elliptic Curves with Efficient Endomorphisms. In: CRYPTO 2001.Canada:certiom,2001
[14] D.Hankerson,L.Hemandez, A.Menezes. Software Implementation of Elliptic Curve Cryptography Over Binary Fields. In:CHES 2000. Canada:certiom, 2000
[15] 顾纯祥，祝跃飞．SEA算法及安全椭圓曲线的有效选择．信息工程大学学报，2000，1(4)：1—4
[16] J.Lopez,R.Dahab,High-Speed Software Multiplication in F2m. In:
INDOCRYPT. Canada:waterloo ,2000
[17] 王育民，刘建伟编著．通信网的安全——理论与技术．第一版．西安：西安电子科技大学出版社，1999
[18] Shuhong Gao. Normal Bases over Finite Fields. http://www.cacr.math.uwaterloo.ca,2003
[19] D.E.Knuth.Seminumerical Algorithms. 2nd Edition.U.S.A.: Addison Weasley,1981
[20] Certicom. OnlineECCTutorlal.http://www.certicom. com/resources/ecc/math9.html,2003
[21] A.R.Masoleh,M.A.Hasan. Fast Normal Basis Multiplication Using General Purpose Processors.In: Technical Report of CACR.Canada:waterloo, 2001
[22] Helger Lipmaa. Elliptic Curves Cryptosystem:Implementation http://www.tcs.hut.fi/～helger/crypto/link/public/elliptic/implementation.html,2003
[23] M.A.Hasan. Efficient Computation of Multiplicative Inverse for Cryptographic Applications. In: Technical Report of CACR.Canada:waterloo, 2001
[24] R.Schroeppel,H.Oraman,S.O'Malley et al. Fast key exchange with elliptic curve systems.In:Advances in Cryptology-Crypto'95. Canada:Certiom, 1995
[25] J.Solinas. Efficient Arithmetic on Koblitz Curves. http://www.cacr.math.uwaterloo.ca,2003
[26] T.Meskanen, A.Renvall,P.Steinby. Efficient Scalar Multiplication on Elliptic Curves. In: Technical Report of CACR.Canada:waterloo, 2001
[27] J.Lopenz and R.Dahab. Fast Multiplication on Elliptic Curve over GF(2^n) without Precomputation. In:Cryptographic Hardware and Embedded Systems-CHES'99. Canada:waterloo, 1999
[28] P.Montgomery. Speeding up the Pollard and Elliptic Curve Methods of Factorization. Mathematics of Computation, 1987,48(8):282-290
[29] C.Lim and P.Lee. More Flexible Exponentiation with Precomputation.In: Advances in Cryptology-Cryto'94. Canada:waterloo, 1994
[30] Claude E. Shannon. Communication Theory of Secrecy Sys? Bell System Technical Journal, 1949,28(5):656-715
[31] N.Koblitz. Course in Number Theory and Cryptography. 2nd Edition. U.S.A:Springer-Verlag, 1994
[32] A.Menezes.Elliptic Curve Public Key Cryptosystems. 2nd Edition.Canada: Kluwer Academic Publisers, 1993
[33] N.Koblitz.Elliptic Curve Cryptosystems. Mathematics of Computation, 1987,49(9):321-335
[34] V.Smiller. Use of Elliptic Curve in Cryptography. Advances in Cryptology: Proceedings of Crypto'85,Lecture Notes in Computer Science,1986,218(9):417-426
[35] R.E.Crandell. Method and Apparatus for Public Key Exchange in a Cryptogrphic System, U.S.Patent#5,159,632,27 Oct, 1992
[36] Certicom.Cryptography Resources. http://www.certicom.com/resources/index.html,2003
[37] R.Schoof. Counting Points on Elliptic Curve over Finite Fields .J.T.Nombres Bordeaux, 1995,7(8):219-254
[38] A .Atkin .The Number of Point on an Elliptic Curve Modulo a Prime.1nd Edition.U.SA.:Preprint,1988
[39] WPI. WPI ECE Dept Computer Services Information and Help. http://www.ece.wpi.edu/research/crypt/publications/,2003
[40] Atsuko Miyaji. Elliptic Curve over F_p, Suitable for Cryptosystems. http://www.cacr.math.uwaterloo.ca,2003
[41] J.M.Pollard. Monte carlo methods for index computations mod p.Math Comp, 1978,32(6):918-924
[42] P.van, Oorschot and M.Wiener. Parallel collision search with cryptanalytic applications, http://www.ece.wpi.edu/research/crypt/publications/,2003
[43] S.Pohlig and M.Hellman.An improved algorithm for computing logarithms over GF(F_p,) and its cryptographic significance. IEEE Transactions on Information Theory, 1978,24(8): 106-110
[44] A.Menezes, T.Okamoto and S.Vanstone. Reducing elliptic curve logarithms to logarithms in a finite field. IEEE Transactions on Information Theory, 1993,39(5): 1639-1646
[45] D. Shanks. Five number theoretical algorithms. 2nd Edition .U.S.A. :Witehall, 1972
[46] N.Smart. Announcement of an attack on the ECDLP for anomalous elliptic curve. http://www.certicom.com/resources/w_papers/w_papers.html,2003
[47] M.Wineer, R.Zuccherato.Faster Attacks on Elliptic Curve Cryptosystems. http: // www. sympatico. ca/wienerfamily/Michael/MichaelPapers/ECattack, pdf,2003
[48] H.Cohen, A.Miyaji, and T.O. Efficient elliptic curve exponentiation using mixed coordinates.In:Asiacrypt 98. Singapore:Berlin, 1998
[49] HelgerLipmaa.CryptoStandards.http://www.tcs.hut.fi/～helger/crypto/link/practice/standards.html,2003
[50] Victor Shoup. Victor Shoup's Research Papers. http://www.shoup.net/papers/,2003
[51] IEEE P1363a/D9 Standard Specification for Public Key Cryptography:Additional Techniques. Draft, June,2001
[52] A.O.L.Atkin and F.Morain .Elliptic curves and primality proving. Mathematics of Computation, 1993,61(7): 29-68
[53] G.Lay and H.Zimmer. Counting the number of points on elliptic curves over finite fields, http://planeta.terra.com.br/informatica/paulobarreto/,2003
[54] Shamus Software Ltd.Multiprecision Integer and Rational Arithmetic C/C++ Library .http ://indigo.ie/～mscott/#P 1363,2003
[55] B. Narasimhan.Diehead. http://stat.fsu.edu/～geo/,2003
[56] Mike Rosing. Implementing Elliptic Curve Cryptography. http://www.manning.com/Rosing/,2003
[2] William Stallings著，杨明等译．密码编码学与网络安全：原理与实践．第二版．北京：电子工业出版社，2001
[3] 孟春岩，范辉，余雪丽．椭圆曲线用于加密的安全性讨论．微型机与应用，2001，6(6)：59—60
[4] 罗涛，易波．基于WAP的移动电子商务的安全．无线电工程，2003，33(1)：45—48
[5] 卢开澄．计算机密码学：计算机网络中的数据保密与安全．第二版．北京：清华大学出版社，1998
[6] 胡冠章．应用近世代数．第二版．北京：清华大学出版社，1999
[7] 张禾瑞．近世代数基础．1978年修订本．北京：高等教育出版社，2001
[8] 王新梅，肖国镇．纠错码—原理与方法．第一版．西安：西安电子科技大学出版社，1991
[9] ANSI X9.62-1998, Public key Cryptography For The Financial Services Industry: The Elliptic Curve Digital Signature Algorithm(ECDSA). Working Draft, 1998
[10] ANSI X9.63-199x, Public key Cryptograph for the Financial Services Industry: Key Agreement and Key Transport Using Elliptic Curve Cryptography. Working Draft, 1999
[11] A.Menezes,T.Okamoto. Reducing elliptic curve logarithms to logarithms in a finite field.http://www.cacr.math.uwaterloo.ca ,2003
[12] M.Brown, D,Hankerson,J.Lopez. Software Implementation of the NIST Elliptic Curve Over Prime Fields. http://www.cacr.math.uwatedoo.ca,2003
[13] R.Gallant,R.Lambert and S.Vanstone. Faster Point Multiplication on Elliptic Curves with Efficient Endomorphisms. In: CRYPTO 2001.Canada:certiom,2001
[14] D.Hankerson,L.Hemandez, A.Menezes. Software Implementation of Elliptic Curve Cryptography Over Binary Fields. In:CHES 2000. Canada:certiom, 2000
[15] 顾纯祥，祝跃飞．SEA算法及安全椭圓曲线的有效选择．信息工程大学学报，2000，1(4)：1—4
[16] J.Lopez,R.Dahab,High-Speed Software Multiplication in F2m. In:
INDOCRYPT. Canada:waterloo ,2000
[17] 王育民，刘建伟编著．通信网的安全——理论与技术．第一版．西安：西安电子科技大学出版社，1999
[18] Shuhong Gao. Normal Bases over Finite Fields. http://www.cacr.math.uwaterloo.ca,2003
[19] D.E.Knuth.Seminumerical Algorithms. 2nd Edition.U.S.A.: Addison Weasley,1981
[20] Certicom. OnlineECCTutorlal.http://www.certicom. com/resources/ecc/math9.html,2003
[21] A.R.Masoleh,M.A.Hasan. Fast Normal Basis Multiplication Using General Purpose Processors.In: Technical Report of CACR.Canada:waterloo, 2001
[22] Helger Lipmaa. Elliptic Curves Cryptosystem:Implementation http://www.tcs.hut.fi/～helger/crypto/link/public/elliptic/implementation.html,2003
[23] M.A.Hasan. Efficient Computation of Multiplicative Inverse for Cryptographic Applications. In: Technical Report of CACR.Canada:waterloo, 2001
[24] R.Schroeppel,H.Oraman,S.O'Malley et al. Fast key exchange with elliptic curve systems.In:Advances in Cryptology-Crypto'95. Canada:Certiom, 1995
[25] J.Solinas. Efficient Arithmetic on Koblitz Curves. http://www.cacr.math.uwaterloo.ca,2003
[26] T.Meskanen, A.Renvall,P.Steinby. Efficient Scalar Multiplication on Elliptic Curves. In: Technical Report of CACR.Canada:waterloo, 2001
[27] J.Lopenz and R.Dahab. Fast Multiplication on Elliptic Curve over GF(2^n) without Precomputation. In:Cryptographic Hardware and Embedded Systems-CHES'99. Canada:waterloo, 1999
[28] P.Montgomery. Speeding up the Pollard and Elliptic Curve Methods of Factorization. Mathematics of Computation, 1987,48(8):282-290
[29] C.Lim and P.Lee. More Flexible Exponentiation with Precomputation.In: Advances in Cryptology-Cryto'94. Canada:waterloo, 1994
[30] Claude E. Shannon. Communication Theory of Secrecy Sys? Bell System Technical Journal, 1949,28(5):656-715
[31] N.Koblitz. Course in Number Theory and Cryptography. 2nd Edition. U.S.A:Springer-Verlag, 1994
[32] A.Menezes.Elliptic Curve Public Key Cryptosystems. 2nd Edition.Canada: Kluwer Academic Publisers, 1993
[33] N.Koblitz.Elliptic Curve Cryptosystems. Mathematics of Computation, 1987,49(9):321-335
[34] V.Smiller. Use of Elliptic Curve in Cryptography. Advances in Cryptology: Proceedings of Crypto'85,Lecture Notes in Computer Science,1986,218(9):417-426
[35] R.E.Crandell. Method and Apparatus for Public Key Exchange in a Cryptogrphic System, U.S.Patent#5,159,632,27 Oct, 1992
[36] Certicom.Cryptography Resources. http://www.certicom.com/resources/index.html,2003
[37] R.Schoof. Counting Points on Elliptic Curve over Finite Fields .J.T.Nombres Bordeaux, 1995,7(8):219-254
[38] A .Atkin .The Number of Point on an Elliptic Curve Modulo a Prime.1nd Edition.U.SA.:Preprint,1988
[39] WPI. WPI ECE Dept Computer Services Information and Help. http://www.ece.wpi.edu/research/crypt/publications/,2003
[40] Atsuko Miyaji. Elliptic Curve over F_p, Suitable for Cryptosystems. http://www.cacr.math.uwaterloo.ca,2003
[41] J.M.Pollard. Monte carlo methods for index computations mod p.Math Comp, 1978,32(6):918-924
[42] P.van, Oorschot and M.Wiener. Parallel collision search with cryptanalytic applications, http://www.ece.wpi.edu/research/crypt/publications/,2003
[43] S.Pohlig and M.Hellman.An improved algorithm for computing logarithms over GF(F_p,) and its cryptographic significance. IEEE Transactions on Information Theory, 1978,24(8): 106-110
[44] A.Menezes, T.Okamoto and S.Vanstone. Reducing elliptic curve logarithms to logarithms in a finite field. IEEE Transactions on Information Theory, 1993,39(5): 1639-1646
[45] D. Shanks. Five number theoretical algorithms. 2nd Edition .U.S.A. :Witehall, 1972
[46] N.Smart. Announcement of an attack on the ECDLP for anomalous elliptic curve. http://www.certicom.com/resources/w_papers/w_papers.html,2003
[47] M.Wineer, R.Zuccherato.Faster Attacks on Elliptic Curve Cryptosystems. http: // www. sympatico. ca/wienerfamily/Michael/MichaelPapers/ECattack, pdf,2003
[48] H.Cohen, A.Miyaji, and T.O. Efficient elliptic curve exponentiation using mixed coordinates.In:Asiacrypt 98. Singapore:Berlin, 1998
[49] HelgerLipmaa.CryptoStandards.http://www.tcs.hut.fi/～helger/crypto/link/practice/standards.html,2003
[50] Victor Shoup. Victor Shoup's Research Papers. http://www.shoup.net/papers/,2003
[51] IEEE P1363a/D9 Standard Specification for Public Key Cryptography:Additional Techniques. Draft, June,2001
[52] A.O.L.Atkin and F.Morain .Elliptic curves and primality proving. Mathematics of Computation, 1993,61(7): 29-68
[53] G.Lay and H.Zimmer. Counting the number of points on elliptic curves over finite fields, http://planeta.terra.com.br/informatica/paulobarreto/,2003
[54] Shamus Software Ltd.Multiprecision Integer and Rational Arithmetic C/C++ Library .http ://indigo.ie/～mscott/#P 1363,2003
[55] B. Narasimhan.Diehead. http://stat.fsu.edu/～geo/,2003
[56] Mike Rosing. Implementing Elliptic Curve Cryptography. http://www.manning.com/Rosing/,2003