Skip to main content
Erschienen in: Designs, Codes and Cryptography 1-2/2017

02.08.2016

Optimal software-implemented Itoh–Tsujii inversion for \(\mathbb {F}_{2^{m}}\)

verfasst von: Jeremy Maitin-Shepard

Erschienen in: Designs, Codes and Cryptography | Ausgabe 1-2/2017

Einloggen, um Zugang zu erhalten

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Field inversion in \(\mathbb {F}_{2^{m}}\) dominates the cost of modern software implementations of certain elliptic curve cryptographic operations, such as point encoding/hashing into elliptic curves (Brown et al. in: Submission to NIST, 2008; Brown in: IACR Cryptology ePrint Archive 2008:12, 2008; Aranha et al. in: Cryptology ePrint Archive, Report 2014/486, 2014) Itoh–Tsujii inversion using a polynomial basis and precomputed table-based multi-squaring has been demonstrated to be highly effective for software implementations (Taverne et al. in: CHES 2011, 2011; Oliveira et al. in: J Cryptogr Eng 4(1):3–17, 2014; Aranha et al. in: Cryptology ePrint Archive, Report 2014/486, 2014), but the performance and memory use depend critically on the choice of addition chain and multi-squaring tables, which in prior work have been determined only by suboptimal ad-hoc methods and manual selection. We thoroughly investigated the performance/memory tradeoff for table-based linear transforms used for efficient multi-squaring. Based upon the results of that investigation, we devised a comprehensive cost model for Itoh–Tsujii inversion and a corresponding optimization procedure that is empirically fast and provably finds globally-optimal solutions. We tested this method on eight binary fields commonly used for elliptic curve cryptography; our method found lower-cost solutions than the ad-hoc methods used previously, and for the first time enables a principled exploration of the time/memory tradeoff of inversion implementations.
Fußnoten
1
As we are primarily concerned with elliptic curve cryptography, binary field sizes of interest range from about \(m = 127\) to about \(m = 571\).
 
2
It is straightforward to verify that this equivalence relation respects all search operations.
 
3
Concretely, we do not expand a state during the search if we have already expanded an equivalent state.
 
