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 3/2018

26-04-2017 | Special Issue on Montgomery Arithmetic

The Montgomery ladder on binary elliptic curves

Authors: Thomaz Oliveira, Julio López, Francisco Rodríguez-Henríquez

Published in: Journal of Cryptographic Engineering | Issue 3/2018

Log in

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

search-config
loading …

Abstract

In this survey paper, we present a careful analysis of the Montgomery ladder procedure applied to the computation of the constant-time point multiplication operation on elliptic curves defined over binary extension fields. We give a general view of the main improvements and formula derivations that several researchers have contributed across the years, since the publication of Peter Lawrence Montgomery seminal work in 1987. We also report a fast software implementation of the Montgomery ladder applied on a Galbraith–Lin–Scott (GLS) binary elliptic curve that offers a security level close to 128 bits. Using our software, we can execute the ephemeral Diffie–Hellman protocol in just 95,702 clock cycles when implemented on an Intel Skylake machine running at 4 GHz.
previous article Montgomery curves and their arithmetic
next article Karatsuba-like formulae and their associated techniques

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
The analogous of this recovering formula has been recently applied in the context of hyperelliptic curves [13, 56].
 
2
Division polynomials also play a crucial role for computing isogenies of elliptic curves [37].
 
3
For the sake of completeness, we present in Appendix A, the derivation of the point doubling formula using division polynomials.
 
4
According to Algorithm 2, at the end of the iteration \(n-1\), \(2^nP\) is assigned to \(R_0\). The point \(2^nP\) is never used in the unknown-point scenario; therefore, this assignation can be avoided in practical implementations.
 
5
In binary fields, the value of h can be as low as 2. Thus, the process of subtracting S is merely a Montgomery point doubling.
 
6
In fixed-point scenarios, the y-coordinate of \(R_1\) can be retrieved. Consequently, Step 11 can be alternatively computed as \(Q = R_1 - S\).
 
7
In the fixed-point setting, one can store the multiples in the affine form. As a result, only mn bits of storage is needed.
 
8
If the order h is prime, then one can return instead the point \(Q = h(R_{1,0} + \psi (R_{1,1}))\).
 
9
It is not known how to efficiently half a point in elliptic curves defined over prime fields.
 
10
In Algorithm 6, \(R_0\) is updated after \(R_1\) and \(R_2\).
 
11
The latency and the throughput of the vector instruction pxor in current desktop architectures are of 1 and 0.33 clock cycles, respectively [31].
 
12
The implementation to be described here closely follows the one presented by Oliveira et al. in [51].
 
13
We stress that binary Weierstrass and Edward curves are birational equivalent [8].
 
14
As the Diffie–Hellman protocol does not need the y-coordinate of any point, the y-coordinate retrieval function was not considered in this estimation.
 
