Efficient elliptic curve cryptosystems from a scalar multiplication algorithm with recovery of the y-coordinate on a montgomery-form elliptic curve

Katsuyuki Okeya; Kouichi Sakurai

doi:10.1007/3-540-44709-1_12

Efficient elliptic curve cryptosystems from a scalar multiplication algorithm with recovery of the y-coordinate on a montgomery-form elliptic curve

Katsuyuki Okeya, Kouichi Sakurai

Mathematical Informatics

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

58 Citations (Scopus)

Abstract

We present a scalar multiplication algorithm with recovery of the y-coordinate on a Montgomery form elliptic curve over any nonbinary field. The previous algorithms for scalar multiplication on a Montgomery form do not consider how to recover the y-coordinate. So although they can be applicable to certain restricted schemes (e.g. ECDH and ECDSA-S), some schemes (e.g. ECDSA-V and MQV) require scalar multiplication with recovery of the y-coordinate. We compare our proposed scalar multiplication algorithm with the traditional scalar multiplication algorithms (including Window-methods in Weierstrass form), and discuss the Montgomery form versus the Weierstrass form in the performance of implementations with several techniques of elliptic curve cryptosystems (including ECES, ECDSA, and ECMQV). Our results clarify the advantage of the cryptographic usage of Montgomery-form elliptic curves in constrained environments such as mobile devices and smart cards.

Original language	English
Title of host publication	Cryptographic Hardware and Embedded Systems - CHES 2001 - 3rd International Workshop, Proceedings
Editors	Cetin K. Koc, David Naccache, Christof Paar, Christof Paar
Publisher	Springer Verlag
Pages	126-141
Number of pages	16
ISBN (Print)	3540425217
DOIs	https://doi.org/10.1007/3-540-44709-1_12
Publication status	Published - 2001
Event	3rd International Workshop on Cryptographic Hardware and Embedded Systems, CHES 2001 - Paris, France Duration: May 14 2001 → May 16 2001

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	2162
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	3rd International Workshop on Cryptographic Hardware and Embedded Systems, CHES 2001
Country/Territory	France
City	Paris
Period	5/14/01 → 5/16/01

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/3-540-44709-1_12

Cite this

Okeya, K., & Sakurai, K. (2001). Efficient elliptic curve cryptosystems from a scalar multiplication algorithm with recovery of the y-coordinate on a montgomery-form elliptic curve. In C. K. Koc, D. Naccache, C. Paar, & C. Paar (Eds.), Cryptographic Hardware and Embedded Systems - CHES 2001 - 3rd International Workshop, Proceedings (pp. 126-141). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2162). Springer Verlag. https://doi.org/10.1007/3-540-44709-1_12

Efficient elliptic curve cryptosystems from a scalar multiplication algorithm with recovery of the y-coordinate on a montgomery-form elliptic curve. / Okeya, Katsuyuki; Sakurai, Kouichi.
Cryptographic Hardware and Embedded Systems - CHES 2001 - 3rd International Workshop, Proceedings. ed. / Cetin K. Koc; David Naccache; Christof Paar; Christof Paar. Springer Verlag, 2001. p. 126-141 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2162).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Okeya, K & Sakurai, K 2001, Efficient elliptic curve cryptosystems from a scalar multiplication algorithm with recovery of the y-coordinate on a montgomery-form elliptic curve. in CK Koc, D Naccache, C Paar & C Paar (eds), Cryptographic Hardware and Embedded Systems - CHES 2001 - 3rd International Workshop, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2162, Springer Verlag, pp. 126-141, 3rd International Workshop on Cryptographic Hardware and Embedded Systems, CHES 2001, Paris, France, 5/14/01. https://doi.org/10.1007/3-540-44709-1_12

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 Koc CK, Naccache D, Paar C, Paar C, editors, Cryptographic Hardware and Embedded Systems - CHES 2001 - 3rd International Workshop, Proceedings. Springer Verlag. 2001. p. 126-141. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-44709-1_12

