One document matched: draft-struik-ecc-efficiencies-00.txt
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]| PAFTECH AB 2003-2026 | 2026-04-22 12:51:01 |