Abstract
Elliptic curves defined over finite fields have been proposed for Diffie-Hellman type crypto systems. Koblitz has suggested to use “anomalous” elliptic curves in characteristic 2, as these are nonsupersingular and allow for efficient multiplication of points by an integer.
For anomalous curves E defined over F 2 and regarded as curves over the extension field F 2 n, a new algorithm for computing multiples of arbitrary points on E is developed. The algorithm is shown to be three times faster than double and add, is easy to implement and does not rely on precomputation or additional memory. The algorithm is used to generate efficient one-way permutations involving pairs of twisted elliptic curves by extending a construction of Kaliski to finite fields of characteristic 2.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
E. Brickell, D.M. Gordon, K.S. McCurley, D. Wilson, Fast Exponentiation with Precomputation, Eurocrypt’92, to appear.
B.S. Kaliski, Jr., One-way Permutations on Elliptic Curves, Journal of Cryptology, Vol.3, No. 3, pp.187–199, 1991.
N. Koblitz, CM-Curves with Good Cryptographic Properties, Advances in Cryptology—Crypto’91, Proceedings, pp. 279–287, Springer-Verlag, 1992.
N. Koblitz, Elliptic Curve Crypto Systems, Math. of Computation, Vol. 48, pp. 203–209, 1987.
N. Koblitz, Hyperelliptic Cryptosystems, Journal of Cryptology, Vol. 1, No. 3, pp. 139–150, 1989.
A. Menezes, T. Okamoto, S.A. Vanstone, Reducing Elliptic Curve Logarithms to Logarithms in a Finite Field, Proceedings of the 23rd ACM Symp. Theory of Computing, 1991.
V. Miller, Use of Elliptic Curves in Cryptography, Advances in Cryptology—Crypto’85, Proceedings, pp. 417–426, Springer-Verlag, 1986.
J.H. Silverman,The Arithmetic of Elliptic Curves, Graduate Texts in Mathematics, Springer-Verlag, 1986.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1993 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Meier, W., Staffelbach, O. (1993). Efficient Multiplication on Certain Nonsupersingular Elliptic Curves. In: Brickell, E.F. (eds) Advances in Cryptology — CRYPTO’ 92. CRYPTO 1992. Lecture Notes in Computer Science, vol 740. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48071-4_24
Download citation
DOI: https://doi.org/10.1007/3-540-48071-4_24
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-57340-1
Online ISBN: 978-3-540-48071-6
eBook Packages: Springer Book Archive