654Accesses
255Citations
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 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 is a preview of subscription content,log in via an institution to check access.
Access this article
Subscribe and save
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
Buy Now
Price includes VAT (Japan)
Instant access to the full article PDF.
Similar content being viewed by others
References
D. W. Ash, I. F. Blake, and S. Vanstone, Low complexity normal bases,Discrete Applied Math., Vol. 25 (1989) pp. 191–210.
E. Berlekamp,Algebraic Coding Theory, Aegean Park Press (1984).
R. Gallant, R. Lambert, and S. Vanstone, Improving the parallelized Pollard lambda search on binary anomalous curves,Math. Comp., posted on May 19, 1999, PII: S-0025–5718(99)01119–9 (to appear in print).
D. Gordon, A survey of fast exponentiation methods,J. Algs., Vol. 27 (1998) pp. 129–146.
C. Günther and A. Stein (to appear).
Institute of Electrical and Electronics Engineers,IEEE P1363: Standard Specifications for Public-Key Cryptography, Draft 10 (1999).
T. Itoh, O. Teechai, and S. Trojii, A fast algorithm for computing multiplicative inverses inGF(2t),J. Soc. Electron. Comm. (Japan), Vol. 44 (1986) pp. 31–36.
D. Johnson and A. Menezes,The Elliptic Curve Digital Signature Algorithm (ECDSA), Univ. of Waterloo (1999) http://cacr.math.waterloo.ca
D. E. Knuth,Seminumerical Algorithms, Addison-Wesley (1981).
N. Koblitz. CM curves with good cryptographic properties,Proc. Crypto '91, Springer-Verlag (1992) pp. 279–287.
. N. Koblitz, A Course of Number Theory and Cryptography, 2nd ed., Springer-Verlag (1994).
N. Koblitz, An elliptic curve implementation of the Finite Field Digital Signature Algorithm,Proc. Crypto '98, Springer-Verlag (1998) pp. 327–337.
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.
J. Lopez, Fast multiplication on elliptic curves overGF(2m) without precomputation (preprint).
F. Morain and J. Olivos, Speeding up the computations on an elliptic curve using addition-subtraction chains,Inform. Theor. Appl., Vol. 24 (1990) pp. 531–543.
A. Menezes, T. Okamoto and S. Vanstone, Reducing elliptic curve logarithms to logarithms in a finite field,IEEE Transactions on Information Theory, Vol. 39 (1993) pp. 1639–1646.
A. Menezes, P. van Oorschot, and S. Vanstone,Handbook of Applied Cryptography, CRC Press (1997).
W. Meier and O. Staffelbach, Efficient multiplication on certain non-supersingular elliptic curves,Proc. Crypto '92, Springer-Verlag (1993) pp. 333–344.
V. Müller, Fast multiplication on elliptic curves over small fields of characteristic two,J. Crypt., Vol. 11 (1998) pp. 219–234.
P. van Oorschot and M. Weiner, Parallel collision search with cryptanalytic applications,J. Crypt., Vol. 12 (1999) pp. 1–28.
G. Seroussi, Compact representations of elliptic curve points overGF(2n), http://grouper.ieee.org/ groups/1363/contributions/hp.ps
J. Silverman,The Arithmetic of Elliptic Curves, Springer-Verlag (1986).
I. Stewart and D. Tall,Algebraic Number Theory, 2nd. ed., Chapman and Hall (1987).
M. Weiner and R. Zuccherato, Faster attacks on elliptic curve cryptosystems,Selected Areas in Cryptography, Springer-Verlag (1999) pp. 190–200.
Author information
Authors and Affiliations
National Security Agency, Ft. Meade, MD, 20755, USA
Jerome A. Solinas (Visitor)
Centre for Applied Cryptographic Research, Univ. of Waterloo, Canada
Jerome A. Solinas (Visitor)
- Jerome A. Solinas
You can also search for this author inPubMed Google Scholar
Rights and permissions
About this article
Cite this article
Solinas, J.A. Efficient Arithmetic on Koblitz Curves.Designs, Codes and Cryptography19, 195–249 (2000). https://doi.org/10.1023/A:1008306223194
Issue Date:
Share this article
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative