1、 American National Standard for Financial Services ANS X9.622005 Public Key Cryptography for the Financial Services Industry The Elliptic Curve Digital Signature Algorithm (ECDSA) Accredited Standards Committee X9, Inc. Financial Industry Standards Date Approved: November 16, 2005 American National
2、Standards Institute ANS X9.622005 ii 2005 All rights reservedForeword Approval of an American National Standard requires verification by ANSI that the requirements for due process, consensus, and other criteria for approval have been met by the standards developer. Consensus is established when, in
3、the judgment of the ANSI Board of Standards Review, substantial agreement has been reached by directly and materially affected interests. Substantial agreement means much more than a simple majority, but not necessarily unanimity. Consensus requires that all views and objections be considered, and t
4、hat a concerted effort be made toward their resolution. The use of American National Standards is completely voluntary; their existence does not in any respect preclude anyone, whether he or she has approved the standards or not from manufacturing, marketing, purchasing, or using products, processes
5、, or procedures not conforming to the standards. The American National Standards Institute does not develop standards and will in no circumstances give an interpretation of any American National Standard. Moreover, no person shall have the right or authority to issue an interpretation of an American
6、 National Standard in the name of the American National Standards Institute. Requests for interpretations should be addressed to the secretariat or sponsor whose name appears on the title page of this standard. CAUTION NOTICE: This American National Standard may be revised or withdrawn at any time.
7、The procedures of the American National Standards Institute require that action be taken to reaffirm, revise, or withdraw this standard no later than five years from the date of approval. Published by Accredited Standards Committee X9, Inc. Financial Services P.O. Box 4035 Annapolis, Maryland 21403
8、X9 Online http:/www.x9.org Copyright 2005 by Accredited Standards Committee X9, Inc. All rights reserved. No part of this publication may be reproduced in any form, in an electronic retrieval system or otherwise, without prior written permission of the publisher. Printed in the United States of Amer
9、ica ANS X9.62-2005 2005 All rights reserved iiiContents Forewordii Figures.vii Tablesviii Introductionix 1 Scope 1 2 Conformance1 3 Normative references2 4 Terms and definitions .2 5 Symbols and abbreviated terms 4 6 Cryptographic Ingredients6 6.1 Security Levels 6 6.2 Cryptographic Hash Functions 7
10、 7 The Elliptic Curve Digital Signature Algorithm (ECDSA) 7 7.1 Overview.7 7.2 Setup Process7 7.3 Signing Process.8 7.4 Verifying Process 9 7.4.1 Verification with the Public Key.9 7.4.2 Verification with the Private Key9 Annex A (normative) Normative Number-Theoretic Algorithms.11 A.1 Primality11 A
11、.1.1 A Probabilistic Primality Test.11 A.1.2 Checking for Near Primality .12 A.2 Finite Fields12 A.2.1 Overview.12 A.2.2 Prime Fields .12 A.2.3 Characteristic Two Fields .13 A.3 Elliptic Curve Domain Parameters.16 A.3.1 Preliminaries 16 A.3.2 Necessary Conditions for Secure Elliptic Curves19 A.3.3 E
12、lliptic Curve Selection.20 A.3.4 Base Point (Generator) Selection 21 A.3.5 Selection of Elliptic Curve Domain Parameters .23 A.4 Elliptic Curve Key Pairs 26 A.4.1 Preliminaries 26 A.4.2 Elliptic Curve Public Key Validation26 A.4.3 Elliptic Curve Key Pair Generation 27 A.5 Data Conversions 27 A.5.1 O
13、verview.27 A.5.2 Integer to Octet String.28 A.5.3 Octet String to Integer.28 A.5.4 Field Element to Octet String .28 ANS X9.622005 iv 2005 All rights reservedA.5.5 Octet String to Field Element .28 A.5.6 Field Element to Integer29 A.5.7 Point to Octet String29 A.5.8 Octet String to Point30 Annex B (
14、normative) Recommended Elliptic Curve Domain Parameters .32 Annex C (normative) Assurances36 Annex D (normative) Random Number Generation 37 D.1 Generation of Elliptic Curve Private Keys 37 D.2 A DRBG Using HMAC37 D.2.1 Overview.37 D.2.2 Instantiation of the HMAC_DRBG38 D.2.3 Reseeding a HMAC_DRBG I
15、nstantiation 40 D.2.4 Pseudorandom Bit Generation Using the HMAC_DRBG 41 D.2.5 Using HMAC_DRBG to Generate Elliptic Curve Private Keys 43 D.3 Requirements on Deterministic Random Number Generators.43 Annex E (normative) ASN.1 Syntax for ECDSA.45 E.1 Introduction45 E.2 Common Object Identifiers.45 E.
16、3 Algorithm Identification 45 E.4 Hash Functions46 E.5 Finite Fields47 E.6 Elliptic Curve Points50 E.7 Elliptic Curve Domain Parameters.50 E.8 Digital Signatures54 E.9 Elliptic Curve Public Keys 56 E.10 ASN.1 Module 58 Annex F (normative) Backwards Compatibility with Legacy Implementations of ECDSA7
17、1 Annex G (informative) Mathematical Background and Examples .73 G.1 The Finite Field Fp73 G.2 The Finite Field F2m74 G.2.1 Overview.74 G.2.2 Polynomial Bases74 G.2.3 Trinomial and Pentanomial Bases.75 G.2.4 Normal Bases.75 G.2.5 Gaussian Normal Bases .76 G.3 Elliptic Curves over Fp76 G.4 Elliptic C
18、urves over F2m 77 G.5 Model for ECDSA Signatures .77 G.5.1 System Setup.77 G.5.2 Key Pair Generation 78 G.5.3 Signature Generation for ECDSA 78 G.5.4 Signature Verification for ECDSA78 Annex H (informative) Tables of Trinomials, Pentanomials and Gaussian Normal Bases .80 H.1 Tables of GNB for F2m.80
19、 H.2 Irreducible Trinomials over F281 H.3 Irreducible Pentanomials over F2.82 H.4 Table of Fields F2m which have both an ONB and a TPB over F2.83 Annex I (informative) Informative Number-Theoretic Algorithms84 I.1 Finite Fields and Modular Arithmetic 84 I.1.1 Exponentiation in a Finite Field .84 I.1
20、.2 Inversion in a Finite Field .84 ANS X9.62-2005 2005 All rights reserved vI.1.3 Generating Lucas Sequences 84 I.1.4 Finding Square Roots Modulo a Prime .85 I.1.5 Trace and Half-Trace Functions.86 I.1.6 Solving Quadratic Equations over F2m87 I.1.7 Checking the Order of an Integer Modulo a Prime.87
21、I.1.8 Computing the Order of an Integer Modulo a Prime88 I.1.9 Constructing an Integer of a Given Order Modulo a Prime.88 I.2 Polynomials over a Finite Field88 I.2.1 The GCD of Polynomials over a Finite Field.88 I.2.2 Finding a Root in F2mof an Irreducible Binary Polynomial.89 I.2.3 Change of Basis.
22、89 I.2.4 Checking Binary Polynomials for Irreducibility .90 I.3 Elliptic Curve Algorithms91 I.3.1 Scalar Multiplication (Computing a Multiple of a Elliptic Curve Point)91 I.3.2 Verifying the Order of an Elliptic Curve Point 91 Annex J (informative) Complex Multiplication (CM) Elliptic Curve Generati
23、on Method93 J.1 Overview.93 J.2 Miscellaneous Number-Theoretic Algorithms93 J.2.1 Overview.93 J.2.2 Evaluating Jacobi Symbols 93 J.2.3 Finding Square Roots Modulo a Power of Two94 J.2.4 Exponentiation Modulo a Polynomial95 J.2.5 Factoring Polynomials over Fp(Special Case).95 J.2.6 Factoring Polynomi
24、als over F2(Special Case) .96 J.3 Class Group Calculations.96 J.3.1 Overview.96 J.3.2 Class Group and Class Number.97 J.3.3 Reduced Class Polynomial.97 J.4 Complex Multiplication .99 J.4.1 Overview.99 J.4.2 Finding a Nearly Prime Order over Fp100 J.4.3 Finding a Nearly Prime Order over F2m102 J.4.4
25、Constructing a Curve and Point (Prime Case) .103 J.4.5 Constructing a Curve and Point (Binary Case) 105 Annex K (informative) Security Considerations.107 K.1 Overview.107 K.2 Elliptic Curve Discrete Logarithm Problem 107 K.2.1 Overview.107 K.2.2 Software Attacks108 K.2.3 Hardware Attacks 109 K.2.4 K
26、ey Length Considerations109 K.3 Elliptic Curve Domain Parameters.110 K.4 Key Pairs 112 K.5 ECDSA 113 Annex L (informative) Examples of ECDSA and Elliptic Curves116 L.1 Overview.116 L.2 Examples of Data Conversion Methods116 L.2.1 Overview.116 L.2.2 Example of Integer-to-Octet-String Conversion.116 L
27、.2.3 Example of Octet-String-to-Integer Conversion.116 L.2.4 Two Examples of Field-Element-to-Octet-String Conversion.116 L.2.5 Two Examples of Octet-String-to-Field-Element Conversion.117 L.2.6 Two Examples of Field-Element-to-Integer Conversion117 ANS X9.622005 vi 2005 All rights reservedL.2.7 Two
28、 Examples of Point-to-Octet-String Conversion .117 L.2.8 Two Examples of Octet-String-to-Point Conversion .119 L.3 Examples of ECDSA over the Field F2m.120 L.3.1 Example of ECDSA over a 233-bit Binary Field120 L.3.2 Example of ECDSA over a 283-bit Binary Field120 L.3.3 Example of ECDSA over a 571-bi
29、t Binary Field121 L.4 Examples of ECDSA over the Field Fp.122 L.4.1 Example of ECDSA over a 224-bit Prime Field.122 L.4.2 Example of ECDSA over a 256-bit Prime Field.122 L.4.3 Example of ECDSA over a 521-bit Prime Field.123 L.5 Examples of Elliptic Curves over the Field F2m124 L.5.1 Overview.124 L.5
30、.2 Three Example Curves over F2163.124 L.5.3 Two Example Curves over F2233.125 L.5.4 Two Example Curves over F2283.126 L.5.5 Two Example Curves over F2409.128 L.5.6 Two Example Curves over F2571.129 L.6 Examples of Elliptic Curves over the Field Fp130 L.6.1 Overview.130 L.6.2 Two Example Curves over
31、 192-bit Prime Fields 131 L.6.3 Two Example Curves over 224-bit Prime Fields 132 L.6.4 Two Example Curves over 256-bit Prime Fields 133 L.6.5 An Example Curve over a 384-bit Prime Field135 L.6.6 An Example Curves over a 521-bit Prime Field135 Annex M (informative) ECDSA in Selected Other Standards .
32、137 M.1 Introduction137 M.2 Other Specifications of ECDSA .137 M.2.1 Introduction137 M.2.2 Previous 1998 Version of this Standard ANS X9.62 138 M.2.3 NIST Publication FIPS 186-2.138 M.2.4 IEEE Std 1363-2000 .138 M.2.5 SEC 1 and SEC 2 .140 M.2.6 IS 14888-3 and IS 15946-2.140 M.2.7 NESSIE140 M.3 Appli
33、cations of ECDSA in Other Standards .141 M.3.1 Introduction141 M.3.2 American National Standards Institute .141 M.3.3 Internet Engineering Task Force .142 Bibliography144 ANS X9.62-2005 2005 All rights reserved viiFigures Figure A.1 Data Conversions 27 ANS X9.622005 viii 2005 All rights reservedTabl
34、es Table A.1 Bounds for n at each Approved security level.18 Table B.1 Recommended Domain Parameters.32 Table B.2 Recommended Elliptic Curves 32 Table B.3 Reduction Polynomials33 Table B.4 Coefficient b33 Table B.5 Base Point Order, Hash Truncation Length and Cofactor 34 Table B.6 Base Points (Compr
35、essed) .34 Table D.1 Security Level that that may be provided by each hash function in a DRBG .38 Table H.1 The types of GNB that shall be used with F2m80 Table H.2 Irreducible trinomials xm+xk+1 over F281 Table H.3 Irreducible pentanomials xm+xk3+xk2+xk1+1 over F282 Table H.4 Values of m for which
36、F2mhas both an ONB and a TPB over F283 Table J.1 Elliptic curves with CM by nine discriminants 104 Table K.1 Computing power needed to find elliptic curve discrete logarithms using the Pollard- method109 Table K.2 Expected end of lifetimes of the five recommended security levels109 ANS X9.62-2005 20
37、05 All rights reserved ixIntroduction Business practice has changed with the introduction of computer-based technologies. The substitution of electronic transactions for their paper-based predecessors has reduced costs and improved efficiency. Trillions of dollars in funds and securities are transfe
38、rred daily by telephone, wire services, and other electronic communication mechanisms. The high value or sheer volume of such transactions within an open environment exposes the financial community and its customers to potentially severe risks from the accidental or deliberate disclosure, alteration
39、, substitution, or destruction of data. These risks are compounded by interconnected networks, and the increased number and sophistication of malicious adversaries. Electronically communicated data may be secured through the use of symmetrically keyed encryption algorithms (e.g. ANS X9.52, Triple-DE
40、A) in combination with public-key cryptography-based key management techniques. Some of the conventional “due care” controls used with paper-based transactions are unavailable in electronic transactions. Examples of such controls are safety paper, which protects integrity, and handwritten signatures
41、 or embossed seals, which indicate the intent of the originator to be legally bound. In an electronic-based environment, controls shall be in place that provide the same degree of assurance and certainty as in a paper environment. The financial community is responding to these needs. This standard,
42、ANS X9.622005, Public Key Cryptography For The Financial Services Industry: The Elliptic Curve Digital Signatures Algorithm defines a mechanism designed to facilitate the secure authentication and non-repudiation of data. This Standard describes a method for digital signatures using the elliptic cur
43、ve analog of the Digital Signature algorithm (DSA) (ANSI X9.30 Part 1). Elliptic curve cryptography is a form of public-key (asymmetric) cryptography, whose algorithms are typically used: a) To create digital signatures (in conjunction with a hash algorithm), and b) To establish secret keys securely
44、 for use in symmetric-key cryptography. When implemented with proper controls, the techniques of this Standard provide: a) Data integrity, b) Data origin authentication, and c) Non-repudiation of the message origin and message. Additionally, when used in conjunction with an appropriately implemented
45、 message identifier, the techniques of this Standard provide the capability of detecting duplicate transactions. It is the Committees belief that the proper implementation of this Standard should also contribute to the enforceability of some legal obligations. The use of this Standard, together with
46、 appropriate controls, may have a legal effect, including the apportionment of liability for erroneous or fraudulent transactions and the satisfaction of statutory or contractual “due care” requirements. The legal implications associated with the use of this Standard may be affected by case law and
47、legislation, including the Uniform Commercial Code Article 4A on Funds Transfers (Article 4A). ANS X9.622005 x 2005 All rights reservedThe details of Article 4A address, in part, the use of commercially reasonable security procedures and the effect of using such procedures on the apportionment of li
48、ability between a customer and a bank. A security procedure is provided by Article 4A-201 “for the purpose of (i) verifying that a payment order or communication amending or canceling a payment order originated is that of the customer, or (ii) detecting an error in the transmission or the content of
49、 the payment order or communication.” The commercial reasonableness of a security procedure is determined by the criteria established in Article 4A-201. While the techniques specified in this standard are designed to facilitate authentication and non-repudiation applications, the standard does not guarantee that a particular implementation is secure. It is the responsibility of the financial institution to put an overall process in place with the necessary controls to ensure that the process is securely implemented
