More Web Proxy on the site http://driver.im/

Article

Exceptional Procedure Attackon Elliptic Curve Cryptosystems

Authors:

Tsuyoshi TakagiAuthors Info & Claims

PKC '03: Proceedings of the 6th International Workshop on Theory and Practice in Public Key Cryptography: Public Key Cryptography

Pages 224 - 239

Published: 06 January 2003 Publication History

Abstract

The scalar multiplication of elliptic curve based cryptosystems (ECC) is computed by repeatedly calling the addition formula that calculates the elliptic curve addition of two points. The addition formula involves several exceptional procedures so that implementers have to carefully consider their treatments. In this paper we study the exceptional procedure attack, which reveals the secret scalar using the error arisen from the exceptional procedures. Recently new forms of elliptic curves and addition formulas for ECC have been proposed, namely the Montgomery form, the Jacobi form, the Hessian form, and the Brier-Joye addition formula. They aim at improving security or efficiency of the underlying scalar multiplications. We analyze the effectiveness of the exceptional procedure attack to some addition formulas. We conclude that the exceptional procedure attack is infeasible against the curves whose order are prime, i.e., the recommended curves by several standards. However, the exceptional procedure attack on the Brier-Joye addition formula is feasible, because it yields non-standard exceptional points. We propose an attack that revealsa few bitso f the secret scalar, provided that this multiplier is constant and fixed. By the experiment over the standard elliptic curves, we have found many non-standard exceptional points even though the standard addition formula over the curves has no exceptional point. When a new addition formula isde veloped, we should be cautious about the proposed attack.

References

[1]

ANSI X9.62, Public Key Cryptography for the Financial Services Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA), draft, 1998.

[2]

I. Biehl, B. Meyer, and V. Müller, "Differential Fault Attackson Elliptic Curve Cryptosystems", CRYPTO 2000 , LNCS 1880, pp.131-146, Springer-Verlag, 2000.

[3]

O. Billet and M. Joye, "The Jacobi Model of an Elliptic Curve and Side-Channel Analysis", Cryptology ePrint Archive, Report 2002/125, 2002.

[4]

D. Boneh, R. DeMillo, and R. Lipton, "On the Importance of Checking Cryptographic Protocolsfor Faults", Eurocrypt'97 , LNCS 1233, pp. 37- 51, Springer-Verlag, 1997.

[5]

E. Brier and M. Joye, "Weierstraß Elliptic Curves and Side-Channel Attacks", PKC 2002 , LNCS 2274, pp.335-345, Springer-Verlag, 2002.

[6]

I. Blake, G. Seroussi, and N. Smart, Elliptic Curves in Cryptography , Cambridge University Press, 1999.

[7]

H. Cohen, A. Miyaji and T. Ono, "Efficient Elliptic Curve Exponentiation using Mixed Coordinates", Asiacrypt'98 , LNCS 1514, Springer-Verlag, pp.51-65, 1998.

[8]

IEEE P1363, Standard Specificationsfor Public-Key Cryptography, 2000. Available from http://groupe.ieee.org/groups/1363/

[9]

T. Izu and T. Takagi, "On the Security of Brier-Joye's Addition Formula for Weierstrass-form Elliptic Curves", Technical Report, No. TI-3/02, Technische Universität Darmstadt, 2002.

[10]

M. Joye and J. Quisqiater, "Hessian Elliptic Curves and Side-Channel Attacks", CHES 2001 , LNCS 2162, pp. 412-420, Springer-Verlag, 2001.

[11]

C. Kocher, J. Jaffe, and B. Jun, "Differential Power Analysis", Crypto'99 , LNCS 1666, pp. 388-397, Springer-Verlag, 1999.

[12]

L. Law, A. Menezes, M. Qu, J. Solinas, and S. Vanstone, "An Efficient Protocol for Authenticated Key Agreement", Technical report CORR 98-05, University of Waterloo, 1998.

[13]

P. Liardet and N. Smart, "Preventing SPA/DPA in ECC System using the Jacobi Form", CHES 2001 , LNCS 2162, pp. 401-411, Springer-Verlag, 2001.

[14]

K. Okeya, H. Kurumatani, and K. Sakurai, "Elliptic Curves with the Montgomery Form and their cryptographic Applications", PKC 2000 , LNCS 1751, pp. 446-465, Springer-Verlag, 2000.

[15]

Standards for Efficient Cryptography Group (SECG), Specification of Standards for Efficient Cryptography. Available from http://www.secg.org

[16]

J. Silverman, The Arithmetic of Elliptic Curves , GMT 106, Springer-Verlag, 1986.

[17]

N. Smart, "The Hessian Form of an Elliptic Curve", CHES 2001 , LNCS 2162, pp.118-125, Springer-Verlag, 2001.

Cited By

Renes JCostello CBatina L(2016)Complete Addition Formulas for Prime Order Elliptic CurvesProceedings, Part I, of the 35th Annual International Conference on Advances in Cryptology --- EUROCRYPT 2016 - Volume 966510.5555/3081770.3081786(403-428)Online publication date: 8-May-2016
https://dl.acm.org/doi/10.5555/3081770.3081786
Koziel BAzarderakhsh RMozaffari-Kermani M(2015)Low-Resource and Fast Binary Edwards Curves CryptographyProceedings of the 16th International Conference on Progress in Cryptology -- INDOCRYPT 2015 - Volume 946210.1007/978-3-319-26617-6_19(347-369)Online publication date: 6-Dec-2015
https://dl.acm.org/doi/10.1007/978-3-319-26617-6_19
Miele ALenstra A(2015)Efficient Ephemeral Elliptic Curve Cryptographic KeysProceedings of the 18th International Conference on Information Security - Volume 929010.1007/978-3-319-23318-5_29(524-547)Online publication date: 9-Sep-2015
https://dl.acm.org/doi/10.1007/978-3-319-23318-5_29
Show More Cited By

