Abstract
It is often required in many elliptic curve cryptosystems to compute kG for a fixed point G and a random integer k. In this paper we present improved algorithms for such elliptic scalar multiplication. Implementation results on Pentium II and Alpha 21164 microprocessors are also provided to demonstrate the presented improvements in actual implementations.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bailey, D.V., Paar, C.: Optimal extension field for fast arithmetic in public key algorithms. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, pp. 472–485. Springer, Heidelberg (1998)
Bailey, D.V., Paar, C.: Inversion in Optimal Extension Fields. In: presented at The Mathematics of Public-Key Cryptography (June 1999) (see also Elliptic curve cryptosystems over large characteristic extension fields by the same authors, preprint, 1999)
Brickell, E.F., Gordon, D.M., McCurley, K.S., Wilson, D.: Fast exponentiation with precomputation. In: Rueppel, R.A. (ed.) EUROCRYPT 1992. LNCS, vol. 658, pp. 200–207. Springer, Heidelberg (1993)
Cheon, J.H., Park, S.M., Park, S.W., Kim, D.H.: Two efficient algorithms for arithmetic of elliptic curves using Frobenius map. In: Imai, H., Zheng, Y. (eds.) PKC 1998. LNCS, vol. 1431, pp. 195–202. Springer, Heidelberg (1998)
Cohen, H.: A course in computational number theory. Graduate Texts in Math, vol. 138. Springer, Heidelberg (1993); Third corrected printing (1996)
Cohen, H., Miyaji, A., Ono, T.: Efficient elliptic curve exponentiation. In: Han, Y., Quing, S. (eds.) ICICS 1997. LNCS, vol. 1334, pp. 282–290. Springer, Heidelberg (1997)
Cohen, H., Miyaji, A., Ono, T.: Efficient elliptic curve exponentiation using mixed coordinates. In: Ohta, K., Pei, D. (eds.) ASIACRYPT 1998. LNCS, vol. 1514, pp. 51–65. Springer, Heidelberg (1998)
Guajardo, J., Paar, C.: Efficient algorithms for elliptic curve cryptosystems. In: Kaliski Jr., B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 342–356. Springer, Heidelberg (1997)
Kobayashi, T., Morita, H., Kobayashi, K., Hoshino, F.: Fast elliptic curve algorithm combining Frobenius map and table reference to adapt to higher characteristic. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 176–189. Springer, Heidelberg (1999)
Koblitz, N.: CM curves with good cryptographic properties. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 279–287. Springer, Heidelberg (1992)
Lim, C.H., Lee, P.J.: More flexible exponentiation with precomputation. In: Desmedt, Y.G. (ed.) CRYPTO 1994. LNCS, vol. 839, pp. 95–107. Springer, Heidelberg (1994)
Lim, C.H., Lee, P.J.: A key recovery attack on discrete log-based schemes using a prime order subgroup. In: Kaliski Jr., B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 249–263. Springer, Heidelberg (1997)
Lim, C.H., Hwang, H.S.: Fast implementation of elliptic curve arithmetic in GF(pn). In: Imai, H., Zheng, Y. (eds.) PKC 2000. LNCS, vol. 1751. Springer, Heidelberg (2000)
Lopez, J., Dahab, R.: Improved algorithms for elliptic curve arithmetic in GF(2n). In: Tavares, S., Meijer, H. (eds.) SAC 1998. LNCS, vol. 1556, pp. 201–212. Springer, Heidelberg (1999)
Meier, W., Staffelbach, O.: Efficient multiplication on certain non-supersingular elliptic curves. In: Brickell, E.F. (ed.) CRYPTO 1992. LNCS, vol. 740, pp. 333–344. Springer, Heidelberg (1993)
Muller, V.: Fast multiplication on elliptic curves over small fields of characteristic two. J. of Cryptology 11(4), 219–234 (1998)
de Rooij, P.: Efficient exponentiation using precomputation and vector addition chains. In: De Santis, A. (ed.) EUROCRYPT 1994. LNCS, vol. 950, pp. 389–399. Springer, Heidelberg (1995)
Solinas, J.A.: An improved algorithm for arithmetic on a family of elliptic curves. In: Kaliski Jr., B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 357–371. Springer, Heidelberg (1997)
Wiener, M.J., Zuccherato, R.J.: Faster attacks on elliptic curve cryptosystems. In: Tavares, S., Meijer, H. (eds.) SAC 1998. LNCS, vol. 1556, pp. 190–200. Springer, Heidelberg (1999)
IEEE P1363: Standard Specifications for Public Key Cryptography, Working Draft (August 1999)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Lim, C.H., Hwang, H.S. (2000). Speeding Up Elliptic Scalar Multiplication with Precomputation. In: Song, J. (eds) Information Security and Cryptology - ICISC’99. ICISC 1999. Lecture Notes in Computer Science, vol 1787. Springer, Berlin, Heidelberg. https://doi.org/10.1007/10719994_9
Download citation
DOI: https://doi.org/10.1007/10719994_9
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-67380-4
Online ISBN: 978-3-540-45568-4
eBook Packages: Springer Book Archive