Okeya, Katsuyuki ; Sakurai, Kouichi. / Efficient elliptic curve cryptosystems from a scalar multiplication algorithm with recovery of the y-coordinate on a montgomery-form elliptic curve. Cryptographic Hardware and Embedded Systems - CHES 2001 - 3rd International Workshop, Proceedings. editor / Cetin K. Koc ; David Naccache ; Christof Paar ; Christof Paar. Springer Verlag, 2001. pp. 126-141 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{2dacb90c6143418aa855ad4dbd80e313,

title = "Efficient elliptic curve cryptosystems from a scalar multiplication algorithm with recovery of the y-coordinate on a montgomery-form elliptic curve",

abstract = "We present a scalar multiplication algorithm with recovery of the y-coordinate on a Montgomery form elliptic curve over any nonbinary field. The previous algorithms for scalar multiplication on a Montgomery form do not consider how to recover the y-coordinate. So although they can be applicable to certain restricted schemes (e.g. ECDH and ECDSA-S), some schemes (e.g. ECDSA-V and MQV) require scalar multiplication with recovery of the y-coordinate. We compare our proposed scalar multiplication algorithm with the traditional scalar multiplication algorithms (including Window-methods in Weierstrass form), and discuss the Montgomery form versus the Weierstrass form in the performance of implementations with several techniques of elliptic curve cryptosystems (including ECES, ECDSA, and ECMQV). Our results clarify the advantage of the cryptographic usage of Montgomery-form elliptic curves in constrained environments such as mobile devices and smart cards.",

author = "Katsuyuki Okeya and Kouichi Sakurai",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2001.; 3rd International Workshop on Cryptographic Hardware and Embedded Systems, CHES 2001 ; Conference date: 14-05-2001 Through 16-05-2001",

year = "2001",

doi = "10.1007/3-540-44709-1_12",

language = "English",

isbn = "3540425217",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "126--141",

editor = "Koc, {Cetin K.} and David Naccache and Christof Paar and Christof Paar",

booktitle = "Cryptographic Hardware and Embedded Systems - CHES 2001 - 3rd International Workshop, Proceedings",

address = "Germany",

}

TY - GEN

T1 - Efficient elliptic curve cryptosystems from a scalar multiplication algorithm with recovery of the y-coordinate on a montgomery-form elliptic curve

AU - Okeya, Katsuyuki

AU - Sakurai, Kouichi

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 2001.

PY - 2001

Y1 - 2001

N2 - We present a scalar multiplication algorithm with recovery of the y-coordinate on a Montgomery form elliptic curve over any nonbinary field. The previous algorithms for scalar multiplication on a Montgomery form do not consider how to recover the y-coordinate. So although they can be applicable to certain restricted schemes (e.g. ECDH and ECDSA-S), some schemes (e.g. ECDSA-V and MQV) require scalar multiplication with recovery of the y-coordinate. We compare our proposed scalar multiplication algorithm with the traditional scalar multiplication algorithms (including Window-methods in Weierstrass form), and discuss the Montgomery form versus the Weierstrass form in the performance of implementations with several techniques of elliptic curve cryptosystems (including ECES, ECDSA, and ECMQV). Our results clarify the advantage of the cryptographic usage of Montgomery-form elliptic curves in constrained environments such as mobile devices and smart cards.

AB - We present a scalar multiplication algorithm with recovery of the y-coordinate on a Montgomery form elliptic curve over any nonbinary field. The previous algorithms for scalar multiplication on a Montgomery form do not consider how to recover the y-coordinate. So although they can be applicable to certain restricted schemes (e.g. ECDH and ECDSA-S), some schemes (e.g. ECDSA-V and MQV) require scalar multiplication with recovery of the y-coordinate. We compare our proposed scalar multiplication algorithm with the traditional scalar multiplication algorithms (including Window-methods in Weierstrass form), and discuss the Montgomery form versus the Weierstrass form in the performance of implementations with several techniques of elliptic curve cryptosystems (including ECES, ECDSA, and ECMQV). Our results clarify the advantage of the cryptographic usage of Montgomery-form elliptic curves in constrained environments such as mobile devices and smart cards.

UR - http://www.scopus.com/inward/record.url?scp=84944875437&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84944875437&partnerID=8YFLogxK

U2 - 10.1007/3-540-44709-1_12

DO - 10.1007/3-540-44709-1_12

M3 - Conference contribution

AN - SCOPUS:84944875437

SN - 3540425217

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 126

EP - 141

BT - Cryptographic Hardware and Embedded Systems - CHES 2001 - 3rd International Workshop, Proceedings

A2 - Koc, Cetin K.

A2 - Naccache, David

A2 - Paar, Christof

PB - Springer Verlag

T2 - 3rd International Workshop on Cryptographic Hardware and Embedded Systems, CHES 2001

Y2 - 14 May 2001 through 16 May 2001

ER -

Efficient elliptic curve cryptosystems from a scalar multiplication algorithm with recovery of the y-coordinate on a montgomery-form elliptic curve

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this