nach oben

Journal of Cryptographic Engineering

Erschienen in:

01.11.2016 | Regular Paper

Selecting elliptic curves for cryptography: an efficiency and security analysis

verfasst von: Joppe W. Bos, Craig Costello, Patrick Longa, Michael Naehrig

Erschienen in: Journal of Cryptographic Engineering | Ausgabe 4/2016

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

We select a set of elliptic curves for cryptography and analyze our selection from a performance and security perspective. This analysis complements recent curve proposals that suggest (twisted) Edwards curves by also considering the Weierstrass model. Working with both Montgomery-friendly and pseudo-Mersenne primes allows us to consider more possibilities which help to improve the overall efficiency of base field arithmetic. Our Weierstrass curves are backwards compatible with current implementations of prime order NIST curves, while providing improved efficiency and stronger security properties. We choose algorithms and explicit formulas to demonstrate that our curves support constant-time, exception-free scalar multiplications, thereby offering high practical security in cryptographic applications. Our implementation shows that variable-base scalar multiplication on the new Weierstrass curves at the 128-bit security level is about 1.4 times faster than the recent implementation record on the corresponding NIST curve. For practitioners who are willing to use a different curve model and sacrifice a few bits of security, we present a collection of twisted Edwards curves with particularly efficient arithmetic that are up to 1.42, 1.26 and 1.24 times faster than the new Weierstrass curves at the 128-, 192- and 256-bit security levels, respectively. Finally, we discuss how these curves behave in a real-world protocol by considering different scalar multiplication scenarios in the transport layer security protocol. The proposed curves and the results of the analysis are intended to contribute to the recent efforts towards recommending new elliptic curves for Internet standards.

Nächster Artikel Harder, better, faster, stronger: elliptic curve discrete logarithm computations on FPGAs

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

Nur mit Berechtigung zugänglich

Cryptographic libraries with support for generic-prime field arithmetic (e.g., using Montgomery arithmetic) are fully compatible with the proposed curves.