Literature
1.
Agnew, G.B., Mullin, R.C., Vanstone, S.A.: An implementation of elliptic curve cryptosystems over \(\mathbb{F}_{2^{155}}\). IEEE J. Sel. Areas Commun. 11(5), 804–813 (1993)CrossRef
2.
ANSI X9.62:2005. Public key cryptography for the financial services industry: The elliptic curve digital signature algorithm (ECDSA). American National Standards Institute (2005)
3.
Aranha, D.F., López, J., Hankerson, D.: Efficient software implementation of binary field arithmetic using vector instruction sets. In: Abdalla, M., Barreto, P.S.L.M. (eds.) LATINCRYPT 2010, LNCS, vol. 6212, pp. 144–161. Springer (2010)
4.
Ay, A.U., Öztürk, E., Rodríguez-Henríquez, F., Savas E.: Design and implementation of a constant-time FPGA accelerator for fast elliptic curve cryptography. In: Athanas, P. M., Cumplido, R., Feregrino C., Sass R. (eds.) International Conference on ReConFigurable Computing and FPGAs, ReConFig 2016 pp. 1–8. IEEE (2016)
5.
6.
Bernstein, D.J., Chuengsatiansup, C., Lange, T., Schwabe, P.: Kummer strikes back: new dh speed records. In: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014, LNCS, vol. 8873, pp. 317–337. Springer (2014)
7.
8.
Bernstein, D.J., Lange, T., Farashahi, R.: Binary Edwards curves. In: Oswald, E., Rohatgi, P. (eds.) CHES 2008, LNCS, vol. 5154, pp. 244–265. Springer (2008)
9.
Bluhm, M., Gueron, S.: Fast software implementation of binary elliptic curve cryptography. J. Cryptogr. Eng. 5(3), 215–226 (2015)CrossRef
10.
Bos, J.W., Costello, C., Hisil, H., Lauter, K.E.: Fast Cryptography in genus 2. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013, LNCS, vol. 7881, pp. 194–210. Springer (2013)
11.
12.
13.
Chung, P.N., Costello, C., Smith, B.: Fast, uniform, and compact scalar multiplication for elliptic curves and genus 2 Jacobians with applications to signature schemes. (2015). arXiv:​1510.​03174
14.
Costello, C., Hisil, H., Smith, B.: Faster compact Diffie–Hellman: endomorphisms on the x-line. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014, LNCS, vol. 8441, pp. 183–200. Springer (2014)
15.
Enge, A., Gaudry, P.: A general framework for subexponential discrete logarithm algorithms. Acta Arith. 102, 83103 (2002)MathSciNetCrossRef
16.
Fan, J., Guo, X., De Mulder, E., Schaumont, P., Preneel, B., Verbauwhede, I.: State-of-the-art of secure ECC Implementations: A survey on known side-channel attacks and countermeasures. In: IEEE International Symposium on Hardware-Oriented Security and Trust (HOST 2010), pp. 76–87. IEEE (2010)
17.
Fan, J., Verbauwhede, I.: An updated survey on secure ECC implementations: Attacks, countermeasures and cost. In: Naccache, D. (ed.) Cryptography and Security: LNCS, vol. 6805, pp. 265–282. Springer (2012)
18.
Faugère, J. Perret, L., Petit, C., Renault G.: Improving the complexity of index calculus algorithms in elliptic curves over binary fields. In: EUROCRYPT 2012, LNCS, vol. 7237, p. 2744. Springer (2012)
19.
Fong, K., Hankerson, D., López, J., Menezes, A.: Field inversion and point halving revisited. IEEE Trans. Comput. 53(8), 1047–1059 (2004)CrossRef
20.
Galbraith, S.D., Gaudry, P.: Recent progress on the elliptic curve discrete logarithm problem. Des. Codes Cryptogr. 78(1), 51–72 (2016)MathSciNetCrossRef
21.
Galbraith, S.D., Lin, X., Scott, M.: Endomorphisms for faster elliptic curve cryptography on a large class of curves. J. Cryptol. 24, 446–469 (2011)MathSciNetCrossRef
22.
Galbraith, S. D., Gebregiyorgis, S. W.: Summation polynomial algorithms for elliptic curves in characteristic two. In: INDOCRYPT 2014, LNCS, vol. 8885, pages 409427. Springer (2014)
23.
Galbraith, S. D., Smart, N. P.: A Cryptographic application of weil descent. In Cryptography and Coding, LNCS, vol. 1746, p. 191200. Springer (1999)
24.
Gallant, R.P., Lambert, R.J., Vanstone, S.A.: faster point multiplication on elliptic curves with efficient endomorphisms. In: Kilian, J. (ed.) CRYPTO 2001, LNCS, vol. 2139, pp. 190–200. Springer (2001)
25.
Gaudry, P., Hess, F., Smart, N.P.: Constructive and destructive facets of Weil descent on elliptic curves. J. Cryptol. 15, 1946 (2002)MathSciNetCrossRef
26.
Hankerson, D., Karabina, K., Menezes, A.: Analyzing the Galbraith-Lin-Scott point multiplication method for elliptic curves over binary fields. IEEE Trans. Comput. 58(10), 1411–1420 (2009)MathSciNetCrossRef
27.
Hess, F.: Generalising the GHS attack on the elliptic curve discrete logarithm problem. LMS J. Comput. Math. 7, 167192 (2004)MathSciNetCrossRef
28.
Huang, Y.-J., Petit, C., Shinohara, N., Takagi, T.: On generalized first fall degree assumptions. IACR Cryptol. ePrint Arch. 2015, 358 (2015)
29.
Hutchinson, A., Karabina, K.: Constructing multidimensional differential addition chains and their applications. IACR Cryptol. ePrint Arch. 2017, 311 (2017)
30.
31.
32.
Karaklajić, D., Fan, J., Schmidt, J-M., Verbauwhede, I.: Low-cost fault detection method for ECC using Montgomery powering ladder. Design, automation and test in Europe, DATE 2011 pp. 1016–1021. IEEE (2011)
33.
Kim, K.H., lee, C.O., Nègre, C.: Binary Edwards curves revisited. In: Meier, W., Mukhopadhyay, D. (eds.) INDOCRYPT 2014, LNCS, vol. 8885, pp. 393–408. Springer (2014)
34.
Knudsen, E.: Elliptic scalar multiplication using point halving. In: Lam, K.Y., Okamoto, E., Xing, C. (eds.) ASIACRYPT 99, LNCS, vol. 1716, pp. 135–149. Springer (1999)
35.
Koblitz, N.: Constructing elliptic curve cryptosystems in characteristic 2. In: Menezes, A., Vanstone, S. (eds.) CRYPTO 90, LNCS, pp. 156–167. Springer (1991)
36.
Kocher, P. C.: Timing attacks on implementations of Diffie–Hellman, RSA, DSS, and other systems. In: CRYPTO 96, LNCS, vol. 1109, pp. 104–113. Springer (1996)
37.
38.
Koziel, B., Azarderakhsh, R., Mozaffari Kermani, M.: Low-resource and fast binary edwards curves cryptography. In: Biryukov, A., Goyal, V. (eds.) INDOCRYPT 2015, LNCS, vol. 9462, pp. 347–369. Springer (2015)
39.
Lang, S.: Elliptic Curves Diophantine Analysis. Springer, New York, USA (1978)CrossRef
40.
Lee, Y.K., Sakiyama, K., Batina, L., Verbauwhede, I.: Elliptic-curve-based security processor for RFID. IEEE Trans. Comput. 57(11), 1514–1527 (2008)MathSciNetCrossRef
41.
42.
Li, L., Li, S.: High-performance pipelined architecture of elliptic curve scalar multiplication over GF(\(2^m\)). IEEE Trans. VLSI Syst. 24(4), 1223–1232 (2016)CrossRef
43.
López, J., Dahab, R.: Fast multiplication on elliptic curves over GF(\(2^m\)) without precomputation. In: Koç, Ç.K., Paar, C. (eds.) (eds.) CHES 99, LNCS, vol. 1717, pp. 316–327. Springer (1999)
44.
Maurer, M., Menezes, A., Teske, E.: Analysis of the GHS weil descent attack on the ECDLP over characteristic two finite fields of composite degree. In INDOCRYPT 2001, LNCS, vol. 2247, p. 195213. Springer (2001)
45.
Meloni, N.: New point addition formulae for ECC applications. In: Carlet, C., Sunar, B. (eds.) WAIFI 2007, LNCS, vol. 4547, pp. 189–201. Springer (2007)
46.
Menezes, A., Vanstone, S.A.: Elliptic curve cryptosystems and their implementations. J. Cryptol. 6(4), 209–224 (1993)MathSciNetCrossRef
47.
Menezes, A., Qu, M: Analysis of the Weil descent attack of Gaudry, Hess and Smart. In CT-RSA 2001, vol. 2020 of LNCS, p. 308318. Springer (2001)
48.
Miller, V.S.: Use of Elliptic curves in cryptography, advances in cryptology. In: Williams, H.C. (ed.) CRYPTO 85, LNCS, vol. 218, pp. 417–426. Springer (1986)
49.
Montgomery, P.L.: Speeding the pollard and elliptic curve methods of factorization. Math.Comput. 48, 243–264 (1987)MathSciNetCrossRef
50.
Nègre, C., Robert, J.-M.: New parallel approaches for scalar multiplication in elliptic curve over fields of small characteristic. IEEE Trans. Comput. 64(10), 2875–2890 (2015)MathSciNetCrossRef
51.
Oliveira, T., Aranha, D.F., López-Hernández, J., Rodríguez-Henríquez, F.: Fast point multiplication algorithms for binary elliptic curves with and without precomputation. In: Joux, A., Youssef, A. M. (eds.) SAC 2014, LNCS, vol. 8781, pp. 324–344. Springer (2014)
52.
Oliveira, T., Aranha, D.F., López-Hernández, J., Rodríguez-Henríquez, F.: Two is the fastest prime: Lambda coordinates for binary elliptic curves. J. Cryptogr. Eng. 4(1), 3–17 (2014)CrossRef
53.
54.
Rashidi, B., Sayedi, S.M., Farashahi, R.R.: High-speed hardware architecture of scalar multiplication for binary elliptic curve cryptosystems. Microelectron. J. 52, 49–65 (2016)CrossRef
55.
Rebeiro, C., Sinha Roy, S., Mukhopadhyay, D.: Pushing the limits of high-speed GF(\(2^m\)) Elliptic curve scalar multiplication on FPGAs. In: Prouff, E., Schaumont, P. (eds.) CHES 2012, LNCS, vol. 7428, pp. 494–511. Springer (2012)
56.
Renes, J., Schwabe, P., Smith, B., Batina, L.: \(\mu \) Kummer: Efficient hyperelliptic signatures and key exchange on microcontrollers. In: Gierlichs, B., Poschmann, A. Y. (eds.) CHES 2016, LNCS, vol. 9813, pp. 301–320. Springer (2016)
57.
Schroeppel, R.: Elliptic curve point halving wins big. In: 2nd Midwest Arithmetical Geometry in Cryptography Workshop (2000)
58.
Schroeppel, R.: Automatically solving equations in finite fields. US patent 2002/0055962 A1 (2002)
59.
60.
61.
Subramanya Rao, S.R.: Three dimensional montgomery ladder, differential point tripling on montgomery curves and point quintupling on Weierstrass’ and Edwards curves. In: Pointcheval, D., Nitaj, A., Rachidi T. (eds.) AFRICACRYPT 2016, LNCS, vol. 9645, pp. 84–106. Springer (2016)
62.
Taverne, J., Faz-Hernández, A., Aranha, D.F., Rodríguez-Henríquez, F., Hankerson, D., López, J.: Speeding scalar multiplication over binary elliptic curves using the new carry-less multiplication instruction. J. Cryptogr. Eng. 1(3), 187–199 (2011)CrossRef
63.
Wenger, E., Wolfger, P.: Harder, better, faster, stronger: Elliptic curve discrete logarithm computations on FPGAs. J. Cryptogr. Eng. 6(4), 287297 (2016)CrossRef
Metadata
Title
The Montgomery ladder on binary elliptic curves
Authors
Thomaz Oliveira
Julio López
Francisco Rodríguez-Henríquez
Publication date
26-04-2017
Publisher
Springer Berlin Heidelberg
Published in
Journal of Cryptographic Engineering / Issue 3/2018
Print ISSN: 2190-8508
Electronic ISSN: 2190-8516
DOI
https://doi.org/10.1007/s13389-017-0163-8

Other articles of this Issue 3/2018

Journal of Cryptographic Engineering 3/2018 Go to the issue

Special Issue on Montgomery Arithmetic

Montgomery inversion

Special Issue on Montgomery Arithmetic

Spectral arithmetic in Montgomery modular multiplication

Special Issue on Montgomery Arithmetic

Special issue in honor of Peter Lawrence Montgomery

Special Issue on Montgomery Arithmetic

Montgomery reduction within the context of residue number system arithmetic

Special Issue on Montgomery Arithmetic

Montgomery curves and their arithmetic

Special Issue on Montgomery Arithmetic

Karatsuba-like formulae and their associated techniques

Premium Partner

    Image Credits