快速有限域计算算法与实现研究
|
摘要
ECC中有限域上运算的速度极大地影响ECC实现速度，寻找有限域快速运算算法也就成了近年来密码学研究的一个热点领域。本文通过对不同结构的有限域（、、、）的分析来寻找一种最有利于软件实现的有限域、并在其上实现快速运算。
研究工作分为两个部分,一部分是对复合域、理想扩域的结构特点和其上的快速运算算法的分析、研究；另一部分是对这些快速算法的测试改进，即本地实现。由于有限域上的运算中，计算域元素的逆元以及域元素相乘是消耗时间最多的两个部分，因此对它们的研究本文给予了特别的重视。
在对复合域中的算法进行详细分析后发现，多项式平方运算比元素自乘有更好的时间特性，因此尽可能地用平方运算替代自乘运算是在复合域中进行算法优化的主要手段。基于这种思想，本人提出了一种复合域中的多项式模指数运算算法。通过对算法的分析我们可以得出结论，随着复合域的不断增大，域上指数运算所需的时间可近似表示为，式中n为指数以二进制表示时的比特串长度，为域元素进行多项式相乘所需的时间。不难发现，与传统的指数运算相比，随着指数值的不断增大改进算法在计算上的优势将更加明显。
在最优扩域中，通过分析域元素求逆（AIA算法、MAIA算法、EEA算法）和多项式相乘（传统的多项式相乘，Karatsuba算法）的几个经典算法后，结合我们选择的有限域（Ⅱ型优化扩域）的特点，本人提出了一种基于查表法的实用的域元素求逆算法和多项式相乘算法。经测试（CPU/PⅣ1.4GHz，MS Visual C++6.0），改进后的域元素求逆算法(MEEA)其性能比原算法（EEA）提高了将近5倍，改进后的多项式相乘（MMP）算法比传统的多项式相乘算法性能提高了将近4倍，比Karatsuba算法的性能提高了将近2倍。
The calculation speed over finite fields greatly affects the performance of ECC implementation. So, to find a fast algorithm for finite field calculation becomes a hot field in recent cryptography researches. Through analyzing the different structure of finite fields （、、、）, we insist to find optimal finite fields for software applications.
This thesis is divided into two parts. The first one is the research on the feature of composition fields and optimal extension fields as well as the fast algorithm in those fields. The other one is the implementation of those improved algorithms. The main focus concentrates on the two most time consuming arithmetic in finite field calculation, field inversion and field multiplication.
By analyzing in detail the performance of algorithms in composition fields, we have drawn a conclusion that the time consuming of square is less than that of multiplication with itself. So, we put forward an optimized exponential algorithm in which the multiplication with itself was substituted mostly by square. Through expanding of composition fields, the time consuming of optimal algorithm is , where n is the number of bits of exponential. Obviously, comparing with normal exponential algorithm, the optimal one is better.
After analyzing several classic algorithms of field-inversion and polynomial multiplication in optimal fields, we propose two efficient algorithms to modified field inversion and polynomial multiplication algorithms. The test results show that the speed performance of the improved field-inversion algorithm has been increased nearly 5 times and the improved polynomial multiplication algorithm has been increased nearly 4 times.
研究工作分为两个部分,一部分是对复合域、理想扩域的结构特点和其上的快速运算算法的分析、研究；另一部分是对这些快速算法的测试改进，即本地实现。由于有限域上的运算中，计算域元素的逆元以及域元素相乘是消耗时间最多的两个部分，因此对它们的研究本文给予了特别的重视。
在对复合域中的算法进行详细分析后发现，多项式平方运算比元素自乘有更好的时间特性，因此尽可能地用平方运算替代自乘运算是在复合域中进行算法优化的主要手段。基于这种思想，本人提出了一种复合域中的多项式模指数运算算法。通过对算法的分析我们可以得出结论，随着复合域的不断增大，域上指数运算所需的时间可近似表示为，式中n为指数以二进制表示时的比特串长度，为域元素进行多项式相乘所需的时间。不难发现，与传统的指数运算相比，随着指数值的不断增大改进算法在计算上的优势将更加明显。
在最优扩域中，通过分析域元素求逆（AIA算法、MAIA算法、EEA算法）和多项式相乘（传统的多项式相乘，Karatsuba算法）的几个经典算法后，结合我们选择的有限域（Ⅱ型优化扩域）的特点，本人提出了一种基于查表法的实用的域元素求逆算法和多项式相乘算法。经测试（CPU/PⅣ1.4GHz，MS Visual C++6.0），改进后的域元素求逆算法(MEEA)其性能比原算法（EEA）提高了将近5倍，改进后的多项式相乘（MMP）算法比传统的多项式相乘算法性能提高了将近4倍，比Karatsuba算法的性能提高了将近2倍。
The calculation speed over finite fields greatly affects the performance of ECC implementation. So, to find a fast algorithm for finite field calculation becomes a hot field in recent cryptography researches. Through analyzing the different structure of finite fields （、、、）, we insist to find optimal finite fields for software applications.
This thesis is divided into two parts. The first one is the research on the feature of composition fields and optimal extension fields as well as the fast algorithm in those fields. The other one is the implementation of those improved algorithms. The main focus concentrates on the two most time consuming arithmetic in finite field calculation, field inversion and field multiplication.
By analyzing in detail the performance of algorithms in composition fields, we have drawn a conclusion that the time consuming of square is less than that of multiplication with itself. So, we put forward an optimized exponential algorithm in which the multiplication with itself was substituted mostly by square. Through expanding of composition fields, the time consuming of optimal algorithm is , where n is the number of bits of exponential. Obviously, comparing with normal exponential algorithm, the optimal one is better.
After analyzing several classic algorithms of field-inversion and polynomial multiplication in optimal fields, we propose two efficient algorithms to modified field inversion and polynomial multiplication algorithms. The test results show that the speed performance of the improved field-inversion algorithm has been increased nearly 5 times and the improved polynomial multiplication algorithm has been increased nearly 4 times.
引文
【1】Miller, V.: Uses of elliptic curves in cryptography. In Lecture Notes in Computer Science 218:Advances in Crytology - CRYPTO '85, pages 417-426, Springer-Verlag, Berlin, 1986.
【2】Koblitz, N.: Elliptic curve cryptosystems. Mathematics of Computation, 48: 203-209, 1987.
【3】Schneier,Elliptic Curve Cryptosystems.Applied Cryptography,P480
【4】D.R.斯廷森著，张文政等译，密码学――理论和实践基础，国防科学技术保密通信重点实验室，1997年
【5】Naoya Torii，Kazuhiro Yokoyama，Elliptic Curve Cryptosystem，FUJITSU Sci. Tech. J.,36, 2,(December 2000)
【6】Julio Lopez,Ricardo Dahab，an overview elliptic curve cryptography，Institute of Computing State University of Campinas,May 22.2000
【7】G. Harper, A. Menezes, and S. Vanstone. Public-key cryptosys temswith very small key lengths. In Rainer A. Rueppel, editor, Advances inCryptology | EUROCRYPT '92, pages 163{173, Berlin, 1992. Springer-Verlag. Lecture Notes in Computer Science Volume 658.
【8】D. Bailey and C. Paar. Optimal Extension Fields for fast Arithmetic in Public-Key Algorithms. In Advances in Cryptology - CRYPTO’98, LNCS 1462, pages472–485, Berlin, 1998. Springer-Verlag.
【9】D. Bailey and C. Paar. E.cient Arithmetic in Finite Field Extensions withApplication in Elliptic Curve Cryptography. Journal of Cryptology, 2001. toappear.
【10】胡冠章，“应用近世代数”p40－42，清华大学出版社，2000.9
【11】王新梅、肖国镇，纠错码――原理与方法p117-118，西安电子科技大学出版社,2001.4
【12】E. De Win, A. Bosselaers, S. Vandenberghe, P. De Gersem, and J. Vandewalle.A fast software implementation for arithmetic operations inGF(2n). In K. Kim and T. Matsumoto, editors, Advances in Cryptology| ASIACRYPT '96, pages 65－76, Berlin, 1996. Springer-Verlag. LectureNotes in Computer Science Volume 1233.
【13】R. Schroeppel, H. Orman, S. O'Malley, and O. Spatscheck. Fast KeyExchange with Elliptic Curve Systems. In Don Coppersmith, editor,Advances in Cryptology | CRYPTO '95, pages 43-56, Berlin, 1995.Springer-Verlag. Lecture Notes in Computer Science Volume 963.
【14】Microprocessor and Microcomputer Standards Committee of the IEEE Computer Society，IEEE Std 1363-2000，IEEE Standard Specifications for Public-Key Cryptography，Approved 30 January 2000 IEEE-SA Standards Board
【15】王新梅、肖国镇，纠错码――原理与方法p114，西安电子科技大学出版社,2001.4
【16】D. Bailey ,Computation in Optimal Extension Fields,May 2000
【17】R. Lidl and H. Niederreiter. Finite Fields, volume 20 of Encyclopedia of athematics and its Applications. Addison-Wesley, Reading, Massachusetts, 1983.
【18】S. B. Mohan and B. S. Adiga. Fast Algorithms for Implementing RSA Public Key Cryptosystem. Electronics Letters, 21(17):761, 1985.
【19】A. J. Menezes, P. C. van Oorschot, and S. A. Vanstone. Handbook of Applied Cryptography. CRC Press, 1997.
【20】Eun Jeong Lee, Duk Soo Kim, and Pil Joong Lee. Speed-up of Fpm Arithmetic for Elliptic Curve Cryptosystems. In Proceedings of ICICS '98, Berlin, 1998. Springer Lecture Notes in Computer Science.
【21】B．施奈尔著，吴世忠、祝世雄等译，应用密码学p177－178，机械工业出版社，2002.3
【22】A Certicom Whitepaper，The Elliptic Curve Cryptosystem，Published: April 1997，
Updated: July 2000
【2】Koblitz, N.: Elliptic curve cryptosystems. Mathematics of Computation, 48: 203-209, 1987.
【3】Schneier,Elliptic Curve Cryptosystems.Applied Cryptography,P480
【4】D.R.斯廷森著，张文政等译，密码学――理论和实践基础，国防科学技术保密通信重点实验室，1997年
【5】Naoya Torii，Kazuhiro Yokoyama，Elliptic Curve Cryptosystem，FUJITSU Sci. Tech. J.,36, 2,(December 2000)
【6】Julio Lopez,Ricardo Dahab，an overview elliptic curve cryptography，Institute of Computing State University of Campinas,May 22.2000
【7】G. Harper, A. Menezes, and S. Vanstone. Public-key cryptosys temswith very small key lengths. In Rainer A. Rueppel, editor, Advances inCryptology | EUROCRYPT '92, pages 163{173, Berlin, 1992. Springer-Verlag. Lecture Notes in Computer Science Volume 658.
【8】D. Bailey and C. Paar. Optimal Extension Fields for fast Arithmetic in Public-Key Algorithms. In Advances in Cryptology - CRYPTO’98, LNCS 1462, pages472–485, Berlin, 1998. Springer-Verlag.
【9】D. Bailey and C. Paar. E.cient Arithmetic in Finite Field Extensions withApplication in Elliptic Curve Cryptography. Journal of Cryptology, 2001. toappear.
【10】胡冠章，“应用近世代数”p40－42，清华大学出版社，2000.9
【11】王新梅、肖国镇，纠错码――原理与方法p117-118，西安电子科技大学出版社,2001.4
【12】E. De Win, A. Bosselaers, S. Vandenberghe, P. De Gersem, and J. Vandewalle.A fast software implementation for arithmetic operations inGF(2n). In K. Kim and T. Matsumoto, editors, Advances in Cryptology| ASIACRYPT '96, pages 65－76, Berlin, 1996. Springer-Verlag. LectureNotes in Computer Science Volume 1233.
【13】R. Schroeppel, H. Orman, S. O'Malley, and O. Spatscheck. Fast KeyExchange with Elliptic Curve Systems. In Don Coppersmith, editor,Advances in Cryptology | CRYPTO '95, pages 43-56, Berlin, 1995.Springer-Verlag. Lecture Notes in Computer Science Volume 963.
【14】Microprocessor and Microcomputer Standards Committee of the IEEE Computer Society，IEEE Std 1363-2000，IEEE Standard Specifications for Public-Key Cryptography，Approved 30 January 2000 IEEE-SA Standards Board
【15】王新梅、肖国镇，纠错码――原理与方法p114，西安电子科技大学出版社,2001.4
【16】D. Bailey ,Computation in Optimal Extension Fields,May 2000
【17】R. Lidl and H. Niederreiter. Finite Fields, volume 20 of Encyclopedia of athematics and its Applications. Addison-Wesley, Reading, Massachusetts, 1983.
【18】S. B. Mohan and B. S. Adiga. Fast Algorithms for Implementing RSA Public Key Cryptosystem. Electronics Letters, 21(17):761, 1985.
【19】A. J. Menezes, P. C. van Oorschot, and S. A. Vanstone. Handbook of Applied Cryptography. CRC Press, 1997.
【20】Eun Jeong Lee, Duk Soo Kim, and Pil Joong Lee. Speed-up of Fpm Arithmetic for Elliptic Curve Cryptosystems. In Proceedings of ICICS '98, Berlin, 1998. Springer Lecture Notes in Computer Science.
【21】B．施奈尔著，吴世忠、祝世雄等译，应用密码学p177－178，机械工业出版社，2002.3
【22】A Certicom Whitepaper，The Elliptic Curve Cryptosystem，Published: April 1997，
Updated: July 2000