More Web Proxy on the site http://driver.im/

Article

Curve41417: Karatsuba Revisited

Authors:

Daniel J. Bernstein,

Chitchanok Chuengsatiansup,

Tanja LangeAuthors Info & Claims

Proceedings of the 16th International Workshop on Cryptographic Hardware and Embedded Systems --- CHES 2014 - Volume 8731

Pages 316 - 334

https://doi.org/10.1007/978-3-662-44709-3_18

Published: 23 September 2014 Publication History

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 2²⁰⁰ using a prime above 2⁴⁰⁰. For comparison, this OpenSSL ECDH option is not constant-time and has a security level of only 2⁸⁰. 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.

References

[1]

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}

[2]

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

Digital Library

[3]

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

Digital Library

[4]

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

[5]

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

Digital Library

[6]

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

Digital Library

[7]

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

[8]

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

[9]

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

[10]

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

[11]

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

Digital Library

[12]

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}

Digital Library

[13]

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

[14]

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

Digital Library

[15]

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

Digital Library

[16]

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

[17]

ECC Brainpool: ECC Brainpool standard curves and curve generation 2005. http://www.ecc-brainpool.org/download/Domain-parameters.pdf. Citations in this document: 2

[18]

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

[19]

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

[20]

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

Digital Library

[21]

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

[22]

Granlund, T. ed.: GMP 5.1.3: GNU multiple precision arithmetic library 2014. http://gmplib.org. Citations in this document: 1.1

[23]

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}

Digital Library

[24]

Hamburg, M.: Fast and compact elliptic-curve cryptography 2012. http://eprint.iacr.org/2012/309. Citations in this document: 1.1

[25]

Hamburg, M.: New Ed448-Goldilocks release 2014. https://moderncrypto.org/mail-archive/curves/2014/000101.html. Citations in this document: 1.4

[26]

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

Digital Library

[27]

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

[28]

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}

[29]

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

[30]

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}

Digital Library

[31]

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}

[32]

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

Digital Library

[33]

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-571819870148:177<243:STPAEC>2.0.CO;2-3. Citations in this document: 2.2

[34]

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

[35]

National Security Agency: Suite B Cryptography / Cryptographic Interoperability 2009. http://www.nsa.gov/ia/programs/suiteb_cryptography/. Citations in this document: 2.1

[36]

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}

[37]

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}

Digital Library

[38]

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}

Digital Library

[39]

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}

Digital Library

[40]

Wang, X., Sako, K. eds.: Advances in cryptology--ASIACRYPT 2012, 18th international conference on the theory and application of cryptology and information security, Beijing, China, December 2---6, 2012, proceedings. LNCS, vol. 7658. Springer 2012. ISBN 978-3-642-34960-7. See {32}

Digital Library

[41]

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}

Digital Library

Cited By

Fotiadis GGroßschädl JRyan PZhou JChattopadhyay S(2024)X2065: Lightweight Key Exchange for the Internet of ThingsProceedings of the 10th ACM Cyber-Physical System Security Workshop10.1145/3626205.3659153(43-52)Online publication date: 2-Jul-2024
https://dl.acm.org/doi/10.1145/3626205.3659153
Sedlacek VSuchanek VDufka ASys MMatyas V(2022)DiSSECT: Distinguisher of Standard and Simulated Elliptic Curves via TraitsProgress in Cryptology - AFRICACRYPT 202210.1007/978-3-031-17433-9_21(493-517)Online publication date: 18-Jul-2022
https://dl.acm.org/doi/10.1007/978-3-031-17433-9_21
Bisheh Niasar MAzarderakhsh RKermani M(2020)Efficient Hardware Implementations for Elliptic Curve Cryptography over Curve448Progress in Cryptology – INDOCRYPT 202010.1007/978-3-030-65277-7_10(228-247)Online publication date: 13-Dec-2020
https://dl.acm.org/doi/10.1007/978-3-030-65277-7_10
Show More Cited By

Recommendations

VLSI Implementation of Double-Precision Floating-Point Multiplier Using Karatsuba Technique

The double-precision floating-point arithmetic, specifically multiplication, is a widely used arithmetic operation for many scientific and signal processing applications. In general, the double-precision floating-point multiplier requires a large 53 53 ...
Batch Binary Edwards
CRYPTO '09: Proceedings of the 29th Annual International Cryptology Conference on Advances in Cryptology

