nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

How to (Pre-)Compute a Ladder

Improving the Performance of X25519 and X448

verfasst von : Thomaz Oliveira, Julio López, Hüseyin Hışıl, Armando Faz-Hernández, Francisco Rodríguez-Henríquez

Erschienen in: Selected Areas in Cryptography – SAC 2017

Verlag: Springer International Publishing

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

In the RFC 7748 memorandum, the Internet Research Task Force specified a Montgomery-ladder scalar multiplication function based on two recently adopted elliptic curves, “curve25519” and “curve448”. The purpose of this function is to support the Diffie-Hellman key exchange algorithm that will be included in the forthcoming version of the Transport Layer Security cryptographic protocol. In this paper, we describe a ladder variant that permits to accelerate the fixed-point multiplication function inherent to the Diffie-Hellman key pair generation phase. Our proposal combines a right-to-left version of the Montgomery ladder along with the pre-computation of constant values directly derived from the base-point and its multiples. To our knowledge, this is the first proposal of a Montgomery ladder procedure for prime elliptic curves that admits the extensive use of pre-computation. In exchange of very modest memory resources and a small extra programming effort, the proposed ladder obtains significant speedups for software implementations. Moreover, our proposal fully complies with the RFC 7748 specification. A software implementation of the X25519 and X448 functions using our pre-computable ladder yields an acceleration factor of roughly 1.20, and 1.25 when implemented on the Haswell and the Skylake micro-architectures, respectively.

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 Efficient Reductions in Cyclotomic Rings - Application to Ring-LWE Based FHE Schemes

Nächstes Kapitel HILA5: On Reliability, Reconciliation, and Error Correction for Ring-LWE Encryption

Here, we are considering an ideal but unrealistic scenario. In practice, an inappropriate choice of the elliptic curve parameters, the prime p, the order r, the implementation of the scalar multiplication algorithm, among many other aspects, could disqualify this statement.

It is also possible to express the u-coordinate of the resulting point \(R_i = 2R_i,\) for \(i \in \{0,1\},\) using only the u-coordinate of the operand P, an operation known as differential doubling.

Where \(\mathbf m _\mathbf{a24 }\) stands for one multiplication by the constant \(a_{24}\).

The description is closely related to [23, Sect. 5].

Notice that in general an Montgomery elliptic curve has the form, \(B v^2 = u^3+A u^2+u\).

For the sake of simplicity, in the remaining of this paper it will be assumed that h is a small power of two.

In fact, given that the difference of the point operands \(P_i - R_1\) is variable, the \(\mathbf m _\mathbf{uP }\) operations were changed into two general multiplications and were included in the \(\mathbf m \) operation count.

The benchmarking reports in [3] shows that the library of Chou [8] currently holds the speed record on computing the scalar multiplication over Curve25519. However, the author decided to embed the field arithmetic functions into the ladder step, in a single assembly code. Isolating the field operations would be impractical and could alter the author’s original intentions.

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). https://doi.org/10.1007/11745853_14 CrossRef

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

Bernstein, D.J., Lange, T.: eBACS: ECRYPT Benchmarking of Cryptographic Systems. https://bench.cr.yp.to. Accessed Mar 2017

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

Bernstein, D.J., Lange, T.: Montgomery curves and the montgomery ladder. Cryptology ePrint Archive, Report 2017/293 (2017). http://eprint.iacr.org/2017/293

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

Certicom Research. SEC 2: Recommended Elliptic Curve Domain Parameters (2010). Version 2.0. Standards for Efficient Cryptography. http://www.secg.org/sec2-v2.pdf

Chou, T.: Sandy2x: new curve25519 speed records. In: Dunkelman, O., Keliher, L. (eds.) SAC 2015. LNCS, vol. 9566, pp. 145–160. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-31301-6_8 CrossRef

Costello, C., Longa, P.: Four\(\mathbb{Q}\): four-dimensional decompositions on a \(\mathbb{Q}\)-curve over the mersenne prime. In: Iwata, T., Cheon, J.H. (eds.) ASIACRYPT 2015. LNCS, vol. 9452, pp. 214–235. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48797-6_10 CrossRef

10.

Costello, C., Smith, B.: Montgomery curves and their arithmetic: the case of large characteristic fields. Cryptology ePrint Archive, Report 2017/212 (2017)

11.

Diffie, W., Hellman, M.E.: New directions in cryptography. IEEE Trans. Inf. Theor. 22(6), 644–654 (1976)MathSciNetCrossRefMATH

12.

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

13.

Faz-Hernández, A., López, J.: Fast implementation of curve25519 using AVX2. In: Lauter, K., Rodríguez-Henríquez, F. (eds.) LATINCRYPT 2015. LNCS, vol. 9230, pp. 329–345. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-22174-8_18 CrossRef

