Elliptic curves with the montgomery-form and their cryptographic applications

Katsuyuki Okeya; Hiroyuki Kurumatani; Kouichi Sakurai

doi:10.1007/978-3-540-46588-1_17

Elliptic curves with the montgomery-form and their cryptographic applications

Katsuyuki Okeya, Hiroyuki Kurumatani, Kouichi Sakurai

Mathematical Informatics

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

65 Citations (Scopus)

Abstract

We show that the elliptic curve cryptosystems based on the Montgomery-form E^M: BY² = X³+ AX² +X are immune to the timing-attacks by using our technique of randomized projective coordinates, while Montgomery originally introduced this type of curves for speeding up the Pollard and Elliptic Curve Methods of integer factorization [Math. Comp. Vol.48, No.177, (1987) pp.243-264]. However, it should be noted that not all the elliptic curves have the Montgomery-form, because the order of any elliptic curve with the Montgomery-form is divisible by “4”. Whereas recent ECC-standards [NIST,SEC-1] recommend that the cofactor of elliptic curve should be no greater than 4 for cryptographic applications. Therefore, we present an efficient algorithm for generating Montgomery-form elliptic curve whose cofactor is exactly “4”. Finally, we give the exact consition on the elliptic curves whether they can be represented as a Montgomery-form or not. We consider divisibility by “8” for Montgomery-form elliptic curves. We implement the proposed algorithm and give some numerical examples obtained by this.

Original language	English
Title of host publication	Public Key Cryptography - 3rd International Workshop on Practice and Theory in Public Key Cryptosystems, PKC 2000, Proceedings
Editors	Hideki Imai, Yuliang Zheng
Publisher	Springer Verlag
Pages	238-257
Number of pages	20
ISBN (Print)	3540669671, 9783540669678
DOIs	https://doi.org/10.1007/978-3-540-46588-1_17
Publication status	Published - 2000
Event	3rd International Workshop on Practice and Theory in Public Key Cryptosystems, PKC 2000 - Melbourne, Australia Duration: Jan 18 2000 → Jan 20 2000

Publication series

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

Other

Other	3rd International Workshop on Practice and Theory in Public Key Cryptosystems, PKC 2000
Country/Territory	Australia
City	Melbourne
Period	1/18/00 → 1/20/00

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-540-46588-1_17

Cite this

Okeya, K., Kurumatani, H., & Sakurai, K. (2000). Elliptic curves with the montgomery-form and their cryptographic applications. In H. Imai, & Y. Zheng (Eds.), Public Key Cryptography - 3rd International Workshop on Practice and Theory in Public Key Cryptosystems, PKC 2000, Proceedings (pp. 238-257). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1751). Springer Verlag. https://doi.org/10.1007/978-3-540-46588-1_17

Elliptic curves with the montgomery-form and their cryptographic applications. / Okeya, Katsuyuki; Kurumatani, Hiroyuki; Sakurai, Kouichi.
Public Key Cryptography - 3rd International Workshop on Practice and Theory in Public Key Cryptosystems, PKC 2000, Proceedings. ed. / Hideki Imai; Yuliang Zheng. Springer Verlag, 2000. p. 238-257 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1751).

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

Okeya, K, Kurumatani, H & Sakurai, K 2000, Elliptic curves with the montgomery-form and their cryptographic applications. in H Imai & Y Zheng (eds), Public Key Cryptography - 3rd International Workshop on Practice and Theory in Public Key Cryptosystems, PKC 2000, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1751, Springer Verlag, pp. 238-257, 3rd International Workshop on Practice and Theory in Public Key Cryptosystems, PKC 2000, Melbourne, Australia, 1/18/00. https://doi.org/10.1007/978-3-540-46588-1_17

Okeya K, Kurumatani H, Sakurai K. Elliptic curves with the montgomery-form and their cryptographic applications. In Imai H, Zheng Y, editors, Public Key Cryptography - 3rd International Workshop on Practice and Theory in Public Key Cryptosystems, PKC 2000, Proceedings. Springer Verlag. 2000. p. 238-257. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-46588-1_17