This paper sets new software speed records for high-security Diffie-Hellman computations, specifically 251-bit elliptic-curve variable-base-point scalar multiplication. In one second of computation on a $200 Core 2 Quad Q6600 CPU, this paper's software ...
A High-Speed Accelerator for Homomorphic Encryption using the Karatsuba Algorithm
Special Issue ESWEEK 2017, CASES 2017, CODES + ISSS 2017 and EMSOFT 2017

Somewhat Homomorphic Encryption (SHE) schemes can be used to carry out operations on ciphered data. In a cloud computing scenario, personal information can be processed secretly, inferring a high level of confidentiality. The principle limitation of SHE ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

Proceedings of the 16th International Workshop on Cryptographic Hardware and Embedded Systems --- CHES 2014 - Volume 8731

September 2014

615 pages

ISBN:9783662447086

Editors:
Lejla Batina
FNWI-iCIS/DS, Radboud University Nijmegen, Nijmegen, The Netherlands
,
Matthew Robshaw
Impinj, Inc., Seattle, USA

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 23 September 2014

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 29 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Fotiadis GGroßschädl JRyan PZhou JChattopadhyay S(2024)X2065: Lightweight Key Exchange for the Internet of ThingsProceedings of the 10th ACM Cyber-Physical System Security Workshop10.1145/3626205.3659153(43-52)Online publication date: 2-Jul-2024
https://dl.acm.org/doi/10.1145/3626205.3659153
Sedlacek VSuchanek VDufka ASys MMatyas V(2022)DiSSECT: Distinguisher of Standard and Simulated Elliptic Curves via TraitsProgress in Cryptology - AFRICACRYPT 202210.1007/978-3-031-17433-9_21(493-517)Online publication date: 18-Jul-2022
https://dl.acm.org/doi/10.1007/978-3-031-17433-9_21
Bisheh Niasar MAzarderakhsh RKermani M(2020)Efficient Hardware Implementations for Elliptic Curve Cryptography over Curve448Progress in Cryptology – INDOCRYPT 202010.1007/978-3-030-65277-7_10(228-247)Online publication date: 13-Dec-2020
https://dl.acm.org/doi/10.1007/978-3-030-65277-7_10
Stoffelen K(2019)Efficient Cryptography on the RISC-V ArchitectureProgress in Cryptology – LATINCRYPT 201910.1007/978-3-030-30530-7_16(323-340)Online publication date: 2-Oct-2019
https://dl.acm.org/doi/10.1007/978-3-030-30530-7_16
Scott M(2018)Missing a trickCryptography and Communications10.1007/s12095-017-0217-x10:1(5-15)Online publication date: 1-Jan-2018
https://dl.acm.org/doi/10.1007/s12095-017-0217-x
Ghatpande SGroßschädl JLiu Z(2018)A Family of Lightweight Twisted Edwards Curves for the Internet of ThingsInformation Security Theory and Practice10.1007/978-3-030-20074-9_14(193-206)Online publication date: 10-Dec-2018
https://dl.acm.org/doi/10.1007/978-3-030-20074-9_14
Genkin DValenta LYarom YThuraisingham BEvans DMalkin TXu D(2017)May the Fourth Be With YouProceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security10.1145/3133956.3134029(845-858)Online publication date: 30-Oct-2017
https://dl.acm.org/doi/10.1145/3133956.3134029
Renes JCostello CBatina L(2016)Complete Addition Formulas for Prime Order Elliptic CurvesProceedings, Part I, of the 35th Annual International Conference on Advances in Cryptology --- EUROCRYPT 2016 - Volume 966510.5555/3081770.3081786(403-428)Online publication date: 8-May-2016
https://dl.acm.org/doi/10.5555/3081770.3081786
Seo HLiu ZNogami YChoi JKim H(2016)Hybrid Montgomery ReductionACM Transactions on Embedded Computing Systems10.1145/289050215:3(1-13)Online publication date: 23-May-2016
https://dl.acm.org/doi/10.1145/2890502
Ali SCenk M(2016)A New Algorithm for Residue Multiplication Modulo $$2^{521}-1$$Proceedings of the 19th International Conference on Information Security and Cryptology - Volume 1015710.1007/978-3-319-53177-9_9(181-193)Online publication date: 30-Nov-2016
https://dl.acm.org/doi/10.1007/978-3-319-53177-9_9

View Options

View options

Figures

Tables

Media

View Table of Conten