Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
ATZ-Fachkongress

Chassis.tech plus 2024


4 Kongresse in einer Veranstaltung

Treffen Sie in München die Fachleute von Chassis, Lenkung, Bremsen sowie Reifen/Räder.
Erweiterte Suche
Anmelden
nach oben
Journal of Cryptographic Engineering
Erschienen in: Journal of Cryptographic Engineering 3/2018

11.03.2017 | Special Issue on Montgomery Arithmetic

Montgomery curves and their arithmetic

The case of large characteristic fields

verfasst von: Craig Costello, Benjamin Smith

Erschienen in: Journal of Cryptographic Engineering | Ausgabe 3/2018

Einloggen

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

search-config
loading …

Abstract

Three decades ago, Montgomery introduced a new elliptic curve model for use in Lenstra’s ECM factorization algorithm. Since then, his curves and the algorithms associated with them have become foundational in the implementation of elliptic curve cryptosystems. This article surveys the theory and cryptographic applications of Montgomery curves over non-binary finite fields, including Montgomery’s x-only arithmetic and Ladder algorithm, x-only Diffie–Hellman, y-coordinate recovery, and two-dimensional and Euclidean differential addition chains such as Montgomery’s PRAC algorithm.
Vorheriger Artikel Spectral arithmetic in Montgomery modular multiplication
Nächster Artikel The Montgomery ladder on binary elliptic curves

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
Fußnoten
1
These conditions imply non-singularity: If \(B = 0\), then \(\mathcal {E}_{(A,B)}\) is a union of three lines, while if \(A^2 = 4\) then \(\mathcal {E}_{(A,B)}\) is a nodal cubic.
 
2
We saw above that since \(j(\mathcal {E}_{(A,B)})\) is a function of \(A^2\), the \(\overline{\mathbb {F}}_q\)-isomorphism class of \(\mathcal {E}_{(A,B)}\) depends only on \(A^2\). Indeed, \(\mathcal {E}_{({-A},B)}\) is \(\mathbb {F}_q\)-isomorphic (via \((x,y)\mapsto (-x,y)\)) to \(\mathcal {E}_{(A,{-B})}\), which is \(\mathbb {F}_q\)-isomorphic to \(\mathcal {E}_{(A,B)}\) if \(-1\) is a square in \(\mathbb {F}_q\) (otherwise, it is a quadratic twist).
 
3
Montgomery notes that in an ECM context, we can take \(B = A+2\) in order to force (1, 1) to be a rational point of order 4.
 
4
Translation by the 2-torsion point (0, 0) is defined by \((x,y) \mapsto (f_1/x,-f_1y/x^2)\); taking \(f_1 = 1\) is therefore equivalent to putting this translation map in the special form of (3).
 
5
Since the \(\mathtt{xADD}\) and \(\mathtt{xDBL}\) calls always share an argument, it is common for high-performance implementations to exploit any overlap between intermediate calculations in the \(\mathtt{xADD}\) and \(\mathtt{xDBL}\) by merging them in one combined function.
 
6
This is not a serious restriction in the context of scalar multiplication, where \(Q = [k]P\): if P is a point of order 2, then either \([k]P = O\) or \(y([k]P) = 0\).
 
7
An analysis of the frequency of prime-order curves with prime-order twists appears in [45], but this does not apply to Montgomery curves, since they cannot have prime order.
 
