On Montgomery-Like Representations for Elliptic Curves over GF(2k)

  • Martijn Stam
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 2567)


This paper discusses representations for computation on non-supersingular elliptic curves over binary fields, where computations are performed on the x-coordinates only. We discuss existing methods and present a new one, giving rise to a faster addition routine than previous Montgomery-representations. As a result a double exponentiation routine is described that requires 8.5 field multiplications per exponent bit, but that does not allow easy y-coordinate recovery. For comparison, we also give a briefu pdate oft he survey by Hankerson et al. and conclude that, for non-constrained devices, using a Montgomeryrepresentation is slower for both single and double exponentiation than projective methods with y-coordinate.


ECC Montgomery point multiplication Lucas chains 


  1. [1]
    G. Agnew, R. Mullin, and S. Vanstone. An implementation ofellip tic curve cryptosystems over F2155. IEEE J-SAC, 11(5):804–813, 1993. 241, 245Google Scholar
  2. [2]
    T. Akishita. Fast simultaneous scalar multiplication on elliptic curve with Montgomery form. SAC’01, LNCS 2259, pages 255–268. 241, 249Google Scholar
  3. [3]
    D. Bailey and C. Paar. Efficient arithmetic in finite field extensions with application in elliptic curve cryptography. Journal of Cryptology, 14(3):153–176, 2001. 240zbMATHMathSciNetGoogle Scholar
  4. [4]
    I. Blake, G. Seroussi, and N. Smart. Elliptic Curvesi n Cryptography. Cambridge University Press, 1999. 243Google Scholar
  5. [5]
    D. Bleichenbacher. Efficiency and Security of Cryptosystems based on Number Theory. PhD thesis, ETH Zürich, 1996. 248Google Scholar
  6. [6]
    É. Brier and M. Joye. Weierstraβ elliptic curves and side-channel attacks. PKC’02, LNCS 2274, pages 335–345. 241, 249Google Scholar
  7. [7]
    H. Cohen, A. Miyaji, and T. Ono. Efficient elliptic curve exponentiation using mixed coordinates. Asiacrypt’98, LNCS 1514, pages 51–65. 240Google Scholar
  8. [8]
    D. Hankerson, J. López Hernandez, and A. Menezes. Software implementation of elliptic curve cryptography over binary fields. CHES’00, LNCS 1965, pages 1–24. 242, 243, 244, 245Google Scholar
  9. [9]
    T. Izu and T. Takagi. A fast parallel elliptic curve multiplication resistant against side channel attacks. PKC’02, LNCS 2274, pages 280–296. 241, 245, 249Google Scholar
  10. [10]
    D. Johnson and A. Menezes. The elliptic curve digital signature algorithm (ECDSA). CACR Technical report CORR 99-31, University of W aterloo, 1999. 241Google Scholar
  11. [11]
    B. King. An improved implementation ofellip tic curves over GF(2n) when using projective point arithmetic. SAC’01, LNCS 2259, pages 134–150. 240, 244Google Scholar
  12. [12]
    D. E. Knuth. Seminumerical Algorithms, volume 2 of The Art of Computer Programming. Addison Wesley, 3 edition, 1997. 248Google Scholar
  13. [13]
    D. E. Knuth, editor. Selected paperson analysis of algorithms. CSLI Publications, Stanford, 2000. 253Google Scholar
  14. [14]
    D. E. Knuth and C. H. Papadimitriou. Duality in addition chains. Bull. Eur. Assoc. Theor. Comput. Sci EATCS, 13:2–4, 1981. Reprinted in [13, Chapter 31]. 251Google Scholar
  15. [15]
    D. H. Lehmer. Computer technology applied to the theory ofn umbers. Studiesin Number Theory, volume 6 of MAA Studiesin Mathematics, pages 117–151, 1969. 249MathSciNetGoogle Scholar
  16. [16]
    J. López and R. Dahab. Improved arithmetic for elliptic curve arithmetic in GF(2m). SAC’98, LNCS 1556, pages 201–212. 244Google Scholar
  17. [17]
    J. López and R. Dahab. Fast multiplication on elliptic curves over GF(2m) without precomputation. CHES’99, LNCS 1717, pages 316–327. 241, 245, 246, 247, 248, 252Google Scholar
  18. [18]
    A. J. Menezes and S. A. Vanstone. Elliptic curve cryptosystems and their implementation. Journal of Cryptology, 6(4):209–224, 1993.zbMATHCrossRefMathSciNetGoogle Scholar
  19. [19]
    B. Möller. Algorithms for multi-exponentiation. SAC’01, LNCS 2259, pages 165–180. 244, 245Google Scholar
  20. [20]
    P. L. Montgomery. Evaluating recurrences off orm X m+n = f(Xm,Xn,Xm-n) via Lucas chains. Available from /pub/pmontgom/, 1983. 241, 248, 249, 250
  21. [21]
    P. L. Montgomery. Speeding the Pollard and elliptic curve methods off actorization. Mathematicsof Computation, 48(170):243–264, 1987. 240, 241, 242zbMATHCrossRefGoogle Scholar
  22. [22]
    P. L. Montgomery, Aug. 2000. Private communication: expon2fitxt, Dual elliptic curve exponentiation. 249Google Scholar
  23. [23]
    National Institute of Sta ndards and Technology. Digital Signature Standard, 2000. FIPS Publication 186–2. 241Google Scholar
  24. [24]
    K. Okeya, H. Kurumatani, and K. Sakurai. Elliptic curves with the Montgomeryform and their cryptographic applications. PKC’00, LNCS 1751, pages 238–257. 241Google Scholar
  25. [25]
    K. Okeya and K. Sakurai. Efficient elliptic curve cryptosystems from a scalar multiplication algorithm with recovery oft he y-coordinate on a Montgomery-form elliptic curve. CHES’01, LNCS 2162, pages 126–141. 241Google Scholar
  26. [26]
    B. Schoenmakers, Aug. 2000. Personal communication. 249Google Scholar
  27. [27]
    M. Stam and A. K. Lenstra. Speeding up XTR. Asiacrypt’01, LNCS 2248, pages 125–143. 241, 251Google Scholar
  28. 28]
    E. G. Straus. Problems and solutions: (5125) addition chains ofv ectors. American Mathematical Monthly, 71:806–808, 1964. 249CrossRefMathSciNetGoogle Scholar
  29. [29]
    Y. Tsuruoka. Computing short Lucas chains for elliptic curve cryptosystems. IEICE Trans. Fundamentals, E84-A(5):1227–1233, 2001. 251Google Scholar
  30. [30]
    S. A. Vanstone, R. C. Mullin, A. Antipa, and R. Gallant. Accelerated finite field operations on an elliptic curve. WO 99/49386, Patent Cooperation Treaty, 1999. 241, 246, 252Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2003

Authors and Affiliations

  • Martijn Stam
    • 1
  1. 1.Technische Universiteit EindhovenEindhovenThe Netherlands

Personalised recommendations