Okeya, Katsuyuki ; Kurumatani, Hiroyuki ; Sakurai, Kouichi. / Elliptic curves with the montgomery-form and their cryptographic applications. Public Key Cryptography - 3rd International Workshop on Practice and Theory in Public Key Cryptosystems, PKC 2000, Proceedings. editor / Hideki Imai ; Yuliang Zheng. Springer Verlag, 2000. pp. 238-257 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{6487c891506a4a239d7609b65bea107f,

title = "Elliptic curves with the montgomery-form and their cryptographic applications",

abstract = "We show that the elliptic curve cryptosystems based on the Montgomery-form EM: BY2 = X3+ AX2 +X are immune to the timing-attacks by using our technique of randomized projective coordinates, while Montgomery originally introduced this type of curves for speeding up the Pollard and Elliptic Curve Methods of integer factorization [Math. Comp. Vol.48, No.177, (1987) pp.243-264]. However, it should be noted that not all the elliptic curves have the Montgomery-form, because the order of any elliptic curve with the Montgomery-form is divisible by “4”. Whereas recent ECC-standards [NIST,SEC-1] recommend that the cofactor of elliptic curve should be no greater than 4 for cryptographic applications. Therefore, we present an efficient algorithm for generating Montgomery-form elliptic curve whose cofactor is exactly “4”. Finally, we give the exact consition on the elliptic curves whether they can be represented as a Montgomery-form or not. We consider divisibility by “8” for Montgomery-form elliptic curves. We implement the proposed algorithm and give some numerical examples obtained by this.",

author = "Katsuyuki Okeya and Hiroyuki Kurumatani and Kouichi Sakurai",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2000; 3rd International Workshop on Practice and Theory in Public Key Cryptosystems, PKC 2000 ; Conference date: 18-01-2000 Through 20-01-2000",

year = "2000",

doi = "10.1007/978-3-540-46588-1_17",

language = "English",

isbn = "3540669671",

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

publisher = "Springer Verlag",

pages = "238--257",

editor = "Hideki Imai and Yuliang Zheng",

booktitle = "Public Key Cryptography - 3rd International Workshop on Practice and Theory in Public Key Cryptosystems, PKC 2000, Proceedings",

address = "Germany",

}

TY - GEN

T1 - Elliptic curves with the montgomery-form and their cryptographic applications

AU - Okeya, Katsuyuki

AU - Kurumatani, Hiroyuki

AU - Sakurai, Kouichi

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 2000

PY - 2000

Y1 - 2000

N2 - We show that the elliptic curve cryptosystems based on the Montgomery-form EM: BY2 = X3+ AX2 +X are immune to the timing-attacks by using our technique of randomized projective coordinates, while Montgomery originally introduced this type of curves for speeding up the Pollard and Elliptic Curve Methods of integer factorization [Math. Comp. Vol.48, No.177, (1987) pp.243-264]. However, it should be noted that not all the elliptic curves have the Montgomery-form, because the order of any elliptic curve with the Montgomery-form is divisible by “4”. Whereas recent ECC-standards [NIST,SEC-1] recommend that the cofactor of elliptic curve should be no greater than 4 for cryptographic applications. Therefore, we present an efficient algorithm for generating Montgomery-form elliptic curve whose cofactor is exactly “4”. Finally, we give the exact consition on the elliptic curves whether they can be represented as a Montgomery-form or not. We consider divisibility by “8” for Montgomery-form elliptic curves. We implement the proposed algorithm and give some numerical examples obtained by this.

AB - We show that the elliptic curve cryptosystems based on the Montgomery-form EM: BY2 = X3+ AX2 +X are immune to the timing-attacks by using our technique of randomized projective coordinates, while Montgomery originally introduced this type of curves for speeding up the Pollard and Elliptic Curve Methods of integer factorization [Math. Comp. Vol.48, No.177, (1987) pp.243-264]. However, it should be noted that not all the elliptic curves have the Montgomery-form, because the order of any elliptic curve with the Montgomery-form is divisible by “4”. Whereas recent ECC-standards [NIST,SEC-1] recommend that the cofactor of elliptic curve should be no greater than 4 for cryptographic applications. Therefore, we present an efficient algorithm for generating Montgomery-form elliptic curve whose cofactor is exactly “4”. Finally, we give the exact consition on the elliptic curves whether they can be represented as a Montgomery-form or not. We consider divisibility by “8” for Montgomery-form elliptic curves. We implement the proposed algorithm and give some numerical examples obtained by this.

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

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

U2 - 10.1007/978-3-540-46588-1_17

DO - 10.1007/978-3-540-46588-1_17

M3 - Conference contribution

AN - SCOPUS:84957794840

SN - 3540669671

SN - 9783540669678

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

SP - 238

EP - 257

BT - Public Key Cryptography - 3rd International Workshop on Practice and Theory in Public Key Cryptosystems, PKC 2000, Proceedings

A2 - Imai, Hideki

A2 - Zheng, Yuliang

PB - Springer Verlag

T2 - 3rd International Workshop on Practice and Theory in Public Key Cryptosystems, PKC 2000

Y2 - 18 January 2000 through 20 January 2000

ER -

Elliptic curves with the montgomery-form and their cryptographic applications

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this