Abstract
This paper introduces constant-time ARM Cortex-A8 ECDH software that (1) is faster than the fastest ECDH option in the latest version of OpenSSL but (2) achieves a security level above 2200 using a prime above 2400. For comparison, this OpenSSL ECDH option is not constant-time and has a security level of only 280. The new speeds are achieved in a quite different way from typical prime-field ECC software: they rely on a synergy between Karatsuba’s method and choices of radix smaller than the CPU word size.
Chapter PDF
Similar content being viewed by others
Keywords
References
Benaloh, J. (ed.): Topics in cryptology—CT-RSA 2014—The cryptographer’s track at the RSA conference 2014, San Francisco, CA, USA, February 25–28, 2014, proceedings. LNCS, vol. 8366. Springer (2014). ISBN 978-3-319-04851-2. See [19]
Bernstein, D.J.: Curve25519: new Diffie-Hellman speed records. In: PKC 2006 [41], pp. 207–228 (2006). http://cr.yp.to/papers.html#curve25519 . Citations in this document: §1
Bernstein, D.J.: Batch binary Edwards. In: Crypto 2009 [23], pp. 317–336 (2009). http://cr.yp.to/papers.html#bbe . Citations in this document: §4.2
Bernstein, D.J., Chuengsatiansup, C., Lange, T., Schwabe, P.: Kummer strikes back: new DH speed records (2014). https://eprint.iacr.org/2014/134 . Citations in this document: §1, §1, §1, §1.1, §1.1, §1.3
Bernstein, D.J., Duif, N., Lange, T., Schwabe, P., Yang, B.-Y.: High-speed highsecurity signatures. In: CHES 2011 [38] (2011). http://eprint.iacr.org/2011/368 . Citations in this document: §3.2
Bernstein, D.J., Lange, T.: Faster addition and doubling on elliptic curves. In: Asiacrypt 2007 [30], pp. 29–50 (2007). http://eprint.iacr.org/2007/286 . Citations in this document: §2.2
Bernstein, D.J., Lange, T.: Security dangers of the NIST curves (2013). http://cr.yp.to/talks/2013.09.16/slides-djb-20130916-a4.pdf . Citations in this document: §1
Bernstein, D.J., Lange, T. (eds.): eBACS: ECRYPT Benchmarking of Cryptographic Systems, accessed 13 June 2014 (2014). http://bench.cr.yp.to . Citations in this document: §1.3
Bernstein, D.J., Lange, T. (eds.): Explicit Formulas Database, accessed 13 June 2014 (2014). http://hyperelliptic.org/EFD . Citations in this document: §3.1, §A
Bernstein, D.J., Lange, T.: SafeCurves: choosing safe curves for elliptic-curve cryptography, accessed 13 June 2014 (2014). http://safecurves.cr.yp.to . Citations in this document: §2, §2.1
Bernstein, D.J., Schwabe, P.: NEON crypto. In: CHES 2012 [39], pp. 320–339 (2012). http://cr.yp.to/papers.html#neoncrypto . Citations in this document: §1, §1.1, §1.1, §1.3
Bertoni, G., Coron, J.-S. (eds.): Cryptographic hardware and embedded systems—CHES 2013—15th international workshop, Santa Barbara, CA, USA, August 20–23, 2013, proceedings. LNCS, vol. 8086. Springer (2013). ISBN 978-3-642-40348-4. See [14]
Bos, J.W., Costello, C., Hisil, H., Lauter, K.: Fast cryptography in genus 2. In: Eurocrypt 2013 [28], pp. 194–210 (2013). http://eprint.iacr.org/2012/670 . Citations in this document: §1.1
Bos, J.W., Costello, C., Hisil, H., Lauter, K.: High-performance scalar multiplication using 8-dimensional GLV/GLS decomposition. In: CHES 2013 [12], pp. 331–348 (2013). http://eprint.iacr.org/2013/146 . Citations in this document: §1.3
Bos, J.W., Montgomery, P.L., Shumow, D., Zaverucha, G.M.: Montgomery multiplication using vector instructions. In: SAC 2013 [31], pp. 471–489 (2014). http://eprint.iacr.org/2013/519 . Citations in this document: §1.1
Costello, C., Hisil, H., Smith, B.: Faster compact Diffie–Hellman: endomorphisms on the x-line. In: Eurocrypt 2014 [36], pp. 183–200 (2014). http://eprint.iacr.org/2013/692 . Citations in this document: §1.1
ECC Brainpool: ECC Brainpool standard curves and curve generation (2005). http://www.ecc-brainpool.org/download/Domain-parameters.pdf . Citations in this document: §2
Edwards, H.M.: A normal form for elliptic curves. Bulletin of the American Mathematical Society 44, 393–422 (2007). http://www.ams.org/bull/2007-44-03/S0273-0979-07-01153-6/home.html . Citations in this document: §2.2
Faz-Hernández, A., Longa, P., Sánchez, A.H.: Efficient and secure algorithms for GLV-based scalar multiplication and their implementation on GLV-GLS curves. In: CT-RSA 2014 [1], pp. 1–27 (2014). http://eprint.iacr.org/2013/158 . Citations in this document: §1.1
Gaudry, P., Schost, É.: Genus 2 point counting over prime fields. Journal of Symbolic Computation 47, 368–400 (2012). http://www.csd.uwo.ca/~eschost/publications/countg2.pdf . Citations in this document: §1
Granger, R., Kleinjung, T., Zumbrägel, J.: Breaking “128-bit secure” supersingular binary curves (or how to solve discrete logarithms in F\(_{2^{4 \cdot 1223}}\) and F\(_{2^{12 \cdot 367}}\)). In: Crypto 2014, to appear (2014). http://eprint.iacr.org/2014/119 . Citations in this document: §1.5
Granlund, T. (ed.): GMP 5.1.3: GNU multiple precision arithmetic library (2014). http://gmplib.org . Citations in this document: §1.1
Halevi, S. (ed.): Advances in cryptology—CRYPTO 2009, 29th annual international cryptology conference, Santa Barbara, CA, USA, August 16–20, 2009, proceedings. LNCS, vol. 5677. Springer (2009). See [3]
Hamburg, M.: Fast and compact elliptic-curve cryptography (2012). http://eprint.iacr.org/2012/309 . Citations in this document: §1.1
Hamburg, M.: New Ed448-Goldilocks release (2014). https://moderncrypto.org/mail-archive/curves/2014/000101.html . Citations in this document: §1.4
Hisil, H., Wong, K.K.-H., Carter, G., Dawson, E.: Twisted Edwards curves revisited. In: Asiacrypt 2008 [37], pp. 326–343 (2008). http://eprint.iacr.org/2008/522 . Citations in this document: §3.1
Institute of Electrical and Electronics Engineers: IEEE 1363-2000: Standard specifications for public key cryptography, Preliminary draft at (2000). http://grouper.ieee.org/groups/1363/P1363/draft.html . Citations in this document: §2
Johansson, T., Nguyen, P.Q. (eds.): Advances in cryptology—EUROCRYPT 2013, 32nd annual international conference on the theory and applications of cryptographic techniques, Athens, Greece, May 26–30, 2013, proceedings. LNCS, vol. 7881. Springer (2013). ISBN 978-3-642-38347-2. See [13]
Karatsuba, A.A., Ofman, Y.: Multiplication of multidigit numbers on automata. Soviet Physics Doklady 7, 595–596 (1963). ISSN 0038-5689. Citations in this document: §1.1, §4.2
Kurosawa, K. (ed.): Advances in cryptology—ASIACRYPT 2007, 13th international conference on the theory and application of cryptology and information security, Kuching, Malaysia, December 2–6, 2007, proceedings. LNCS, vol. 4833. Springer (2007). ISBN 978-3-540-76899-9. See [6]
Lange, T., Lauter, K., Lisonek, P. (eds.): Selected areas in cryptography—SAC 2013—20th international conference, Burnaby, BC, Canada, August 14–16, 2013, revised selected papers. LNCS, vol. 8282. Springer (2014). ISBN 978-3-662-43413-0. See [15]
Longa, P., Sica, F.: Four-dimensional Gallant–Lambert–Vanstone scalar multiplication. In: Asiacrypt 2012 [40], pp. 718–739 (2012). http://eprint.iacr.org/2011/608 . Citations in this document: §1.1
Montgomery, P.L.: Speeding the Pollard and elliptic curve methods of factorization. Mathematics of Computation 48, 243–264 (1987). ISSN 0025-5718. MR 88e:11130. http://links.jstor.org/sici?sici=0025-5718(198701)48:177<243:STPAEC>2.0.CO;2-3. Citations in this document: §2.2
National Institute for Standards and Technology: Digital signature standard. Federal Information Processing Standards Publication 186-2 (2000). http://csrc.nist.gov/publications/fips/archive/fips186-2/fips186-2.pdf . Citations in this document: §1.2
National Security Agency: Suite B Cryptography / Cryptographic Interoperability (2009). http://www.nsa.gov/ia/programs/suiteb_cryptography/ . Citations in this document: §2.1
Nguyen, P.L., Oswald, E. (eds.): Advances in cryptology—EUROCRYPT 2014— 33rd annual international conference on the theory and applications of cryptographic techniques, Copenhagen, Denmark, May 11–15, 2014, proceedings. LNCS, vol. 8441. Springer (2014). ISBN 978-3-642-55219-9. See [16]
Pieprzyk, J. (ed.): Advances in cryptology—ASIACRYPT 2008, 14th international conference on the theory and application of cryptology and information security, Melbourne, Australia, December 7–11, 2008. LNCS, vol. 5350 (2008). ISBN 978-3-540-89254-0. See [26]
Preneel, B., Takagi, T. (eds.): Cryptographic hardware and embedded systems—CHES 2011, 13th international workshop, Nara, Japan, September 28–October 1, 2011, proceedings. LNCS, vol. 6917. Springer (2011). ISBN 978-3-642-23950-2. See [5]
Prouff, E., Schaumont, P. (eds.): Cryptographic hardware and embedded systems—CHES 2012—14th international workshop, Leuven, Belgium, September 9–12, 2012, proceedings. LNCS, vol. 7428. Springer (2012). ISBN 978-3-642-33026-1. See [11]
Wang, X., Sako, K. (eds.): Advances in cryptology—ASIACRYPT 2012, 18th international conference on the theory and application of cryptology and information security, Bei**g, China, December 2–6, 2012, proceedings. LNCS, vol. 7658. Springer (2012). ISBN 978-3-642-34960-7. See [32]
Yung, M., Dodis, Y., Kiayias, A., Malkin, T. (eds.): Public key cryptography—9th international conference on theory and practice in public-key cryptography, New York, NY, USA, April 24–26, 2006, proceedings. LNCS, vol. 3958. Springer (2006). ISBN 978-3-540-33851-2. See [2]
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bernstein, D.J., Chuengsatiansup, C., Lange, T. (2014). Curve41417: Karatsuba Revisited. In: Batina, L., Robshaw, M. (eds) Cryptographic Hardware and Embedded Systems – CHES 2014. CHES 2014. Lecture Notes in Computer Science, vol 8731. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-44709-3_18
Download citation
DOI: https://doi.org/10.1007/978-3-662-44709-3_18
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-44708-6
Online ISBN: 978-3-662-44709-3
eBook Packages: Computer ScienceComputer Science (R0)