ANSI ASC X9 X9.42-2003 Public Key Cryptography for the Financial Services Industry Agreement of Symmetric Keys Using Discrete Logarithm Cryptography.pdf

1、 ASC X9, Inc. 2003 All rights reserved American National Standard for Financial Services X9.422003 Public Key Cryptography for the Financial Services Industry: Agreement of Symmetric Keys Using Discrete Logarithm Cryptography Accredited Standards Committee X9, Incorporated Financial Industry Standar

2、ds Date Approved: November 19, 2003 American National Standards Institute ASC X9, Inc. 2003 All rights reserved ANS X9.422003 ii ASC X9, Inc. 2003 All rights reserved Contents 1 SCOPE.1 2 NORMATIVE REFERENCES .1 3 DEFINITIONS.2 4. SYMBOLS AND ABBREVIATIONS 7 4.1 SYMBOLS 7 4.2 ABBREVIATIONS 9 5. ORGA

3、NIZATION 9 6. APPLICATION .10 7. BASIC ALGORITHMS, FUNCTIONS, AND CONVERS ION RULES .11 7.1 DOMAIN PARAMETER GENERATION 11 7.2 DOMAIN PARAMETER VALIDATION. 12 7.3 PRIVATE/PUBLIC KEY GENERATION 12 7.4 PUBLIC KEY VALIDATION 13 7.5 CALCULATION OF SHARED SECRET ELEMENTS 14 7.5.1 Diffie-Hellman Algorithm

4、14 7.5.2 MQV Algorithm.15 7.6 DATA CONVERSION RULES 18 7.6.1 Integer-to-Bit-String Conversion18 7.6.2 Bit-String-to-Integer Conversion18 7.6.3 Integer-to-Octet-String Conversion.18 7.6.4 Octet-String-to-Integer Conversion.19 7.7 KEY DERIVATION FROM A SHARED SECRET VALUE 19 7.7.1 Key Derivation Funct

5、ion Based on ASN.120 7.7.2 Key Derivation Function Based on Concatenation.21 7.8 MAC COMPUTATION 23 7.9 ANS X9.42 IMPLEMENTATION VALIDATION. 23 8 KEY AGREEMENT SCHEMES .24 8.1 KEY AGREEMENT USING THE DIFFIE-HELLMAN ALGORITHM. 24 8.1.1 dhStatic.24 8.1.2 dhEphem.26 8.1.3 dhOneFlow.28 8.1.4 dhHybrid1.2

6、9 8.1.5 dhHybrid2.32 8.1.6 dhHybridOneFlow34 8.2 KEY AGREEMENT USING THE MQV ALGORITHM. 36 8.2.1 MQV2 Interactive Form of the MQV Algorithm36 8.2.2 MQV1 Store and Forward Form of the MQV Algorithm38 ANS X9.422003 ASC X9, Inc. 2003 All rights reserved iiiANNEX A (NORMATIVE) PARAMETER SYNTAX AND ENCOD

7、ING RULES .41 A.1 FINITE FIELD SYNTAX 41 A.2 PARAMETER SYNTAX. 42 A.2.1 Domain Parameters43 A.2.2 Scheme Parameters.44 A.3 PUBLIC KEY SYNTAX 45 A.4 SCHEME SYNTAX. 47 A.4.1 dhStatic.48 A.4.2 dhEphem.48 A.4.3 dhOneFlow.49 A.4.4 dhHybrid1.49 A.4.5 dhHybrid2.49 A.4.6 dhHybridOneFlow49 A.4.7 MQV2 50 A.4.

8、8 MQV1 50 A.4.9 Key Agreement Object Sets .50 A.5 KEY DERIVATION SYNTAX 51 A.6 MAC FOR ANS X9.42 IMPLEMENTATION VALIDATION 52 A.7 ASN.1 MODULE 52 ANNEX B (NORMATIVE) DOMAIN PARAMETER GENERATION.60 B.1 GENERATION OF PRIME MODULI 60 B.1.1 Probabilistic Primality Test 60 B.1.2 Generation of Primes .62

9、B.1.3 Validation of Primes .64 B.2 SELECTION OF A GENERATOR FOR Q-ORDER SUBGROUP 66 B.3 JACOBI SYMBOL ALGORIT HM (REVISED) 66 ANNEX C (NORMATIVE) PSEUDO-RANDOM NUMBER GENERATOR.69 C.1 PSEUDO-RANDOM NUMBER GENERATOR BASED ON G(T, C) . 69 C.2 PSEUDO-RANDOM NUMBER GENERATOR USING THE TDEA . 70 ANNEX D

10、(INFORMATIVE) CALCULATION EXAMPLES 72 D.1 GENERATION OF DOMAIN PARAMETERS. 72 D.1.1 Static-Key Domain Parameters (1024-bit prime)72 D.1.2 Ephemeral-Key Domain Parameters (1024-bit prime)73 D.2 GENERATION OF PRIVATE/PUBLIC KEYS. 74 D.2.1 Ephemeral Private keys for U and V .74 D.2.2 Static Private and

11、 Public Keys for U and V .74 D.3 SHARED SECRET VALUE CALCULATION USING DIFFIE-HELLMAN ALGORITHM. 75 D.3.1 dhStatic.75 D.3.2 dhEphem.76 D.3.3 dhOneFlow.77 D.3.4 dhHybrid1.78 D.3.5 dhHybrid2.79 D.3.6 dhHybridOneFlow81 D.4 SHARED SECRET VALUE CALCULATIONS USING MQV ALGORITHM 82 D.4.1 MQV2 Interactive F

12、orm .82 D.4.2 MQV1 Store and Forward Form.87 D.5 KEY DERIVATION FUNCTION. 90 D.5.1 Examples of the Key Derivation function Based on Concatenation.90 ANS X9.422003 iv ASC X9, Inc. 2003 All rights reserved D.5.2 Example of the Derivation Function Based on ASN.1 - Single Invocation Where Keys are Gener

13、ated for One Purpose 95 D.6 MAC COMPUTATION 97 ANNEX E (INFORMATIVE) SECURITY CONSIDERATIONS . 100 E.1 SECURITY OF THE DISCRETE LOGARITHM PROBLEM IN GF(P)* 100 E.1.1 Discrete Logarithm Problem and Key Agreement . 100 E.1.2 Complexity of the Discrete Logarithm Problem. 100 E.1.3 Expense of Solving th

14、e Discrete Logarithm Problem 101 E.1.4 Relative Security Strength and Appropriate Key Lengths. 102 E.2 SECURITY OF KEY AGREEMENT SCHEMES104 E.2.1 Man-in-the-Middle-Attack 104 E.2.2 Small Subgroup Attacks on Invalid Public Keys. 105 E.2.3 Security Attributes of the Schemes in this Standard. 105 E.3 G

15、UIDELINES ON SELECTING AN ANS X9.42 KEY AGREEMENT SCHEME.108 E.4 GENERAL SECURITY CONSIDERATIONS.111 E.4.1 Setup Negotiation. 111 E.4.2 Private/Public Key Management. 111 E.4.3 Parameter Management 112 E.4.4 Generation of Public and Private Keys 112 ANNEX F (INFORMATIVE) SUMMARY OF CHANGES FROM ANS

16、X9.422001 114 F.1 TECHNICAL ISSUES114 F.1.1 Range of bases in Miller-Rabin test 114 F.1.2 Perfect squares in Lucas test 114 F.1.3 Discriminants with Jacobi symbol 0 in Lucas test. 114 F.1.4 Errors in the Jacobi symbol algorithm. 114 F.2 EDITORIAL ISSUES.115 F.2.1 Lucas-Lehmer vs. Lucas 115 F.2.2 Ref

17、erence for combining Miller-Rabin and Lucas tests 115 F.2.3 Binary expansion 115 F.2.4 Inconsistent notation in the Lucas test. 115 F.2.5 Modular division in Lucas test. 115 ANNEX G (INFORMATIVE) REFERENCES 116 ANS X9.422003 ASC X9, Inc. 2003 All rights reserved vTables Table 1 Key Agreement Scheme

18、dhStatic 25 Table 2 Key Agreement Scheme dhEphem. 27 Table 3 Key Agreement Scheme dhOneFlow . 29 Table 4 Key Agreement Scheme dhHybrid1 31 Table 5 Key Agreement Scheme dhHybrid2 33 Table 6 Key Agreement Scheme dhHybridOneFlow. 35 Table 7 Key Agreement Scheme MQV2 38 Table 8 Key Agreement Scheme MQV1

19、 40 Table E.1 Complexity of Attacks on Cryptographic Algorithms .103 Table E.2 Approximate Equivalence of Keys In Bits To Known Best General Attacks .104 Table E.3 Attributes Provided by Key Agreement Schemes 107 ANS X9.422003 vi ASC X9, Inc. 2003 All rights reserved Forward Approval of an American

20、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

21、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

22、 is completely voluntary; their existence does not in any respect preclude anyone, whether he 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 d

23、evelop 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 interpretat

24、ion 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,

25、revise, or withdraw this standard no later than five years from the date of approval. Published by Accredited Standards Committee X9, Incorporated Financial Industry Standards P.O. Box 4035 Annapolis, MD 21403 USA X9 Online http:/www.x9.org Copyright 2003 ASC X9, Inc. All rights reserved. No part of

26、 this publication may be reproduced in any form, in an electronic retrieval system or otherwise, without prior written permission of the publisher. Published in the United States of America. ANS X9.422003 ASC X9, Inc. 2003 All rights reserved viiIntroduction Business practice has changed with the in

27、troduction 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 transferred daily by telephone, wire services, and other electronic communication mech

28、anisms. 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 accidental or deliberate disclosure, alteration, substitution, or destruction of data. These risks are compounded by interconnecte

29、d networks, and the increased number and sophistication of malicious adversaries. Electronically communicated data may be secured using symmetrically-keyed encryption algorithms (e.g. ANS X9.52, Triple -DEA) in combination with public key cryptography-based key management techniques. This standard,

30、ANS X9.42-2003, Public Key Cryptography For The Financial Services Industry: Agreement of Symmetric Keys Using Discrete Logarithm Cryptography, defines the secure establishment of cryptographic data for the keying of symmetrically-keyed algorithms (e.g. TDEA). Schemes are provided for the agreement

31、of symmetric keys using Diffie-Hellman and MQV algorithms. The Diffie-Hellman key agreement mechanism is a well-understood and widely implemented public key technique that facilitates cost-effective cryptographic key agreement across modern distributed electronic networks such as the Internet. The M

32、QV algorithm is a variation of the Diffie-Hellman algorithm that has more security attributes and may provide better performance over analogous Diffie-Hellman methods. Because the Diffie-Hellman and the MQV techniques are based on the same fundamental mathematics as the Digital Signature Algorithm (

33、DSA) (see 4), additional efficiencies and functionality may be obtained by combining these and other cryptographic techniques. While the techniques specified in this standard are designed to facilitate key management applications, the standard does not guarantee that a particular implementation is s

34、ecure (even though the techniques specified in the standard are a basis for security). 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. Furthermore, the controls should include the

35、 application of appropriate audit tests in order to verify compliance. This standard also does not guarantee interoperability (though, again, the techniques specified in this standard are a basis for interoperability). ANS X9.42 is not a standard for interoperability, but a set of ASC X9-approved ke

36、y establishment schemes with varying attributes. NOTE The users attention is called to the possibility that compliance with this standard may require use of an invention covered by patent rights. By publication of this standard, no position is taken with respect to the validity of this claim or of a

37、ny patent rights in connection therewith. The patent holder has, however, filed a statement of willingness to grant a license under these rights on reasonable and nondiscriminatory terms and conditions to applicants desiring to obtain such a license. Details may be obtained from the standards develo

38、per. Suggestions for the improvement or revision of this Standard are welcome. They should be sent to the X9 Committee Secretariat, Accredited Standards Committee X9, Inc., Financial Industry Standards, P.O. Box 4035, Annapolis, MD 21403 USA. ANS X9.422003 viii ASC X9, Inc. 2003 All rights reserved

39、This Standard was processed and approved for submittal to ANSI by the Accredited Standards Committee on Financial Services, X9. Committee approval of the Standard does not necessarily imply that all the committee members voted for its approval. The X9 committee had the following members: Harold Deal

40、, X9 Chairman Vincent DeSantis, X9 Vice-Chairman Cynthia Fuller, Executive Director Isabel Bailey, Managing Director Organization Represented Representative ACI Worldwide Cindy Rink ACI Worldwide Jim Shaffer American Express Company Mike Jones American Express Company Barbara Wakefield American Fina

41、ncial Services Association John Freeman American Financial Services Association Mark Zalewski Bank o f America Mack Hicks Bank of America Richard Phillips Bank of America Daniel Welch Bank One Corporation Jacqueline Pagan BB and T Michael Saviak BB and T Woody Tyner Cable the two keys have the prope

42、rty that, given the public key, it is computationally infeasible to derive the private key. Bit string A bit string is an ordered sequence of 0s and 1s. The left-most bit is the most-significant bit of the string. The right-most bit is the least-significant bit of the string. Certificate The public

43、key and identity of an entity, together with some other information, that is rendered unforgeable by signing the certificate with the private key of the Certification Authority that issued the certificate. Certification authority (CA) An entity trusted by one or more other entities to create and ass

44、ign certificates. ANS X9.422003 ASC X9, Inc. 2003 All rights reserved 3Cryptographic hash function A (mathematical) function that maps values from a large (possibly very large) domain into a smaller range. The function satisfies the following properties: 1. (One-way) It is computationally infeasible

45、 to find any input that maps to any pre-specified output; 2. (Collision Free) It is computationally infeasible to find any two distinct inputs that map to the same output. Cryptographic key (key) A parameter that determines, possibly with other parameters, the operation of a cryptographic function s

46、uch as: (a) the transformation from plaintext to ciphertext and vice versa; (b) the synchronized generation of keying material; (c) digital signature computation or validation. Cryptography The discipline which embodies principles, means and methods for the transformation of data in order to hide it

47、s information content, prevent its undetected modification, prevent its unauthorized use or a combination thereof. Diffie-Hellman private key Given a set of domain parameters (p, q, g), a Diffie -Hellman private key x is an integer where 1 x q-1. Note that it is acceptable to further restrict the in

48、terval to 1 2m-1. GF(p)* has a cyclic subgroup of order q. rU,V Party U or Party Vs ephemeral private key. rU,V is a random or pseudo-random integer with 1 rU,V (qe-1) when ephemeral-key domain parameters are used. For the case where only static-key domain parameters are being used, then rU,V should

49、 be chosen such that 1 rU,V (qs-1). Note that it is acceptable to further restrict the interval to 1 rU,V (qs-1), if desired. seed Random value that is used as input to a pseudorandom number generator. tU,V Party U or Party Vs ephemeral public key. tU,V is an element of GF(pe), tU,V = (ge rU,V) mod pe when ephemeral-key domain parameters are used. For the case where only static-key domain parameters are being used, tU,V = (gs rU,V) mod ps. tU,V tU,V =