Abstract
It has become increasingly common to implement discrete-logarithm based public-key protocols on elliptic curves over finite fields. The basic operation is scalar multiplication: taking a given integer multiple of a given point on the curve. The cost of the protocols depends on that of the elliptic scalar multiplication operation.
Koblitz introduced a family of curves which admit especially fast elliptic scalar multiplication. His algorithm was later modified by Meier and Staffelbach. We give an improved version of the algorithm which runs 50% faster than any previous version. It is based on a new kind of representation of an integer, analogous to certain kinds of binary expansions. We also outline further speedups using precomputation and storage.
This paper presents the results of cryptographic research conducted at NSA and does not necessarily represent the policies of the NSA or U.S. Government.
Chapter PDF
References
D. Gordon, “A survey of fast exponentiation methods” (to appear).
D. E. Knuth, Seminumerical Algorithms, Addison-Wesley, 1981, p. 272.
F. Morain and J. Olivos, “Speeding up the computations on an elliptic curve using addition-subtraction chains”, Inform. Theor. Appl. 24 (1990), pp. 531–543.
A. Menezes, T. Okamoto and S. Vanstone, “Reducing elliptic curve logarithms to logarithms in a finite field”, Proc. 23rd Annual ACM Symp. on Theory of Computing (1991), pp. 80–89.
N. Koblitz, “CM curves with good cryptographic properties”, Proc. Crypto '91, Springer-Verlag, 1992, pp. 279–287.
D. W. Ash, I. F. Blake, and S. Vanstone, “Low complexity normal bases”, Discrete Applied Math. 25 (1989), pp. 191–210.
T. Itoh, O Teechai, and S. Trojii, “A fast algorithm for computing multiplicative inverses in GF(2t)”, J. Soc. Electron. Comm. (Japan) 44 (1986), pp. 31–36.
E. Berlekamp, Algebraic Coding Theory, Aegean Park Press, 1984, pp. 36–44.
A. Menezes, P. van Oorschot, and S. Vanstone, Handbook of Applied Cryptography, CRC Press, 1997, pp. 107–109.
W. Meier and O. Staffelbach, “Efficient multiplication on certain non-supersingular elliptic curves”, Proc. Crypto '92, Springer-Verlag, 1993, pp. 333–344.
R. Reiter and J. Solinas, “Fast elliptic arithmetic on special curves”, NSA/R21 Informal Tech. Report, 1997.
K. Koyama and Y. Tsuruoka, “Speeding up elliptic cryptosystems by using a signed binary window method”, Proc. Crypto '92, Springer-Verlag, 1993, pp. 345–357.
R. Schroeppel, H. Orman, S. O'Malley, and O. Spatscheck, “Fast key exchange with elliptic curve systems”, Proc. Crypto '95, Springer-Verlag, 1995, pp. 43–56.
R. Schroeppel, H. Orman, S. O'Malley, and O. Spatscheck, “Fast key exchange with elliptic curve systems”, Univ. of Arizona. Comp. Sci. Tech. Report 95-03, 1995.
F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, Elsevier, 1977, pp. 277–279.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1997 Springer-Verlag
About this paper
Cite this paper
Solinas, J.A. (1997). An improved algorithm for arithmetic on a family of elliptic curves. In: Kaliski, B.S. (eds) Advances in Cryptology — CRYPTO '97. CRYPTO 1997. Lecture Notes in Computer Science, vol 1294. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0052248
Download citation
DOI: https://doi.org/10.1007/BFb0052248
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-63384-6
Online ISBN: 978-3-540-69528-8
eBook Packages: Springer Book Archive