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

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 -