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
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Tightly CCA-Secure Encryption Without Pairings Kapitel lesen Erstes Kapitel lesen

2016 | OriginalPaper | Buchkapitel

Complete Addition Formulas for Prime Order Elliptic Curves

verfasst von : Joost Renes, Craig Costello, Lejla Batina

Erschienen in: Advances in Cryptology – EUROCRYPT 2016

Verlag: Springer Berlin Heidelberg

Einloggen

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

search-config
loading …

Abstract

An elliptic curve addition law is said to be complete if it correctly computes the sum of any two points in the elliptic curve group. One of the main reasons for the increased popularity of Edwards curves in the ECC community is that they can allow a complete group law that is also relatively efficient (e.g., when compared to all known addition laws on Edwards curves). Such complete addition formulas can simplify the task of an ECC implementer and, at the same time, can greatly reduce the potential vulnerabilities of a cryptosystem. Unfortunately, until now, complete addition laws that are relatively efficient have only been proposed on curves of composite order and have thus been incompatible with all of the currently standardized prime order curves.
In this paper we present optimized addition formulas that are complete on every prime order short Weierstrass curve defined over a field k with \(\mathrm{char}(k) \ne 2,3\). Compared to their incomplete counterparts, these formulas require a larger number of field additions, but interestingly require fewer field multiplications. We discuss how these formulas can be used to achieve secure, exception-free implementations on all of the prime order curves in the NIST (and many other) standards.

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
Vorheriges Kapitel Reverse-Engineering the S-Box of Streebog, Kuznyechik and STRIBOBr1
Nächstes Kapitel New Complexity Trade-Offs for the (Multiple) Number Field Sieve Algorithm in Non-Prime Fields
Fußnoten
1
See ec_smpl.c in crypto/ec/ in the latest release at http://​openssl.​org/​source/​.
 
3
mul_int denotes the cost of Bitcoin’s specialized function that multiplies field elements by small integers.
 
5
These are addition formulas that also work for point doublings.
 
6
Notation here is the same as in Table 1, except for \(\mathbf{m_{3b}}\) which denotes multiplication by the curve constant 3b.
 
7
We thank Emmanuel Thomé whose careful read-through resulted in a \(1\mathbf{m}_a\) saving in all three of the explicit formulas for the general case.
 
8
We note that it is not technically correct to call “mixed” additions complete, since \(Z_2=1\) precludes the second point being the point at infinity. However, this is not a problem in practice as the second point is typically taken from a precomputed lookup table consisting of small multiples of the input point \(P \ne \mathcal {O}\). For prime order curves, these small multiples can never be at infinity.
 
9
When \(\mathbb {F}_q\) is a large prime field, \(a=-3\) covers 1/2 (resp. 1/4) of the isomorphism classes for \(q \equiv 3 \mod 4\) (resp. \(q \equiv 1 \mod 4\)) – see [21, Sect. 3].
 
10
Our experimentation did suggest that computing (1) in any reasonable way with fewer than 12 generic multiplications appears to be difficult.
 
11
Lower bidegree addition laws are possible for other embeddings (i.e., models) of E in the case where E has a k-rational torsion structure – see [47].
 