Exceptional Procedure Attackon Elliptic Curve Cryptosystems
1. Security and privacy
  1. Cryptography
    1. Public key (asymmetric) techniques
2. Theory of computation

Recommendations

Evolution of hyperelliptic curve cryptosystems
ICDCIT'10: Proceedings of the 6th international conference on Distributed Computing and Internet Technology

Due to short operand size, Hyperelliptic Curve Cryptosystem (HECC) of genus 3 is well suited for all kinds of embedded processor architectures, where resources such as storage, time or power are constrained. In the implementation of HECC, a significant ...
Pipelined Computation of Scalar Multiplication in Elliptic Curve Cryptosystems (Extended Version)

In the current work, we propose a pipelining scheme for implementing Elliptic Curve Cryptosystems (ECC). The scalar multiplication is the dominant operation in ECC. It is computed by a series of point additions and doublings. The pipelining scheme is ...
Some improved algorithms for hyperelliptic curve cryptosystems using degenerate divisors
ICISC'04: Proceedings of the 7th international conference on Information Security and Cryptology

Hyperelliptic curve cryptosystems (HECC) can be good alternatives to elliptic curve cryptosystems, and there is a good possibility to improve the efficiency of HECC due to its flexible algebraic structure. Recently, an efficient scalar multiplication ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

PKC '03: Proceedings of the 6th International Workshop on Theory and Practice in Public Key Cryptography: Public Key Cryptography

January 2003

366 pages

ISBN:354000324X

Editor:
Yvo Desmedt

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 06 January 2003

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Renes JCostello CBatina L(2016)Complete Addition Formulas for Prime Order Elliptic CurvesProceedings, Part I, of the 35th Annual International Conference on Advances in Cryptology --- EUROCRYPT 2016 - Volume 966510.5555/3081770.3081786(403-428)Online publication date: 8-May-2016
https://dl.acm.org/doi/10.5555/3081770.3081786
Koziel BAzarderakhsh RMozaffari-Kermani M(2015)Low-Resource and Fast Binary Edwards Curves CryptographyProceedings of the 16th International Conference on Progress in Cryptology -- INDOCRYPT 2015 - Volume 946210.1007/978-3-319-26617-6_19(347-369)Online publication date: 6-Dec-2015
https://dl.acm.org/doi/10.1007/978-3-319-26617-6_19
Miele ALenstra A(2015)Efficient Ephemeral Elliptic Curve Cryptographic KeysProceedings of the 18th International Conference on Information Security - Volume 929010.1007/978-3-319-23318-5_29(524-547)Online publication date: 9-Sep-2015
https://dl.acm.org/doi/10.1007/978-3-319-23318-5_29
Bernstein DHamburg MKrasnova ALange TSadeghi AGligor VYung M(2013)ElligatorProceedings of the 2013 ACM SIGSAC conference on Computer & communications security10.1145/2508859.2516734(967-980)Online publication date: 4-Nov-2013
https://dl.acm.org/doi/10.1145/2508859.2516734
Danger JGuilley SHoogvorst PMurdica CNaccache D(2012)Low-Cost countermeasure against RPAProceedings of the 11th international conference on Smart Card Research and Advanced Applications10.1007/978-3-642-37288-9_8(106-122)Online publication date: 28-Nov-2012
https://dl.acm.org/doi/10.1007/978-3-642-37288-9_8
Chatterjee ASengupta I(2012)High-Speed unified elliptic curve cryptosystem on FPGAs using binary huff curvesProceedings of the 16th international conference on Progress in VLSI Design and Test10.1007/978-3-642-31494-0_28(243-251)Online publication date: 1-Jul-2012
https://dl.acm.org/doi/10.1007/978-3-642-31494-0_28
Devigne JJoye M(2011)Binary huff curvesProceedings of the 11th international conference on Topics in cryptology: CT-RSA 201110.5555/1964621.1964653(340-355)Online publication date: 14-Feb-2011
https://dl.acm.org/doi/10.5555/1964621.1964653
Chatterjee ASengupta IAtienza DXie YAyala JStevens K(2011)FPGA implementation of binary edwards curve usingternary representationProceedings of the 21st edition of the great lakes symposium on Great lakes symposium on VLSI10.1145/1973009.1973025(73-78)Online publication date: 2-May-2011
https://dl.acm.org/doi/10.1145/1973009.1973025
Hisil HWong KCarter GDawson E(2008)Twisted Edwards Curves RevisitedProceedings of the 14th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology10.1007/978-3-540-89255-7_20(326-343)Online publication date: 7-Dec-2008
https://dl.acm.org/doi/10.1007/978-3-540-89255-7_20
Bernstein DLange TRezaeian Farashahi R(2008)Binary Edwards CurvesProceeding sof the 10th international workshop on Cryptographic Hardware and Embedded Systems10.1007/978-3-540-85053-3_16(244-265)Online publication date: 10-Aug-2008
https://dl.acm.org/doi/10.1007/978-3-540-85053-3_16
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Table of Contents