椭圆曲线密码算法的研究
|
摘要
自从1985年Koblitz和Miller分别独立提出椭圆曲线密码体制(ECC)之后,这种公钥密码的优势逐渐被人们所认同。与另一著名的公钥密码RSA相比,椭圆曲线密码体制需要的密钥长度短,相同位长安全性更高,运算速度快,存储空间占用少和带宽要求低,它的这些优势使得业内人士普遍认为ECC将成为下一代最通用的公钥加密算法标准。在许多安全标准如IPsec、WAPI中,都包含了椭圆曲线密码体制的使用。因此,椭圆曲线密码具有广阔的应用情景。
标量乘是椭圆曲线运算中最耗时也是最基本的运算,目前标量乘的实现快速算法主要有二进制法、m-ary方法、NAF编码、窗口法以及滑动窗口法等,本文对这些算法进行深入的分析和研究,同时标量乘又是由点加和点倍运算组成的,在分析不同坐标系下点加点倍运算效率的基础上,依据并行运算的思想,优化混合坐标下点加点倍的运算序列,使得改进后的运算序列可以并行运算。本文通过对混合坐标Jacobian坐标下点加点倍运算序列的优化,使得运算的并行性大大提高,在使用双乘法器的情况下使点倍的运算时间由10个模乘周期变成5个模乘周期,点加的运算时间由11个模乘周期变成6个模乘周期,运算效率提高了接近2倍。另一方面,点加点倍运算最终可以转换为有限域上的模运算,由于模加模减相对于模乘而言,运算比较简单而且速度较快,因此我们主要考虑模乘运算。早在1985年,P. L. Montgomery提出Montgomery算法,其思想是在古典归约运算中用加法和移位运算代替高成本的除法。1996年,KOC对各种Montgomery算法的实现方法进行了详细的分析和总结,我们对这些算法进行分析发现两次大整数乘之间,必须先求退位因子,这在一定程度上限制了数据的并行运算,而一个算法的并行性的优劣,在密码芯片设计中是非常重要的,我们可以利用脉动加流水设计理念,通过增加一定的硬件资源,使之能够并行运算,使运算速度得到成倍的提高,基于这样的思想,我们给出了Montgomery模乘的改进算法,改进后的算法省去求退位因子的过程,使算法的并行性得到了很大的提高,经分析表明在双乘法器的情况下,运算效率提高了2倍。
Since Elliptic curve cryptography was proposed independently by Neal Koblitz and Victor Miller in 1985, the advantage of this Public key cryptosystem has been recognized. Compared to another famous public key algorithm based on RSA, ECC allows for shorter key length, has a higher safety property, faster speed, and requires fewer storage and bandwidth. Because of these advantages, many professionals think that elliptic curve crypto-system will be the most common standards of Public key cryptosystems. In recent years, ECC has received increased commercial acceptance as evidenced by its inclusion in standards by many accredited standards organizations such as IPsec and WAPI and so on.
Scalar multiplication is the basic operation in Elliptic curve cryptography. In this paper, the general algorithms (such as binary method, NAF, sliding window method and so on) for scalar multiplication are analyzed and discussed, On the other hand, scalar multiplication consists of point addition and point double, on the basis of analyzing the speed of point addition and point double under different coordinate systems, we optimize operations in point addition and point double computation in mixed Jacobian coordinate. After optimization, in case of two multipliers, point double which costs 10 modular multiplication time could be finished in 5 modular multiplication time and point addition which cost 11 modular multiplication time could be finished in 6 modular multiplication time. On the other hand, point addition and point double can be implemented by modular multiplication in finite field. As early as 1985, P. L. Montgomery proposed Montgomery algorithm, this method replaced time-consuming division by addition and shift operations. In 1996, KOC discusses and analyzes several Montgomery multiplication algorithms. We find that a factor must be computed before computing another two large integers'multiplication, which hampers the parallelism of computation. A parallel algorithm is very important in design of cryptosystem chips. A high-speed chip could be designed using a good parallelism of the algorithm, by increasing certain of hardware resources and using parallelism and pipeline technique. In this paper we give improved algorithm. The analysis of application suggested that the efficiency of computation is obvious improved.
标量乘是椭圆曲线运算中最耗时也是最基本的运算,目前标量乘的实现快速算法主要有二进制法、m-ary方法、NAF编码、窗口法以及滑动窗口法等,本文对这些算法进行深入的分析和研究,同时标量乘又是由点加和点倍运算组成的,在分析不同坐标系下点加点倍运算效率的基础上,依据并行运算的思想,优化混合坐标下点加点倍的运算序列,使得改进后的运算序列可以并行运算。本文通过对混合坐标Jacobian坐标下点加点倍运算序列的优化,使得运算的并行性大大提高,在使用双乘法器的情况下使点倍的运算时间由10个模乘周期变成5个模乘周期,点加的运算时间由11个模乘周期变成6个模乘周期,运算效率提高了接近2倍。另一方面,点加点倍运算最终可以转换为有限域上的模运算,由于模加模减相对于模乘而言,运算比较简单而且速度较快,因此我们主要考虑模乘运算。早在1985年,P. L. Montgomery提出Montgomery算法,其思想是在古典归约运算中用加法和移位运算代替高成本的除法。1996年,KOC对各种Montgomery算法的实现方法进行了详细的分析和总结,我们对这些算法进行分析发现两次大整数乘之间,必须先求退位因子,这在一定程度上限制了数据的并行运算,而一个算法的并行性的优劣,在密码芯片设计中是非常重要的,我们可以利用脉动加流水设计理念,通过增加一定的硬件资源,使之能够并行运算,使运算速度得到成倍的提高,基于这样的思想,我们给出了Montgomery模乘的改进算法,改进后的算法省去求退位因子的过程,使算法的并行性得到了很大的提高,经分析表明在双乘法器的情况下,运算效率提高了2倍。
Since Elliptic curve cryptography was proposed independently by Neal Koblitz and Victor Miller in 1985, the advantage of this Public key cryptosystem has been recognized. Compared to another famous public key algorithm based on RSA, ECC allows for shorter key length, has a higher safety property, faster speed, and requires fewer storage and bandwidth. Because of these advantages, many professionals think that elliptic curve crypto-system will be the most common standards of Public key cryptosystems. In recent years, ECC has received increased commercial acceptance as evidenced by its inclusion in standards by many accredited standards organizations such as IPsec and WAPI and so on.
Scalar multiplication is the basic operation in Elliptic curve cryptography. In this paper, the general algorithms (such as binary method, NAF, sliding window method and so on) for scalar multiplication are analyzed and discussed, On the other hand, scalar multiplication consists of point addition and point double, on the basis of analyzing the speed of point addition and point double under different coordinate systems, we optimize operations in point addition and point double computation in mixed Jacobian coordinate. After optimization, in case of two multipliers, point double which costs 10 modular multiplication time could be finished in 5 modular multiplication time and point addition which cost 11 modular multiplication time could be finished in 6 modular multiplication time. On the other hand, point addition and point double can be implemented by modular multiplication in finite field. As early as 1985, P. L. Montgomery proposed Montgomery algorithm, this method replaced time-consuming division by addition and shift operations. In 1996, KOC discusses and analyzes several Montgomery multiplication algorithms. We find that a factor must be computed before computing another two large integers'multiplication, which hampers the parallelism of computation. A parallel algorithm is very important in design of cryptosystem chips. A high-speed chip could be designed using a good parallelism of the algorithm, by increasing certain of hardware resources and using parallelism and pipeline technique. In this paper we give improved algorithm. The analysis of application suggested that the efficiency of computation is obvious improved.
引文
[1]W. Diffie and M. E. Hellman, New directions in cryptography, IEEE Transactions on Information Theory,22(1976),644-645.
[2]R. L. Rivest, A. Shamir, and L, Adleman. A method for obtaining digital signatures and public-key cryptosystems.Comm. of the ACM,21(1978),120-126.
[3]T. ELGamal, A Public-Key Cryptosystem and a Signature Based on Discrete Logarithms, IEEE Transactions on Information Theory,31(1985),469-472.
[4]Darrel Hankerson, Alfred Menezes and Scott Vanstone. Guide to Elliptic Curve Cryptography.2004.
[5]National Institute of Standards and Technology. Digital Signature Standard,2000. FIPS Publication 186-2.
[6]Mill. V. Use of Elliptic Curves in Cryptography, Advances in Cryptology Proceeding of CRYPTO'85, Springer-Verlag,1986,417-426.
[7]Neal Koblitz, Elliptic Curves Cryptosystems, Mathematics of Computation,1987, 177(48),203-209.
[8]J. P. Buhler, W. Lenstra, and C. Pomeranee. "Factoring integers with the number Field sieve". The Development of the Number Field Sieve. New York:Springer-Verlag,1993, pp.50-94.
[9]R. Gallant, R. Lambert, and S. Vanstone, Improving the parallelized Pollard lambda search on anomalous binary curves, Mathematics of computation, vol.69,2000, pp.1699-1705.
[10]R. Schoof. Elliptic Curves Over Finite Fields and the Computation of square Roots mod P[J]. Mathematics of Computation,1985,44(170):483-494.
[11]Aol Atkin. The number of points on an elliptic curve modulo a Prime[J]. Series of e-mail to the NMBRTHRY mailing list,1988.
[12]N. D. Elkies. Elliptic and modular curves over finite fields and related computational issues[M]. AMS/International Press,1998.
[13]潘承洞,潘承彪.初等数论(第二版).北京：北京大学出版社,2003.
[14]J. H. Silverman, The Arithmetic of Elliptic curves,Graduate Texts in Mathematics, vol.106, Springer-Verlag,1986.
[15]P. L. Montgomery. Modular multiplication without trial division[J]. Mathematics of Computation,1985,44(170):519-521.
[16]SR Dusse, BS Kaliski Jr. A Cryptographic Library for the Motorola DSP 56000[C].
[17]C. K. Koc, T-Acar, and B. S. Kaliski. Analyzing and comparing montgomery multiplication algorithms[J]. IEEE. Micro,1996,26-33.
[18]Kazuo Ohta, Dingyi Pei (Eds.), Efficient elliptic curve exponentiation using mixed coordinates, Advances in Cryptology-ASIACRYPT'98, Beijing, China, October 18-22,1998, Lecture Notes in Computer Science 1514 Springer 1998, ISBN 3-540-65109-8.
[19]B. S. Kaliski Jr. The Z80180 and big-number arithmetic Dr. Dobb's Journal, pages 50-58, September 1993.
[20]I. Blake, G. Seroussi, and N. Smart Elliptic Curves in Cryptography. Cambridge University Press,1999
[21]N. Kunihiro and H. Yamamoto. Window and extended window methods for Addition chain and addition-subtraction chain. IEICE Trans. Fundamentals, E81-A,1998.
[22]D. E. Knuth. The Art of Computer Programming:Seminumerical Algorithms, vol.2, Addison-Wesley,3th edition,1998.
[23]D. M. Gordon. A survey of fast exponentiation methods. J. algorithms,27, 129-146.
[24]S. Amo and ES. Wheeler signed digit representations of minimal Hamming weight. IEEE Transactions on Computers.1993,42(8):1007-1010.
[25]H. Cohen. Analysis of the sliding window powering algorithm. J. of Cryptology, Vol.18,no.1,pp.63-76,2005.
[26]M. Joy and S, M, Yen. The Montgomery powering ladder. CHES'2002, LNCS 2523, pp.291-302, Springer-Verlag,2003.
[27]K. Koyama and T. Tsuruoka.Speeding up elliptic curve cryptosystems using a signed binary window method. Advances in Cryptology-CRYPTO'1992, LNCS 740, pp,345-357, Springer-Verlag,1992.
[28]R. M. Avanzi. A Note on the Signed Sliding Window Integer Recoding and a Left-to-Right. Analogue.SAC'2004, LNCS 3357, pp.130-143, Springer-Verlag, 2005
[29]M. Joye and S. M. Yen. Optimal Left-to-Right binary signed-digit recoding. IEEE Trans, on Comp.49(7), pp,740-748,2000.
[30]M. Khabbazian, T. A. Gulliver, and V. K. Bhargava. A new minimal average weight representation for Left-to-Right point multiplication methods. IEEE Trans. on Comp.54 (11), pp,1454-1459,2005.
[31]W. Fischer, C. Giraud, E. W. Knudsen, J. P. Seifert. Parallel Scalar Multiplication on General Elliptic Curves Over F(p) Hedged against Non-Differential Side-Channel Attacks[R].IACR eprint archive, Technical Report No 2002/007.Wieland Fischer:Christophe Giraud,2002.
[32]C. K. Koc. Analysis of sliding window techniques for exponentiation [J]. Computers and Mathematics with Applications,1995,30 (10):17-24.
[33]Muir, J. A. and Stinson, D. R. New minimal weight representations for left-to-fight window methods[R].Technical Report CORR 2004-19,University of Water 2004.
[34]GW. Reitwiesner, Binary arithmetic, Advances in Computers,1960,1:231-308.
[35]M. Brown, D. Hankerson, J, Lopez, and A. Menezes, Software Implementation of the NIST Elliptic Curves Over Prime Fields.
[36]Gerardo Orlando and Christ of Para. A scalable gf (p) elliptic curve processor architecture for programmable hardware [J]. In CHES 2001, Springer-Verlag, 2001,348-363.
[37]JA. Solinas. Low-Weight Binary Representations for Pairs of Integers [R]. Technical Report CORR 2001-41, Center for Applied Cryptographic Research, University of Waterloo,Canada,2001.
[38]Haodong Wang, Bo Sheng, and Qun Li, TelosB Implementation of Elliptic Curve Cryptography over Primary Field WM-CS Technical Report(WM-CS-2005-12).
[39]J. Pollard, Monte Carlo methods for index computation (mod p), Mathematics of Computation, vol.32,1978, pp.106-110.
[40]A. Menezes, T. Okamoto, and S. Vanstone, Reducing elliptic curve logarithms to logarithms in a finite field, IEEE Transactions on Information Theory, vol.39. no.51993, pp.1639-1646.
[41]N. Smart, The discrete logarithm Problem on elliptic curves of trace one, Journal of Cryptology, vol.12, no.3,1999, pp.193-196.
[2]R. L. Rivest, A. Shamir, and L, Adleman. A method for obtaining digital signatures and public-key cryptosystems.Comm. of the ACM,21(1978),120-126.
[3]T. ELGamal, A Public-Key Cryptosystem and a Signature Based on Discrete Logarithms, IEEE Transactions on Information Theory,31(1985),469-472.
[4]Darrel Hankerson, Alfred Menezes and Scott Vanstone. Guide to Elliptic Curve Cryptography.2004.
[5]National Institute of Standards and Technology. Digital Signature Standard,2000. FIPS Publication 186-2.
[6]Mill. V. Use of Elliptic Curves in Cryptography, Advances in Cryptology Proceeding of CRYPTO'85, Springer-Verlag,1986,417-426.
[7]Neal Koblitz, Elliptic Curves Cryptosystems, Mathematics of Computation,1987, 177(48),203-209.
[8]J. P. Buhler, W. Lenstra, and C. Pomeranee. "Factoring integers with the number Field sieve". The Development of the Number Field Sieve. New York:Springer-Verlag,1993, pp.50-94.
[9]R. Gallant, R. Lambert, and S. Vanstone, Improving the parallelized Pollard lambda search on anomalous binary curves, Mathematics of computation, vol.69,2000, pp.1699-1705.
[10]R. Schoof. Elliptic Curves Over Finite Fields and the Computation of square Roots mod P[J]. Mathematics of Computation,1985,44(170):483-494.
[11]Aol Atkin. The number of points on an elliptic curve modulo a Prime[J]. Series of e-mail to the NMBRTHRY mailing list,1988.
[12]N. D. Elkies. Elliptic and modular curves over finite fields and related computational issues[M]. AMS/International Press,1998.
[13]潘承洞,潘承彪.初等数论(第二版).北京：北京大学出版社,2003.
[14]J. H. Silverman, The Arithmetic of Elliptic curves,Graduate Texts in Mathematics, vol.106, Springer-Verlag,1986.
[15]P. L. Montgomery. Modular multiplication without trial division[J]. Mathematics of Computation,1985,44(170):519-521.
[16]SR Dusse, BS Kaliski Jr. A Cryptographic Library for the Motorola DSP 56000[C].
[17]C. K. Koc, T-Acar, and B. S. Kaliski. Analyzing and comparing montgomery multiplication algorithms[J]. IEEE. Micro,1996,26-33.
[18]Kazuo Ohta, Dingyi Pei (Eds.), Efficient elliptic curve exponentiation using mixed coordinates, Advances in Cryptology-ASIACRYPT'98, Beijing, China, October 18-22,1998, Lecture Notes in Computer Science 1514 Springer 1998, ISBN 3-540-65109-8.
[19]B. S. Kaliski Jr. The Z80180 and big-number arithmetic Dr. Dobb's Journal, pages 50-58, September 1993.
[20]I. Blake, G. Seroussi, and N. Smart Elliptic Curves in Cryptography. Cambridge University Press,1999
[21]N. Kunihiro and H. Yamamoto. Window and extended window methods for Addition chain and addition-subtraction chain. IEICE Trans. Fundamentals, E81-A,1998.
[22]D. E. Knuth. The Art of Computer Programming:Seminumerical Algorithms, vol.2, Addison-Wesley,3th edition,1998.
[23]D. M. Gordon. A survey of fast exponentiation methods. J. algorithms,27, 129-146.
[24]S. Amo and ES. Wheeler signed digit representations of minimal Hamming weight. IEEE Transactions on Computers.1993,42(8):1007-1010.
[25]H. Cohen. Analysis of the sliding window powering algorithm. J. of Cryptology, Vol.18,no.1,pp.63-76,2005.
[26]M. Joy and S, M, Yen. The Montgomery powering ladder. CHES'2002, LNCS 2523, pp.291-302, Springer-Verlag,2003.
[27]K. Koyama and T. Tsuruoka.Speeding up elliptic curve cryptosystems using a signed binary window method. Advances in Cryptology-CRYPTO'1992, LNCS 740, pp,345-357, Springer-Verlag,1992.
[28]R. M. Avanzi. A Note on the Signed Sliding Window Integer Recoding and a Left-to-Right. Analogue.SAC'2004, LNCS 3357, pp.130-143, Springer-Verlag, 2005
[29]M. Joye and S. M. Yen. Optimal Left-to-Right binary signed-digit recoding. IEEE Trans, on Comp.49(7), pp,740-748,2000.
[30]M. Khabbazian, T. A. Gulliver, and V. K. Bhargava. A new minimal average weight representation for Left-to-Right point multiplication methods. IEEE Trans. on Comp.54 (11), pp,1454-1459,2005.
[31]W. Fischer, C. Giraud, E. W. Knudsen, J. P. Seifert. Parallel Scalar Multiplication on General Elliptic Curves Over F(p) Hedged against Non-Differential Side-Channel Attacks[R].IACR eprint archive, Technical Report No 2002/007.Wieland Fischer:Christophe Giraud,2002.
[32]C. K. Koc. Analysis of sliding window techniques for exponentiation [J]. Computers and Mathematics with Applications,1995,30 (10):17-24.
[33]Muir, J. A. and Stinson, D. R. New minimal weight representations for left-to-fight window methods[R].Technical Report CORR 2004-19,University of Water 2004.
[34]GW. Reitwiesner, Binary arithmetic, Advances in Computers,1960,1:231-308.
[35]M. Brown, D. Hankerson, J, Lopez, and A. Menezes, Software Implementation of the NIST Elliptic Curves Over Prime Fields.
[36]Gerardo Orlando and Christ of Para. A scalable gf (p) elliptic curve processor architecture for programmable hardware [J]. In CHES 2001, Springer-Verlag, 2001,348-363.
[37]JA. Solinas. Low-Weight Binary Representations for Pairs of Integers [R]. Technical Report CORR 2001-41, Center for Applied Cryptographic Research, University of Waterloo,Canada,2001.
[38]Haodong Wang, Bo Sheng, and Qun Li, TelosB Implementation of Elliptic Curve Cryptography over Primary Field WM-CS Technical Report(WM-CS-2005-12).
[39]J. Pollard, Monte Carlo methods for index computation (mod p), Mathematics of Computation, vol.32,1978, pp.106-110.
[40]A. Menezes, T. Okamoto, and S. Vanstone, Reducing elliptic curve logarithms to logarithms in a finite field, IEEE Transactions on Information Theory, vol.39. no.51993, pp.1639-1646.
[41]N. Smart, The discrete logarithm Problem on elliptic curves of trace one, Journal of Cryptology, vol.12, no.3,1999, pp.193-196.