Literatur
1.
2.
3.
4.
Arène, C., Kohel, D., Ritzenthaler, C.: Complete addition laws on abelian varieties. LMS J. Comput. Math. 15, 308–316 (2012)MathSciNetCrossRefMATH
5.
Barreto, P.S.L.M., Naehrig, M.: Pairing-friendly elliptic curves of prime order. In: Preneel, B., Tavares, S. (eds.) SAC 2005. LNCS, vol. 3897, pp. 319–331. Springer, Heidelberg (2006)CrossRef
6.
Batina, L., Bruin-Muurling, G., Örs, S.: Flexible hardware design for RSA and elliptic curve cryptosystems. In: Okamoto, T. (ed.) CT-RSA 2004. LNCS, vol. 2964, pp. 250–263. Springer, Heidelberg (2004)CrossRef
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, Heidelberg (2006)CrossRef
8.
Bernstein, D.J., Birkner, P., Joye, M., Lange, T., Peters, C.: Twisted edwards curves. In: Vaudenay, S. (ed.) AFRICACRYPT 2008. LNCS, vol. 5023, pp. 389–405. Springer, Heidelberg (2008)CrossRef
9.
Bernstein, D.J., Chuengsatiansup, C., Kohel, D., Lange, T.: Twisted hessian curves. In: Lauter, K., Rodríguez-Henríquez, F. (eds.) LatinCrypt 2015. LNCS, vol. 9230, pp. 269–294. Springer, Heidelberg (2015)CrossRef
10.
Bernstein, D.J., Chuengsatiansup, C., Lange, T.: Curve41417: karatsuba revisited. In: Batina, L., Robshaw, M. (eds.) CHES 2014. LNCS, vol. 8731, pp. 316–334. Springer, Heidelberg (2014)
11.
Bernstein, D.J., Hamburg, M., Krasnova, A., Lange, T.: Elligator: elliptic-curve points indistinguishable from uniform random strings. In: Sadeghi, A., Gligor, V.D., Yung, M., (eds.) ACM SIGSAC Conference on Computer and Communications Security, CCS 2013, Berlin, Germany, 4–8 November 2013, pp. 967–980. ACM (2013)
12.
Bernstein, D.J., Lange, T.: Faster addition and doubling on elliptic curves. In: Kurosawa, K. (ed.) ASIACRYPT 2007. LNCS, vol. 4833, pp. 29–50. Springer, Heidelberg (2007)CrossRef
13.
14.
15.
16.
17.
Bos, J.W., Halderman, J.A., Heninger, N., Moore, J., Naehrig, M., Wustrow, E.: Elliptic curve cryptography in practice. In: Christin and Safavi-Naini [26], pp. 157–175
18.
Bosma, W., Cannon, J.J., Playoust, C.: The magma algebra system I: the user language. J. Symb. Comput. 24(3/4), 235–265 (1997)MathSciNetCrossRefMATH
19.
Bosma, W., Lenstra, H.W.: Complete systems of two addition laws for elliptic curves. J. Number Theory 53(2), 229–240 (1995)MathSciNetCrossRefMATH
20.
Brier, E., Joye, M.: Weierstraß elliptic curves and side-channel attacks. In: Naccache, D., Paillier, P. (eds.) PKC 2002. LNCS, vol. 2274, pp. 335–345. Springer, Heidelberg (2002)CrossRef
21.
Brier, E., Joye, M.: Fast point multiplication on elliptic curves through isogenies. In: Fossorier, M.P.C., Høholdt, T., Poli, A. (eds.) AAECC 2003. LNCS, vol. 2643, pp. 43–50. Springer, Heidelberg (2003)CrossRef
22.
23.
24.
Chen, G., Bai, G., Chen, H.: A high-performance elliptic curve cryptographic processor for general curves over GF(p) based on a systolic arithmetic unit. IEEE Trans. Circ. Syst. II Express Briefs 54(5), 412–416 (2007)CrossRef
25.
26.
Christin, N., Safavi-Naini, R. (eds.): FC 2014. LNCS, vol. 8437. Springer, Heidelberg (2014)MATH
27.
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. 51–65. Springer, Heidelberg (1998)CrossRef
28.
29.
Coron, J.-S.: Resistance against differential power analysis for elliptic curve cryptosystems. In: Koç, Ç.K., Paar, C. (eds.) CHES 1999. LNCS, vol. 1717, p. 292. Springer, Heidelberg (1999)CrossRef
30.
31.
32.
Fan, J., Gierlichs, B., Vercauteren, F.: To infinity and beyond: combined attack on ECC using points of low order. In: Preneel, B., Takagi, T. (eds.) CHES 2011. LNCS, vol. 6917, pp. 143–159. Springer, Heidelberg (2011)CrossRef
33.
Fan, J., Verbauwhede, I.: An updated survey on secure ECC implementations: attacks, countermeasures and cost. In: Naccache, D. (ed.) Cryphtography and Security: From Theory to Applications. LNCS, vol. 6805, pp. 265–282. Springer, Heidelberg (2012)CrossRef
34.
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, Heidelberg (2001)CrossRef
35.
36.
Güneysu, T., Paar, C.: Ultra high performance ECC over NIST primes on commercial FPGAs. In: Oswald, E., Rohatgi, P. (eds.) CHES 2008. LNCS, vol. 5154, pp. 62–78. Springer, Heidelberg (2008)CrossRef
37.
38.
Hamburg, M.: Decaf: eliminating cofactors through point compression. In: Gennaro, R., Robshaw, M. (eds.) Advances in Cryptology – CRYPTO 2015. LNCS, vol. 9215, pp. 705–723. Springer, Heidelberg (2015)CrossRef
39.
40.
Hankerson, D., Menezes, A.J., Vanstone, S.: Guide to Elliptic Curve Cryptography. Springer Science and Business Media, Heidelberg (2006)MATH
41.
42.
Hu, Z., Longa, P., Xu, M.: Implementing the 4-dimensional GLV method on GLS elliptic curves with j-invariant 0. Des. Codes Crypt. 63(3), 331–343 (2012)MathSciNetCrossRefMATH
43.
Izu, T., Takagi, T.: Exceptional procedure attack on elliptic curve cryptosystems. In: Desmedt, Y. (ed.) Public Key Cryptography - PKC 2003. LNCS, vol. 2567, pp. 224–239. Springer, Heidelberg (2003)CrossRef
44.
Joye, M., Tunstall, M.: Exponent recoding and regular exponentiation algorithms. In: Preneel, B. (ed.) AFRICACRYPT 2009. LNCS, vol. 5580, pp. 334–349. Springer, Heidelberg (2009)CrossRef
45.
Käsper, E.: Fast elliptic curve cryptography in openSSL. In: Danezis, G., Dietrich, S., Sako, K. (eds.) FC 2011 Workshops 2011. LNCS, vol. 7126, pp. 27–39. Springer, Heidelberg (2012)CrossRef
46.
Kocher, P.C.: Timing attacks on implementations of diffie-hellman, RSA, DSS, and other systems. In: Koblitz, N. (ed.) CRYPTO 1996. LNCS, vol. 1109, pp. 104–113. Springer, Heidelberg (1996)
47.
48.
Lange, H., Ruppert, W.: Complete systems of addition laws on abelian varieties. Inventiones mathematicae 79(3), 603–610 (1985)MathSciNetCrossRefMATH
49.
Lim, C.H., Lee, P.J.: More flexible exponentiation with precomputation. In: Desmedt, Y.G. (ed.) CRYPTO 1994. LNCS, vol. 839, pp. 95–107. Springer, Heidelberg (1994)
50.
Liu, Z., Seo, H., Großschädl, J., Kim, H.: Efficient implementation of NIST-compliant elliptic curve cryptography for sensor nodes. In: Qing, S., Zhou, J., Liu, D. (eds.) ICICS 2013. LNCS, vol. 8233, pp. 302–317. Springer, Heidelberg (2013)CrossRef
51.
Longa, P., Gebotys, C.: Efficient techniques for high-speed elliptic curve cryptography. In: Mangard, S., Standaert, F. (eds.) CHES 2010. LNCS, vol. 6225, pp. 80–94. Springer, Heidelberg (2010)CrossRef
52.
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)
53.
54.
55.
56.
57.
Okeya, K., Takagi, T.: The width-\(w\) NAF method provides small memory and fast elliptic scalar multiplications secure against side channel attacks. In: Joye, M. (ed.) CT-RSA 2003. LNCS, vol. 2612, pp. 328–342. Springer, Heidelberg (2003)CrossRef
58.
59.
Szczechowiak, P., Oliveira, L.B., Scott, M., Collier, M., Dahab, R.: NanoECC: testing the limits of elliptic curve cryptography in sensor networks. In: Verdone, R. (ed.) EWSN 2008. LNCS, vol. 4913, pp. 305–320. Springer, Heidelberg (2008)CrossRef
60.
61.
Tibouchi, M.: Elligator squared: Uniform points on elliptic curves of prime order as uniform random strings. In: Christin and Safavi-Naini [26], pp. 139–156
Metadaten
Titel
Complete Addition Formulas for Prime Order Elliptic Curves
verfasst von
Joost Renes
Craig Costello
Lejla Batina
Copyright-Jahr
2016
Verlag
Springer Berlin Heidelberg
Buch
Advances in Cryptology – EUROCRYPT 2016

Print ISBN: 978-3-662-49889-7

Electronic ISBN: 978-3-662-49890-3

Copyright-Jahr: 2016

DOI
https://doi.org/10.1007/978-3-662-49890-3_16

Premium Partner

    Bildnachweise