Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Journal of Cryptographic Engineering
Erschienen in: Journal of Cryptographic Engineering 1/2014

01.04.2014 | CHES 2013

Two is the fastest prime: lambda coordinates for binary elliptic curves

verfasst von: Thomaz Oliveira, Julio López, Diego F. Aranha, Francisco Rodríguez-Henríquez

Erschienen in: Journal of Cryptographic Engineering | Ausgabe 1/2014

Einloggen

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

search-config
loading …

Abstract

In this work, we present new arithmetic formulas for a projective version of the affine point representation \((x,x+y/x),\) for \(x\ne 0,\) which leads to an efficient computation of the scalar multiplication operation over binary elliptic curves. A software implementation of our formulas applied to a binary Galbraith–Lin–Scott elliptic curve defined over the field \(\mathbb {F}_{2^{254}}\) allows us to achieve speed records for protected/unprotected single/multi-core random-point elliptic curve scalar multiplication at the 127-bit security level. When executed on a Sandy Bridge 3.4 GHz Intel Xeon processor, our software is able to compute a single/multi-core unprotected scalar multiplication in 69,500 and 47,900 clock cycles, respectively, and a protected single-core scalar multiplication in 114,800 cycles. These numbers are improved by around 2 and 46 % on the newer Ivy Bridge and Haswell platforms, respectively, achieving in the latter a protected random-point scalar multiplication in 60,000 clock cycles.
Vorheriger Artikel Introduction to the CHES 2013 special issue
Nächster Artikel Stealthy dopant-level hardware Trojans: extended version

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Anhänge
Nur mit Berechtigung zugänglich
Fußnoten
1
The benchmarking was run on Intel platforms Xeon E31270 3.4 GHz (Sandy Bridge), Core i5 3570 3.4 GHz (Ivy Bridge), and Core i7 4770K (Haswell). In addition, our library was submitted to the ECRYPT Benchmarking of Asymmetric Systems (eBATS) where it is publicly available.
 
2
See Sect. 2.5 for a definition of the trace function \(\mathrm{Tr}(c).\)
 
3
Notice that the atomic doubling and addition operation are exclusive of the \(\lambda \)-projective coordinate system. For the sake of a fair comparison, in the second row and fifth column of Table 3, the cost of performing a non-atomic point doubling plus a mixed point addition using LD coordinates is reported.
 
4
We stress that \(k\) can be recovered at a very low computational effort. From our experiments, the scalar \(k\) could be reconstructed with cost lower than \(5\tilde{m}\).
 
5
For \(w = 4\), the method is described as follows. \(Q_5 = Q_5 + Q_7\), \(Q_3 = Q_3 + Q_5\), \(Q_1 = Q_1 + Q_3\), \(Q_7 = Q_7 + Q_5 + Q_3\), \(Q = 2Q_7 + Q_1\), which requires six point additions and one point doubling.
 
6
The pseudo-instruction Barrier refers to an OpenMP synchronization clause that forces each thread to wait until all the other threads have completed their assigned tasks.
 
