椭圆曲线密码的快速算法及安全基础研究
|
摘要
标量乘和双线性对的计算以及离散对数问题是椭圆曲线密码的基础问题。标量乘和双线性对的计算速度决定了椭圆曲线密码的实现效率,离散对数问题决定了椭圆曲线密码的安全性。对标量乘和双线性对的研究有助于使椭圆曲线密码效率更高、应用更广。对椭圆曲线离散对数问题的跟踪研究可以及时评估椭圆曲线密码的安全强度,有助于降低密码系统被破译的风险。本文研究了椭圆曲线的标量乘、双线性对和离散对数等问题,主要工作如下:
1.二元域上椭圆曲线可以用仿射坐标、标准射影坐标、Jacobian射影坐标或L′opez-Dahab射影坐标表示。其中L′opez-Dahab射影坐标下的点加和倍点运算具有最快的速度,其次是Jacobian射影坐标。我们在L′opez-Dahab射影坐标下推导出了3P的一个快速计算公式。于是用双基链计算标量乘时,L′opez-Dahab射影坐标比Jacobian射影坐标快12%左右。
2.在2007年亚洲密码会议上,Avanzi等人针对Koblitz曲线提出了用复数双基链计算标量乘。但是该方法把标量表示成复数双基过程中使用了大量的复数除法。我们利用同构的方法减少了复数除法,从而加快了标量的有效表示算法。
3.在椭圆曲线签名方案中,对签名的验证需要计算多标量乘。在2009年的欧洲密码会议上,Doche等人提出了用双基链来计算多标量乘的方法。我们给出了计算多标量乘的多基链方法,理论分析表明:标量的有效表示长度降低了大约10%,从而提高了多标量乘的计算速度。
4.双线性对在密码学中有着广泛应用:基于身份的加密、三方Di?e Hellman协议等。实现这些方案的关键是快速计算双线性对。Miller首先给出了在Weierstrass曲线上计算双线性对的方法。2009年,Ar`ene等人给出了计算Edwards曲线上Tate双线性对的方法。但是目前绝大部分标准中的椭圆曲线都不能映射到Edwards曲线。而Smart指出IEEE,SECG标准中的部分椭圆曲线可以映射到Hessian曲线上。为此我们首先提出了在Hessian曲线上计算Tate双线性对的算法。分析表明:除了a4 = 0,a6 = b2的特殊Weierstrass曲线外,我们提出的算法在计算Tate双线性对的所有已知算法中是最快的。
5.针对二元域上的椭圆曲线,GHS方法把椭圆曲线离散对数问题归约为超椭圆曲线离散对数问题,而超椭圆曲线离散对数问题是可以在亚指数时间内解决。推广的GHS具有更强的攻击能力,它的思想是寻找一条新的同种曲线,使得它在GHS攻击下是脆弱的。针对ANSI X9.62标准中定义在有限域GF(2N)上的椭圆曲线,我们给出了另外一个寻找脆弱同种曲线的方法。
6.在推广的GHS攻击中需要计算同种映射。但是对于一般椭圆曲线,目前计算同种映射的时间复杂度是指数的。微软公司的研究员针对素数域上的椭圆曲线提出了一个多项式时间的算法来计算同种映射,只是该算法要求椭圆曲线的自同态环所在虚二次域的类数较小。由此可见,虚二次域的类数也是椭圆曲线密码中的一个重要问题。我们在推广的Riemann假设下,证明了Cohen-Sonn猜想:虚二次域Q(d~(1/2))的类数等于3当且仅当Onod=3且-d≡3 (mod 4)是一个素数。
Scalar multiplication, pairing computation and discrete logarithm problemare fundamental problems in elliptic curve cryptography. Scalar multiplicationand pairing computation are key to the efficiency of elliptic curve cryptosystemswhile discrete logarithm problem is key to the security of elliptic curve cryptosystems.Researches on scalar multiplication and pairing computation makecryptosystems more efficient and wider utilization. Track down investigations ondiscrete logarithm problem can estimate the security of cryptosystems in timewhich reduces the risk of being broken. In this thesis, we consider such problemsas scalar multiplication, pairing computation and discrete logarithm problem.
1. Elliptic curves over binary fields can be represented by affine coordinates,standard projective coordinates, Jacobian projective coordinates and Lop′ez-Dahab projective coordinates. Point addition and doubling are fastest inLop′ez-Dahab projective coordinates, and then in Jacobian projective coordinates.We propose efficient formulas to compute 3P in Lop′ez-Dahabprojective coordinates. This leads scalar multiplication using double basechain in Lop′ez-Dahab projective coordinates to be about 12% faster thanin Jacobian projective coordinates.
2. In Asiacrypt’07, Avanzi et.al. proposed complex double base chain tocompute scalar multiplication for Koblitz curves. However, their scalarrecoding algorithm needs a lot of divisions in complex field. We reduce thedivisions via isomorphism to speed up the scalar recoding algorithm.
3. In elliptic curve signature schemes, verifers have to compute multi-scalarmultiplication. Doche et.al. presented a method of using double base chainto compute multi-scalar multiplication in Eurocrypt’09. We give a wayto compute multi-scalar multiplication by multi-base chain. Theoreticalanalysis shows that the length of scalar recoding can be reduced about10% which speeds up the multi-scalar multiplication.
4. Pairings have many applications in a lot of cryptographic protocols suchas identity-based encryption, the tripartite Diffie Hellman protocols. Forimplementing such protocols, it is essential to have an efficient algorithmof pairing computation. Miller proposed the first algorithm for computingpairings on Weierstrass curves. In 2009, Ar`ene et.al. showed how tocompute the Tate pairing on Edwards curves. But elliptic curves in moststandards can’t be mapped to Edwards curves at present. However, Smartpointed out that some elliptic curves from IEEE, SECG standards can betransformed into Hessian curves. So we develop explicit formulas for computingTate pairings on Hessian curves originally. Analysis shows that ouralgorithm is fastest among all known algorithms for Tate pairing computationexcept for special Weierstrass curves with a4 = 0,a6 = b2.
5. For elliptic curves over binary fields, the GHS method reduces the ellipticcurve discrete logarithm problem to a discrete logarithm problem forhyperelliptic curves and the hyperelliptic curve discrete logarithm problemcan be solved within subexponential time. The extended GHS attack hasstronger power, and the idea is to find an isogenous curve which is vulnerableunder the GHS attack. For elliptic curves over finite fields GF(2N),we give an alternative algorithm to find such isogenous curves.
6. It is necessary to compute isogeny in the extended GHS attack. However,for general elliptic curves, the complexity of computing isogeny is exponential.Researcheres from Microsoft proposed a polynomial time algorithmto compute isogeny for elliptic curves over prime fields, only if the imaginequadratic field containing the endomorphism ring has small class number.Thus, the class number problem for imagine quadratic fields is an importantissue in cryptography. We prove the Sohen-Sonn conjecture assuming theextended Riemann hypothesis: the class number of an imagine quadraticfield is 3 if and only if Onod=3 and ?d≡3 (mod 4) is prime.
1.二元域上椭圆曲线可以用仿射坐标、标准射影坐标、Jacobian射影坐标或L′opez-Dahab射影坐标表示。其中L′opez-Dahab射影坐标下的点加和倍点运算具有最快的速度,其次是Jacobian射影坐标。我们在L′opez-Dahab射影坐标下推导出了3P的一个快速计算公式。于是用双基链计算标量乘时,L′opez-Dahab射影坐标比Jacobian射影坐标快12%左右。
2.在2007年亚洲密码会议上,Avanzi等人针对Koblitz曲线提出了用复数双基链计算标量乘。但是该方法把标量表示成复数双基过程中使用了大量的复数除法。我们利用同构的方法减少了复数除法,从而加快了标量的有效表示算法。
3.在椭圆曲线签名方案中,对签名的验证需要计算多标量乘。在2009年的欧洲密码会议上,Doche等人提出了用双基链来计算多标量乘的方法。我们给出了计算多标量乘的多基链方法,理论分析表明:标量的有效表示长度降低了大约10%,从而提高了多标量乘的计算速度。
4.双线性对在密码学中有着广泛应用:基于身份的加密、三方Di?e Hellman协议等。实现这些方案的关键是快速计算双线性对。Miller首先给出了在Weierstrass曲线上计算双线性对的方法。2009年,Ar`ene等人给出了计算Edwards曲线上Tate双线性对的方法。但是目前绝大部分标准中的椭圆曲线都不能映射到Edwards曲线。而Smart指出IEEE,SECG标准中的部分椭圆曲线可以映射到Hessian曲线上。为此我们首先提出了在Hessian曲线上计算Tate双线性对的算法。分析表明:除了a4 = 0,a6 = b2的特殊Weierstrass曲线外,我们提出的算法在计算Tate双线性对的所有已知算法中是最快的。
5.针对二元域上的椭圆曲线,GHS方法把椭圆曲线离散对数问题归约为超椭圆曲线离散对数问题,而超椭圆曲线离散对数问题是可以在亚指数时间内解决。推广的GHS具有更强的攻击能力,它的思想是寻找一条新的同种曲线,使得它在GHS攻击下是脆弱的。针对ANSI X9.62标准中定义在有限域GF(2N)上的椭圆曲线,我们给出了另外一个寻找脆弱同种曲线的方法。
6.在推广的GHS攻击中需要计算同种映射。但是对于一般椭圆曲线,目前计算同种映射的时间复杂度是指数的。微软公司的研究员针对素数域上的椭圆曲线提出了一个多项式时间的算法来计算同种映射,只是该算法要求椭圆曲线的自同态环所在虚二次域的类数较小。由此可见,虚二次域的类数也是椭圆曲线密码中的一个重要问题。我们在推广的Riemann假设下,证明了Cohen-Sonn猜想:虚二次域Q(d~(1/2))的类数等于3当且仅当Onod=3且-d≡3 (mod 4)是一个素数。
Scalar multiplication, pairing computation and discrete logarithm problemare fundamental problems in elliptic curve cryptography. Scalar multiplicationand pairing computation are key to the efficiency of elliptic curve cryptosystemswhile discrete logarithm problem is key to the security of elliptic curve cryptosystems.Researches on scalar multiplication and pairing computation makecryptosystems more efficient and wider utilization. Track down investigations ondiscrete logarithm problem can estimate the security of cryptosystems in timewhich reduces the risk of being broken. In this thesis, we consider such problemsas scalar multiplication, pairing computation and discrete logarithm problem.
1. Elliptic curves over binary fields can be represented by affine coordinates,standard projective coordinates, Jacobian projective coordinates and Lop′ez-Dahab projective coordinates. Point addition and doubling are fastest inLop′ez-Dahab projective coordinates, and then in Jacobian projective coordinates.We propose efficient formulas to compute 3P in Lop′ez-Dahabprojective coordinates. This leads scalar multiplication using double basechain in Lop′ez-Dahab projective coordinates to be about 12% faster thanin Jacobian projective coordinates.
2. In Asiacrypt’07, Avanzi et.al. proposed complex double base chain tocompute scalar multiplication for Koblitz curves. However, their scalarrecoding algorithm needs a lot of divisions in complex field. We reduce thedivisions via isomorphism to speed up the scalar recoding algorithm.
3. In elliptic curve signature schemes, verifers have to compute multi-scalarmultiplication. Doche et.al. presented a method of using double base chainto compute multi-scalar multiplication in Eurocrypt’09. We give a wayto compute multi-scalar multiplication by multi-base chain. Theoreticalanalysis shows that the length of scalar recoding can be reduced about10% which speeds up the multi-scalar multiplication.
4. Pairings have many applications in a lot of cryptographic protocols suchas identity-based encryption, the tripartite Diffie Hellman protocols. Forimplementing such protocols, it is essential to have an efficient algorithmof pairing computation. Miller proposed the first algorithm for computingpairings on Weierstrass curves. In 2009, Ar`ene et.al. showed how tocompute the Tate pairing on Edwards curves. But elliptic curves in moststandards can’t be mapped to Edwards curves at present. However, Smartpointed out that some elliptic curves from IEEE, SECG standards can betransformed into Hessian curves. So we develop explicit formulas for computingTate pairings on Hessian curves originally. Analysis shows that ouralgorithm is fastest among all known algorithms for Tate pairing computationexcept for special Weierstrass curves with a4 = 0,a6 = b2.
5. For elliptic curves over binary fields, the GHS method reduces the ellipticcurve discrete logarithm problem to a discrete logarithm problem forhyperelliptic curves and the hyperelliptic curve discrete logarithm problemcan be solved within subexponential time. The extended GHS attack hasstronger power, and the idea is to find an isogenous curve which is vulnerableunder the GHS attack. For elliptic curves over finite fields GF(2N),we give an alternative algorithm to find such isogenous curves.
6. It is necessary to compute isogeny in the extended GHS attack. However,for general elliptic curves, the complexity of computing isogeny is exponential.Researcheres from Microsoft proposed a polynomial time algorithmto compute isogeny for elliptic curves over prime fields, only if the imaginequadratic field containing the endomorphism ring has small class number.Thus, the class number problem for imagine quadratic fields is an importantissue in cryptography. We prove the Sohen-Sonn conjecture assuming theextended Riemann hypothesis: the class number of an imagine quadraticfield is 3 if and only if Onod=3 and ?d≡3 (mod 4) is prime.
引文
[1] L.Adleman, A Subexponential Algorithm for the Discrete Logarithm Problemwith Applications to Cryptography, In: Proc. 20th IEEE Found. Comp.Sci. Symp., 1979, pp.55-60.
[2] L.Adleman, J.Demarrais and M.Huang, A subexponential Algorithm for DiscreteLogarithm over the Rational Subgroup of the Jacobians of Large Genushyperelliptic Curves over Finite Fields, In: ANTS I, LNCS 877,Springer Verlag,1994, pp. 28-40.
[3] M. Agrawal, N. Kayal and N. Saxenag, Primes is in P, Annals of Math.,2004,160(2): 781-793.
[4] E.AlDaoud, R.Mahmod, M.Rushdan and A.Kilicman, A new addition formulafor elliptic curves over GF(2n), IEEE Trans. Comput., 2002, 51: 972-975.
[5] ANSI X9.62, Public Key Cryptography for the Financial Services Industry:The Elliptic Curve Digital Signature Algorithm (ECDSA), AmericanNational Standards Institute, 1999.
[6] ANSI X9.63, Public Key Cryptography for the Financial Services Industry- Key Agreement and Key Transport Using Elliptic Curve Cryptography,American Bankers Association, November 20, 2001.
[7] A.O.L. Atkin and F. Morain, Elliptic curves and primality proving, Math.Comp.,1993, 61(203): 29-68.
[8] R.Avanzi,V.Dimitrov, C.Doche and F.Sica, Extending Scalar MultiplicationUsing Double Bases, In: Advances in Cryptology-ASIACRYPT’06, LNCS4284, Springer-Verlag, 2006, pp.130-144.
[9] C. Ar`ene, T. Lange, M. Naehrig, and C. Ritzenthaler, Faster Computationof Tate Pairings, Cryptology ePrint Archive, Report 2009/155,http://eprint.iacr.org/2009/155.pdf
[10] E. Bach, Explicit bounds for primality testing and related problems, Math.Comp., 1990, 55: 355-380.
[11] E. Bach, J. Sorenson, Explicit bounds for primes in residue classes, Math.Comp., 1996, 65: 1717–1735.
[12] H.Baier, Efficient algorithms for generating elliptic curves over finite fieldssuitable for use in cryptography, Ph.D. Thesis, Dept. of Computer Science,Technical Univ. of Darmstadt, May 2002.
[13] R.Balasubramanian and N.Koblitz, The improbability that an elliptic curvehas subexponential discrete logarithm problem under the Menezes-Okamoto-Vanstone algorithm, J. Crypto., 1998, 11: 141-145.
[14] P. Barreto, H.Y. Kim, B. Lynn, M. Scott, Efficient algorithms for pairingbasedcryptosystems, In: Advances in Cryptology - Crypto’02, LNCS 2442,Springer-Verlag, 2002, pp. 354-368.
[15] P.S.L.M. Barreto, S. Galbraith, C.′Oh′Eigeartaigh, M. Scott, Effcient PairingComputation on Supersingular Abelian Varieties, In Designs, Codes andCryptography, 2007, 42(3): 239-271.
[16] Daniel J. Bernstein and Tanja Lange, Faster addition and doubling on ellipticcurves, In: Advances in Cryptology - ASIACRYPT’07, LNCS 4833,Springer-Verlag, 2007, pp. 29–50.
[17] Daniel J. Bernstein and Tanja Lange, Analysis and optimization of ellipticcurvesingle-scalar multiplication, In: Finite fields and applications, Contemp.Math. 461, American Mathematical Society ,2008, pp. 1-19.
[18] Daniel J. Bernstein and Tanja Lange, Inverted Edwards coordinates, In:AAECC-17, LNCS 4851, Springer-Verlag, 2007, pp. 20–27.
[19] V. Berth′e and L. Imbert, On converting numbers to the double base numbersystem, Advanced Signal Processing Algorithms, Architecture and ImplementationsXIV, Proc. SPIE, 5559, 2004, pp. 70–78.
[20] O. Billet and M. Joye, The Jacobi model of an elliptic curve and side-channelanalysis, In: AAECC-15, LNCS 2643, Springer-Verlag, 2003, pp. 34-42.
[21] I.F.Blake, G.Seroussi, N.P.Smart, Advances in Elliptic curve cryptography,Cambridge University Press, 2005, pp. 183-196.
[22] I.F.Blake, K. Murty, G. Xu, Refinements of Miller’s algorithm for computingWeil/Tate pairing, J. Algorithm, 2006, 58(2): 134 - 149.
[23] D. Boneh, The decision Diffie-Hellman problem, In: ANTS-3, LNCS 1423,Springer-Verlag, 1998, pp. 48–63.
[24] D. Boneh and M. Franklin, Identity based encryption from the Weil pairing,SIAM J. Comp., 2003, 32: 586–615.
[25] D.Boneh, H.Shacham, Group signatures with verifier-local revocation, In:Atluri, V., Pfitzmann, B., McDaniel, P. (eds.) ACM CCS 04, ACM Press2004, pp. 168-177.
[26] W. Bosma, J. Cannon, C. Playoust, The Magma algebra system. I. The userlanguage, J. Symbolic Comput., 1997, 24(3-4):235-265.
[27]′E.Brier and M.Joye, Fast point multiplication on elliptic curves throughisogenies. In: AAECC-15, LNCS 2643, Springer-Verlag, 2003, pp. 43-50.
[28] B. Br¨oker, D. Charles and K. Lauter, Evaluating large degree isogenies andapplications to pairing based cryptography, In: Pairing 2008, LNCS 5209,Springer-Verlag, 2008, pp.100-112.
[29] S. Chatterjee, P. Sarkar, R. Barua, Efficient computation of Tate pairingin projective coordinate over general characteristic fields, In: ICISC 2004,LNCS 3506, Springer-Verlag, 2005, pp. 168-181.
[30] Z. Cheng and M. Nistazakis, Implementing pairing-based cryptosystems,In: 3rd International Workshop on Wireless Security Technologies IWWST-2005, London, UK, April, 2005.
[31] David V. Chudnovsky and Gregory V. Chudnovsky, Sequences of numbersgenerated by addition in formal groups and new primality and factorizationtests, Adv. Appl. Math., 7(4):385–434, 1986.
[32] M. Ciet, K. Lauter, M. Joye, P.L. Montgomery, Trading inversions for multiplicationsin elliptic curve cryptography, Designs, Codes Cryptography,2006, 39 (2): 189-206.
[33] H.Cohen, G.Frey, R.Avanzi, C.Doche, T.Lange, K.Nguyen and F. Vercauteren,Handbook of Elliptic and Hyperelliptic Curve Cryptography.Taylor & Francis Group, LLC, 2006.
[34] H. Cohen and H. W. Lenstra, Jr., Primality Testing and Jacobi Sums, Math.Comp. , 1984, 42: 297-330.
[35] M.Coban, Primitive Elements in Finite Fields with Arbitrary Trace, SabanclUniversity Thesis, Spring-Verlag, 2003.
[36] H.Cohen, A.Miyaji and T. Ono, Efficient elliptic curve exponentiation usingmixed coordinates, In: Advance in Cryptology-Asiacrypt 1998, LNCS, vol.1514, Springer-Verlag, 1998, pp. 51-65.
[37] D. Coppersmith, Fast evaluation of logarithms in fields of characteristic two,IEEE Trans. Inf. Theory, 1984, 30: 587-594.
[38] Joseph Cohen and Jack Sonn, On the Ono invariants of imaginary quadraticfields, J. Number Theory, 2002, 95: 259-267.
[39] H. Cohen, A course in computational algebraic number theory, 3., corr.print. Graduate Texts in Mathematics 138, Springer-Verlag, 1996.
[40] H.Cohen, A.Miyaji and T.Ono, Efficient elliptic curve exponentiation, advancesin cryptology-Proceedings of ICICS’97, LNCS 1334, Springer-Verlag,1997, pp. 282-290.
[41] H.Cohen, A.Miyaji and T.Ono, Efficient elliptic curve exponentiation usingmixed coordinates, in: Advances in Cryptology-Asiacrypt 1998, LNCS 1514,Springer-Verlag, 1998, pp. 51-65.
[42] J.Coron, Resistance against differential power analysis for elliptic curve cryptosystems,CHES’99, LNCS 1717, Springer-Verlag, 1999,292-302.
[43] C. Costello, H. Hisil, C. Boyd, J.M.G. Nieto and K.K.H. Wong, Fasterpairings on special Weierstrass curves, Cryptology ePrint Archive, Report2009/243, http://eprint.iacr.org/2009/243.pdf
[44] M.Das, P. Sarkar, Pairing computation on twisted Edwards form ellipticcurves, In: Pairing 2008, LNCS 5209, Springer-Verlag, 2008, pp. 192-210.
[45] T.Denny, B.Dodson, A.K.Lenstra and M.S.Manasse, On the factorization ofRSA-120, in: Advances in Cryptology - Crypto’93, LNCS 773 , Springer-Verlag, 1994, pp.166-174.
[46] W.Diffie and M.E. Hellman, New directions in cryptography, IEEE Trans.Inf. Theory, 1976,22:644-654.
[47] V.S.Dimitorv,G A.Julliena and W.C.Miller, An algorithm for Modular Exponentiation,Inf. Proc. Lett., 1998,66 (3):155-159.
[48] VS.Dimitrov, GA.Jullien and W.C.Miller, Theory and applications of thedouble-base number system, IEEE Trans. comput., 1999,48(10):1098-1106.
[49] V.S.Dimitrov, L.Imbert, P.K.Mishra, Efficient and Secure Elliptic CurvePoint Multiplication Using Double-Base Chains, In: Proc. ASIACRYPT’05,LNCS 3788, Springer-Verlag, 2005, pp.624-643.
[50] V.S.Dimitrov, L.Imbert, P.K.Mishra, The Double Base Number System andIts Application to Elliptic Curve Cryptography, Math. Comp., 2008, 77:1075-1104.
[51] C. Doche, D. R.Kohel, F. Sica, Double-Base Number System for Multi-ScalarMultiplications, in: Advances in Cryptology - Eurocrypt 2009, Cologne,Germany, April 26-30.
[52] I.Duursma, H.S.Lee, Tate Pairing Implementation for Hyperelliptic Curvesy2 = xp ? x + d, In: Advances in Cryptology - Asiacrypt 2003, LNCS 2894,2003, pp. 111-123.
[53] I.Duursma,P.Gaudry, F.Morain, Speeding up the discrete log compuationon curves with automorphisms, Proc. Int. Conf. Theory App. Crypto. Inf.Secur., LNCS 1716, 1999, pp.103-121.
[54] Harold M. Edwards, A normal form for elliptic curves, Bull. Am. Math. Soc.,2007, 44: 393–422.
[55] K. Eisentr¨aer, K.Lauter, P.Montgomery, Improved Weil and Tate Pairingfor Elliptic and Hyperelliptic Curves, In: ANTS VI, LNCS 3076, Springer-Verlag, 2004, pp.169-183.
[56] K. Eisentr¨aer, K. Lauter, P.L. Montgomery, Fast elliptic curve arithmeticand improved Weil pairing evaluation, in: CT-RSA 2003, LNCS 2612,Springer-Verlag, 2003, pp. 343-354.
[57] T.ElGamal, A public key cryptosystem and a signature scheme based ondiscrete logarithms, In: Advances in Cryptology-CRYPTO’84, LNCS 196,Springer-Verlag, 1985, pp.10-18.
[58] A.Enge and P.Gaudry, A General Framework for Subexponential DiscreteLogarithm Algorithms, Acta Arithmetica, 2002, 102:83-103.
[59] G.Frey, How to disguise an elliptic curve (Weil descent),Talk at ECC’98,Waterloo, 1998. http://www.cacr.math.uwaterloo.ca/conferences/1998/ecc98/frey.ps
[60] G.Frey, M.M¨uller and H.R¨uck, The Tate Pairing and the Discrete LogarithmApplied to Elliptic Curve Cryptosystems, IEEE Trans. Inf. Theory,1999,45(5): 1717-1719.
[61] G.Frey and H.G.R¨uck, A remark concerning m-divisibility and the discretelogarithm problem in the divisor class group of curves, Math. Comp.,1994,62: 865-874.
[62] S.D. Galbraith, K. Harrison, D. Soldera, Implementing the Tate pairing, In:ANTS V, LNCS 2369, Springer-Verlag, 2002, pp. 324-337.
[63] p. Gaudry,F. Hess and N. Smart, Constructive and destructive facets of Weildescent on elliptic curves, J. Crypto., 2002, 15(1):19-46.
[64] S.D. Galbraith,F. Hess and N. Smart, Extending the GHS Weil descentattack, In: Advances in Cryptology-EUROCRYPT 2002, LNCS 2332,Springer-Verlag, 2002, pp. 29-44.
[65] S. Galbraith, X. Lin and M. Scott, Endomorphisms for faster elliptic curvecryptography on general curves, In: Advances in Cryptology - EUROCRYPT2009, LNCS 5479, Springer-Verlag, 2009, pp. 518-535.
[66] R.P.Gallant,R.J.Lambert and S.A.Vanstone, Faster Point Multiplication onElliptic Curves with Efficient Endomorphisms, In: Advances in Cryptology-CRYPTO 2001, LNCS 2139, Springer-Verlag, 2001, pp.190-200.
[67] P. Gaudry, An algorithm for solving the discrete log problem on hyperellipticcurves, In: Advances in Cryptology-EUROCRYPT 2000. LNCS 1807,Springer-Verlag, 2000, pp. 19-34.
[68] D. Gordon, Discrete logarithms in GF(p) using the number field sieve, SIAMJ. Discrete Math., 1993, 6:124-138.
[69] G¨unter M. Ziegler, The great prime number record races, Notices of theAMS, 2004, 51(4): 414–416.
[70] D.Hankerson, A. Menezes and S.Vanstone, Guide to Elliptic Curve Cryptography,Springer-Verlag, New York, 2004, pp. 76-86.
[71] F. Hess, N. Smart, F. Vercauteren, The Eta pairing revisited, IEEE Transactionson Information Theory, 2006, 52(10):4595–4602.
[72] A.Higuchi and N.Takagi, A fast addition algorithm for elliptic curve arithmeticin GF(2n) using projective coordinates, Inf. Process. Lett., 2000, 76:101-103.
[73] H. Hisil, G. Carter, and E. Dawson, New formulae for efficient elliptic curvearithmetic, In: Advances in Cryptology-INDOCRYPT 2007, LNCS 4859,Springer-Verlag, 2007, pp. 138-151.
[74] H.Hisil, K.Wong, G.Carter and E.Dawson, Faster group operations on ellipticcurves, In: AISC 2009, Wellington, New Zealand. CRPIT, 98. Brankovic,L. and Susilo, W., Eds. ACS. pp. 7-19.
[75] J.Hoffstein, J.Pipher and J.Silverman, NTRU: A Ring-Based Public KeyCryptosystem, In: ANTS III, LNCS 1423, Springer-Verlag, 1998, pp. 267-288.
[76] E.W.Knudsen, Elliptic Scalar Multiplication Using Point Halving, In: Advancesin Cryptology-ASIACRYPT’99, LNCS 1716, 1999, pp.135-149.
[77] IEEE P1363, Standard Specifications for Public Key Cryptography (1999).
[78] ISO/IEC 15946, Information technology– Security techniques– Cryptographictechniques based on elliptic curves,2002.
[79] K. Ireland and M. Rosen, A classical introduction to modern number theory,Graduate Texts in Mathematics 84, Springer-Verlag, New York, 1982.
[80] S. Ionica and A. Joux, Another approach to pairing computation in Edwardscoordinates, In: INDOCRYPT 2008, LNCS 5365, Springer-Verlag, 2008, pp.400-413.
[81] A. Joux, The Weil and Tate pairings as building blocks for public key cryptosystems,In: ANTS-5, LNCS 2369, Springer-Verlag, 2002, pp. 20–32.
[82] A. Joux, A one round protocol for tripartite Diffie-Hellman, J. Crypto., 2004,17(4): 263-276.
[83] A. Joux and K. Nguyen, Separating Decision Diffie–Hellman fromDiffie–Hellman in cryptographic groups, J. Crypto., 2003, 16: 239–248.
[84] M. Joye and J. J. Quisquater, Hessian elliptic curves and side-channel attacks,In: CHES 2001, LNCS 2162, Springer-Verlag, 2001, pp. 402–410.
[85] Marc Joye, Fast Point Multiplication on Elliptic Curves without Precomputation,In WAIFI 2008, LNCS 5130, Springer-Verlag, 2008, pp. 36-46.
[86] T. Kobayashi, K. Aoki, H. Imai, Efficient algorithms for Tate pairing, IEICETrans. fundam. Electron. Commun. & Comput. Sci. E89-A, 2006, 1: 134-142.
[87] N. Koblitz, Elliptic Curve Cryptosystem, Math. Comp. , 1987, 48(177): 203-209.
[88] N.Koblitz, CM Curves with Good Cryptographic properties, In: Advances inCryptography-CRYPTO’91, LNCS 576, Springer-Verlag, 1992,pp.279-287.
[89] N.Koblitz, J.Silverman, A. Stein, Analysis of the Xedni Calculus Attack,Design Codes and Cryptolography, 2000, 20(1): 41-64.
[90] C.K.Koc, Analysis of Slideing Window Techniques for Exponentiation, Comput.Math. Appl., 1995, 30(10):17-24.
[91] D.R. Kohel and I.E. Shparlinski, On exponential sums and group generatorsfor elliptic curves over finite fields, In: ANTS-4, LNCS 1838, Springer-Verlag, 2000, pp. 395–404.
[92] E.Konstantinou, A.Kontogeorgis, Y.C.Stamatiou, C.Zaroliagis, On the efficientgeneration of prime order elliptic curves, J. Cryptol. Preprint, 2009.
[93] K.Koyama and Y. Tsuruoka, Speeding up Elliptic Cryptosystems by Using aSigned Binary Window Method, In: Advances in Cryptology-CRYPTO’92,LNCS 740, Springer-Verlag, 1992, pp.345-357.
[94] J. Lagarias and A. Odlyzko, Effective versions of the Chebotarev densitytheorem, In: Algebraic Number Fields, Academic Press, London, 1977.
[95] S. Lang, Introduction to modular forms, Springer-Verlag, 1995.
[96] T.Lange, A note on L′opez-Dahab coordinates, Tatra Mt. Math. Publ., 2006,33:75-81.
[97] G.L.Lay, H.Zimmer, Constructing elliptic curves with given group order overlarge finite fields, In: Algorithmic Number Theory - ANTS-I, LNCS 877,Springer-Verlag, 1994, pp. 250-263.
[98] H.W.Lenstra, Factoring with elliptic curves, Ann. Math., 1987, 126:649-673.
[99] A.K.Lenstra and H.W.Lenstra, The Development of the Number Field Sieve,LNCS 1554, Springer-Verlag, Berlin, 1993.
[100] A.K.Lenstra and E.R.Verheul, The XTR public key system, In: Advancesin Cryptology–CRYPTO 2000, LNCS 1880, Springer-Verlag,2000,pp.1-19.
[101] P.Y. Liardet, N.P.Smart, Preventing SPA/DPA in ECC systems using theJacobi form. In: Cryptographic Hardware and Embedded Systems - CHES2001, LNCS 2162, Springer-Verlag, 2001, pp.391-401.
[102] D. Lorenzini, An Invitation to Arithmetic Geometry. AMS, Graduate Studiesin Mathematics 106, 1993.
[103] J.L′opez and R. Dahab, Improved algorithms for elliptic curve arithmeticin GF(2n), Tech. Report IC-98-39, Relat′orio T′ecnico, October 1998.
[104] M. Maurer, A. Menezes, and E. Teske, Analysis of the GHSWeil descent attackon the ECDLP over characteristic two finite fields of composite degree,In: Advances in Cryptology–INDOCRYPT 2001, LNCS 2247, Springer-Verlag, 2001, pp. 195-213.
[105] W.Meier and O.Staffelbach, Efficient Multiplication on Certain NonsupersingularElliptic Curves, in: Advances in Cryptology-CRYPTO’92, LNCS740, Springer-Verlag, 1992, pp. 333-344.
[106] A. Menezes,T. Okamoto and S.A. Vanstone, Reducing Elliptic Curves Logarithmsto Logarithms in a Finite Field, IEEE Trans. Inf. Theory, 1993,39(5):1639-1646.
[107] A.Menezes and M.Qu, Analysis of the Weil Descent Attack of Gaudry, Hessand Smart, In: Topics in Cryptology-CT-RSA 2001,LNCS 2020, Springer-Verlag, 2001, pp. 308-318.
[108] A.Menezes, E.Teske and A.Weng, Weak Fields for ECC, In: Topics inCryptology-CT-RSA 2004, LNCS 2964, Springer-Verlag, 2004, pp. 366-386.
[109] A.Menezes, S.Vanstone, The implementation of elliptic curve cryptosystems,Advances in Cryptology - AUSCRYPT’90, LNCS 453，Springer-Verlag, 1990, pp. 2-13.
[110] V.Miller. Use of Elliptic Curves in Cryptography. In: Advances in Cryptology- CRYPTO’85, LNCS 218, Springer-Verlag, 1986, pp. 417-426.
[111] V. Miller, Short programs for functions on curves, Unpublished manuscript,1986
[112] V.S. Miller, TheWeil pairing and its Efficient Calculation, J. Crypto., 2004,17:235-261.
[113] A.Miyaji, Elliptic Curve over Fp suitable for cryptosystems, In: Advancesin Cryptology - Auscrypt 92, LNCS 718, Springer-Verlag, 1993, pp.479-491.
[114] F.Morain and J.Olivos, Speeding up the Computations on an Elliptic CurveUsing Addition-Subtraction Chains, Inf. Theory Appl., 1990, 24: 531-543.
[115] F.Morain ,Calcul du nombre de points sur une courbe elliptique dans uncorps fini : aspects algorithmiques. Journal de théorie des nombres de Bordeaux,1995, 7(1): 255-282.
[116] V.M¨uller, Fast Multiplication on Elliptic Curves over Small Fields of CharacteristicTwo, J. Crypto., 1998, 11: 219-234.
[117] P.C. Van Oorschot and M.J. Wiener, Parallel collision search with cryptanalyticapplications, J. Crypto., 1999, 12(1): 1-28.
[118] H.Cohen and K.Belabas, pari/gp: computer algebra system, version 2.1.5,Bordeaux, 2003, http://pari.math.u-bordeaux.fr/.
[119] C. Pomerance, The quadratic sieve factoring algorithm, In: Advances inCryptology-Eurocrypt’84, LNCS 209, Springer-Verlag, 1985, pp.169-182.
[120] S.C.Pohlig and M.E.Hellman, An improved Algorithm for Computing Logarithmsover GF(p) and its Cryptographic Significance, IEEE Trans. Inf.Theory, 1978, 24:106-110.
[121] J.M.Pollard, Monte Carlo Methods for Index Computation mod p, Math.Comput., 1978, 32: 918-924.
[122] G. Rabinowitch, Eindeutigkeit der Zerlegung in Primzahlfaktoren inquadratischen Zahlk¨orpern, J.R. Ang. Math., 1913, 142: 153-164.
[123] R.L.Rivest, A.Shamir and L.Adleman, A method for obtaining digital signaturesand public-key cryptosystems, Commun. ACM, 1978, 21(2):120-126.
[124] R. Sasaki, On a lower bound for the class number of an imaginary quadraticfield, In: Proc. Japan Acad. Ser. A, 1986, 62: 37-39.
[125] T.Satoh and K.Araki, Fermat Quotients and the Polynomial Time DiscreteLog Algorithm for Anomalous Elliptic Curves, Commentarii MathematiciUniversitatis Sancti Pauli, 1998, 47: 81-92.
[126] E.Savas, T.A.Schmidt, C.K.Koc, Generating elliptic curves of prime order,In: Cryptographic Hardware and Embedded Systems - CHES 2001, LNCS2162，Springer-Verlag, 2001, pp. 145-161.
[127] O. Schirokauer, Discrete logarithms and local units, Philosophical Transactionsof the Royal Society of London, Series A, 1993, 345: 409-423.
[128] M. Scott, Faster Pairings Using an Elliptic Curve with an Efficient Endomorphism,In: Advances in Cryptology - Indocrypt 2005, LNCS 3797,Springer-Verlag, 2005, pp. 258-269.
[129] M.Scoot, N.Benger, M.Charlemagne, J. Perez, J. Kachisa, Fast hashing toG2 on pairing friendly curves, In: Pairing 2009, LNCS 5671, Springer-Verlag,2009, pp. 102-113.
[130] Standards for Efficient Cryptography, Elliptic Curve Cryptography Version1.0, (2000).
[131] I.A.Semaev, Evaluation of Discrete Logarithms in a Group of p-TorsionPoints of an Elliptic Curve in Characteristic p. Math. Comp., 1998, 67(221):353-356.
[132] J.H.Silverman, The Arithmetic of Elliptic Curves. GTM106, Spring-Verlag,1986.
[133] J.Silverman, J. Suzuki, Elliptic Curve Discrete Logarithms and the IndexCalculus, In: Advances in Cryptology - AsiaCrypt’98, LNCS 1514 Springer-Verlag,1998, pp.110-125.
[134] J.Silverman, The Xedni Calculus and the Elliptic Curve Discrete LogarithmProblem, Design, Codes and Cryptography, 2000,20 (1): 5-20.
[135] N.P.Smart, The Discrete Logarithms Problem on Elliptic Curves of TraceOne, J. Crypto., 1999, 12:193-196.
[136] N.P.Smart, S-integral Points on Elliptic Curves, In: Proc. Camb. Phil. Soc.,1994, 116:391-399.
[137] Nigel P. Smart, The Hessian form of an elliptic curve, In: CHES 2001,LNCS 2162, Springer-Verlag, 2001, pp. 118–125.
[138] J.Solinas, An Improved Algorithm for Arithmetic on a Family of EllipticCurves, In: Advances in Cryptology-CRYPTO’97, LNCS 1294, Springer-Verlag, 1997, pp.357-371.
[139] J.Solinas, Efficient Arithmetic on Koblitz Curves, Designs, Codes andCryptography, 2000,19(2-3):195-249.
[140] E.Teske, On Random Walks for Pollard’s rho Method, Math. Comp., 2001,70(234):809-825.
[141] D.Terr, A Modification of Shank’s Baby-step Giant-Step Algorithm, Math.Comp., 1999, 69(230):767-773.
[142] F.Vercauteren, B.Preneel and J.Vandewalle, A memory efficient versionof Satoh’s algorithm, In: B. Pfitzmann (ed.) Advances in Cryptology-Eurocrypt 2002, LNCS 2045, Springer-Verlag, pp. 1-13.
[143] A.Wiles, Modular Elliptic-Curves and Fermat’s Last Theorem, Ann. Math.1995, 141: 443-551.
[144] K.W.Wong, Edward C.W.Lee,L.M.Cheng and Xiaofeng Liao, Fast EllipticScalar Multiplication using New Double-base Chain and Point Halving,Appl. Math. Comp., 2006, 183 (2): 1000-1007.
[145] Chang-An Zhao, Fangguo Zhang and Jiwu Huang, A note on the Ate pairing,Int. J. Inf. Secur., 2008, 7(6): 379-382.
[146] Chang-An Zhao, Fangguo Zhang and Jiwu Huang, All Pairings are in aGroup, IEICE, 2008, Vol.E91-A, No.10: 3084-3087.
[147] Chang’an Zhao, Fangguo Zhang and Dongqing Xie, Reducing the Complexityof the Weil Pairing Computation, accepted by ChinaCrypto 2009.
[148]白国强，椭圆曲线密码及其算法研究，［学位论文］，西安电子科技大学，2000, pp.33-38.
[149]顾海华，虚二次数域上类数与Ono不变量的关系，[硕士学位论文]，安徽师范大学，2006, pp. 19-28.
[150]裴定一，祝跃飞，算法数论，北京：科学出版社，2002，pp. 97-104.
[2] L.Adleman, J.Demarrais and M.Huang, A subexponential Algorithm for DiscreteLogarithm over the Rational Subgroup of the Jacobians of Large Genushyperelliptic Curves over Finite Fields, In: ANTS I, LNCS 877,Springer Verlag,1994, pp. 28-40.
[3] M. Agrawal, N. Kayal and N. Saxenag, Primes is in P, Annals of Math.,2004,160(2): 781-793.
[4] E.AlDaoud, R.Mahmod, M.Rushdan and A.Kilicman, A new addition formulafor elliptic curves over GF(2n), IEEE Trans. Comput., 2002, 51: 972-975.
[5] ANSI X9.62, Public Key Cryptography for the Financial Services Industry:The Elliptic Curve Digital Signature Algorithm (ECDSA), AmericanNational Standards Institute, 1999.
[6] ANSI X9.63, Public Key Cryptography for the Financial Services Industry- Key Agreement and Key Transport Using Elliptic Curve Cryptography,American Bankers Association, November 20, 2001.
[7] A.O.L. Atkin and F. Morain, Elliptic curves and primality proving, Math.Comp.,1993, 61(203): 29-68.
[8] R.Avanzi,V.Dimitrov, C.Doche and F.Sica, Extending Scalar MultiplicationUsing Double Bases, In: Advances in Cryptology-ASIACRYPT’06, LNCS4284, Springer-Verlag, 2006, pp.130-144.
[9] C. Ar`ene, T. Lange, M. Naehrig, and C. Ritzenthaler, Faster Computationof Tate Pairings, Cryptology ePrint Archive, Report 2009/155,http://eprint.iacr.org/2009/155.pdf
[10] E. Bach, Explicit bounds for primality testing and related problems, Math.Comp., 1990, 55: 355-380.
[11] E. Bach, J. Sorenson, Explicit bounds for primes in residue classes, Math.Comp., 1996, 65: 1717–1735.
[12] H.Baier, Efficient algorithms for generating elliptic curves over finite fieldssuitable for use in cryptography, Ph.D. Thesis, Dept. of Computer Science,Technical Univ. of Darmstadt, May 2002.
[13] R.Balasubramanian and N.Koblitz, The improbability that an elliptic curvehas subexponential discrete logarithm problem under the Menezes-Okamoto-Vanstone algorithm, J. Crypto., 1998, 11: 141-145.
[14] P. Barreto, H.Y. Kim, B. Lynn, M. Scott, Efficient algorithms for pairingbasedcryptosystems, In: Advances in Cryptology - Crypto’02, LNCS 2442,Springer-Verlag, 2002, pp. 354-368.
[15] P.S.L.M. Barreto, S. Galbraith, C.′Oh′Eigeartaigh, M. Scott, Effcient PairingComputation on Supersingular Abelian Varieties, In Designs, Codes andCryptography, 2007, 42(3): 239-271.
[16] Daniel J. Bernstein and Tanja Lange, Faster addition and doubling on ellipticcurves, In: Advances in Cryptology - ASIACRYPT’07, LNCS 4833,Springer-Verlag, 2007, pp. 29–50.
[17] Daniel J. Bernstein and Tanja Lange, Analysis and optimization of ellipticcurvesingle-scalar multiplication, In: Finite fields and applications, Contemp.Math. 461, American Mathematical Society ,2008, pp. 1-19.
[18] Daniel J. Bernstein and Tanja Lange, Inverted Edwards coordinates, In:AAECC-17, LNCS 4851, Springer-Verlag, 2007, pp. 20–27.
[19] V. Berth′e and L. Imbert, On converting numbers to the double base numbersystem, Advanced Signal Processing Algorithms, Architecture and ImplementationsXIV, Proc. SPIE, 5559, 2004, pp. 70–78.
[20] O. Billet and M. Joye, The Jacobi model of an elliptic curve and side-channelanalysis, In: AAECC-15, LNCS 2643, Springer-Verlag, 2003, pp. 34-42.
[21] I.F.Blake, G.Seroussi, N.P.Smart, Advances in Elliptic curve cryptography,Cambridge University Press, 2005, pp. 183-196.
[22] I.F.Blake, K. Murty, G. Xu, Refinements of Miller’s algorithm for computingWeil/Tate pairing, J. Algorithm, 2006, 58(2): 134 - 149.
[23] D. Boneh, The decision Diffie-Hellman problem, In: ANTS-3, LNCS 1423,Springer-Verlag, 1998, pp. 48–63.
[24] D. Boneh and M. Franklin, Identity based encryption from the Weil pairing,SIAM J. Comp., 2003, 32: 586–615.
[25] D.Boneh, H.Shacham, Group signatures with verifier-local revocation, In:Atluri, V., Pfitzmann, B., McDaniel, P. (eds.) ACM CCS 04, ACM Press2004, pp. 168-177.
[26] W. Bosma, J. Cannon, C. Playoust, The Magma algebra system. I. The userlanguage, J. Symbolic Comput., 1997, 24(3-4):235-265.
[27]′E.Brier and M.Joye, Fast point multiplication on elliptic curves throughisogenies. In: AAECC-15, LNCS 2643, Springer-Verlag, 2003, pp. 43-50.
[28] B. Br¨oker, D. Charles and K. Lauter, Evaluating large degree isogenies andapplications to pairing based cryptography, In: Pairing 2008, LNCS 5209,Springer-Verlag, 2008, pp.100-112.
[29] S. Chatterjee, P. Sarkar, R. Barua, Efficient computation of Tate pairingin projective coordinate over general characteristic fields, In: ICISC 2004,LNCS 3506, Springer-Verlag, 2005, pp. 168-181.
[30] Z. Cheng and M. Nistazakis, Implementing pairing-based cryptosystems,In: 3rd International Workshop on Wireless Security Technologies IWWST-2005, London, UK, April, 2005.
[31] David V. Chudnovsky and Gregory V. Chudnovsky, Sequences of numbersgenerated by addition in formal groups and new primality and factorizationtests, Adv. Appl. Math., 7(4):385–434, 1986.
[32] M. Ciet, K. Lauter, M. Joye, P.L. Montgomery, Trading inversions for multiplicationsin elliptic curve cryptography, Designs, Codes Cryptography,2006, 39 (2): 189-206.
[33] H.Cohen, G.Frey, R.Avanzi, C.Doche, T.Lange, K.Nguyen and F. Vercauteren,Handbook of Elliptic and Hyperelliptic Curve Cryptography.Taylor & Francis Group, LLC, 2006.
[34] H. Cohen and H. W. Lenstra, Jr., Primality Testing and Jacobi Sums, Math.Comp. , 1984, 42: 297-330.
[35] M.Coban, Primitive Elements in Finite Fields with Arbitrary Trace, SabanclUniversity Thesis, Spring-Verlag, 2003.
[36] H.Cohen, A.Miyaji and T. Ono, Efficient elliptic curve exponentiation usingmixed coordinates, In: Advance in Cryptology-Asiacrypt 1998, LNCS, vol.1514, Springer-Verlag, 1998, pp. 51-65.
[37] D. Coppersmith, Fast evaluation of logarithms in fields of characteristic two,IEEE Trans. Inf. Theory, 1984, 30: 587-594.
[38] Joseph Cohen and Jack Sonn, On the Ono invariants of imaginary quadraticfields, J. Number Theory, 2002, 95: 259-267.
[39] H. Cohen, A course in computational algebraic number theory, 3., corr.print. Graduate Texts in Mathematics 138, Springer-Verlag, 1996.
[40] H.Cohen, A.Miyaji and T.Ono, Efficient elliptic curve exponentiation, advancesin cryptology-Proceedings of ICICS’97, LNCS 1334, Springer-Verlag,1997, pp. 282-290.
[41] H.Cohen, A.Miyaji and T.Ono, Efficient elliptic curve exponentiation usingmixed coordinates, in: Advances in Cryptology-Asiacrypt 1998, LNCS 1514,Springer-Verlag, 1998, pp. 51-65.
[42] J.Coron, Resistance against differential power analysis for elliptic curve cryptosystems,CHES’99, LNCS 1717, Springer-Verlag, 1999,292-302.
[43] C. Costello, H. Hisil, C. Boyd, J.M.G. Nieto and K.K.H. Wong, Fasterpairings on special Weierstrass curves, Cryptology ePrint Archive, Report2009/243, http://eprint.iacr.org/2009/243.pdf
[44] M.Das, P. Sarkar, Pairing computation on twisted Edwards form ellipticcurves, In: Pairing 2008, LNCS 5209, Springer-Verlag, 2008, pp. 192-210.
[45] T.Denny, B.Dodson, A.K.Lenstra and M.S.Manasse, On the factorization ofRSA-120, in: Advances in Cryptology - Crypto’93, LNCS 773 , Springer-Verlag, 1994, pp.166-174.
[46] W.Diffie and M.E. Hellman, New directions in cryptography, IEEE Trans.Inf. Theory, 1976,22:644-654.
[47] V.S.Dimitorv,G A.Julliena and W.C.Miller, An algorithm for Modular Exponentiation,Inf. Proc. Lett., 1998,66 (3):155-159.
[48] VS.Dimitrov, GA.Jullien and W.C.Miller, Theory and applications of thedouble-base number system, IEEE Trans. comput., 1999,48(10):1098-1106.
[49] V.S.Dimitrov, L.Imbert, P.K.Mishra, Efficient and Secure Elliptic CurvePoint Multiplication Using Double-Base Chains, In: Proc. ASIACRYPT’05,LNCS 3788, Springer-Verlag, 2005, pp.624-643.
[50] V.S.Dimitrov, L.Imbert, P.K.Mishra, The Double Base Number System andIts Application to Elliptic Curve Cryptography, Math. Comp., 2008, 77:1075-1104.
[51] C. Doche, D. R.Kohel, F. Sica, Double-Base Number System for Multi-ScalarMultiplications, in: Advances in Cryptology - Eurocrypt 2009, Cologne,Germany, April 26-30.
[52] I.Duursma, H.S.Lee, Tate Pairing Implementation for Hyperelliptic Curvesy2 = xp ? x + d, In: Advances in Cryptology - Asiacrypt 2003, LNCS 2894,2003, pp. 111-123.
[53] I.Duursma,P.Gaudry, F.Morain, Speeding up the discrete log compuationon curves with automorphisms, Proc. Int. Conf. Theory App. Crypto. Inf.Secur., LNCS 1716, 1999, pp.103-121.
[54] Harold M. Edwards, A normal form for elliptic curves, Bull. Am. Math. Soc.,2007, 44: 393–422.
[55] K. Eisentr¨aer, K.Lauter, P.Montgomery, Improved Weil and Tate Pairingfor Elliptic and Hyperelliptic Curves, In: ANTS VI, LNCS 3076, Springer-Verlag, 2004, pp.169-183.
[56] K. Eisentr¨aer, K. Lauter, P.L. Montgomery, Fast elliptic curve arithmeticand improved Weil pairing evaluation, in: CT-RSA 2003, LNCS 2612,Springer-Verlag, 2003, pp. 343-354.
[57] T.ElGamal, A public key cryptosystem and a signature scheme based ondiscrete logarithms, In: Advances in Cryptology-CRYPTO’84, LNCS 196,Springer-Verlag, 1985, pp.10-18.
[58] A.Enge and P.Gaudry, A General Framework for Subexponential DiscreteLogarithm Algorithms, Acta Arithmetica, 2002, 102:83-103.
[59] G.Frey, How to disguise an elliptic curve (Weil descent),Talk at ECC’98,Waterloo, 1998. http://www.cacr.math.uwaterloo.ca/conferences/1998/ecc98/frey.ps
[60] G.Frey, M.M¨uller and H.R¨uck, The Tate Pairing and the Discrete LogarithmApplied to Elliptic Curve Cryptosystems, IEEE Trans. Inf. Theory,1999,45(5): 1717-1719.
[61] G.Frey and H.G.R¨uck, A remark concerning m-divisibility and the discretelogarithm problem in the divisor class group of curves, Math. Comp.,1994,62: 865-874.
[62] S.D. Galbraith, K. Harrison, D. Soldera, Implementing the Tate pairing, In:ANTS V, LNCS 2369, Springer-Verlag, 2002, pp. 324-337.
[63] p. Gaudry,F. Hess and N. Smart, Constructive and destructive facets of Weildescent on elliptic curves, J. Crypto., 2002, 15(1):19-46.
[64] S.D. Galbraith,F. Hess and N. Smart, Extending the GHS Weil descentattack, In: Advances in Cryptology-EUROCRYPT 2002, LNCS 2332,Springer-Verlag, 2002, pp. 29-44.
[65] S. Galbraith, X. Lin and M. Scott, Endomorphisms for faster elliptic curvecryptography on general curves, In: Advances in Cryptology - EUROCRYPT2009, LNCS 5479, Springer-Verlag, 2009, pp. 518-535.
[66] R.P.Gallant,R.J.Lambert and S.A.Vanstone, Faster Point Multiplication onElliptic Curves with Efficient Endomorphisms, In: Advances in Cryptology-CRYPTO 2001, LNCS 2139, Springer-Verlag, 2001, pp.190-200.
[67] P. Gaudry, An algorithm for solving the discrete log problem on hyperellipticcurves, In: Advances in Cryptology-EUROCRYPT 2000. LNCS 1807,Springer-Verlag, 2000, pp. 19-34.
[68] D. Gordon, Discrete logarithms in GF(p) using the number field sieve, SIAMJ. Discrete Math., 1993, 6:124-138.
[69] G¨unter M. Ziegler, The great prime number record races, Notices of theAMS, 2004, 51(4): 414–416.
[70] D.Hankerson, A. Menezes and S.Vanstone, Guide to Elliptic Curve Cryptography,Springer-Verlag, New York, 2004, pp. 76-86.
[71] F. Hess, N. Smart, F. Vercauteren, The Eta pairing revisited, IEEE Transactionson Information Theory, 2006, 52(10):4595–4602.
[72] A.Higuchi and N.Takagi, A fast addition algorithm for elliptic curve arithmeticin GF(2n) using projective coordinates, Inf. Process. Lett., 2000, 76:101-103.
[73] H. Hisil, G. Carter, and E. Dawson, New formulae for efficient elliptic curvearithmetic, In: Advances in Cryptology-INDOCRYPT 2007, LNCS 4859,Springer-Verlag, 2007, pp. 138-151.
[74] H.Hisil, K.Wong, G.Carter and E.Dawson, Faster group operations on ellipticcurves, In: AISC 2009, Wellington, New Zealand. CRPIT, 98. Brankovic,L. and Susilo, W., Eds. ACS. pp. 7-19.
[75] J.Hoffstein, J.Pipher and J.Silverman, NTRU: A Ring-Based Public KeyCryptosystem, In: ANTS III, LNCS 1423, Springer-Verlag, 1998, pp. 267-288.
[76] E.W.Knudsen, Elliptic Scalar Multiplication Using Point Halving, In: Advancesin Cryptology-ASIACRYPT’99, LNCS 1716, 1999, pp.135-149.
[77] IEEE P1363, Standard Specifications for Public Key Cryptography (1999).
[78] ISO/IEC 15946, Information technology– Security techniques– Cryptographictechniques based on elliptic curves,2002.
[79] K. Ireland and M. Rosen, A classical introduction to modern number theory,Graduate Texts in Mathematics 84, Springer-Verlag, New York, 1982.
[80] S. Ionica and A. Joux, Another approach to pairing computation in Edwardscoordinates, In: INDOCRYPT 2008, LNCS 5365, Springer-Verlag, 2008, pp.400-413.
[81] A. Joux, The Weil and Tate pairings as building blocks for public key cryptosystems,In: ANTS-5, LNCS 2369, Springer-Verlag, 2002, pp. 20–32.
[82] A. Joux, A one round protocol for tripartite Diffie-Hellman, J. Crypto., 2004,17(4): 263-276.
[83] A. Joux and K. Nguyen, Separating Decision Diffie–Hellman fromDiffie–Hellman in cryptographic groups, J. Crypto., 2003, 16: 239–248.
[84] M. Joye and J. J. Quisquater, Hessian elliptic curves and side-channel attacks,In: CHES 2001, LNCS 2162, Springer-Verlag, 2001, pp. 402–410.
[85] Marc Joye, Fast Point Multiplication on Elliptic Curves without Precomputation,In WAIFI 2008, LNCS 5130, Springer-Verlag, 2008, pp. 36-46.
[86] T. Kobayashi, K. Aoki, H. Imai, Efficient algorithms for Tate pairing, IEICETrans. fundam. Electron. Commun. & Comput. Sci. E89-A, 2006, 1: 134-142.
[87] N. Koblitz, Elliptic Curve Cryptosystem, Math. Comp. , 1987, 48(177): 203-209.
[88] N.Koblitz, CM Curves with Good Cryptographic properties, In: Advances inCryptography-CRYPTO’91, LNCS 576, Springer-Verlag, 1992,pp.279-287.
[89] N.Koblitz, J.Silverman, A. Stein, Analysis of the Xedni Calculus Attack,Design Codes and Cryptolography, 2000, 20(1): 41-64.
[90] C.K.Koc, Analysis of Slideing Window Techniques for Exponentiation, Comput.Math. Appl., 1995, 30(10):17-24.
[91] D.R. Kohel and I.E. Shparlinski, On exponential sums and group generatorsfor elliptic curves over finite fields, In: ANTS-4, LNCS 1838, Springer-Verlag, 2000, pp. 395–404.
[92] E.Konstantinou, A.Kontogeorgis, Y.C.Stamatiou, C.Zaroliagis, On the efficientgeneration of prime order elliptic curves, J. Cryptol. Preprint, 2009.
[93] K.Koyama and Y. Tsuruoka, Speeding up Elliptic Cryptosystems by Using aSigned Binary Window Method, In: Advances in Cryptology-CRYPTO’92,LNCS 740, Springer-Verlag, 1992, pp.345-357.
[94] J. Lagarias and A. Odlyzko, Effective versions of the Chebotarev densitytheorem, In: Algebraic Number Fields, Academic Press, London, 1977.
[95] S. Lang, Introduction to modular forms, Springer-Verlag, 1995.
[96] T.Lange, A note on L′opez-Dahab coordinates, Tatra Mt. Math. Publ., 2006,33:75-81.
[97] G.L.Lay, H.Zimmer, Constructing elliptic curves with given group order overlarge finite fields, In: Algorithmic Number Theory - ANTS-I, LNCS 877,Springer-Verlag, 1994, pp. 250-263.
[98] H.W.Lenstra, Factoring with elliptic curves, Ann. Math., 1987, 126:649-673.
[99] A.K.Lenstra and H.W.Lenstra, The Development of the Number Field Sieve,LNCS 1554, Springer-Verlag, Berlin, 1993.
[100] A.K.Lenstra and E.R.Verheul, The XTR public key system, In: Advancesin Cryptology–CRYPTO 2000, LNCS 1880, Springer-Verlag,2000,pp.1-19.
[101] P.Y. Liardet, N.P.Smart, Preventing SPA/DPA in ECC systems using theJacobi form. In: Cryptographic Hardware and Embedded Systems - CHES2001, LNCS 2162, Springer-Verlag, 2001, pp.391-401.
[102] D. Lorenzini, An Invitation to Arithmetic Geometry. AMS, Graduate Studiesin Mathematics 106, 1993.
[103] J.L′opez and R. Dahab, Improved algorithms for elliptic curve arithmeticin GF(2n), Tech. Report IC-98-39, Relat′orio T′ecnico, October 1998.
[104] M. Maurer, A. Menezes, and E. Teske, Analysis of the GHSWeil descent attackon the ECDLP over characteristic two finite fields of composite degree,In: Advances in Cryptology–INDOCRYPT 2001, LNCS 2247, Springer-Verlag, 2001, pp. 195-213.
[105] W.Meier and O.Staffelbach, Efficient Multiplication on Certain NonsupersingularElliptic Curves, in: Advances in Cryptology-CRYPTO’92, LNCS740, Springer-Verlag, 1992, pp. 333-344.
[106] A. Menezes,T. Okamoto and S.A. Vanstone, Reducing Elliptic Curves Logarithmsto Logarithms in a Finite Field, IEEE Trans. Inf. Theory, 1993,39(5):1639-1646.
[107] A.Menezes and M.Qu, Analysis of the Weil Descent Attack of Gaudry, Hessand Smart, In: Topics in Cryptology-CT-RSA 2001,LNCS 2020, Springer-Verlag, 2001, pp. 308-318.
[108] A.Menezes, E.Teske and A.Weng, Weak Fields for ECC, In: Topics inCryptology-CT-RSA 2004, LNCS 2964, Springer-Verlag, 2004, pp. 366-386.
[109] A.Menezes, S.Vanstone, The implementation of elliptic curve cryptosystems,Advances in Cryptology - AUSCRYPT’90, LNCS 453，Springer-Verlag, 1990, pp. 2-13.
[110] V.Miller. Use of Elliptic Curves in Cryptography. In: Advances in Cryptology- CRYPTO’85, LNCS 218, Springer-Verlag, 1986, pp. 417-426.
[111] V. Miller, Short programs for functions on curves, Unpublished manuscript,1986
[112] V.S. Miller, TheWeil pairing and its Efficient Calculation, J. Crypto., 2004,17:235-261.
[113] A.Miyaji, Elliptic Curve over Fp suitable for cryptosystems, In: Advancesin Cryptology - Auscrypt 92, LNCS 718, Springer-Verlag, 1993, pp.479-491.
[114] F.Morain and J.Olivos, Speeding up the Computations on an Elliptic CurveUsing Addition-Subtraction Chains, Inf. Theory Appl., 1990, 24: 531-543.
[115] F.Morain ,Calcul du nombre de points sur une courbe elliptique dans uncorps fini : aspects algorithmiques. Journal de théorie des nombres de Bordeaux,1995, 7(1): 255-282.
[116] V.M¨uller, Fast Multiplication on Elliptic Curves over Small Fields of CharacteristicTwo, J. Crypto., 1998, 11: 219-234.
[117] P.C. Van Oorschot and M.J. Wiener, Parallel collision search with cryptanalyticapplications, J. Crypto., 1999, 12(1): 1-28.
[118] H.Cohen and K.Belabas, pari/gp: computer algebra system, version 2.1.5,Bordeaux, 2003, http://pari.math.u-bordeaux.fr/.
[119] C. Pomerance, The quadratic sieve factoring algorithm, In: Advances inCryptology-Eurocrypt’84, LNCS 209, Springer-Verlag, 1985, pp.169-182.
[120] S.C.Pohlig and M.E.Hellman, An improved Algorithm for Computing Logarithmsover GF(p) and its Cryptographic Significance, IEEE Trans. Inf.Theory, 1978, 24:106-110.
[121] J.M.Pollard, Monte Carlo Methods for Index Computation mod p, Math.Comput., 1978, 32: 918-924.
[122] G. Rabinowitch, Eindeutigkeit der Zerlegung in Primzahlfaktoren inquadratischen Zahlk¨orpern, J.R. Ang. Math., 1913, 142: 153-164.
[123] R.L.Rivest, A.Shamir and L.Adleman, A method for obtaining digital signaturesand public-key cryptosystems, Commun. ACM, 1978, 21(2):120-126.
[124] R. Sasaki, On a lower bound for the class number of an imaginary quadraticfield, In: Proc. Japan Acad. Ser. A, 1986, 62: 37-39.
[125] T.Satoh and K.Araki, Fermat Quotients and the Polynomial Time DiscreteLog Algorithm for Anomalous Elliptic Curves, Commentarii MathematiciUniversitatis Sancti Pauli, 1998, 47: 81-92.
[126] E.Savas, T.A.Schmidt, C.K.Koc, Generating elliptic curves of prime order,In: Cryptographic Hardware and Embedded Systems - CHES 2001, LNCS2162，Springer-Verlag, 2001, pp. 145-161.
[127] O. Schirokauer, Discrete logarithms and local units, Philosophical Transactionsof the Royal Society of London, Series A, 1993, 345: 409-423.
[128] M. Scott, Faster Pairings Using an Elliptic Curve with an Efficient Endomorphism,In: Advances in Cryptology - Indocrypt 2005, LNCS 3797,Springer-Verlag, 2005, pp. 258-269.
[129] M.Scoot, N.Benger, M.Charlemagne, J. Perez, J. Kachisa, Fast hashing toG2 on pairing friendly curves, In: Pairing 2009, LNCS 5671, Springer-Verlag,2009, pp. 102-113.
[130] Standards for Efficient Cryptography, Elliptic Curve Cryptography Version1.0, (2000).
[131] I.A.Semaev, Evaluation of Discrete Logarithms in a Group of p-TorsionPoints of an Elliptic Curve in Characteristic p. Math. Comp., 1998, 67(221):353-356.
[132] J.H.Silverman, The Arithmetic of Elliptic Curves. GTM106, Spring-Verlag,1986.
[133] J.Silverman, J. Suzuki, Elliptic Curve Discrete Logarithms and the IndexCalculus, In: Advances in Cryptology - AsiaCrypt’98, LNCS 1514 Springer-Verlag,1998, pp.110-125.
[134] J.Silverman, The Xedni Calculus and the Elliptic Curve Discrete LogarithmProblem, Design, Codes and Cryptography, 2000,20 (1): 5-20.
[135] N.P.Smart, The Discrete Logarithms Problem on Elliptic Curves of TraceOne, J. Crypto., 1999, 12:193-196.
[136] N.P.Smart, S-integral Points on Elliptic Curves, In: Proc. Camb. Phil. Soc.,1994, 116:391-399.
[137] Nigel P. Smart, The Hessian form of an elliptic curve, In: CHES 2001,LNCS 2162, Springer-Verlag, 2001, pp. 118–125.
[138] J.Solinas, An Improved Algorithm for Arithmetic on a Family of EllipticCurves, In: Advances in Cryptology-CRYPTO’97, LNCS 1294, Springer-Verlag, 1997, pp.357-371.
[139] J.Solinas, Efficient Arithmetic on Koblitz Curves, Designs, Codes andCryptography, 2000,19(2-3):195-249.
[140] E.Teske, On Random Walks for Pollard’s rho Method, Math. Comp., 2001,70(234):809-825.
[141] D.Terr, A Modification of Shank’s Baby-step Giant-Step Algorithm, Math.Comp., 1999, 69(230):767-773.
[142] F.Vercauteren, B.Preneel and J.Vandewalle, A memory efficient versionof Satoh’s algorithm, In: B. Pfitzmann (ed.) Advances in Cryptology-Eurocrypt 2002, LNCS 2045, Springer-Verlag, pp. 1-13.
[143] A.Wiles, Modular Elliptic-Curves and Fermat’s Last Theorem, Ann. Math.1995, 141: 443-551.
[144] K.W.Wong, Edward C.W.Lee,L.M.Cheng and Xiaofeng Liao, Fast EllipticScalar Multiplication using New Double-base Chain and Point Halving,Appl. Math. Comp., 2006, 183 (2): 1000-1007.
[145] Chang-An Zhao, Fangguo Zhang and Jiwu Huang, A note on the Ate pairing,Int. J. Inf. Secur., 2008, 7(6): 379-382.
[146] Chang-An Zhao, Fangguo Zhang and Jiwu Huang, All Pairings are in aGroup, IEICE, 2008, Vol.E91-A, No.10: 3084-3087.
[147] Chang’an Zhao, Fangguo Zhang and Dongqing Xie, Reducing the Complexityof the Weil Pairing Computation, accepted by ChinaCrypto 2009.
[148]白国强，椭圆曲线密码及其算法研究，［学位论文］，西安电子科技大学，2000, pp.33-38.
[149]顾海华，虚二次数域上类数与Ono不变量的关系，[硕士学位论文]，安徽师范大学，2006, pp. 19-28.
[150]裴定一，祝跃飞，算法数论，北京：科学出版社，2002，pp. 97-104.