第1页 / 共163页
第2页 / 共163页
第3页 / 共163页
第4页 / 共163页
第5页 / 共163页
第6页 / 共163页
第7页 / 共163页
第8页 / 共163页
ANSI-X962-2005.pdf
American National Standard for Financial Services ANS X9.62–2005 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 Standards Institute
ANS X9.62–2005 ii © 2005 – All rights reserved Foreword 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 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 that 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, 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 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. 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 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 America
ANS X9.62-2005 © 2005 – All rights reserved iii Contents Foreword......................................................................................................................................................................ii Figures.......................................................................................................................................................................vii Tables........................................................................................................................................................................viii Introduction................................................................................................................................................................ix 1 Scope..............................................................................................................................................................1 2 Conformance..................................................................................................................................................1 3 Normative references....................................................................................................................................2 4 Terms and definitions...................................................................................................................................2 5 Symbols and abbreviated terms..................................................................................................................4 6 Cryptographic Ingredients............................................................................................................................6 6.1 Security Levels..............................................................................................................................................6 6.2 Cryptographic Hash Functions....................................................................................................................7 7 The Elliptic Curve Digital Signature Algorithm (ECDSA)..........................................................................7 7.1 Overview.........................................................................................................................................................7 7.2 Setup Process................................................................................................................................................7 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 Key..................................................................................................................9 Annex A (normative) Normative Number-Theoretic Algorithms.........................................................................11 A.1 Primality........................................................................................................................................................11 A.1.1 A Probabilistic Primality Test.....................................................................................................................11 A.1.2 Checking for Near Primality.......................................................................................................................12 A.2 Finite Fields..................................................................................................................................................12 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 Curves....................................................................................19 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 Validation..........................................................................................................26 A.4.3 Elliptic Curve Key Pair Generation............................................................................................................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 --`,``,,,`,,,,`,,```,``,,,,,-`-`,,`,,`,`,,`---
ANS X9.62–2005 iv © 2005 – All rights reserved A.5.5 Octet String to Field Element.....................................................................................................................28 A.5.6 Field Element to Integer..............................................................................................................................29 A.5.7 Point to Octet String....................................................................................................................................29 A.5.8 Octet String to Point....................................................................................................................................30 Annex B (normative) Recommended Elliptic Curve Domain Parameters.........................................................32 Annex C (normative) Assurances..........................................................................................................................36 Annex D (normative) Random Number Generation..............................................................................................37 D.1 Generation of Elliptic Curve Private Keys................................................................................................37 D.2 A DRBG Using HMAC..................................................................................................................................37 D.2.1 Overview.......................................................................................................................................................37 D.2.2 Instantiation of the HMAC_DRBG..............................................................................................................38 D.2.3 Reseeding a HMAC_DRBG Instantiation..................................................................................................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 Introduction..................................................................................................................................................45 E.2 Common Object Identifiers.........................................................................................................................45 E.3 Algorithm Identification..............................................................................................................................45 E.4 Hash Functions............................................................................................................................................46 E.5 Finite Fields..................................................................................................................................................47 E.6 Elliptic Curve Points....................................................................................................................................50 E.7 Elliptic Curve Domain Parameters.............................................................................................................50 E.8 Digital Signatures........................................................................................................................................54 E.9 Elliptic Curve Public Keys..........................................................................................................................56 E.10 ASN.1 Module..............................................................................................................................................58 Annex F (normative) Backwards Compatibility with Legacy Implementations of ECDSA................................71 Annex G (informative) Mathematical Background and Examples.......................................................................73 G.1 The Finite Field Fp........................................................................................................................................73 G.2 The Finite Field F2m......................................................................................................................................74 G.2.1 Overview.......................................................................................................................................................74 G.2.2 Polynomial Bases........................................................................................................................................74 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 Fp................................................................................................................................76 G.4 Elliptic Curves 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 ECDSA..............................................................................................................78 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 F2....................................................................................................................81 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 Algorithms........................................................................84 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 --`,``,,,`,,,,`,,```,``,,,,,-`-`,,`,,`,`,,`---
ANS X9.62-2005 © 2005 – All rights reserved v I.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 F2m......................................................................................................87 I.1.7 Checking the Order of an Integer Modulo a Prime...................................................................................87 I.1.8 Computing the Order of an Integer Modulo a Prime................................................................................88 I.1.9 Constructing an Integer of a Given Order Modulo a Prime.....................................................................88 I.2 Polynomials over a Finite Field..................................................................................................................88 I.2.1 The GCD of Polynomials over a Finite Field.............................................................................................88 I.2.2 Finding a Root in F2m of 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 Algorithms............................................................................................................................91 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 Generation Method....................................93 J.1 Overview.......................................................................................................................................................93 J.2 Miscellaneous Number-Theoretic Algorithms..........................................................................................93 J.2.1 Overview.......................................................................................................................................................93 J.2.2 Evaluating Jacobi Symbols........................................................................................................................93 J.2.3 Finding Square Roots Modulo a Power of Two........................................................................................94 J.2.4 Exponentiation Modulo a Polynomial........................................................................................................95 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 Nearly Prime Order over Fp......................................................................................................100 J.4.3 Finding a Nearly Prime Order over F2m....................................................................................................102 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............................................................................................107 K.2.1 Overview.....................................................................................................................................................107 K.2.2 Software Attacks........................................................................................................................................108 K.2.3 Hardware Attacks......................................................................................................................................109 K.2.4 Key Length Considerations......................................................................................................................109 K.3 Elliptic Curve Domain Parameters...........................................................................................................110 K.4 Key Pairs....................................................................................................................................................112 K.5 ECDSA........................................................................................................................................................113 Annex L (informative) Examples of ECDSA and Elliptic Curves........................................................................116 L.1 Overview.....................................................................................................................................................116 L.2 Examples of Data Conversion Methods..................................................................................................116 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-Element-to-Integer Conversion........................................................................117 --`,``,,,`,,,,`,,```,``,,,,,-`-`,,`,,`,`,,`---
ANS X9.62–2005 vi © 2005 – All rights reserved L.2.7 Two 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 Field......................................................................................120 L.3.2 Example of ECDSA over a 283-bit Binary Field......................................................................................120 L.3.3 Example of ECDSA over a 571-bit Binary Field......................................................................................121 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 F2m......................................................................................124 L.5.1 Overview.....................................................................................................................................................124 L.5.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 Fp........................................................................................130 L.6.1 Overview.....................................................................................................................................................130 L.6.2 Two Example Curves over 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 Field........................................................................................135 L.6.6 An Example Curves over a 521-bit Prime Field......................................................................................135 Annex M (informative) ECDSA in Selected Other Standards.............................................................................137 M.1 Introduction................................................................................................................................................137 M.2 Other Specifications of ECDSA...............................................................................................................137 M.2.1 Introduction................................................................................................................................................137 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 NESSIE........................................................................................................................................................140 M.3 Applications of ECDSA in Other Standards...........................................................................................141 M.3.1 Introduction................................................................................................................................................141 M.3.2 American National Standards Institute...................................................................................................141 M.3.3 Internet Engineering Task Force.............................................................................................................142 Bibliography............................................................................................................................................................144 --`,``,,,`,,,,`,,```,``,,,,,-`-`,,`,,`,`,,`---
ANS X9.62-2005 © 2005 – All rights reserved vii Figures Figure A.1 — Data Conversions..............................................................................................................................27
ANS X9.62–2005 viii © 2005 – All rights reserved Tables 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 Polynomials........................................................................................................................33 Table B.4 —Coefficient b..........................................................................................................................................33 Table B.5 — Base Point Order, Hash Truncation Length and Cofactor..................................................................34 Table B.6 — Base Points (Compressed).................................................................................................................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 F2m....................................................................................80 Table H.2 — Irreducible trinomials xm+xk+1 over F2................................................................................................81 Table H.3 — Irreducible pentanomials xm+xk3+xk2+xk1+1 over F2............................................................................82 Table H.4 — Values of m for which F2m has both an ONB and a TPB over F2........................................................83 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-ρ method......109 Table K.2 — Expected end of lifetimes of the five recommended security levels..................................................109
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