Literatur
1.
Agnew, G.B., Mullin, R.C., Vanstone, S.A.: An implementation of elliptic curve cryptosystems over \(F_{2^{155}}\). IEEE J. Sel. Areas Commun. 11(5), 804–813 (1993)CrossRef
2.
Ahmadi, O., Hankerson, D., Rodríguez-Henríquez, F.: Parallel formulations of scalar multiplication on Koblitz curves. J. UCS 14(3), 481–504 (2008)MATHMathSciNet
3.
Al-Daoud, E., Mahmod, R., Rushdan, M., Kilicman, A.: A new addition formula for elliptic curves over \(GF(2^n)\). IEEE Trans. Comput. 51(8), 972–975 (2002)CrossRefMathSciNet
4.
Aranha, D.F., Faz-Hernández, A., López, J., Rodríguez-Henríquez, F.: Faster implementation of scalar multiplication on Koblitz curves. In: Hevia, A., Neven, G. (eds.) LATINCRYPT 2012, LNCS, vol. 7533, pp. 177–193. Springer, New York (2012)CrossRef
5.
Aranha, D.F., López, J., Hankerson, D.: Efficient software implementation of binary field arithmetic using vector instruction sets. In: Abdalla, M., Barreto, P.S.L.M. (eds.) LATINCRYPT 2010, LNCS, vol. 6212, pp. 144–161. Springer, New York (2010)CrossRef
6.
Avanzi, R.M., Ciet, M., Sica, F.: Faster scalar multiplication on Koblitz curves combining point halving with the Frobenius endomorphism. In: Bao, F., Deng, R.H., Zhou, J. (eds.) PKC 2004, LNCS, vol. 2947, pp. 28–40. Springer, New York (2004)
7.
Bernstein, D.J.: Curve25519: new Diffie–Hellman speed records. In: Yung, M., Dodis, Y., Kiayias, A., Malkin, T. (eds.) PKC 2006, LNCS, vol. 3958, pp. 207–228. Springer, New York (2006)
8.
9.
Bernstein, D.J., Lange, T., Farashahi, R.: Binary Edwards curves. In: Oswald, E., Rohatgi, P. (eds.) CHES 2008, LNCS, vol. 5154, pp. 244–265. Springer, New York (2008)
10.
Bos, J.W., Kleinjung, T., Niederhagen, R., Schwabe, P.: ECC2K-130 on cell CPUs. In: Bernstein, D.J., Lange, T. (eds.) AFRICACRYPT 2010, LNCS, vol. 6055, pp. 225–242. Springer, New York (2010)CrossRef
11.
Bos, J.W., Costello, C., Hisil, H., Lauter, K.: Fast cryptography in genus 2. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013, LNCS, vol. 7881, pp. 194–210. Springer, New York (2013)CrossRef
12.
Chatterjee, S., Karabina, K., Menezes, A.: A new protocol for the nearby friend problem. In: Parker, M.G. (ed.) IMACC 2009, LNCS, vol. 5921, pp. 236–251. Springer, New York (2009)
13.
Chudnovsky, D.V., Chudnovsky, G.V.: Sequences of numbers generated by addition in formal groups and new primality and factorization tests. Adv. Appl. Math. 7(4), 385–434 (1986)CrossRefMATHMathSciNet
14.
15.
Faz-Hernández, A., Longa, P., Sanchez, A.H.: Efficient and secure algorithms for GLV-based scalar multiplication and their implementation on GLV–GLS curves, In: Benaloh, J. (ed.) CT-RSA 2014. To appear (2014)
16.
Firasta, M., Buxton, M., Jinbo, P., Nasri, K., Kuo, S.: Intel AVX: New Frontiers in Performance Improvements and Energy Efficiency. White paper, Intel Corporation. http://​software.​intel.​com (2008)
17.
Fong, K., Hankerson, D., López, J., Menezes, A.: Field inversion and point halving revisited. IEEE Trans. Comput. 53(8), 1047–1059 (2004)CrossRef
18.
Galbraith, S., Lin, X., Scott, M.: Endomorphisms for faster elliptic curve cryptography on a large class of curves. J. Cryptol. 24, 446–469 (2011)CrossRefMATHMathSciNet
19.
Gallant, R.P., Lambert, R.J., Vanstone, S.A.: Faster point multiplication on elliptic curves with efficient endomorphisms. In: Kilian, J. (ed.) CRYPTO 2001, LNCS, vol. 2139, pp. 190–200. Springer, New York (2001)CrossRef
20.
Gaudry, P., Hess, F., Smart, N.P.: Constructive and destructive facets of Weil descent on elliptic curves. J. Cryptol. 15, 19–46 (2002)CrossRefMathSciNet
21.
22.
Hankerson, D., Karabina, K., Menezes, A.: Analyzing the Galbraith–Lin–Scott point multiplication method for elliptic curves over binary fields. IEEE Trans. Comput. 58(10), 1411–1420 (2009)CrossRefMathSciNet
23.
Hankerson, D., Menezes, A., Vanstone, S.: Guide to Elliptic Curve Cryptography. Springer, New York (2003)
24.
Hankerson, D., Hernandez, J., Menezes, A.: Software implementation of elliptic curve cryptography over binary fields. In: Koç, Ç.K., Paar, C. (eds.) CHES 2000, LNCS, vol. 1965, pp. 1–24. Springer, New York (2000)
25.
Hess, F.: Generalising the GHS attack on the elliptic curve discrete logarithm problem. LMS J. Comput. Math. 7, 167–192 (2004)CrossRefMATHMathSciNet
26.
27.
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)CrossRefMATHMathSciNet
28.
Joye, M., Tunstall, M.: Exponent recoding and regular exponentiation algorithms. In: Preneel, B. (ed.) AFRICACRYPT 2009, LNCS, vol. 5580, pp. 334–349. Springer, New York (2009)CrossRef
29.
Kim, D., Lim, S.: Integer decomposition for fast scalar multiplication on elliptic curves. In: Nyberg, K., Heys, H. (eds.) SAC 2003, LNCS, vol. 2595, pp. 13–20. Springer, New York (2003)
30.
31.
King, B.: An improved implementation of elliptic curves over \(GF(2^n)\) when using projective point arithmetic. In: Vaudenay, S., Youssef, A. (eds.) SAC 2001, LNCS, vol. 2259, pp. 134–150. Springer, New York (2001)
32.
Knudsen, E.: Elliptic scalar multiplication using point halving. In: Lam, K.Y., Okamoto, E., Xing, C. (eds.) ASIACRYPT99, LNCS, vol. 1716, pp. 135–149. Springer, New York (1999)
33.
Knuth, D.E.: The Art of Computer Programming: Seminumerical Algorithms, vol. 2. Addison-Wesley, Boston (1997)
34.
35.
Lim, C.H., Hwang, H.S.: Speeding up elliptic scalar multiplication with precomputation. In: Song, J. (ed.) ICISC 1999, LNCS, vol. 1787, pp. 102–119. Springer, New York (2000)
36.
Longa, P., Sica, F.: Four-dimensional Gallant–Lambert–Vanstone scalar multiplication. In: Wang, X., Sako, K. (eds.) ASIACRYPT 2012, LNCS, vol. 7658, pp. 718–739. Springer, New York (2012)CrossRef
37.
Longa, P., Sica, F.: Four-dimensional Gallant–Lambert–Vanstone scalar multiplication. J. Cryptol. (2014)
38.
López, J., Dahab, R.: Improved algorithms for elliptic curve arithmetic in GF(\(2^n\)). In: Tavares, S.E., Meijer, H. (eds.) SAC 1998, LNCS, vol. 1556, pp. 201–212. Springer, New York (1998)
39.
40.
López, J., Dahab, R.: New point compression algorithms for binary curves. In: IEEE Information Theory Workshop (ITW 2006), pp. 126–130. IEEE Press, New York (2006)
41.
Park, Y.H., Jeong, S., Kim, C., Lim, J.: An alternate decomposition of an integer for faster point multiplication on certain elliptic curves. In: Naccache, D., Paillier, P. (eds.) PKC 2002, LNCS, vol. 2274, pp. 323–334. Springer, New York (2002)
42.
Rodríguez-Henríquez, F., Morales-Luna, G., López, J.: Low-complexity bit-parallel square root computation over GF(\(2^{m}\)) for all trinomials. IEEE Trans. Comput. 57(4), 472–480 (2008)CrossRefMathSciNet
43.
Schroeppel, R.: Cryptographic elliptic curve apparatus and method. US Patent 2002/6490352 B1, 2000
44.
Schroeppel, R.: Elliptic curve point halving wins big. In: Proceedings of 2nd Midwest Arithmetical Geometry in Cryptography Workshop (2000)
45.
Schroeppel, R.: Automatically solving equations in finite fields. US Patent 2002/0055962 A1, 2002
46.
Taverne, J., Faz-Hernández, A., Aranha, D.F., Rodríguez-Henríquez, F., Hankerson, D., López, J.: Speeding scalar multiplication over binary elliptic curves using the new carry-less multiplication instruction. J. Cryptogr. Eng. 1, 187–199 (2011)CrossRef
Metadaten
Titel
Two is the fastest prime: lambda coordinates for binary elliptic curves
verfasst von
Thomaz Oliveira
Julio López
Diego F. Aranha
Francisco Rodríguez-Henríquez
Publikationsdatum
01.04.2014
Verlag
Springer Berlin Heidelberg
Erschienen in
Journal of Cryptographic Engineering / Ausgabe 1/2014
Print ISSN: 2190-8508
Elektronische ISSN: 2190-8516
DOI
https://doi.org/10.1007/s13389-013-0069-z

Weitere Artikel der Ausgabe 1/2014

Journal of Cryptographic Engineering 1/2014 Zur Ausgabe

CHES 2013

Using Bleichenbacher’s solution to the hidden number problem to attack nonce leaks in 384-bit ECDSA: extended version

CHES 2013

Stealthy dopant-level hardware Trojans: extended version

CHES 2013

Masking vs. multiparty computation: how large is the gap for AES?

CHES 2013

On measurable side-channel leaks inside ASIC design primitives

CHES 2013

Introduction to the CHES 2013 special issue