The only instance where the first twisted Edwards curve we found did not fulfill all of the SafeCurves requirements was in the search for ed-383-mers: the constant \(A=1629146\) corresponds to a curve-twist pair with \(\#E_A=4r\) and \(E_A'=4r'\), where \(r\) and \(r'\) are both prime, but the embedding degree of \(E_A\) with respect to \(r\) is \((r-1)/188\), which fails to meet the minimum requirement of \((r-1)/100\) imposed in [12].

Except for when \(w=2\), where this comes for free.

We note that this cost increases by a single point addition when \(wv \mid t\), since an extra precomputed point is needed in this case.

Again, except for when \(w=2\), where this comes for free.

Again, we note that when \(wv \mid t\), an extra precomputed point is needed.

Validating that \(x_1 \in \mathbf{{F}}_p\) corresponds to \(E_A\) would incur the small relative cost of an exponentiation and a few multiplications: namely, we reject \(x_1\) if \((x_1^3+Ax_1^2+x_1)^{(p-1)/2} = -1\).

A version of the library (known as MSR ECCLib [44]) which supports a subset of the curves presented in this work is publicly available at http://research.microsoft.com/en-us/downloads/149804d4-b5f5-496f-9a17-a013b242c02d/.

This cost assumes the use of the simplest, most secure implementation approach, i.e., each ephemeral key is used once and then discarded.

We also corrected some typos in [18] that were pointed out in [6].

We did not optimize (1) aggressively; we simply grouped common subexpressions and employed obvious operation scheduling—it is likely that there are faster routes.

Acar, T., Shumow, D.: Modular reduction without pre-computation for special moduli. Technical report. Microsoft Research (2010)

Ahmadi, O., Granger, R.: On isogeny classes of edwards curves over finite fields. J. Number Theory 132(6), 1337–1358 (2012)MathSciNetCrossRefMATH

Aranha, D.F., Barreto, P.S.L.M., Pereira, G.C.C.F., Ricardini, J.E.: A note on high-security general-purpose elliptic curves. Cryptology ePrint Archive, Report 2013, 647 (2013). http://eprint.iacr.org/

Bernstein, D.J.: Can we avoid tests for zero in fast elliptic-curve arithmetic? (2006). http://cr.yp.to/papers.html#curvezero

Bernstein, D.J.: Curve25519: New Diffie–Hellman speed records. In: Yung, M., Dodis, Y., Kiayias, A., Malkin, T. (eds.) Public Key Cryptography—PKC 2006, vol. 3958 of LNCS, pp. 207–228. Springer, Heidelberg (2006)

Bernstein, D.J.: Counting points as a video game, 2010. Slides of a talk given at Counting Points: Theory, Algorithms and Practice, April 19, University of Montreal. http://cr.yp.to/talks/2010.04.19/slides.pdf

Bernstein, D.J., Birkner, P., Joye, M., Lange, T., Peters, C.: Twisted Edwards curves. In: Vaudenay, S. (ed.) AFRICACRYPT, vol. 5023 of LNCS, pp. 389–405. Springer, Berlin (2008)

Bernstein, D.J., Birkner, P., Lange, T., Peters, C.: ECM using Edwards curves. Math. Comput. 82(282), 1139–1179 (2013)

Bernstein, D.J., Duif, N., Lange, T., Schwabe, P., Yang, B.-Y.: High-speed high-security signatures. J. Cryptogr. Eng. 2(2), 77–89 (2012)CrossRefMATH

10.

Bernstein, D.J., Hamburg, M., Krasnova, A., Lange, T.: Elligator: elliptic-curve points indistinguishable from uniform random strings. In: ACM conference on computer and communications security (2013)

11.

Bernstein, D.J., Lange, T.: Faster addition and doubling on elliptic curves. In: Kurosawa, K. (ed.) ASIACRYPT, vol. 4833 of LNCS, pp. 29–50. Springer, Berlin (2007)

12.

Bernstein, D.J., Lange, T.: SafeCurves: choosing safe curves for elliptic-curve cryptography. http://safecurves.cr.yp.to. Accessed 16 Oct 2013

13.

Bernstein, D.J., Lange, T. (eds.): eBACS: ECRYPT benchmarking of cryptographic systems. http://bench.cr.yp.to. Accessed 3 Feb 2014

14.

Blake-Wilson, S., Bolyard, N., Gupta, V., Hawk, C., Moeller, B.: Elliptic curve cryptography (ECC) cipher suites for transport layer security (TLS). RFC 4492 (2006)

15.

Bos, J.W., Costello, C., Hisil, H., Lauter, K.: Fast cryptography in genus 2. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT, vol. 7881 of LNCS, pp. 194–210. Springer, Berlin (2013)

16.

Bos, J.W., Halderman, J.A., Heninger, N., Moore, J., Naehrig, M., Wustrow, E.: Elliptic curve cryptography in practice. In: Christin, N., Safavi-Naini, R. (eds.) Financial Cryptography and Data Security, vol. 8437 of LNCS, pp. 157–175. Springer, Berlin (2014)

17.

Bosma, W., Cannon, J., Playoust, C.: The Magma algebra system. I. The user language. J. Symb. Comput. 24(3–4), 235–265 (1997). Computational algebra and number theory (London, 1993)MathSciNetCrossRefMATH

18.

Bosma, W., Lenstra, H.W.: Complete systems of two addition laws for elliptic curves. J. Number Theory 53(2), 229–240 (1995)MathSciNetCrossRefMATH

19.

Brumley, B.B., Hakala, R.M.: Cache-timing template attacks. In: Matsui, M. (ed.) ASIACRYPT, vol. 5912 of LNCS, pp. 667–684. Springer, Berlin (2009)

20.

Brumley, D., Boneh, D.: Remote timing attacks are practical. In: Mangard, S. Standaert, F.-X. (eds.) Proceedings of the 12th USENIX security symposium, vol. 6225 of LNCS, pp. 80–94. Springer (2003)

21.

Certicom Research.: Standards for efficient cryptography 2: recommended elliptic curve domain parameters. Standard SEC2, Certicom (2000)

22.

Chevallier-Mames, B., Ciet, M., Joye, M.: Low-cost solutions for preventing simple side-channel analysis: side-channel atomicity. IEEE Trans. Comput. 53(6), 760–768 (2004)CrossRefMATH

23.

Chudnovsky, D., Chudnovsky, G.: Sequences of numbers generated by addition in formal groups and new primality and factorization tests. Adv. Appl. Math. 7(4), 385–434 (1986)MathSciNetCrossRefMATH

24.

ECC Brainpool.: ECC Brainpool Standard Curves and Curve Generation. http://www.ecc-brainpool.org/download/Domain-parameters.pdf (2005)

25.

Edwards, H.M.: A normal form for elliptic curves. Bull. Am. Math. Soc. 44, 393–422 (2007)MathSciNetCrossRefMATH

26.

Faugère, J.-C., Perret, L., Petit, C., Renault, G.: Improving the complexity of index calculus algorithms in elliptic curves over binary fields. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT, vol. 7237 of LNCS, pp. 27–44. Springer, Berlin (2012)

27.

Faz-Hernández, A., Longa, P., Sánchez, A.: Efficient and secure algorithms for GLV-based scalar multiplication and their implementation on GLV-GLS curves (extended version). J. Cryptogr. Eng. 5(1), 31–52 (2015)

28.

Feng, M., Zhu, B., Xu, M., Li, S.: Efficient comb elliptic curve multiplication methods resistant to power analysis. In: Cryptology ePrint Archive, Report 2005/222 (2005). http://eprint.iacr.org/2005/222

29.

Fouque, P.-A., Joux, A., Tibouchi, M.: Injective encodings to elliptic curves. In: Boyd, C., Simpson, L. (eds.) ACISP, vol. 7959 of LNCS, pp. 203–218. Springer, Berlin (2013)

30.

Gallant, R.P., Lambert, R.J., Vanstone, S.A.: Faster point multiplication on elliptic curves with efficient endomorphisms. In: Kilian, J. (ed.) CRYPTO, vol. 2139 of LNCS, pp. 190–200. Springer, Berlin (2001)

31.

Gueron, S., Krasnov, V.: Fast prime field elliptic curve cryptography with 256 bit primes. Cryptology ePrint Archive, Report 2013/816 (2013). http://eprint.iacr.org/

32.

Hamburg, M.: Fast and compact elliptic-curve cryptography. Cryptology ePrint Archive, Report 2012/309 (2012). http://eprint.iacr.org/

33.

Hamburg, M.: Twisting Edwards curves with isogenies. Cryptology ePrint Archive, Report 2014/027 (2014). http://eprint.iacr.org/

34.

Hankerson, D., Menezes, A., Vanstone, S.: Guide to Elliptic Curve Cryptography. Springer Verlag, Berlin (2004)MATH

35.

Hisil, H., Wong, K.K.-H., Carter, G., Dawson, E.: Twisted Edwards curves revisited. In: Pieprzyk, J. (ed.) Asiacrypt 2008, vol. 5350 of LNCS, pp. 326–343. Springer, Heidelberg (2008)

36.

Joye, M., Tunstall, M.: Exponent recoding and regular exponentiation algorithms. In: Joye, M. (ed.) Proceedings of Africacrypt 2003, vol. 5580 of LNCS, pp. 334–349. Springer, Berlin (2009)

37.

Knežević, M., Vercauteren, F., Verbauwhede, I.: Speeding up bipartite modular multiplication. In: Hasan, M., Helleseth, T. (eds.) Arithmetic of Finite Fields—WAIFI 2010, vol. 6087 of LNCS, pp. 166–179. Springer, Berlin/Heidelberg (2010)

38.

Kocher, P.C.: Timing attacks on implementations of Diffie–Hellman, RSA, DSS, and other systems. In: Koblitz, N. (ed.) Crypto 1996, vol. 1109 of LNCS, pp. 104–113. Springer, Heidelberg (1996)

39.

Lenstra, A.K.: Generating RSA moduli with a predetermined portion. In: Ohta, K., Pei, D. (eds.) Asiacrypt’98, vol. 1514 of LNCS, pp. 1–10. Springer, Berlin/Heidelberg (1998)

40.

Lim, C.H., Lee, P.J.: More flexible exponentiation with precomputation. In: Desmedt, Y. (ed.) CRYPTO, vol. 839 of LNCS, pp. 95–107. Springer, Berlin (1994)

41.

Longa, P., Gebotys, C.: Efficient techniques for high-speed elliptic curve cryptography. In: Mangard, S., Standaert, F.-X. (eds.) Proceedings of CHES 2010, vol. 6225 of LNCS, pp. 80–94. Springer, Berlin (2010)

42.

Longa, P., Miri, A.: New composite operations and precomputation scheme for elliptic curve cryptosystems over prime fields. In: Cramer, R. (ed.) Proceedings of PKC 2008, vol. 4939 of LNCS, pp. 229–247. Springer, Berlin (2008)

43.

Meloni, N.: New point addition formulae for ECC applications. In: Carlet, C., Sunar, B. (eds.) Workshop on Arithmetic of Finite Fields (WAIFI), vol. 4547 of LNCS, pp. 189–201. Springer, Berlin (2007)

44.

Microsoft Research.: MSR Elliptic Curve Cryptography Library (MSR ECCLib) (2014). http://research.microsoft.com/en-us/projects/nums

45.

Möller, B.: Algorithms for multi-exponentiation. In: Vaudenay, S., Youssef, A.M. (eds.) Selected Areas in Cryptography, vol. 2259 of LNCS, pp. 165–180. Springer, Berlin (2001)

46.

Montgomery, P.L.: Modular multiplication without trial division. Math. Comput. 44(170), 519–521 (1985)MathSciNetCrossRefMATH

47.

Montgomery, P.L.: Speeding the Pollard and elliptic curve methods of factorization. Math. Comput. 48(177), 243–264 (1987)MathSciNetCrossRefMATH

48.

National Security Agency.: Fact sheet NSA Suite B Cryptography. http://www.nsa.gov/ia/programs/suiteb_cryptography/index.shtml (2009)

49.

Okeya, K., Takagi, T.: The width-\(w\) NAF method provides small memory and fast elliptic curve scalars multiplications against side-channel attacks. In: Joye, M. (ed.) Proceedings of CT-RSA 2003, vol. 2612 of LNCS, pp. 328–342. Springer, Berlin (2003)

50.

Osvik, D.A., Shamir, A., Tromer, E.: Cache attacks and countermeasures: the case of AES. In: Pointcheval, D. (ed.) CT-RSA, vol. 3860 of LNCS, pp. 1–20. Springer, Berlin (2006)

51.

Schoof, R.: Counting points on elliptic curves over finite fields. Journal de théorie des nombres de Bordeaux 7(1), 219–254 (1995)

52.

Shumow, D., Ferguson, N.: On the possibility of a back door in the NIST SP800-90 dual ec prng. http://rump2007.cr.yp.to/15-shumow.pdf (2007)

53.

Solinas, J.A.: Generalized Mersenne numbers. Technical report CORR 99–39, Centre for Applied Cryptographic Research, University of Waterloo (1999)

54.

Solinas, J.A.: Efficient arithmetic on Koblitz curves. Des. Codes Cryptogr. 19, 195–249 (2000)MathSciNetCrossRefMATH

55.

The New York Times: Government announces steps to restore confidence on encryption standards. http://bits.blogs.nytimes.com/2013/09/10/government-announces-steps-to-restore-confidence-on-encryption-standards (2013)

56.

Tibouchi, M.: Elligator squared: uniform points on elliptic curves of prime order as uniform random strings. Cryptology ePrint Archive, Report 2014/043 (2014) http://eprint.iacr.org/

57.

U.S. Department of Commerce/National Institute of Standards and Technology: Digital signature standard (DSS). FIPS-186-4 (2013). http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf

58.

Walter, C.D.: Montgomery exponentiation needs no final subtractions. Electron. Lett. 35(21), 1831–1832 (1999)CrossRef

Titel: Selecting elliptic curves for cryptography: an efficiency and security analysis
verfasst von: Joppe W. Bos
Craig Costello
Patrick Longa
Michael Naehrig
Publikationsdatum: 01.11.2016
Verlag: Springer Berlin Heidelberg
Erschienen in: Journal of Cryptographic Engineering / Ausgabe 4/2016
Print ISSN: 2190-8508
Elektronische ISSN: 2190-8516
DOI: https://doi.org/10.1007/s13389-015-0097-y

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 4/2016

SPA on Rabin variant with public key

Harder, better, faster, stronger: elliptic curve discrete logarithm computations on FPGAs

Hardware attacks: an algebraic approach

RunFein: a rapid prototyping framework for Feistel and SPN-based block ciphers