Abstract
Elliptic curve cryptosystems have attracted much attention in recent years and one of major interests in ECC is to develop fast algorithms for field/elliptic curve arithmetic. In this paper we present various improvement techniques for field arithmetic in GF(pn)(p a prime), in particular, fast field multiplication and inversion algorithms, and provide our implementation results on Pentium II and Alpha 21164 microprocessors.
Chapter PDF
Similar content being viewed by others
References
Agnew, G.B., Mullin, R.C., Vanstone, S.A.: An implementation of elliptic curve cryptosystems over F\(_{2^155}\). IEEE J. Selected Areas in Commum. 11(5), 804–813 (1993)
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.: Elliptic curve cryptosystems over large characteristic extension fields (1999) (preprint)
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. 50–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.: Elliptic curve cryptosystems. Math. Comp. 48, 203–209 (1987)
Koblitz, N.: CM curves with good cryptographic properties. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 279–287. Springer, Heidelberg (1992)
Koyama, K., Tsuruoka, Y.: Speeding up elliptic cryptosystems using a signed binary method. In: Brickell, E.F. (ed.) CRYPTO 1992. LNCS, vol. 740, pp. 345–357. Springer, Heidelberg (1993)
Knuth, D.E.: The art of Computer Programming: Seminumerical Algorithms, 3rd edn. Addison Wesley, Reading (1998)
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 elliptic scalar multiplication with precomputation (1999) (preprint)
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)
Lopez, J., Dahab, R.: Fast multiplication on elliptic curves over GF(2m) without precomputation. In: Koç, Ç.K., Paar, C. (eds.) CHES 1999. LNCS, vol. 1717, p. 316. 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)
Miller, V.S.: Use of elliptic curves in cryptography. In: Williams, H.C. (ed.) CRYPTO 1985. LNCS, vol. 218, pp. 417–426. Springer, Heidelberg (1986)
Montgomery, P.L.: Speeding the Pollard and elliptic curve methods of factorization. Math. of Computation 48(177), 243–264 (1987)
Muller, V.: Fast multiplication on elliptic curves over small fields of characteristic two. J. of Cryptology 11(4), 219–234 (1998)
Schroeppel, A., Orman, H., O’Malley, S., Spatschek, O.: Fast key exchange with elliptic curve systems. In: Coppersmith, D. (ed.) CRYPTO 1995. LNCS, vol. 963, pp. 43–56. 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)
de Win, E., Bosselaers, A., Vandenberghe, S.: A fast software implementation for arithmetic operations in GF(2n). In: Kim, K.-c., Matsumoto, T. (eds.) ASIACRYPT 1996. LNCS, vol. 1163, pp. 65–76. Springer, Heidelberg (1996)
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 (October 1998)
ANSI X9.62: The elliptic curve digital signature algorithm, Working Draft (October 1998)
ANSI X9.63: Elliptic curve key agreement and key transport protocols, Working Draft (October 1998)
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). Fast Implementation of Elliptic Curve Arithmetic in GF(p n). In: Imai, H., Zheng, Y. (eds) Public Key Cryptography. PKC 2000. Lecture Notes in Computer Science, vol 1751. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-46588-1_27
Download citation
DOI: https://doi.org/10.1007/978-3-540-46588-1_27
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-66967-8
Online ISBN: 978-3-540-46588-1
eBook Packages: Springer Book Archive