Literatur
1.
2.
3.
Bernstein, Daniel J.: Curve25519: New Diffie-Hellman speed records. In: Yung et al. [48], pp. 207–228CrossRef
4.
5.
Bernstein, D.J., Birkner, P., Joye, M., Lange, T., Peters, C.: Twisted Edwards Curves. In: Vaudenay, S. (ed.) Progress in Cryptology - AFRICACRYPT 2008, First International Conference on Cryptology in Africa, Casablanca, Morocco, June 11-14, 2008. Proceedings, volume 5023 of Lecture Notes in Computer Science, pp. 389–405. Springer, (2008)
6.
Bernstein, D.J., Chuengsatiansup, C., Lange, T., Schwabe, P.: Kummer strikes back: New DH Speed Records. In: Sarkar, P., Iwata, T., (eds), Advances in Cryptology - ASIACRYPT 2014—20th International Conference on the Theory and Application of Cryptology and Information Security, Kaoshiung, Taiwan, R.O.C., December 7-11, 2014. Proceedings, Part I, volume 8873 of Lecture Notes in Computer Science, pp. 317–337. Springer, (2014)
7.
Bernstein, D.J., Lange, T.: Faster addition and doubling on elliptic curves. In: Kurosawa, K. (eds.) 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, volume 4833 of Lecture Notes in Computer Science, pp. 29–50. Springer, (2007)
8.
Biehl, I., Meyer, B., Müller, V.: Differential fault attacks on elliptic curve cryptosystems. In: Bellare, M. (ed.) Advances in Cryptology—CRYPTO 2000, 20th Annual International Cryptology Conference, Santa Barbara, California, USA, August 20-24, 2000, Proceedings, volume 1880 of Lecture Notes in Computer Science, pp. 131–146. Springer, (2000)
9.
Bos, J.W., Costello, C., Hisil, H., Lauter, K.E.: Fast cryptography in genus 2. In: 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, volume 7881 of Lecture Notes in Computer Science, pp. 194–210. Springer, (2013)
10.
Brier, E., Joye, M.: Weierstraß elliptic curves and side-channel attacks. In: Naccache, D., Paillier, P., (eds.) Public Key Cryptography, 5th International Workshop on Practice and Theory in Public Key Cryptosystems, PKC 2002, Paris, France, February 12-14, 2002, Proceedings, volume 2274 of Lecture Notes in Computer Science, pp. 335–345. Springer (2002)
11.
12.
Cassels, J.W.S.: Lectures on Elliptic Curves, volume 240 of London Mathematical Society Student Texts. Cambridge University Press, Cambridge (1991)
13.
Cassels, J.W.S., Flynn, E.V.: Prolegomena to a Middlebrow Arithmetic of Curves of Genus 2, volume 230 of London Mathematical Society Lecture Note Series. Cambridge University Press, (1996)
14.
Castryck, W., Galbraith, S.D., Farashahi, R.R.: Efficient arithmetic on elliptic curves using a mixed Edwards-Montgomery representation. IACR Cryptol. ePrint Arch. 2008, 218 (2008)
15.
Chudnovsky, D.V., Chudnovsky, G.V.: Sequences of numbers generated by addition in formal groups and new primality and factorization tests. Adv. Appl. Math. 7(4), 385–434 (1986)MathSciNetCrossRef
16.
Chung, P.N., Costello, C., Smith, B.: Fast, uniform scalar multiplication for genus 2 Jacobians with fast Kummers. In: Avanzi, R., Heys, H. (eds.) Selected Areas in Cryptography-SAC 2016-23rd International Conference, Newfoundland, NL, Canada, August 10-12, 2016, Revised Selected Papers, Lecture Notes in Computer Science. Springer, (2016)
17.
18.
Costello, C., Hisil, H., Smith, B.: Faster compact Diffie–Hellman: Endomorphisms on the x-line. In: Nguyen, P.Q., 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, volume 8441 of Lecture Notes in Computer Science, pp. 183–200. Springer, (2014)
19.
Doche, C., Icart, T., Kohel, D.R.: Efficient scalar multiplication by isogeny decompositions. In: Yung et al. [48], pp. 191–206
20.
Duquesne, S.: Montgomery scalar multiplication for genus 2 curves. In: Buell, D.A. (ed.) Algorithmic Number Theory, 6th International Symposium, ANTS-VI, Burlington, VT, USA, June 13-18, 2004, Proceedings, volume 3076 of Lecture Notes in Computer Science, pp. 153–168. Springer, (2004)
21.
Duquesne, S.: Traces of the group law on the Kummer surface of a curve of genus 2 in characteristic 2. Math. Comput. Sci. 3(2), 173–183 (2010)MathSciNetCrossRef
22.
23.
24.
25.
Gallant, R.P., Lambert, R.J., Vanstone, S.A.: Faster point multiplication on elliptic curves with efficient endomorphisms. In: Kilian, J., (ed.) Advances in Cryptology - CRYPTO 2001, 21st Annual International Cryptology Conference, Santa Barbara, California, USA, August 19–23, 2001, Proceedings, volume 2139 of Lecture Notes in Computer Science, pp. 190–200. Springer, (2001)
26.
27.
Gaudry, P., Lubicz, D.: The arithmetic of characteristic 2 Kummer surfaces and of elliptic Kummer lines. Finite Fields Their Appl. 15(2), 246–260 (2009)MathSciNetCrossRef
28.
29.
Hisil, H., Wong, K.K.H., Carter, G., Dawson, E.: Twisted Edwards curves revisited. In: 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. Proceedings, volume 5350 of Lecture Notes in Computer Science, pp. 326–343. Springer, (2008)
30.
Kocher, P.C.: Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems. In: Koblitz, N. (ed.), Advances in Cryptology - CRYPTO ’96, 16th Annual International Cryptology Conference, Santa Barbara, California, USA, August 18–22, 1996, Proceedings, volume 1109 of Lecture Notes in Computer Science, pp. 104–113. Springer, (1996)
31.
Kohel, D.: Arithmetic of split Kummer surfaces: Montgomery endomorphism of Edwards products. In: Chee, Y.M, Guo, Z., Ling, S., Shao, F., Tang, Y., Wang, H., Xing, C. (eds.) Coding and Cryptology - Third International Workshop, IWCC 2011, Qingdao, China, May 30-June 3, 2011. Proceedings, volume 6639 of Lecture Notes in Computer Science, pp. 238–245. Springer, (2011)
32.
33.
34.
Lim, C.H., Lee, P.J.,: A key recovery attack on discrete log-based schemes using a prime order subgroup. In: Kaliski, B.S. Jr. (ed.), Advances in Cryptology - CRYPTO ’97, 17th Annual International Cryptology Conference, Santa Barbara, California, USA, August 17–21, 1997, Proceedings, volume 1294 of Lecture Notes in Computer Science, pp. 249–263. Springer (1997)CrossRef
35.
López, J., Dahab, R.: Fast multiplication on elliptic curves over GF(2\({}^{\text{m}}\)) without precomputation. In: Koç, Ç.K., Paar, C. (eds.) Cryptographic Hardware and Embedded Systems, First International Workshop, CHES’99, Worcester, MA, USA, August 12–13, 1999, Proceedings, volume 1717 of Lecture Notes in Computer Science, pp. 316–327. Springer, (1999)
36.
Lubicz, D., Damien, R.: Arithmetic on abelian and Kummer varieties. Finite Fields and Their Appl. 39, 130–158 (2016)MathSciNetCrossRef
37.
Miller, V.S.: Use of elliptic curves in cryptography. In: Advances of Cryptology - CRYPTO, pp. 417–426. Springer, (1985)
38.
Montgomery, P.L.: Speeding the Pollard and elliptic curve methods of factorization. Math. Comput. 48(177), 243–264 (1987)MathSciNetCrossRef
39.
40.
41.
Okeya, K., Kurumatani, H., Sakurai, K.: Elliptic curves with the Montgomery-form and their cryptographic applications. In: Imai, H., Zheng, Y. (ed), Public Key Cryptography, Third International Workshop on Practice and Theory in Public Key Cryptography, PKC 2000, Melbourne, Victoria, Australia, January 18-20, 2000, Proceedings, volume 1751 of Lecture Notes in Computer Science, pp. 238–257. Springer, (2000)
42.
Okeya, K., Sakurai, K.: Efficient elliptic curve cryptosystems from a scalar multiplication algorithm with recovery of the y-coordinate on a Montgomery-form elliptic curve. In: Koç, Ç.K, Naccache, D., Paar, C. (eds.) Cryptographic Hardware and Embedded Systems-CHES 2001, Third International Workshop, Paris, France, May 14–16, 2001, Proceedings, volume 2162 of Lecture Notes in Computer Science, pp. 126–141. Springer (2001)CrossRef
43.
Pollard, J.M.: Monte Carlo methods for index computation (mod \(p\)). Math. Comput. 32(143), 918–924 (1978)MathSciNetMATH
44.
Renes, J., Schwabe, P., Smith, B., Batina, L.: \(\mu \)Kummer: Efficient hyperelliptic signatures and key exchange on microcontrollers. In: Gierlichs, B., Poschmann, A.Y., (ed) Cryptographic Hardware and Embedded Systems–CHES 2016: 18th International Conference, Santa Barbara, CA, USA, August 17-19, 2016, Proceedings, pp. 301–320, Berlin, Heidelberg, (2016) Springer Berlin Heidelberg
45.
Shparlinski, I.E., Sutantyo, D.: Distribution of elliptic twin primes in isogeny and isomorphism classes. J. Number Theory 137, 1–15 (2014)MathSciNetCrossRef
46.
47.
Stam, M.: Speeding up subgroup cryptosystems. PhD thesis, Technische Universiteit Eindhoven, (2003)
48.
Yung, M., Dodis, Y., Kiayias, A., Malkin, T. (eds.): Public Key Cryptography-PKC 2006, 9th International Conference on Theory and Practice of Public-Key Cryptography, New York, NY, USA, April 24-26, 2006, Proceedings, volume 3958 of Lecture Notes in Computer Science. Springer, (2006)
49.
Zimmermann, P., Dodson, B.: 20 years of ECM. In: Hess, F., Pauli, S., Pohst, M.E. (eds), Algorithmic Number Theory, 7th International Symposium, ANTS-VII, Berlin, Germany, July 23-28, 2006, Proceedings, volume 4076 of Lecture Notes in Computer Science, pp. 525–542. Springer, (2006)
Metadaten
Titel
Montgomery curves and their arithmetic
The case of large characteristic fields
verfasst von
Craig Costello
Benjamin Smith
Publikationsdatum
11.03.2017
Verlag
Springer Berlin Heidelberg
Erschienen in
Journal of Cryptographic Engineering / Ausgabe 3/2018
Print ISSN: 2190-8508
Elektronische ISSN: 2190-8516
DOI
https://doi.org/10.1007/s13389-017-0157-6

Weitere Artikel der Ausgabe 3/2018

Journal of Cryptographic Engineering 3/2018 Zur Ausgabe

Special Issue on Montgomery Arithmetic

Karatsuba-like formulae and their associated techniques

Special Issue on Montgomery Arithmetic

Special issue in honor of Peter Lawrence Montgomery

Special Issue on Montgomery Arithmetic

Spectral arithmetic in Montgomery modular multiplication

Special Issue on Montgomery Arithmetic

Montgomery inversion

Special Issue on Montgomery Arithmetic

Montgomery reduction within the context of residue number system arithmetic

Special Issue on Montgomery Arithmetic

The Montgomery ladder on binary elliptic curves

Premium Partner

    Bildnachweise