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 Copyright American National Standards Institute Provided by IHS under license with ANSI Not for ResaleNo reproduction or networking permitted without license from IHS-,-,-ANS X9.622005 ii 2005 All rights reservedForeword Approval of an American National Standard requires verifica
3、tion 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 the judgment of the ANSI Board of Standards Review, substantial agreement has been reached by directly and materially affected in
4、terests. Substantial agreement means much more than a simple majority, but not necessarily unanimity. Consensus requires that all views and objections be considered, and that a concerted effort be made toward their resolution. The use of American National Standards is completely voluntary; their exi
5、stence 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, or procedures not conforming to the standards. The American National Standards Institute does not develop standards and will in
6、 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 National Standard in the name of the American National Standards Institute. Requests for interpretations should be addressed to
7、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. The procedures of the American National Standards Institute require that action be taken to reaffirm, revise, or withdraw this st
8、andard 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 X9 Online http:/www.x9.org Copyright 2005 by Accredited Standards Committee X9, Inc. All rights reserved. No part of this publica
9、tion 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 America Copyright American National Standards Institute Provided by IHS under license with ANSI Not for ResaleNo reproduction or netw
10、orking permitted without license from IHS-,-,-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 L
11、evels 6 6.2 Cryptographic Hash Functions 7 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
12、-Theoretic Algorithms.11 A.1 Primality11 A.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 Condi
13、tions for Secure Elliptic Curves19 A.3.3 Elliptic 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 Gen
14、eration 27 A.5 Data Conversions 27 A.5.1 Overview.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 Copyright American National Standards Institute Provided by IHS under license with ANSI Not for ResaleNo reproduction or networking permitted
15、 without license from IHS-,-,-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 (normative) Recommended Elliptic Curve Domain Parameters .32 Annex C (normative) Assuran
16、ces36 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 Instantiation 40 D.2.4 Pseudorandom Bit Generation Using the HMAC_DRBG 41 D.2.5 Using HM
17、AC_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.3 Algorithm Identification 45 E.4 Hash Functions46 E.5 Finite Fields47 E.6 Elliptic Cur
18、ve 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 ECDSA71 Annex G (informative) Mathematical Background and Examples .73 G.1 The Finite Field F
19、p73 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 Curves over F2m 77 G.5 Model for ECDSA Signatures .77 G.5.1 System Setup.77 G.5.2 Key Pa
20、ir 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 H.2 Irreducible Trinomials over F281 H.3 Irreducible Pentanomials over F2.82 H.4 Table
21、 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.2 Inversion in a Finite Field .84 Copyright American National Standards Institute Prov
22、ided by IHS under license with ANSI Not for ResaleNo reproduction or networking permitted without license from IHS-,-,-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 Quad
23、ratic Equations over F2m87 I.1.7 Checking the Order of an Integer Modulo a Prime.87 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.
24、2 Finding a Root in F2mof an Irreducible Binary Polynomial.89 I.2.3 Change of Basis.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 Curv
25、e Point 91 Annex J (informative) Complex Multiplication (CM) Elliptic Curve Generation 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 Polyno
26、mial95 J.2.5 Factoring Polynomials over Fp(Special Case).95 J.2.6 Factoring Polynomials 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
27、 Nearly Prime Order over Fp100 J.4.3 Finding a Nearly Prime Order over F2m102 J.4.4 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
28、 107 K.2.1 Overview.107 K.2.2 Software Attacks108 K.2.3 Hardware Attacks 109 K.2.4 Key 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 Met
29、hods116 L.2.1 Overview.116 L.2.2 Example of Integer-to-Octet-String Conversion.116 L.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
30、-Element-to-Integer Conversion117 Copyright American National Standards Institute Provided by IHS under license with ANSI Not for ResaleNo reproduction or networking permitted without license from IHS-,-,-ANS X9.622005 vi 2005 All rights reservedL.2.7 Two Examples of Point-to-Octet-String Conversion
31、 .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-bit Binary Field121 L.4 Examples of ECDSA over
32、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.2 Three Example Curves over F2163.124 L.5.3
33、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 192-bit Prime Fields 131 L.6.3 Two Example C
34、urves 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 .137 M.1 Introduction137 M.2 Other Specificati
35、ons 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 Applications of ECDSA in Other Standards .141 M.3.
36、1 Introduction141 M.3.2 American National Standards Institute .141 M.3.3 Internet Engineering Task Force .142 Bibliography144 Copyright American National Standards Institute Provided by IHS under license with ANSI Not for ResaleNo reproduction or networking permitted without license from IHS-,-,-ANS
37、 X9.62-2005 2005 All rights reserved viiFigures Figure A.1 Data Conversions 27 Copyright American National Standards Institute Provided by IHS under license with ANSI Not for ResaleNo reproduction or networking permitted without license from IHS-,-,-ANS X9.622005 viii 2005 All rights reservedTables
38、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 (Compress
39、ed) .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 F2m
40、has 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 Copyright American N
41、ational Standards Institute Provided by IHS under license with ANSI Not for ResaleNo reproduction or networking permitted without license from IHS-,-,-ANS X9.62-2005 2005 All rights reserved ixIntroduction Business practice has changed with the introduction of computer-based technologies. The substi
42、tution of electronic transactions for their paper-based predecessors has reduced costs and improved efficiency. Trillions of dollars in funds and securities are transferred daily by telephone, wire services, and other electronic communication mechanisms. The high value or sheer volume of such transa
43、ctions within an open environment exposes the financial community and its customers to potentially severe risks from the accidental or deliberate disclosure, alteration, substitution, or destruction of data. These risks are compounded by interconnected networks, and the increased number and sophisti
44、cation of malicious adversaries. Electronically communicated data may be secured through the use of symmetrically keyed encryption algorithms (e.g. ANS X9.52, Triple-DEA) in combination with public-key cryptography-based key management techniques. Some of the conventional “due care” controls used wi
45、th paper-based transactions are unavailable in electronic transactions. Examples of such controls are safety paper, which protects integrity, and handwritten signatures or embossed seals, which indicate the intent of the originator to be legally bound. In an electronic-based environment, controls sh
46、all 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, ANS X9.622005, Public Key Cryptography For The Financial Services Industry: The Elliptic Curve Digital Signatures Algorithm defines
47、a mechanism designed to facilitate the secure authentication and non-repudiation of data. This Standard describes a method for digital signatures using the elliptic curve analog of the Digital Signature algorithm (DSA) (ANSI X9.30 Part 1). Elliptic curve cryptography is a form of public-key (asymmet
48、ric) cryptography, whose algorithms are typically used: a) To create digital signatures (in conjunction with a hash algorithm), and b) To establish secret keys securely 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 message identifier, the techniques of this Standard provide the capability of detecting duplicate transactions. It is the Com
