Network Working Group R. Struik Internet Draft independent Intended status: Informational July 5, 2010 Expires: January 2011 Facilitating Speed-ups of Elliptic Curve Based Schemes draft-struik-ecc-efficiencies-00.txt Abstract We discuss several methods that can be used to accelerate the verification step of ECC-based signature schemes. These include a 40% efficiency improvement of ordinary ECDSA signature verification and even a factor 2.4x efficiency improvement when ECDSA certificate verification is combined with the key computation step in Diffie- Hellman-based protocols, such as static-ECDH and ECMQV. This challenges the conventional wisdom that with ECC-based signature schemes, signature verification is always considerably slower than signature generation and slower than RSA signature verification. Results apply to all prime curves standardized by NIST, the NSA 'Suite B' curves, and the so-called Brainpool curves. While the efficiency advantages of these methods are most apparent for a slightly modified version of ECDSA, these can also be enjoyed if the signer appends a small number of bits ("side information") to standardized ECDSA signatures or generates these ECDSA signatures in a particular "fast verification friendly" way. Since the latter can be done as a post-processing operation by any third party, this does not require changes to the standardized specifications of ECDSA (or, e.g., recertification by a Certificate Authority). Status of this Memo This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. This document may not be modified, and derivative works of it may not be created, except to publish it as an RFC and to translate it into languages other than English. This document may contain material from IETF Documents or IETF Contributions published or made publicly available before November 10, 2008. The person(s) controlling the copyright in some of this material may not have granted the IETF Trust the right to allow modifications of such material outside the IETF Standards Process. Without obtaining an adequate license from the person(s) controlling the copyright in such materials, this document may not be modified Struik Expires January 5, 2011 [Page 1] Internet-Draft Facilitating ECC Speed-ups July 2010 outside the IETF Standards Process, and derivative works of it may not be created outside the IETF Standards Process, except to format it for publication as an RFC or to translate it into languages other than English. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet- Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html This Internet-Draft will expire on January 5, 2011. Copyright Notice Copyright (c) 2010 IETF Trust and the persons identified as the document authors. All rights reserved. This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. Table of Contents 1. Introduction...................................................3 2. ECDSA and Modified ECDSA.......................................3 3. Security Considerations........................................5 4. IANA Considerations............................................6 5. Conclusions....................................................6 6. References.....................................................6 Struik Expires January 5, 2011 [Page 2] Internet-Draft Facilitating ECC Speed-ups July 2010 6.1. Normative References......................................6 6.2. Informative References....................................6 7. Acknowledgments................................................8 1. Introduction The elliptic curve digital signature algorithm (ECDSA) is a widely standardized variant of the original ElGamal signature scheme. As is the case with most ElGamal signature schemes, ECDSA has the property that signature verification is about twice as slow as signature generation (and many times slower if the signer is afforded the luxury of precomputation). The opposite is true in the RSA signature scheme with small encryption exponent e, where signature verification is many times faster than generation. Thus speeding up ECDSA signature verification is a problem of considerable practical importance. Recently, some techniques that significantly enhance the efficiency of ECDSA signature verification have been introduced [4], [5], [15]. This document aims to facilitate the optional use of these techniques, so as to foster wide-scale adoption. 2. ECDSA and Modified ECDSA With ECDSA, signatures consist of two non-negative integers, called "r" and "s" in [2]. Here, the signature component "r" is derived from an ephemeral private key R:=(x1,y1):=kG (cf. [2]) using a publicly known algorithm. We call the signature scheme that results in signature components (R, s), rather than (r,s), the "modified ECDSA scheme". We provide a summary of technical properties of ECDSA and Modified ECDSA below (for a more detailed discussion, cf. [4]): 1. Equivalence of operation. ECDSA Ordinary Verify yields a verdict on whether a particular ECDSA signature (r,s) over a message m signed by an entity with authentic public key Q is valid. Fast ECDSA Verify, as described in Section 4.2 [4], yields the same verdict and, thus, is equivalent to Ordinary ECDSA Verify. 2. Performance comparison. ECDSA Fast Verify relies on correctly recovering the ephemeral elliptic curve point R used during the ECDSA signing operation and then checking a particular elliptic curve equation. In general, reconstruction of this value from signature component r yields two candidate solutions (R, -R), rather than one. Struik Expires January 5, 2011 [Page 3] Internet-Draft Facilitating ECC Speed-ups July 2010 Thus, verification may necessitate trying either value to see if the verification equation is satisfied. Performance is as follows: If the verifier can always discard one of the two candidate solutions (R, -R), the speed-up of ECDSA signature verification is roughly 40%. This situation occurs if one knows ECDSA signatures have been generated in a "Fast Verify friendly" way (e.g., by changing the sign of signature component s if appropriate) or if there is some side information communicated with the ECDSA signature that allows efficiently discarding one of these solutions. If the verifier cannot discard one of the two candidate solutions (R,-R), the speed-up of ECDSA signature verification is only roughly 8%, since one has to try either value of R and has no way of knowing which of the two values is the correct one. This situation occurs if ECDSA signatures have been generated in the "standard" way [1] and there is no side information communicated with the ECDSA signature that allows discarding one of these solutions. Note that while the average speed-up is 8%, the per-signature speed-up is between +40% (correct value of R picked first) and -12% (incorrect value of R picked first). The following compliance aspects seem to apply: 1. Standards Compliance of ECDSA Fast Verify. ECDSA Ordinary Verify and ECDSA Fast Verify are equivalent operations. Thus, it seems that any implementation of ECDSA Fast Verify will automatically be compliant with standards that specify ECDSA Ordinary Verify (this includes ANSI X9.62-2005). 2. Standards Compliance of ECDSA Sign. The elliptic curve point R used for computing the ECDSA signature (r,s) can be recomputed by any party from the signature and the public key of the signer alone. In particular, the value of R does not leak any information on the internal mechanics of the signing operation (including the signer's private key). Thus, it seems that any implementation of ECDSA that exposes this value R as an additional output of the ECDSA signing operation would be compliant with standards that specify ECDSA Signing (this includes [1]). This would essentially mean that ECDSA* Signing would be compliant. Note, though, that Struik Expires January 5, 2011 [Page 4] Internet-Draft Facilitating ECC Speed-ups July 2010 the standard does not stipulate anything on additional output parameters of the ECDSA signing or verification operation. 3. Post-processing operations. Any party may be able to change the s component of the ECDSA signature without impacting the validity hereof: validity of ECDSA signatures does not depend on the sign of signature component s. This allows implementation of an efficient mechanism for putting an ECDSA signature into a 'Fast Verify friendly' format (by changing the sign of signature component s depending on inspection of R) as a post-processing operation. Note that this can be done efficiently in a standards compliant way if implementations of ECDSA signing that expose the ephemeral public key used in the signing process are standards compliant (i.e., it depends on the answer to #2 above). Furthermore, note that ECDSA has no way of preventing any party from executing this post-processing operation (since it can be done, e.g., while the signature is in transit). This suggests that this *should* be allowed for compliant implementations. Additional techniques that result in speed-up of ECDSA signature generation and those of related signature schemes will be described in a later version of this document. The techniques described are most beneficial if reconstruction of the ephemeral key R used during ECDSA signature generation from signature component r is a 1-1 mapping. This could be facilitated by generating these so as to allow discarding one of the pair (R,-R) of ephemeral keys that normally would result from this reconstruction operation, via a predetermined rule. As an example, one could change the signature (r,s) into (r,-s) if the y-coordinate of R during signature verification has an odd integer value. This could be indicated via an OID number. 3. Security Considerations The techniques to accelerate elliptic curve schemes discussed in this submission are most advantageous if the signature scheme ECDSA (or ECGDSA) are generated in a particular way, so as to ensure that conversions between the original scheme and the modified scheme are 1-1 mappings. One can show that for elliptic curves widely used in practice (such as the so-called NIST curves, the NSA 'Suite B' curves, and Brainpool curves) this transformation results in an equally secure scheme. For details re ECDSA and modified ECDSA, cf., e.g., [4]; for details re combined key agreement and signature Struik Expires January 5, 2011 [Page 5] Internet-Draft Facilitating ECC Speed-ups July 2010 verification, cf., e.g., [15]. More details for other schemes, such as ECGDSA, will be provided in a later version of this document. 4. IANA Considerations This document contains a request to IANA to assign new OIDs for ECDSA signatures generated so as to most efficiently making available the efficiency enhancements described in this document. A detailed list will be provided in a later version of this document. 5. Conclusions We described various techniques that can be used to accelerate ECDSA signature verification, either separately, or combined with other signature verifications, or with key computations. We also outlined how to enable a world where one would be able to reap the benefits of these techniques always, via the use of a new OID. As poor man's version, one could simply phase out generation of ECDSA signatures in a non-friendly format (which can be done since there are several orders of magnitude difference between actual and potential deployment right now). 6. References 6.1. Normative References [1] ANSI X9.62-1998, Public Key Cryptography for the Financial Services Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA), American National Standard for Financial Services, American Bankers Association, January 7, 1999. [2] FIPS Pub 186-3, Digital Signature Standard (DSS), Federal Information Processing Standards Publication 186-3, US Department of Commerce/National Institute of Standards and Technology, Gaithersburg, Maryland, USA, February 2009. (Includes change notice, October 5, 2001.) 6.2. Informative References [3] ANSI X9.63-2001, Public Key Cryptography for the Financial Services Industry: Key Agreement and Key Transport Using Elliptic Curve Cryptography, American National Standard for Financial Services, American Bankers Association, November 20, 2001. Struik Expires January 5, 2011 [Page 6] Internet-Draft Facilitating ECC Speed-ups July 2010 [4] A. Antipa, D.R. Brown, R. Gallant, R. Lambert, R. Struik, S.A. Vanstone, 'Accelerated Verification of ECDSA Signatures,' in Proceedings of Selected Areas in Cryptography - SAC2005, B. Preneel, S. Tavares, Eds., Lecture Notes in Computer Science, Vol. 3897, pp. 307-318, New York: Springer, 2006. [5] M. Bellare, J.A. Garay, T. Rabin, 'Fast Batch Verification for Modular Exponentiation and Digital Signatures,' in Proceedings of Advances in Cryptology - EUROCRYPT'98, K. Nyberg, Ed., Lecture Notes in Computer Science, Vol. 1403, pp. 236-250, New York: Springer-Verlag, 1998. [6] W. Diffie, M.E. Hellmann, 'New Directions in Cryptography,' IEEE.Trans.Inform.Theory, Vol. IT-22, pp. 644-654, 1976. [7] D.R. Hankerson, A.J. Menezes, S.A. Vanstone, Guide to Elliptic Curve Cryptography, New York: Springer, 2003. [8] D.J. Johnson, A.J. Menezes, S.A. Vanstone, 'The Elliptic Curve Digital Signature Algorithm (ECDSA),' International Journal of Information Security}, Vol. 1, pp. 36-63, 2001. [9] L. Law, A. Menezes, M. Qu, J. Solinas, S. Vanstone, 'An Efficient Protocol for Authenticated Key Agreement,' Centre for Applied Cryptographic Research, Corr 1998-05, University of Waterloo, Ontario, Canada, 1998. [10] D. McGrew, K. Igoe, M. Salter, 'Fundamental Elliptic Curve Cryptography Algorithms,' draft-mcgrew-fundamental-ecc-03, IETF draft, May 21, 2010. [11] P. Hoffman, 'Elliptic Curve DSA for DNSSec,' draft-hoffman- dnssec-ecdsa-01, IETF draft, January 25, 2010. [12] NIST Pub 800-56a, Recommendation for Pair-Wise Key Establishment Schemes Using Discrete Logarithm Cryptography (Revised), NIST Special Publication 800-56A, US Department of Commerce/National Institute of Standards and Technology, Springfield, Virginia, March 8, 2007. [13] J. Proos, 'Joint Sparse Forms and Generating Zero Columns when Combing,' Centre for Applied Cryptographic Research, Corr 2003-23, University of Waterloo, Ontario, Canada, 2003. [14] J. Solinas, 'Low-Weight Binary Representations for Pairs of Integers,' Centre for Applied Cryptographic Research, Corr 2001-41, University of Waterloo, Ontario, Canada, 2001. Struik Expires January 5, 2011 [Page 7] Internet-Draft Facilitating ECC Speed-ups July 2010 [15] R. Struik, 'Speed-ups of elliptic curve-based schemes,' invited paper, presented at Fields Institute Workshop on New Directions in Cryptography, Ottawa, ON, June 25-27, 2008. [16] R. Struik, 'Speed-ups of Elliptic Curve Based Schemes,' rump session presentation to NIST Key Management Workshop, Gaithersburg, MD, June 8-9, 2009. [17] RFC 4492, Elliptic Curve Cryptography (ECC) Cipher Suites for Transport Layer Security (TLS), Internet Request for Comments 5912, S. Blake-Wilson, N. Boluard, V. Gupta, C. Hawk, B. Moeller, June 2010. [18] RFC 5114, Additional Diffie-Hellman Groups for Use with IETF Standards, Internet Request for Comments 5114, M. Lepinski, S. Kent, January 2010. [19] RFC 5280, Internet X.509 Public Key Infrastructure Certificate and Certificate Revocation List (CRL) Profile, Internet Request for Comments 5280, D. Cooper, S. Santesson, S. Farrell, S. Boeyen, R. Housley, W. Polk, May 2008. [20] RFC 5639, ECC Brainpool Standard Curves and Curve Generation, M. Lochter, J. Merkle, Internet Request for Comments 5912, March 2010. [21] RFC 5759, Suite B Certificate and Certificate Revocation List (CRL) Profile, J. Solinas, L. Zieglar, Internet Request for Comments 5759, January 2010. 7. Acknowledgments The techniques discussed in this submissions benefitted from discussions with the Certicom Research team. This document was prepared using 2-Word-v2.0.template.dot. Authors' Addresses Rene Struik Independent 723 Carlaw Avenue Toronto, ON Canada M4K 3K8 Email: rstruik.ext@gmail.com Struik Expires January 5, 2011 [Page 8]