Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Journal of Cryptographic Engineering
Published in: Journal of Cryptographic Engineering 4/2016

01-11-2016 | Regular Paper

Selecting elliptic curves for cryptography: an efficiency and security analysis

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

Published in: Journal of Cryptographic Engineering | Issue 4/2016

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

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.
next article Harder, better, faster, stronger: elliptic curve discrete logarithm computations on FPGAs

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now
Appendix
Available only for authorised users
Footnotes
1
Cryptographic libraries with support for generic-prime field arithmetic (e.g., using Montgomery arithmetic) are fully compatible with the proposed curves.
 
2
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].
 
3
Except for when \(w=2\), where this comes for free.
 
4
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.
 
5
Again, except for when \(w=2\), where this comes for free.
 
6
Again, we note that when \(wv \mid t\), an extra precomputed point is needed.
 
7
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\).
 
8
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/​.
 
9
This cost assumes the use of the simplest, most secure implementation approach, i.e., each ephemeral key is used once and then discarded.
 
10
We also corrected some typos in [18] that were pointed out in [6].
 
11
We did not optimize (1) aggressively; we simply grouped common subexpressions and employed obvious operation scheduling—it is likely that there are faster routes.
 
Literature
1.
Acar, T., Shumow, D.: Modular reduction without pre-computation for special moduli. Technical report. Microsoft Research (2010)
2.
3.
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/​
4.
5.
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)
6.
7.
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)
8.
Bernstein, D.J., Birkner, P., Lange, T., Peters, C.: ECM using Edwards curves. Math. Comput. 82(282), 1139–1179 (2013)
9.
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.
13.
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.
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.
25.
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.
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.
32.
33.
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.
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.
47.
48.
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.
53.
Solinas, J.A.: Generalized Mersenne numbers. Technical report CORR 99–39, Centre for Applied Cryptographic Research, University of Waterloo (1999)
54.
55.
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.
58.
Walter, C.D.: Montgomery exponentiation needs no final subtractions. Electron. Lett. 35(21), 1831–1832 (1999)CrossRef
Metadata
Title
Selecting elliptic curves for cryptography: an efficiency and security analysis
Authors
Joppe W. Bos
Craig Costello
Patrick Longa
Michael Naehrig
Publication date
01-11-2016
Publisher
Springer Berlin Heidelberg
Published in
Journal of Cryptographic Engineering / Issue 4/2016
Print ISSN: 2190-8508
Electronic ISSN: 2190-8516
DOI
https://doi.org/10.1007/s13389-015-0097-y

Other articles of this Issue 4/2016

Journal of Cryptographic Engineering 4/2016 Go to the issue

Regular Paper

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

Regular Paper

Hardware attacks: an algebraic approach

Regular Paper

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

Regular Paper

SPA on Rabin variant with public key

Premium Partner

    Image Credits