椭圆曲线密码体制中若干问题的研究
|
摘要
本文主要研究了椭圆曲线密码体制中几个最重要的算法问题.首先研究素域GF(p)上的三种类型的大整数模乘算法,对其中的Montgomery模乘算法的实现算法CIOS算法进行改进,提出了基于无符号滑动窗口CIOS算法,并给出算法分析,证明该算法的运算效率较高.针对椭圆曲线标量乘法的快速算法中自然数k的表示问题,提出基于半点-多基表示(PH-MBR)的标量乘法快速算法,与已有的算法进行比较,证明本方法的优越性.同时给出Koblitz曲线密码中倍点运算的一种改进算法.之后,基于椭圆曲线及其挠曲线,构造出有限域GF(q)上一类伪随机性很强的交错序列,对其0-1平衡性,周期性,线性复杂度进行分析,证明了该序列的较好实用性.研究和分析椭圆曲线有限群阶#E(F_q)的计算的两种重要算法:SEA算法和Satoh算法.另外,独立于本文的主要内容,我们把应用勒让德小波求非线性微积分方程和常微分方程数值解方面的一些研究放在文章的最后.
Researches on some problems in elliptic curve cryptographyElliptic curves were first applied to cryptosystem by Koblitz and Miller independently in 1985, which have been greatly used to encryption and decryption, Key changing, digital signatures and integer factorization etc in recent years. Elliptic Curve Cryptography(ECC) systems are based on discrete logarithm problem which is produced by Abel Group that consists of points on some elliptic curve. Most researches of mathematicians and cryptanalysts think that discrete logarithm problems of elliptic curve are more difficult than those of finite field. Experiments show that ECC algorithm has a faster speed, allows shorter key lengths, requires fewer computational resources for implementation than other traditional public-key algorithms such as RSA in the same safety property. While the computational speed of ECC is much lower than that of symmetry cryptography, and this affects its application in a certain extent. So how to improve the computational efficiency of ECC becomes a hot problem in elliptic curve cryptology.
Modular multiplication of long integers or polynomials is a fundamental operation for ECC in finite field GF(q). While q is prime number p, we need integer modular multiplication x×y mod p; While q = p~m, we need polynomial modular multiplication f(x)×h(x) mod f(x). The computation of modular n or modular f(x) wasting more time than multiplication is the key to improve efficiency of modular multiplication.
Scalar multiplication computation is the Most important in ECC of all kinds of computation, and the computational efficiency influence the whole implementation efficiency of ECC. So the research of fast computation of scalar multiplication is a hot-spot of ECC all the time.
Constructing pseudo-random sequences is an important problem in cryptogramresearch. In public-key cryptosystem, random numbers are a little short random sequences, and used to digital signatures, message authentication, encryption algorithm, identity authentication and large numbers of cryptology protocol. The character of pseudo-random number generator plays an important role in security of those systems.
Point counting problem is a pure mathematical problem. It is a fundamental question not only in selecting random curve to construct ECC, but also in the area of cryptography such as primality proof and elliptic curve decomposition. Consequently, it is of great value in modern cryptography to solve this problem.
In this dissertation we get some most significant problems in ECC to study and analyze. The main contributions are as follows:
·Study several recently widely used modular multiplication algorithms in prime field GF(p) based on addition, estimating quotient and Montgomery algorithm. Then present a new algorithm based on CIOS which is one of implementation algorithms of Montgomery, analyzing the improved algorithm. Here we mostly make use of the USW_(2,h) algorithm to coding one of the multipliers in the multiplication. Then we can compute the MonPro(α, b, r, n). The analysis show that the multiplication times in new algorithm reduce from 2s~2 + s to 3hs, and the temporary memory units only increased 3.
·Study the scalar multiplication on elliptic curve. We first summarize the expression method of the scalar k such as binary system method, windows method, DBNS and SDBNS etc, then we get a new fast method for scalar multiplication based on PH-MBR. last we produce an improved method on computing of multiplying points on Koblitz curve cryptography. A half point multi-based present of integer k is called when it is presented asFrom the analysis we can conclude that the inverse computing times are reduced by 23% when compared to algorithm in paper[57], 12% to that in paper[59]. The square times are reduced by 31% than that in paper[57], 10% in[59]. The multiplication times are reduced by 15% than the other three kinds of algorithm.
·A kind of binary sequences from an elliptic curve and its twisted curves over a field F_q. Studying of the period, hamming weight and the linear complexity of the sequence shows that the sequence are a kind of good pseudo random sequences.
Theorem 0.1 the lengths of interleaved sequence S and R are both 4kq, and
(1) hamming weight of S is W_H(S) = kp~(k-1)(2p - 1);
(2) hamming weight of R is W_H(R) = kp~(k-1)(2p - 1) - k;
here q = p~k, p is a prime number and p > 3.
Theorem 0.2 When the interleaved sequence S or R is looked as periodic sequence S~∞or R~∞with the period S or R, then
(1) the period of S~∞is per{S~∞) = 4kq;
(2) the period of R~∞is per(R~∞) = 4kq.
Theorem 0.3 if 2 is original unit of F_q, then
(1) the linear complexity of S~∞is L(S~∞)∈{4k + s(q - 1), s = 1,2,…, 4k};
(2) the linear complexity of R~∞is L(R~∞)≥3(p - 1).
From these theorems we can get the conclusion that the interleaved sequence we construct has a better kind of pseudo random character.
·Introduce the new trends of algorithms in computing the order of elliptic curves at present, SEA and Satoh algorithm. An improvement project is brought forward.
·Making use of Legendre wavelet expression, we get a new numerical method to solve a kind of nonlinear differential integral equation and a kind of ODE. Examples show that this method is effective.
Researches on some problems in elliptic curve cryptographyElliptic curves were first applied to cryptosystem by Koblitz and Miller independently in 1985, which have been greatly used to encryption and decryption, Key changing, digital signatures and integer factorization etc in recent years. Elliptic Curve Cryptography(ECC) systems are based on discrete logarithm problem which is produced by Abel Group that consists of points on some elliptic curve. Most researches of mathematicians and cryptanalysts think that discrete logarithm problems of elliptic curve are more difficult than those of finite field. Experiments show that ECC algorithm has a faster speed, allows shorter key lengths, requires fewer computational resources for implementation than other traditional public-key algorithms such as RSA in the same safety property. While the computational speed of ECC is much lower than that of symmetry cryptography, and this affects its application in a certain extent. So how to improve the computational efficiency of ECC becomes a hot problem in elliptic curve cryptology.
Modular multiplication of long integers or polynomials is a fundamental operation for ECC in finite field GF(q). While q is prime number p, we need integer modular multiplication x×y mod p; While q = p~m, we need polynomial modular multiplication f(x)×h(x) mod f(x). The computation of modular n or modular f(x) wasting more time than multiplication is the key to improve efficiency of modular multiplication.
Scalar multiplication computation is the Most important in ECC of all kinds of computation, and the computational efficiency influence the whole implementation efficiency of ECC. So the research of fast computation of scalar multiplication is a hot-spot of ECC all the time.
Constructing pseudo-random sequences is an important problem in cryptogramresearch. In public-key cryptosystem, random numbers are a little short random sequences, and used to digital signatures, message authentication, encryption algorithm, identity authentication and large numbers of cryptology protocol. The character of pseudo-random number generator plays an important role in security of those systems.
Point counting problem is a pure mathematical problem. It is a fundamental question not only in selecting random curve to construct ECC, but also in the area of cryptography such as primality proof and elliptic curve decomposition. Consequently, it is of great value in modern cryptography to solve this problem.
In this dissertation we get some most significant problems in ECC to study and analyze. The main contributions are as follows:
·Study several recently widely used modular multiplication algorithms in prime field GF(p) based on addition, estimating quotient and Montgomery algorithm. Then present a new algorithm based on CIOS which is one of implementation algorithms of Montgomery, analyzing the improved algorithm. Here we mostly make use of the USW_(2,h) algorithm to coding one of the multipliers in the multiplication. Then we can compute the MonPro(α, b, r, n). The analysis show that the multiplication times in new algorithm reduce from 2s~2 + s to 3hs, and the temporary memory units only increased 3.
·Study the scalar multiplication on elliptic curve. We first summarize the expression method of the scalar k such as binary system method, windows method, DBNS and SDBNS etc, then we get a new fast method for scalar multiplication based on PH-MBR. last we produce an improved method on computing of multiplying points on Koblitz curve cryptography. A half point multi-based present of integer k is called when it is presented asFrom the analysis we can conclude that the inverse computing times are reduced by 23% when compared to algorithm in paper[57], 12% to that in paper[59]. The square times are reduced by 31% than that in paper[57], 10% in[59]. The multiplication times are reduced by 15% than the other three kinds of algorithm.
·A kind of binary sequences from an elliptic curve and its twisted curves over a field F_q. Studying of the period, hamming weight and the linear complexity of the sequence shows that the sequence are a kind of good pseudo random sequences.
Theorem 0.1 the lengths of interleaved sequence S and R are both 4kq, and
(1) hamming weight of S is W_H(S) = kp~(k-1)(2p - 1);
(2) hamming weight of R is W_H(R) = kp~(k-1)(2p - 1) - k;
here q = p~k, p is a prime number and p > 3.
Theorem 0.2 When the interleaved sequence S or R is looked as periodic sequence S~∞or R~∞with the period S or R, then
(1) the period of S~∞is per{S~∞) = 4kq;
(2) the period of R~∞is per(R~∞) = 4kq.
Theorem 0.3 if 2 is original unit of F_q, then
(1) the linear complexity of S~∞is L(S~∞)∈{4k + s(q - 1), s = 1,2,…, 4k};
(2) the linear complexity of R~∞is L(R~∞)≥3(p - 1).
From these theorems we can get the conclusion that the interleaved sequence we construct has a better kind of pseudo random character.
·Introduce the new trends of algorithms in computing the order of elliptic curves at present, SEA and Satoh algorithm. An improvement project is brought forward.
·Making use of Legendre wavelet expression, we get a new numerical method to solve a kind of nonlinear differential integral equation and a kind of ODE. Examples show that this method is effective.
引文
[1] Menezes A..Okamoto,T. and Vanstones S. Reducing elliptic curve logarithms to logarithms in a finite field[J]. IEEE Transactions on information theory, Vol.17-39,1993, 5: 1639-1646.
[2] 裴定一，祝跃飞．算法数论[M]．北京：科学出版社，2002：114-133.
[3] 胡磊，冯登围，文铁华．一类Koblitz椭网曲线的快速点乘[J]．软件学报，2003，14(11)：1907-1910．
[4] J. Hoffstein, J. Pipher and J. H. Silverman. NTRU: A ring-based pulic key cryptosystem, ANTS IIIM[C], LNCS 1423, Springer-Verlag, 1998: 267-288.
[5] A. K. Lenstra and E. R. Verheul. The XTR public key system. Advances in Cryptography-CRYPTO'2000[C], LNCS 1880, Springer-Verlag, 2000: 1-19.
[6] David W. Ash, Ina F. Blake, Scott A. Vnastone. Low complexity nomral bases[J]. Discrete Applied Mathematics, 1989(25): 191-210.
[7] A survey of elliptic curve cryptosystems, part 1: Introductory. NASA Advanced supercomputing(NAS) Division-Research Branch(INR), Information Sciences & Technology Directorate NASA Ames Research Center[R], Moffett Field, CA 94043 NAS-03-12. August 2003.
[8] R.Lidl and H.Niederreiter. Encyclopedia of mathematics and its applications[M]. Cambridge: Cambridge University Press, 1997.
[9] C.Karlof and D.Wagner. Hidden markov model cryptanalysis. CHES'2003[C], LNCS 2779. Springer-Verlag, 2003.
[10] Elisabeth Oswald. Markov model side-channel analysis. Technical report[J/OL]. http://www.iaik.tu-graz.ac.at/aboutus/people/oswald/papers/.
[11] O.H(?)ggstr(?)m. Finite Markov chains and algorithmic applications[M]. Cambridge University Press, 2002.
[12] Olivier Semay. Efficiency analysis of window methods using Markov chains[C]. Diplomarbeit, Summer 2004.
[13] STANDS FOR EFFICIENT CRYPTOGRAPHY. SEC1: Elliptic curve cryptography, Certicom research contact: secg-talk@lists.certicom.com. [2000-09-20], Version 1.0.
[14] STANDS FOR EFFICIENT CRYPTOGRAPHY. SEC2:Recommended elliptic curve domain parameters, Certicom research contact: secg-talk@lists.certicom.com. [2000-09-20], Version 1.0.
[15] 朱天平．近世代数[M]．北京：科学出版社，2001．
[16] Knuth D E. The Art of Computer Programming. Seminumerical Algorithms(2) [M]. Reading MA: Addison-Wesley, 1981.
[17] Barrett P. Implementing the Rivest, Shamir and Adleman Public-key Encryption Algorithm on a Standard Digital Signal Processor[C]// Proc. of Advances in Cryptology-CRYPTO' 86. Springer-Verlag, 1987, 263: 311-323.
[18] Dhem J F. Design of an Efficient Public-key Cryptographic Library for RISC-based Smart Cards[D]. Universite Catholique de Louvain, 1998-05.
[19] Blakley G R. A Computer Algorithm for Calculating the Product AB Modular M[J]. IEEE Trans, on Computers, 1983, 32(5): 497-500.
[20] Chiou C W, Yang T C. Iterative Modular Multiplication Algorithm Without Magnitude Comparison [J]. Electronic Letter, 1994, 30(24): 2017-2018.
[21] 丁宏，郭艳华．快速大数模乘算法及其应用[J].小型微型计算机系统，2003，24(7)：1367-1370．
[22] Phillips B J, Burgess N. Implementing 1024-bits RSA exponentiation on a 32-bits processor core[J]. IEEE International Conference on Application Specific Systems, Architecture, and Processors(ASAP' 00).
[23] Chen C Y, Liu T C. A Fast Modular Multiplication Method Based on the Lemple-Ziv Binary Tree[J]. Computer Communications, 1999, 22(9): 871-874.
[24] P.L.Montgomery. Modular multiplication without trial division[J]. Mathematies of Computation, 1985, 44(170): 519-521.
[25] Kaya Koc C, Acar T and Kaliski BSJr. Analyzing and comparing Montgomery multiplication algorithms. IEEE Micro, 1996, 16(3): 26-33.
[26] D. J. Bernstein. Detecting Perefet Powers in Essentially Linear Time and Other Studies in Computational Number Theory[D]. Berkeley: Univ. of California, 1995.
[27] A. Skavantzos and M. Abdallah. Implementation issues of the two-level residue nmuber system with pairs of conjugate moduli[C]. IEEE Transactions on Singal Processing, 1999, 47(3): 826-838.
[28] N. Burgess. Scaling an RNS number using the core function[C]. Proc. 16th IEEE Symposium on Computer Arithmetic-ARITH'03, 2003, 6: 262-269.
[29] B.S.Kaliski. The Montgomery invers and its applications [J]. IEEE Transactios on Computers, 1995, 44(8): 1064-1065, .
[30] E. Savas, C. K. Koc. The Montgomery Modular Inverse-Revisited[J]. IEEE Transactions on ComPuters, 2000, 49(7).
[31] C. McIvor, M. McLoon, J. V. McCanny. Improved Montgomery modular inverse algorithm[J]. IEEE Electronics Letters, 2004, 40(18): 1110-1111.
[32] C. K. Koc, T. Acar. Montgomery multiplication in GF(2~k)[J]. Designs, Codes and Cryptography, 1998, 14: 57-69.
[33] 张焕围等译，D．Hankerson et al.著．椭圆曲线密码学导论[M]．北京：电子工业出版社．2005．
[34] C. K. Koc. High-Speed RSA Implementation. RSA Labs Technical Report TR-201 [R]. RSA Labs, 1994.
[35] 张宝华．椭圆曲线公钥密码体制中标量乘法运算快速算法的研究[D]．扬州：扬州大学计算机学院，2004．
[36] D.M.Gordon. A survey of fast exponentiation methods[J]. Journal of algorithms, 1998, 27: 129-146,.
[37] N.Smart. Eclliptic curve cryptosystems over small fields of odd characteristic[J]. Journal of cryptology, 1999, 12: 141-151.
[38] A.Avizienis. Signed-digit number representation for fast parallel arithmetic[J]. IRE Transactions on electronic computers, 1961, 9:389-400.
[39] Dimitrov, Jullien and Miller. Theory and applications for a double-base number system[J]. IEEE, Transactions on compuers, 1098-1106.
[40] B.M.M. de-Weger. Algorithms for diophantine equations[C]. CWI Tracts-Amsterdam, 1989, 65.
[41] G.Hardy. Ramanujan[M]. Cambridge: Cambridge Univ. Press, 1940.
[42] Hellman M. E. The mathematies of Public-key cruptography[J]. Scientific Ameriena, 1979, 7, 16(7): 32-39.
[43] Darrel Hankerson, Junio Lopez, Alrfed Menezes. Sotfware implementation of elliptic curve cryptography over binary fields[C]. Proceedings of the Second International Workshop on Cryptographic Hardware and Embedded Systems, 2000: 1-24.
[44] J.Lopez, R.Dahab. Improved algorithm for elliptic curve arithmetic over GF(2~n)[C]. Selected Areas in Cyrptography-SAC' 98 LCNS 1556, 1999: 201-212.
[45] J.Solinas. Efficient arithmetic on Koblitz curves[J]. Designs, Codes, and Cyrptography, 2000: 195-249.
[46] Koblitz N. Elliptic Curve Cryptosystems[J]. Mathematics of computation, 1987, 48(177): 203-209.
[47] Guajardjo J, Paar C. Efficient algorithms for elliptic curve cryptosystems[C]. Advances in Cryptology, Proceedings of Eurocrypt'97. Springer-Verlag, 1997: 342-356.
[48] 李湛．一种改进的椭圆曲线密码实现算法[J]．电子科技，2004，7：31-33.
[49] 张静，辛小龙．椭圆曲线密码的快速算法[J]．纯粹数学与应用数学，2008，24(1)：133-135．
[50] J. Lopez, R. Dahab. Fast multiplication on elliptic curves over GF(2~m) without precomputation [J]. Cryptographic Hardware and Embedded System, Lecture notes in computer science, 1999, 1717: 316-327.
[51] 白国强．椭圆曲线密码及其算法研究[D].西安：西安电子科技大学，2000，10．
[52] Menezes A., van Oorschot P., and Vanstone S. Handbook of Applied Cryptography[M]. Florida: CRC Press, 1996.
[53] Blake I., Seroussi G., Smart N. Elliptic Curves in Cryptography[M]. Cambridge: Cambridge University Press, 1999.
[54] Jerome A.Solinas, Efficient arithmetic on Koblitz curves[J]. Designs codes and cryptography, 2000: 125-179.
[55] Dimtrov V S, Imbert L, Mishra P K. Fast elliptic curve point multiplication using double-base chain[J/OL].(2005-06-05) http://eprint.iacr.org/2005/069.
[56] Mishra P K, Dimitrov V. Efficient quintuple formulas for elliptic curves and efficient scalar multiplication using multibass number representation[J/OL].(2007-04-01).http://eprint.iacr.org/2007/040.
[57] Knudsen E W. Elliptic scalar multiplication using point halving[C]//pro.of ASI-ACRYPT'99. [S.1.]: Springer-Verlag, 1999: 135-149.
[58] Wong K W, Lee E C W. Fast elliptic scalar multiplication using new couble-base chain and pointi halving[J/OL].(2006-12-01). http://eprint.iacr.org/2006/124.
[59] Fang K, Hankerson D, Lopez J, et al. Field inversion and point halving revisited[J]. IEEE Transactions on Computers, 2004, 53(8): 1047-1059.
[60] 陈辉，鲍皖苏．基于半点运算与多基表示的椭圆曲线标量乘法[J]．计算机工程，2008，34(15)：153-155．
[61] 魏仕民．流密码及其复杂度分析[D]．西安：西安电子科技大学，2001．
[62] 陈智雄．椭圆曲线与伪随机序列的构造[D]．西安：西安电子科技大学，2001．
[63] G.Frey, M.Müller, H.Rück. The Tate pairing and the discrete logarithm applied to elliptic curve cryptosystems[J]. IEEE Trans, on Information Theory, 1999, 45: 1717-1719.
[64] A.J.Menezes, T.Okamoto, S.A.Vanstone. Reducing elliptic curve logarithms to logarithms in a finite field [J]. IEEE Trans. Inform. Theory, 1993, 39(5): 1639-1646.
[65] G.Gong. Theory and applications of q-ary interleaved sequences [J]. IEEE Trans, on Information Theory, 1995, 41(2): 400-411.
[66] G.Gong, T.Berson, D.Stinson. Elliptic curve pseudorandom sequence generator[R/OL]. 1998, CORR1998-53,http://www.cacr.math.uwaterloo.ca.
[67] G.Gong, C.Lam. Linear recursive sequences over elliptic curves[C]. Proceedings of Sequences and Their Applications-SETA'01,DMTCS Series, Berlin: Spring-Verlag, 2001: 182-196.
[68] C.Y.Lam, G.Gong, Randomness of elliptic curve sequences[R/OL]. 2002, CORR2002-18,http://www.cacr.math.uwaterloo.ca.
[69] S.Q.Jiang, Z.D.Dai, G.Gong. On interleaved sequences over finite fields[J]. Discrete Mathematics, 2002, 252: 161-178.
[70] H.Baier, Efficient algrithms for generating elliptic curves over finite fields suitable for use in cryptography[D]. Darmstadt University of Technology, 2002. Available from http://www.cde.informatik.tu-darmstadt.de/- hbaier/
[71] H.Baier, A fast Java implementation of a provably secure pseudo random bit generator based on the elliptic curve [C]. Discrete Logarithm Problem. Conference on Applied Cryptography and Network Security, Huangshan, China, ISSN 1009-8054, 2004: 94-105.
[72] R.Crandall, C.Pomerance. Prime Numbers[M]. A computational perspective. NewYork: Springer, 2001.
[73] A.Enge. Elliptic curves and their applications to cryptography: an introduction [M]. Dordrecht: Kluwer Academic Publishers, 1999.
[74] P.S.L.M.Barreto, H.Y.Kim, B.Lynn and M.Scott, Efficient Algorithms for Pairing-Based Cryptosystems. In: Advances in Cryptology-CRYPTO' 2002, NLCS 2442, 354-368, Springer-Verlag, 2002.
[75] H.Cohen, A Course in Computational Algebraic Number Theory, Springer-Verlag, 1993.
[76] R.Crandall and C.Pomerance, Prime Numbers. A Computational Perspective, Springer-Verlag, 2001.
[77] IEEE P1363,Standard Specifications for Public Key Cryptography,2000.
[78] A.O.L.Atkin and F.Morain, Elliptic curves and primality proving,Math.Comp.,Vol.61(1993),29-68.
[79] E.Bach, A note on square roots in finite fields, IEEE Transactions on Information Theory, 36(6)(1990), 1494-1498.
[80] A.O.L.Atkin, Probabilistic primaliyty testing, Summary by F.Morain, INRIA Res. Rep. 1779(1992), 159-163.
[81] D.Shanks, Five number-theoretic algorithms, In Proc. 2nd Manitoba Conf. Nu-mer. Math., Manitoba, Canada(1972), 51-70.
[82] S.Lindhurst, An analysis of Shanks's algorithm for computing square roots in finite fields, CRM Proceedings and Lecture Notes, vol. 19, 1999, 231-242.
[83] S.Müller, On the computation of square roots in finite fields, Designs, Codes and Cryptography, 31(2), 2004, 301-312
[84] R.Lidl and H.Niederreiter, Encyclopedia of mathematics and its applications volume 20: Finite Fields, Cambridge University Press, 1997.
[85] D.M.Gordon, A Survey of fast exponentiation methods, Journal of algorithms, 27(1998), 129-146.
[86] T.Itoh and S.Tsujii, A fast algorithm for computing multiplicative inverses in GF(2~m) using normal bases, Information and Computation 78(1998) 171-177.
[87] Joachim von zur Gathen, Michael Nocker, Computing special powers in finite fields[J]. Math.Comput. 73(247), 2004, 1499-1523.
[88] 张亚娟，祝跃飞，黄秋生．有效的椭圆曲线求阶算法[J]．自然科学进展，2003，10，13(10)：1084-1088．
[89] 张雁，林英，郝林．椭圆曲线求阶算法的研究动态[J]．计算机工程，2004，12，30(23)：114-115．
[90] Izu T, Kogure J, Noro M, et al. Efficient Implementation of Schoofs Algorithmic]. In Proceedings of ASIACRYPT..8, of Lecture Notes in Computer Science, Springer, 1998, 1514:66-79
[91] Lercier R, et al. Counting the number of points on elliptic curves over finite fields: Strategies and performances [J]. Eurocrypto 1995, LNCS 2045: 79.
[92] Schoof R. Elliptic curves over finite fields and the computation of square roots mod p[J]. Math Comput, 1985, 44: 483.
[93] Fouquet M, Gaudry P, Harley R. An Extension of Satoh's Algorithm and Its Implementation [J]. J.Ramanujan Matn.Soc, 2000, 15: 281.
[94] Vercauteren F, et al. A memory efficient version of Satoh's algorithm[J]. Eurocrypto 2001, LNCS 2045: 1.
[95] Lehmann F, et al. Counting the number of point on elliptic curves over finite fields of characteristic greater then three [J]. Algorithmic Number Theory, 1994: 60.
[96] 祝跃飞，顾纯祥，斐定一．SEA算法的有效实现[J].软件学报,2002，13(6)：1154-1160．
[97] Lee H, Ubrhanuddin I. Point Counting Algorithms-A Survey. 2002. http://www-scf.usc.edu
[98] Y. Mahmoudi. Wavelet Galerkin method for numerical solution of nonlinear integral equation [J]. Appl. Math. Comp., 2005, 167: 1119-1129.
[99] S. Yalcinbas. Taylor polynomial solution of nonlinear Volterra-Fredholm integral equations [J]. Appl. Math. Comp., 2002, 127: 195-206.
[100] S. Yousefi, M. Razzaghi. Legendre wavelets methods for the nonlinear Volterra-Fredholm integral equations [J]. Math. Comp. in Simulat, 2005, 70: 1-8.
[101] (?)lo Lepik. Haar wavelet method for nonlinear integro-differential equations [J]. Appl. Math. Comp., 2006, 176: 324-333.
[102] M. Tavassoli Kajani, A. Hadi Venchen. Solving linear integro-differential equation with Legendre wavelets [J]. Internatial Journal of Comp. Math., 2004, 81 (6): 719-726.
[103] A. Avudainayagam, C. Vani. Wavelet-Galerkin method for integro-differential equations [J]. Appl. Numer. Math., 2000, 32: 247-254.
[104] M. Razzaghi, S.Yousefi. Legendre wavelets method for constrained optimal contral problems [J]. Math. Meth. Appl. Sci., 2002, 25: 529-539.
[105] A. Constantinides. Applied Numerical Methods with Personal Computers [M]. New York: McGraw-Hill, 1987.
[2] 裴定一，祝跃飞．算法数论[M]．北京：科学出版社，2002：114-133.
[3] 胡磊，冯登围，文铁华．一类Koblitz椭网曲线的快速点乘[J]．软件学报，2003，14(11)：1907-1910．
[4] J. Hoffstein, J. Pipher and J. H. Silverman. NTRU: A ring-based pulic key cryptosystem, ANTS IIIM[C], LNCS 1423, Springer-Verlag, 1998: 267-288.
[5] A. K. Lenstra and E. R. Verheul. The XTR public key system. Advances in Cryptography-CRYPTO'2000[C], LNCS 1880, Springer-Verlag, 2000: 1-19.
[6] David W. Ash, Ina F. Blake, Scott A. Vnastone. Low complexity nomral bases[J]. Discrete Applied Mathematics, 1989(25): 191-210.
[7] A survey of elliptic curve cryptosystems, part 1: Introductory. NASA Advanced supercomputing(NAS) Division-Research Branch(INR), Information Sciences & Technology Directorate NASA Ames Research Center[R], Moffett Field, CA 94043 NAS-03-12. August 2003.
[8] R.Lidl and H.Niederreiter. Encyclopedia of mathematics and its applications[M]. Cambridge: Cambridge University Press, 1997.
[9] C.Karlof and D.Wagner. Hidden markov model cryptanalysis. CHES'2003[C], LNCS 2779. Springer-Verlag, 2003.
[10] Elisabeth Oswald. Markov model side-channel analysis. Technical report[J/OL]. http://www.iaik.tu-graz.ac.at/aboutus/people/oswald/papers/.
[11] O.H(?)ggstr(?)m. Finite Markov chains and algorithmic applications[M]. Cambridge University Press, 2002.
[12] Olivier Semay. Efficiency analysis of window methods using Markov chains[C]. Diplomarbeit, Summer 2004.
[13] STANDS FOR EFFICIENT CRYPTOGRAPHY. SEC1: Elliptic curve cryptography, Certicom research contact: secg-talk@lists.certicom.com. [2000-09-20], Version 1.0.
[14] STANDS FOR EFFICIENT CRYPTOGRAPHY. SEC2:Recommended elliptic curve domain parameters, Certicom research contact: secg-talk@lists.certicom.com. [2000-09-20], Version 1.0.
[15] 朱天平．近世代数[M]．北京：科学出版社，2001．
[16] Knuth D E. The Art of Computer Programming. Seminumerical Algorithms(2) [M]. Reading MA: Addison-Wesley, 1981.
[17] Barrett P. Implementing the Rivest, Shamir and Adleman Public-key Encryption Algorithm on a Standard Digital Signal Processor[C]// Proc. of Advances in Cryptology-CRYPTO' 86. Springer-Verlag, 1987, 263: 311-323.
[18] Dhem J F. Design of an Efficient Public-key Cryptographic Library for RISC-based Smart Cards[D]. Universite Catholique de Louvain, 1998-05.
[19] Blakley G R. A Computer Algorithm for Calculating the Product AB Modular M[J]. IEEE Trans, on Computers, 1983, 32(5): 497-500.
[20] Chiou C W, Yang T C. Iterative Modular Multiplication Algorithm Without Magnitude Comparison [J]. Electronic Letter, 1994, 30(24): 2017-2018.
[21] 丁宏，郭艳华．快速大数模乘算法及其应用[J].小型微型计算机系统，2003，24(7)：1367-1370．
[22] Phillips B J, Burgess N. Implementing 1024-bits RSA exponentiation on a 32-bits processor core[J]. IEEE International Conference on Application Specific Systems, Architecture, and Processors(ASAP' 00).
[23] Chen C Y, Liu T C. A Fast Modular Multiplication Method Based on the Lemple-Ziv Binary Tree[J]. Computer Communications, 1999, 22(9): 871-874.
[24] P.L.Montgomery. Modular multiplication without trial division[J]. Mathematies of Computation, 1985, 44(170): 519-521.
[25] Kaya Koc C, Acar T and Kaliski BSJr. Analyzing and comparing Montgomery multiplication algorithms. IEEE Micro, 1996, 16(3): 26-33.
[26] D. J. Bernstein. Detecting Perefet Powers in Essentially Linear Time and Other Studies in Computational Number Theory[D]. Berkeley: Univ. of California, 1995.
[27] A. Skavantzos and M. Abdallah. Implementation issues of the two-level residue nmuber system with pairs of conjugate moduli[C]. IEEE Transactions on Singal Processing, 1999, 47(3): 826-838.
[28] N. Burgess. Scaling an RNS number using the core function[C]. Proc. 16th IEEE Symposium on Computer Arithmetic-ARITH'03, 2003, 6: 262-269.
[29] B.S.Kaliski. The Montgomery invers and its applications [J]. IEEE Transactios on Computers, 1995, 44(8): 1064-1065, .
[30] E. Savas, C. K. Koc. The Montgomery Modular Inverse-Revisited[J]. IEEE Transactions on ComPuters, 2000, 49(7).
[31] C. McIvor, M. McLoon, J. V. McCanny. Improved Montgomery modular inverse algorithm[J]. IEEE Electronics Letters, 2004, 40(18): 1110-1111.
[32] C. K. Koc, T. Acar. Montgomery multiplication in GF(2~k)[J]. Designs, Codes and Cryptography, 1998, 14: 57-69.
[33] 张焕围等译，D．Hankerson et al.著．椭圆曲线密码学导论[M]．北京：电子工业出版社．2005．
[34] C. K. Koc. High-Speed RSA Implementation. RSA Labs Technical Report TR-201 [R]. RSA Labs, 1994.
[35] 张宝华．椭圆曲线公钥密码体制中标量乘法运算快速算法的研究[D]．扬州：扬州大学计算机学院，2004．
[36] D.M.Gordon. A survey of fast exponentiation methods[J]. Journal of algorithms, 1998, 27: 129-146,.
[37] N.Smart. Eclliptic curve cryptosystems over small fields of odd characteristic[J]. Journal of cryptology, 1999, 12: 141-151.
[38] A.Avizienis. Signed-digit number representation for fast parallel arithmetic[J]. IRE Transactions on electronic computers, 1961, 9:389-400.
[39] Dimitrov, Jullien and Miller. Theory and applications for a double-base number system[J]. IEEE, Transactions on compuers, 1098-1106.
[40] B.M.M. de-Weger. Algorithms for diophantine equations[C]. CWI Tracts-Amsterdam, 1989, 65.
[41] G.Hardy. Ramanujan[M]. Cambridge: Cambridge Univ. Press, 1940.
[42] Hellman M. E. The mathematies of Public-key cruptography[J]. Scientific Ameriena, 1979, 7, 16(7): 32-39.
[43] Darrel Hankerson, Junio Lopez, Alrfed Menezes. Sotfware implementation of elliptic curve cryptography over binary fields[C]. Proceedings of the Second International Workshop on Cryptographic Hardware and Embedded Systems, 2000: 1-24.
[44] J.Lopez, R.Dahab. Improved algorithm for elliptic curve arithmetic over GF(2~n)[C]. Selected Areas in Cyrptography-SAC' 98 LCNS 1556, 1999: 201-212.
[45] J.Solinas. Efficient arithmetic on Koblitz curves[J]. Designs, Codes, and Cyrptography, 2000: 195-249.
[46] Koblitz N. Elliptic Curve Cryptosystems[J]. Mathematics of computation, 1987, 48(177): 203-209.
[47] Guajardjo J, Paar C. Efficient algorithms for elliptic curve cryptosystems[C]. Advances in Cryptology, Proceedings of Eurocrypt'97. Springer-Verlag, 1997: 342-356.
[48] 李湛．一种改进的椭圆曲线密码实现算法[J]．电子科技，2004，7：31-33.
[49] 张静，辛小龙．椭圆曲线密码的快速算法[J]．纯粹数学与应用数学，2008，24(1)：133-135．
[50] J. Lopez, R. Dahab. Fast multiplication on elliptic curves over GF(2~m) without precomputation [J]. Cryptographic Hardware and Embedded System, Lecture notes in computer science, 1999, 1717: 316-327.
[51] 白国强．椭圆曲线密码及其算法研究[D].西安：西安电子科技大学，2000，10．
[52] Menezes A., van Oorschot P., and Vanstone S. Handbook of Applied Cryptography[M]. Florida: CRC Press, 1996.
[53] Blake I., Seroussi G., Smart N. Elliptic Curves in Cryptography[M]. Cambridge: Cambridge University Press, 1999.
[54] Jerome A.Solinas, Efficient arithmetic on Koblitz curves[J]. Designs codes and cryptography, 2000: 125-179.
[55] Dimtrov V S, Imbert L, Mishra P K. Fast elliptic curve point multiplication using double-base chain[J/OL].(2005-06-05) http://eprint.iacr.org/2005/069.
[56] Mishra P K, Dimitrov V. Efficient quintuple formulas for elliptic curves and efficient scalar multiplication using multibass number representation[J/OL].(2007-04-01).http://eprint.iacr.org/2007/040.
[57] Knudsen E W. Elliptic scalar multiplication using point halving[C]//pro.of ASI-ACRYPT'99. [S.1.]: Springer-Verlag, 1999: 135-149.
[58] Wong K W, Lee E C W. Fast elliptic scalar multiplication using new couble-base chain and pointi halving[J/OL].(2006-12-01). http://eprint.iacr.org/2006/124.
[59] Fang K, Hankerson D, Lopez J, et al. Field inversion and point halving revisited[J]. IEEE Transactions on Computers, 2004, 53(8): 1047-1059.
[60] 陈辉，鲍皖苏．基于半点运算与多基表示的椭圆曲线标量乘法[J]．计算机工程，2008，34(15)：153-155．
[61] 魏仕民．流密码及其复杂度分析[D]．西安：西安电子科技大学，2001．
[62] 陈智雄．椭圆曲线与伪随机序列的构造[D]．西安：西安电子科技大学，2001．
[63] G.Frey, M.Müller, H.Rück. The Tate pairing and the discrete logarithm applied to elliptic curve cryptosystems[J]. IEEE Trans, on Information Theory, 1999, 45: 1717-1719.
[64] A.J.Menezes, T.Okamoto, S.A.Vanstone. Reducing elliptic curve logarithms to logarithms in a finite field [J]. IEEE Trans. Inform. Theory, 1993, 39(5): 1639-1646.
[65] G.Gong. Theory and applications of q-ary interleaved sequences [J]. IEEE Trans, on Information Theory, 1995, 41(2): 400-411.
[66] G.Gong, T.Berson, D.Stinson. Elliptic curve pseudorandom sequence generator[R/OL]. 1998, CORR1998-53,http://www.cacr.math.uwaterloo.ca.
[67] G.Gong, C.Lam. Linear recursive sequences over elliptic curves[C]. Proceedings of Sequences and Their Applications-SETA'01,DMTCS Series, Berlin: Spring-Verlag, 2001: 182-196.
[68] C.Y.Lam, G.Gong, Randomness of elliptic curve sequences[R/OL]. 2002, CORR2002-18,http://www.cacr.math.uwaterloo.ca.
[69] S.Q.Jiang, Z.D.Dai, G.Gong. On interleaved sequences over finite fields[J]. Discrete Mathematics, 2002, 252: 161-178.
[70] H.Baier, Efficient algrithms for generating elliptic curves over finite fields suitable for use in cryptography[D]. Darmstadt University of Technology, 2002. Available from http://www.cde.informatik.tu-darmstadt.de/- hbaier/
[71] H.Baier, A fast Java implementation of a provably secure pseudo random bit generator based on the elliptic curve [C]. Discrete Logarithm Problem. Conference on Applied Cryptography and Network Security, Huangshan, China, ISSN 1009-8054, 2004: 94-105.
[72] R.Crandall, C.Pomerance. Prime Numbers[M]. A computational perspective. NewYork: Springer, 2001.
[73] A.Enge. Elliptic curves and their applications to cryptography: an introduction [M]. Dordrecht: Kluwer Academic Publishers, 1999.
[74] P.S.L.M.Barreto, H.Y.Kim, B.Lynn and M.Scott, Efficient Algorithms for Pairing-Based Cryptosystems. In: Advances in Cryptology-CRYPTO' 2002, NLCS 2442, 354-368, Springer-Verlag, 2002.
[75] H.Cohen, A Course in Computational Algebraic Number Theory, Springer-Verlag, 1993.
[76] R.Crandall and C.Pomerance, Prime Numbers. A Computational Perspective, Springer-Verlag, 2001.
[77] IEEE P1363,Standard Specifications for Public Key Cryptography,2000.
[78] A.O.L.Atkin and F.Morain, Elliptic curves and primality proving,Math.Comp.,Vol.61(1993),29-68.
[79] E.Bach, A note on square roots in finite fields, IEEE Transactions on Information Theory, 36(6)(1990), 1494-1498.
[80] A.O.L.Atkin, Probabilistic primaliyty testing, Summary by F.Morain, INRIA Res. Rep. 1779(1992), 159-163.
[81] D.Shanks, Five number-theoretic algorithms, In Proc. 2nd Manitoba Conf. Nu-mer. Math., Manitoba, Canada(1972), 51-70.
[82] S.Lindhurst, An analysis of Shanks's algorithm for computing square roots in finite fields, CRM Proceedings and Lecture Notes, vol. 19, 1999, 231-242.
[83] S.Müller, On the computation of square roots in finite fields, Designs, Codes and Cryptography, 31(2), 2004, 301-312
[84] R.Lidl and H.Niederreiter, Encyclopedia of mathematics and its applications volume 20: Finite Fields, Cambridge University Press, 1997.
[85] D.M.Gordon, A Survey of fast exponentiation methods, Journal of algorithms, 27(1998), 129-146.
[86] T.Itoh and S.Tsujii, A fast algorithm for computing multiplicative inverses in GF(2~m) using normal bases, Information and Computation 78(1998) 171-177.
[87] Joachim von zur Gathen, Michael Nocker, Computing special powers in finite fields[J]. Math.Comput. 73(247), 2004, 1499-1523.
[88] 张亚娟，祝跃飞，黄秋生．有效的椭圆曲线求阶算法[J]．自然科学进展，2003，10，13(10)：1084-1088．
[89] 张雁，林英，郝林．椭圆曲线求阶算法的研究动态[J]．计算机工程，2004，12，30(23)：114-115．
[90] Izu T, Kogure J, Noro M, et al. Efficient Implementation of Schoofs Algorithmic]. In Proceedings of ASIACRYPT..8, of Lecture Notes in Computer Science, Springer, 1998, 1514:66-79
[91] Lercier R, et al. Counting the number of points on elliptic curves over finite fields: Strategies and performances [J]. Eurocrypto 1995, LNCS 2045: 79.
[92] Schoof R. Elliptic curves over finite fields and the computation of square roots mod p[J]. Math Comput, 1985, 44: 483.
[93] Fouquet M, Gaudry P, Harley R. An Extension of Satoh's Algorithm and Its Implementation [J]. J.Ramanujan Matn.Soc, 2000, 15: 281.
[94] Vercauteren F, et al. A memory efficient version of Satoh's algorithm[J]. Eurocrypto 2001, LNCS 2045: 1.
[95] Lehmann F, et al. Counting the number of point on elliptic curves over finite fields of characteristic greater then three [J]. Algorithmic Number Theory, 1994: 60.
[96] 祝跃飞，顾纯祥，斐定一．SEA算法的有效实现[J].软件学报,2002，13(6)：1154-1160．
[97] Lee H, Ubrhanuddin I. Point Counting Algorithms-A Survey. 2002. http://www-scf.usc.edu
[98] Y. Mahmoudi. Wavelet Galerkin method for numerical solution of nonlinear integral equation [J]. Appl. Math. Comp., 2005, 167: 1119-1129.
[99] S. Yalcinbas. Taylor polynomial solution of nonlinear Volterra-Fredholm integral equations [J]. Appl. Math. Comp., 2002, 127: 195-206.
[100] S. Yousefi, M. Razzaghi. Legendre wavelets methods for the nonlinear Volterra-Fredholm integral equations [J]. Math. Comp. in Simulat, 2005, 70: 1-8.
[101] (?)lo Lepik. Haar wavelet method for nonlinear integro-differential equations [J]. Appl. Math. Comp., 2006, 176: 324-333.
[102] M. Tavassoli Kajani, A. Hadi Venchen. Solving linear integro-differential equation with Legendre wavelets [J]. Internatial Journal of Comp. Math., 2004, 81 (6): 719-726.
[103] A. Avudainayagam, C. Vani. Wavelet-Galerkin method for integro-differential equations [J]. Appl. Numer. Math., 2000, 32: 247-254.
[104] M. Razzaghi, S.Yousefi. Legendre wavelets method for constrained optimal contral problems [J]. Math. Meth. Appl. Sci., 2002, 25: 529-539.
[105] A. Constantinides. Applied Numerical Methods with Personal Computers [M]. New York: McGraw-Hill, 1987.