Advertisement

The Security of DSA and ECDSA

Bypassing the Standard Elliptic Curve Certification Scheme
  • Serge Vaudenay
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 2567)

Abstract

DSA and ECDSA are well established standards for digital signature based on the discrete logarithmp roblem. In this paper we survey known properties, certification issues regarding the public parameters, and security proofs.

ECDSA also includes a standard certification scheme for elliptic curve which is assumed to guarantee that the elliptic curve was randomly selected, preventing from any potential malicious choice. In this paper we show how to bypass this scheme and certify any elliptic curve in characteristic two. The prime field case is also studied. Although this does not lead to any attack at this time since all possible malicious choices which are known at this time are specifically checked, this demonstrates that some part of the standard is not well designed. We finally propose a tweak.

References

  1. [1]
    ANSI X9.30. Public Key Cryptography for the Financial Services Industry: Part 1: The Digital Signature Algorithm( DSA). American National Standard Institute. American Bankers Association. 1997. 309, 310Google Scholar
  2. [2]
    ANSI X9.62. Public Key Cryptography for the Financial Services Industry: The Elliptic Curve Digital Signature Algorithm( ECDSA). American National Standard Institute. American Bankers Association. 1998. 310, 318Google Scholar
  3. [3]
    ISO/IEC 14888. Information Technology — Security Techniques — Digital Signatures with Appendix. ISO/IEC, Geneva, Switzerland, 1998. 315Google Scholar
  4. [4]
    Secure Hash Standard. Federal Information Processing Standard publication #180-1. U. S. Department of Commerce, National Institute of Standards and Technology, 1995. 310Google Scholar
  5. [5]
    Digital Signature Standard (DSS). Federal Information Processing Standards publication #186-2. U. S. Department of Commerce, National Institute of Standards and Technology, 2000. 309, 310, 312Google Scholar
  6. [7]
    D. Bleichenbacher. Generating ElGamal Signatures without Knowing the Secret Key. In Advances in Cryptology EUROCRYPT’96, Zaragoza, Spain, Lectures Notes in Computer Science 1070, pp. 10–18, Springer-Verlag, 1996.Google Scholar
  7. [8]
    E. Brickell, D. Pointcheval, S. Vaudenay, M. Yung. Design Validations for Discrete LogarithmBased Signature Schemes. In Public Key Cryptography, Melbourne, Australia, Lectures Notes in Computer Science 1751, pp. 276–292, Springer-Verlag, 2000. 314, 315Google Scholar
  8. [9]
    D.R.L. Brown. The Exact Security of ECDSA. Technical Report CORR 2000–34, Certicom Research, 2000. http://www.cacr.math.uwaterloo.ca 315
  9. [10]
    T. ElGamal. Cryptography and Logarithms over Finite Fields. PhD Thesis, Stanford University, 1984. 309Google Scholar
  10. [11]
    T. ElGamal. A Public-key Cryptosystem and a Signature Scheme based on Discrete Logarithms. In Advances in Cryptology CRYPTO’84, Santa Barbara, California, U.S.A., Lectures Notes in Computer Science 196, pp. 10–18, Springer-Verlag, 1985. 309Google Scholar
  11. [12]
    T. ElGamal. A Public-key Cryptosystem and a Signature Scheme based on Discrete Logarithms. IEEE Transactions on Information Theory, vol. IT-31, pp. 469–472, 1985. 309CrossRefMathSciNetGoogle Scholar
  12. [13]
    N. Koblitz. CM-Curves with good Cryptographic Properties. In Advances in Cryptology CRYPTO’91, Santa Barbara, California, U.S.A., Lectures Notes in Computer Science 576, pp. 279–287, Springer-Verlag, 1992.Google Scholar
  13. [14]
    R. Lidl, H. Niederreiter. Introduction to Finite Fields and their Applications, Revised Edition, Cambridge University Press, 1994. 322Google Scholar
  14. [15]
    J. Malone-Lee, N.P. Smart. Modifications of ECDSA. To appear in the proceedings of SAC’02. 315Google Scholar
  15. [16]
    U. Maurer, S. Wolf. Lower Bounds on Generic Algorithms in Groups. In Advances in Cryptology EUROCRYPT’98, Espoo, Finland, Lectures Notes in Computer Science 1403, pp. 72–84, Springer-Verlag, 1998.Google Scholar
  16. [17]
    J. Monnerat. Computation of the Discrete Logarithm on Elliptic Curves of Trace One — Tutorial. Technical report IC 200249, EPFL, 2002. http://lasecwww.epfl.ch 318
  17. [18]
    D. Pointcheval, J. Stern. Security Arguments for Digital Signatures and Blind Signatures. Journal of Cryptology, vol. 13, pp. 361–396, 2000. 314zbMATHCrossRefGoogle Scholar
  18. [19]
    D. Pointcheval, S. Vaudenay. On Provable Security for Digital Signature Algorithms. Technical report LIENS 96-17, Ecole Normale Supérieure, 1996. 314, 315Google Scholar
  19. [20]
    C.P. Schnorr. Efficient Identification and Signature for Smart Cards. In Advances in Cryptology CRYPTO’89, Santa Barbara, California, U.S.A., Lectures Notes in Computer Science 435, pp. 235–251, Springer-Verlag, 1990. 315Google Scholar
  20. [21]
    C.P. Schnorr. Efficient Identification and Signature for Smart Cards. Journal of Cryptology, vol. 4, pp. 161–174, 1991. 315zbMATHCrossRefGoogle Scholar
  21. [22]
    V. Shoup. Lower Bounds for Discrete Logarithms and Related Problems. In Advances in Cryptology EUROCRYPT’97, Konstanz, Germany, Lectures Notes in Computer Science 1233, pp. 256–266, Springer-Verlag, 1997. 316Google Scholar
  22. [23]
    N.P. Smart. The Discrete Logarithm Problem on Elliptic Curves of Trace One. Journal of Cryptology, vol. 12, pp. 193–196, 1999. 318zbMATHCrossRefMathSciNetGoogle Scholar
  23. [24]
    J. Stern, D. Pointcheval, J. Malone-Lee, N.P. Smart. Flaws in Applying Proof Methodologies to Signature Schemes. In Advances in Cryptology CRYPTO’02, Santa Barbara, California, U.S.A., Lectures Notes in Computer Science 2442, pp. 93–110, Springer-Verlag, 2002. 311, 316Google Scholar
  24. [25]
    S. Vaudenay. Hidden Collisions on DSS. In Advances in Cryptology CRYPTO’96, Santa Barbara, California, U.S.A., Lectures Notes in Computer Science 1109, pp. 83–88, Springer-Verlag, 1996. 312, 313Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2003

Authors and Affiliations

  • Serge Vaudenay
    • 1
  1. 1.Swiss Federal Institute of Technology (EPFL)Switzerland

Personalised recommendations