14.

Fog, A.: Instruction tables: lists of instruction latencies, throughputs and micro-operation breakdowns for Intel, AMD and VIA CPUs (2016). http://www.agner.org/optimize/

15.

Hamburg, M.: Ed448-Goldilocks, a new elliptic curve. Cryptology ePrint Archive, Report 2015/625 (2015). http://eprint.iacr.org/2015/625

16.

Hutter, M., Schwabe, P.: Multiprecision multiplication on AVR revisited. J. Cryptographic Eng. 5(3), 201–214 (2015)CrossRef

17.

Hutter, M., Wenger, E.: Fast multi-precision multiplication for public-key cryptography on embedded microprocessors. In: Preneel, B., Takagi, T. (eds.) CHES 2011. LNCS, vol. 6917, pp. 459–474. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-23951-9_30 CrossRef

18.

Joye, M.: Highly regular right-to-left algorithms for scalar multiplication. In: Paillier, P., Verbauwhede, I. (eds.) CHES 2007. LNCS, vol. 4727, pp. 135–147. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-74735-2_10 CrossRef

19.

Koblitz, N.: Elliptic curve cryptosystems. Math. Comput. 48, 203–209 (1987)MathSciNetCrossRefMATH

20.

Kocher, P., Jaffe, J., Jun, B.: Differential power analysis. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 388–397. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48405-1_25 CrossRef

21.

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). https://doi.org/10.1007/3-540-68697-5_9

22.

Langley, A.: curve25519-donna. https://github.com/agl/curve25519-donna. Accessed Mar 2017

23.

Langley, A., Hamburg, M., Turner, S.: Elliptic Curves for Security (2016). Request for Comments. https://tools.ietf.org/html/rfc7748

24.

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). https://doi.org/10.1007/3-540-39799-X_31 CrossRef

25.

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

26.

National Institute of Standards and Technology. FIPS PUB 186-4: Digital Signature Standard (DSS). Federal Information Processing Standards (2013). http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf

27.

National Institute of Standards and Technology. NIST Removes Cryptography Algorithm from Random Number Generator Recommendations (2014). https://www.nist.gov/news-events/news/2014/04/nist-removes-cryptography-algorithm-random-number-generator-recommendations

28.

National Institute of Standards and Technology. Special Publication 800-90A Rev. 1: Recommendation for Random Number Generation Using Deterministic Random Bit Generators (2015). http://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-90Ar1.pdf

29.

Oliveira, T., Aranha, D.F., López, J., Rodríguez-Henríquez, F.: Fast point multiplication algorithms for binary elliptic curves with and without precomputation. In: Joux, A., Youssef, A. (eds.) SAC 2014. LNCS, vol. 8781, pp. 324–344. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-13051-4_20 CrossRef

30.

Oliveira, T., López, J., Rodríguez-Henríquez, F.: The Montgomery ladder on binary elliptic curves. J. Cryptographic Eng. (2017, to be submitted)

31.

Ozturk, E., Guilford, J., Gopal, V., Feghali, W.: New Instructions Supporting Large Integer Arithmetic on Intel® Architecture Processors. Intel Corporation, White Paper 327831-001, August 2012. http://www.intel.com/content/dam/www/public/us/en/documents/white-papers/ia-large-integer-arithmetic-paper.pdf

32.

Patterson, K.: Formal request from TLS WG to CFRG for new elliptic curves. Crypto Forum Research Group archives (2015). https://mailarchive.ietf.org/arch/msg/cfrg/Hvihr_yQhVB_Qdl-mtwTdVbHGiU

33.

Perlroth, N.: Government Announces Steps to Restore Confidence on Encryption Standards. New York Times (2013). https://bits.blogs.nytimes.com/2013/09/10/government-announces-steps-to-restore-confidence-on-encryption-standards/

34.

Perlroth, N., Larson, J., Shane, S.: N.S.A. Able to Foil Basic Safeguards of Privacy on Web. New York Times (2013). http://www.nytimes.com/2013/09/06/us/nsa-foils-much-internet-encryption.html

35.

Rescorla, E.: The Transport Layer Security (TLS) Protocol Version 1.3 (2017). Internet-Draft. https://tools.ietf.org/html/draft-ietf-tls-tls13-19

Titel: How to (Pre-)Compute a Ladder
verfasst von: Thomaz Oliveira
Julio López
Hüseyin Hışıl
Armando Faz-Hernández
Francisco Rodríguez-Henríquez
Verlag: Springer International Publishing
Buch: Selected Areas in Cryptography – SAC 2017
Print ISBN: 978-3-319-72564-2

Electronic ISBN: 978-3-319-72565-9

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-319-72565-9_9

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"