Literatur
1.
Zurück zum Zitat Ahmadi O., Hankerson D., Rodrıguez-Henrıquez F.: Parallel formulations of scalar multiplication on Koblitz curves. J. Univ. Comput. Sci. 14(3), 481–504 (2008). Ahmadi O., Hankerson D., Rodrıguez-Henrıquez F.: Parallel formulations of scalar multiplication on Koblitz curves. J. Univ. Comput. Sci. 14(3), 481–504 (2008).
2.
Zurück zum Zitat Aranha D.F., López J., Hankerson D.: Efficient software implementation of binary field arithmetic using vector instruction sets. In: Progress in Cryptology—LATINCRYPT 2010, pp. 144–161. Springer, Berlin (2010). Aranha D.F., López J., Hankerson D.: Efficient software implementation of binary field arithmetic using vector instruction sets. In: Progress in Cryptology—LATINCRYPT 2010, pp. 144–161. Springer, Berlin (2010).
4.
Zurück zum Zitat Bahig H.M.: Improved generation of minimal addition chains. Computing 78(2), 161–172 (2006). Bahig H.M.: Improved generation of minimal addition chains. Computing 78(2), 161–172 (2006).
5.
Zurück zum Zitat Bluhm M., Gueron S.: Fast software implementation of binary elliptic curve cryptography. IACR Cryptology ePrint Archive 2013, 741 (2013). Bluhm M., Gueron S.: Fast software implementation of binary elliptic curve cryptography. IACR Cryptology ePrint Archive 2013, 741 (2013).
6.
Zurück zum Zitat Bos J.W., Kleinjung T., Niederhagen R., Schwabe P.: Ecc2k-130 on cell cpus. In: Progress in Cryptology—AFRICACRYPT 2010, pp. 225–242. Springer, Berlin (2010). Bos J.W., Kleinjung T., Niederhagen R., Schwabe P.: Ecc2k-130 on cell cpus. In: Progress in Cryptology—AFRICACRYPT 2010, pp. 225–242. Springer, Berlin (2010).
7.
Zurück zum Zitat Brown D.R.L.: The encrypted elliptic curve hash. IACR Cryptology ePrint Archive 2008, 12 (2008). Brown D.R.L.: The encrypted elliptic curve hash. IACR Cryptology ePrint Archive 2008, 12 (2008).
8.
Zurück zum Zitat Brown D.R.L., Antipa A., Campagna M., Struik R.: ECOH: the elliptic curve only hash. Submission to NIST (2008). Brown D.R.L., Antipa A., Campagna M., Struik R.: ECOH: the elliptic curve only hash. Submission to NIST (2008).
10.
Zurück zum Zitat Fong K., Hankerson D., López J., Menezes A.: Field inversion and point halving revisited. IEEE Trans. Comput. 53(8), 1047–1059 (2004). Fong K., Hankerson D., López J., Menezes A.: Field inversion and point halving revisited. IEEE Trans. Comput. 53(8), 1047–1059 (2004).
11.
Zurück zum Zitat Guajardo J., Paar C.: Itoh-Tsujii inversion in standard basis and its application in cryptography and codes. Des. Codes Cryptogr. 25(2), 207–216 (2002). Guajardo J., Paar C.: Itoh-Tsujii inversion in standard basis and its application in cryptography and codes. Des. Codes Cryptogr. 25(2), 207–216 (2002).
12.
Zurück zum Zitat Hankerson D., Vanstone S., Menezes A.J.: Guide to Elliptic Curve Cryptography. Springer, Berlin (2004). Hankerson D., Vanstone S., Menezes A.J.: Guide to Elliptic Curve Cryptography. Springer, Berlin (2004).
13.
Zurück zum Zitat Itoh T., Tsujii S.: A fast algorithm for computing multiplicative inverses in GF(\(2^m\)) using normal bases. Inf. Comput. 78(3), 171–177 (1988). Itoh T., Tsujii S.: A fast algorithm for computing multiplicative inverses in GF(\(2^m\)) using normal bases. Inf. Comput. 78(3), 171–177 (1988).
14.
Zurück zum Zitat Järvinen K.U.: On repeated squarings in binary fields. In: Selected Areas in Cryptography, pp. 331–349. Springer, Berlin (2009). Järvinen K.U.: On repeated squarings in binary fields. In: Selected Areas in Cryptography, pp. 331–349. Springer, Berlin (2009).
17.
Zurück zum Zitat Oliveira T., López J., Aranha D.F., Rodríguez-Henríquez F.: Two is the fastest prime: lambda coordinates for binary elliptic curves. J. Cryptogr. Eng. 4(1), 3–17 (2014). Oliveira T., López J., Aranha D.F., Rodríguez-Henríquez F.: Two is the fastest prime: lambda coordinates for binary elliptic curves. J. Cryptogr. Eng. 4(1), 3–17 (2014).
18.
Zurück zum Zitat Paoloni G.: How to benchmark code execution times on Intel IA-32 and IA-64 instruction set architectures. Tech. Rep. (2010). Paoloni G.: How to benchmark code execution times on Intel IA-32 and IA-64 instruction set architectures. Tech. Rep. (2010).
19.
Zurück zum Zitat Rebeiro C., Mukhopadhyay D.: High speed compact elliptic curve cryptoprocessor for FPGA platforms. In: Progress in Cryptology—INDOCRYPT 2008, pp. 376–388. Springer, Berlin (2008). Rebeiro C., Mukhopadhyay D.: High speed compact elliptic curve cryptoprocessor for FPGA platforms. In: Progress in Cryptology—INDOCRYPT 2008, pp. 376–388. Springer, Berlin (2008).
20.
Zurück zum Zitat Russell S., Norvig P.: Artificial Intelligence: A Modern Approach, Prentice Hall Series in Artificial Intelligence. Prentice Hall, Upper Saddle River (2010). Russell S., Norvig P.: Artificial Intelligence: A Modern Approach, Prentice Hall Series in Artificial Intelligence. Prentice Hall, Upper Saddle River (2010).
21.
Zurück zum Zitat Shacham H., Boneh D.: Improving SSL handshake performance via batching. In: Topics in Cryptology CT-RSA 2001, pp. 28–43. Springer, Berlin (2001). Shacham H., Boneh D.: Improving SSL handshake performance via batching. In: Topics in Cryptology CT-RSA 2001, pp. 28–43. Springer, Berlin (2001).
22.
Zurück zum Zitat Taverne J., Faz-Hernández A., Aranha D.F., Rodríguez-Henríquez F., Hankerson D., López J.: Software implementation of binary elliptic curves: impact of the carry-less multiplier on scalar multiplication. In: Cryptographic Hardware and Embedded Systems—CHES 2011, pp. 108–123. Springer, Heidelberg (2011). Taverne J., Faz-Hernández A., Aranha D.F., Rodríguez-Henríquez F., Hankerson D., López J.: Software implementation of binary elliptic curves: impact of the carry-less multiplier on scalar multiplication. In: Cryptographic Hardware and Embedded Systems—CHES 2011, pp. 108–123. Springer, Heidelberg (2011).
23.
Zurück zum Zitat Thurber E.G.: Efficient generation of minimal length addition chains. SIAM J. Comput. 28(4), 1247–1263 (1999). Thurber E.G.: Efficient generation of minimal length addition chains. SIAM J. Comput. 28(4), 1247–1263 (1999).
Metadaten
Titel
Optimal software-implemented Itoh–Tsujii inversion for
verfasst von
Jeremy Maitin-Shepard
Publikationsdatum
02.08.2016
Verlag
Springer US
Erschienen in
Designs, Codes and Cryptography / Ausgabe 1-2/2017
Print ISSN: 0925-1022
Elektronische ISSN: 1573-7586
DOI
https://doi.org/10.1007/s10623-016-0260-1

Weitere Artikel der Ausgabe 1-2/2017

Designs, Codes and Cryptography 1-2/2017 Zur Ausgabe

Premium Partner