Elliptic curve cryptography (ECC) is one of the most promising public-key techniques in terms of short key size and various crypto protocols. For this reason, many studies on the implementation of ECC on resource-constrained devices within a practical execution time have been conducted. To this end, we must focus on scalar multiplication, which is the most expensive operation in ECC. A number of studies have proposed pre-computation and advanced scalar multiplication using a non-adjacent form (NAF) representation, and more sophisticated approaches have employed a width-w NAF representation and a modified pre-computation table. In this paper, we propose a new pre-computation method in which zero occurrences are much more frequent than in previous methods. This method can be applied to ordinary group scalar multiplication, but it requires large pre-computation table, so we combined the previous method with ours for practical purposes. This novel structure establishes a new feature that adjusts speed performance and table size finely, so we can customize the pre-computation table for our own purposes. Finally, we can establish a customized look-up table for embedded microprocessors.
References
[1]
Cohen, H.; Frey, G.; Avanzi, R.; Doche, C.; Lange, T.; Nguyen, K.; Vercauteren, F. Handbook of Elliptic and Hyperelliptic Curve Cryptography; Taylor and Francis Group LLC: Boca Raton, FL, USA, 2006.
[2]
Hankerson, D.; Menezes, A.; Vanstone, S. Guide to Elliptic Curve Cryptography; Springer: New York, NY, USA, 2004.
[3]
Silverman, J.H. The Arithmetic of Elliptic Curves; Springer: Berlin, Germany, 1986; Volume 106.
Miller, V.S. Use of Elliptic Curves in Cryptography. Proceedings of the International Cryptology Conference (CRYPTO 1985), Santa Barbara, CA, USA, 18–22 August 1985; Williams, H.C., Ed.; Springer: Heidelberg, Germany, 1986; Volume 218, pp. 417–426.
[6]
Brickell, E.F.; Gordon, D.M.; McCurley, K.S.; Wilson, D.B. Fast Exponentiation with PrecomputationExtended Abstract. Proceedings of the International Conference on Cryptology in Europe (EUROCRYPT 1992), Balatonfred, Hungary, 24–28 May 1992; Rueppel, R.A., Ed.; Springer: Heidelberg, Germany, 1993; Volume 658, pp. 200–207.
[7]
Lim, C.H.; Lee, P.J. More Flexible Exponentiation with Precomputation. Proceedings of the International Cryptology Conference (CRYPTO 1994), Santa Barbara, CA, USA, 21– 25 August 1994; Desmedt, Y.G., Ed.; Springer: Heidelberg, Germany, 1994. LNCS; Volume 839, pp. 95–107.
[8]
Tsaur, W.J.; Chou, C.H. Efficient algorithm for speeding up the computations of elliptic curve cryptosystem. Appl. Math. Comput 2005, 168, 1045–1064, doi:10.1016/j.amc.2004.10.010.
[9]
Sakai, Y.; Sakurai, K. Speeding up elliptic scalar multiplication using multidoubling. IEICE Trans. Inf. Syst. 2002, E-84-A, 1075–1083.
[10]
Mohamed, N.A.F.; Hashim, M.H.A.; Hutter, M. Improved Fixed-Base Comb Method for Fast Scalar Multiplication. Proceedings of the International Conference on Cryptology in Africa (AFRICACRYPT 2012), Morocco, 10– 12 July 2012; Mitrokotsa, A., Vaudenay, S., Eds.; Springer: Heidelberg, Germany, 2012. LNCS; Volume 7374, pp. 342–359.
[11]
A Statistical Test Suite for the Validation of Random Number Generators and Pseudo Random Number Generators for Cryptographic Applications Version sts-2.1. National Institute of Standards and Technology (NIST). Available online: http://csrc.nist.gov/groups/ST/toolkit/rng/index.html (on accessed 22 July 2013).
