Abstract
We describe an implementation of binary field arithmetic written in the C programming language. Even though the implementation targets 32-bit CPUs, the results can be applied also to CPUs with different granularity.
We begin with separate routines for each operand size in words to minimize performance penalties that have a bigger relative impact for shorter operands – such as those used to implement modern curve based cryptography. We then proceed to use techniques specific to operand size in bits for several field sizes.
This results in an implementation of field arithmetic where the curve representing field multiplication performance closely resembles the theoretical quadratic bit-complexity that can be expected for small inputs.
This has important practical consequences: For instance, it will allow us to compare the performance of the arithmetic on curves of different genera and defined over fields of different sizes without worrying about penalties introduced by field arithmetic and concentrating on the curve arithmetic itself. Moreover, the cost of field inversion is very low, making the use of affine coordinates in curve arithmetic more interesting. These applications will be mentioned.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Avanzi, R.: Aspects of hyperelliptic curves over large prime fields in software implementations. In: Joye, M., Quisquater, J.-J. (eds.) CHES 2004. LNCS, vol. 3156, pp. 148–162. Springer, Heidelberg (2004)
Avanzi, R., Cohen, H., Doche, C., Frey, G., Lange, T., Nguyen, K., Vercauteren, F.: The Handbook of Elliptic and Hyperelliptic Curve Cryptography. CRC Press, Boca Raton (2005)
Fan, X., Wollinger, T., Wang, Y.: Efficient Doubling on Genus 3 Curves over Binary Fields. IACR ePrint 2005/228
Fong, K., Hankerson, D., López, J., Menezes, A.: Field Inversion and Point Halving Revisited. IEEE Trans. Computers 53(8), 1047–1059 (2004)
Guyot, C., Kaveh, K., Patankar, V.M.: Explicit algorithm for the arithmetic on the hyperelliptic Jacobians of genus 3. J. Ramanujan Math. Soc. 19(2), 75–115 (2004)
Hankerson, D., López-Hernandez, J., Menezes, A.: Software Implementation of Elliptic Curve Cryprography over Binary Fields. In: Paar, C., Koç, Ç.K. (eds.) CHES 2000. LNCS, vol. 1965, pp. 1–24. Springer, Heidelberg (2000)
Karatsuba, A., Ofman, Y.: Multiplication of Multidigit Numbers on Automata. Soviet Physics - Doklady 7, 595–596 (1963)
King, B.: An Improved Implementation of Elliptic Curves over GF(2n) when Using Projective Point Arithmetic. In: Vaudenay, S., Youssef, A.M. (eds.) SAC 2001. LNCS, vol. 2259, pp. 134–150. Springer, Heidelberg (2001)
Knuth, D.: The Art of Computer Programming, 3rd edn. Seminumerical Algorithms, vol. 2. Addison Wesley Longman, Redwood City (1998)
Lange, T.: Efficient Arithmetic on Genus 2 Hyperelliptic Curves over Finite Fields via Explicit Formulae. Cryptology ePrint Archive, Report 2002/121
Lange, T., Stevens, M.: Efficient doubling for genus two curves over binary fields. In: Handschuh, H., Hasan, M.A. (eds.) SAC 2004. LNCS, vol. 3357, pp. 170–181. Springer, Heidelberg (2005)
Lim, C., Lee, P.: More flexible exponentiation with precomputation. In: Desmedt, Y.G. (ed.) CRYPTO 1994. LNCS, vol. 839, pp. 95–107. Springer, Heidelberg (1994)
López, J., Dahab, R.: High-speed software multiplication in \(F_{2^m}\). In: Roy, B., Okamoto, E. (eds.) INDOCRYPT 2000. LNCS, vol. 1977, pp. 203–212. Springer, Heidelberg (2000)
Pelzl, J., Wollinger, T., Guajardo, J., Paar, C.: Hyperelliptic curve cryptosystems: closing the perfomance gap to elliptic curves (Update). IACR ePrint 2003/026
Pelzl, J., Wollinger, T., Paar, C.: Low cost Security: Explicit Formulae for Genus 4 Hyperelliptic Curves. In: Matsui, M., Zuccherato, R.J. (eds.) SAC 2003. LNCS, vol. 3006, pp. 1–16. Springer, Heidelberg (2004)
Pippenger, N.: On the evaluation of powers and related problems (preliminary version). 17th Annual Symp. on Foundations of Comp. Sci, pp. 258–263. IEEE Computer Society, Los Alamitos (1976)
Schönhage, A., Grotefeld, A.F.W., Vetter, E.: Fast Algorithms–A Multitape Turing Machine Implementation. BI Wissenschafts-Verlag, Mannheim (1994)
Schroeppel, R., Orman, H., O’Malley, S., Spatscheck, O.: Fast key exchange with elliptic curve systems. In: Coppersmith, D. (ed.) CRYPTO 1995. LNCS, vol. 963, pp. 43–56. Springer, Heidelberg (1995)
Shoup, V.: NTL: A Library for doing number theory. URL: http://shoup.net/ntl/
Sun Corporation’s Elliptic Curve Cryptography contributions to OpenSSL. Available at http://research.sun.com/projects/crypto/
Weimerskirch, A., Stebila, D., Shantz, S.C.: Generic GF(2m) Arithmetic in Software and its Application to ECC. In: Safavi-Naini, R., Seberry, J. (eds.) ACISP 2003. LNCS, vol. 2727, pp. 79–92. Springer, Heidelberg (2003)
Wollinger, T.: Software and Hardware Implementation of Hyperelliptic Curve Cryptosystems. Ph.D. Thesis, Ruhr-Universität Bochum, Germany (2004)
Wollinger, T., Pelzl, J., Paar, C.: Cantor versus Harley: Optimization and Analysis of Explicit Formulae for Hyperelliptic Curve Cryptosystems. IEEE Transactions on Computers (To appear)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Avanzi, R., Thériault, N. (2007). Effects of Optimizations for Software Implementations of Small Binary Field Arithmetic. In: Carlet, C., Sunar, B. (eds) Arithmetic of Finite Fields. WAIFI 2007. Lecture Notes in Computer Science, vol 4547. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-73074-3_7
Download citation
DOI: https://doi.org/10.1007/978-3-540-73074-3_7
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-73073-6
Online ISBN: 978-3-540-73074-3
eBook Packages: Computer ScienceComputer Science (R0)