| < draft-mcgrew-fundamental-ecc-03.txt | draft-mcgrew-fundamental-ecc-04.txt > | |||
|---|---|---|---|---|
| Network Working Group D. McGrew | Network Working Group D. McGrew | |||
| Internet-Draft Cisco Systems | Internet-Draft Cisco Systems | |||
| Intended status: Informational K. Igoe | Intended status: Informational K. Igoe | |||
| Expires: November 22, 2010 M. Salter | Expires: June 13, 2011 M. Salter | |||
| National Security Agency | National Security Agency | |||
| May 21, 2010 | December 10, 2010 | |||
| Fundamental Elliptic Curve Cryptography Algorithms | Fundamental Elliptic Curve Cryptography Algorithms | |||
| draft-mcgrew-fundamental-ecc-03.txt | draft-mcgrew-fundamental-ecc-04.txt | |||
| Abstract | Abstract | |||
| This note describes the fundamental algorithms of Elliptic Curve | This note describes the fundamental algorithms of Elliptic Curve | |||
| Cryptography (ECC) as they are defined in some early references. | Cryptography (ECC) as they were defined in some early references. | |||
| These descriptions may be useful for implementing the fundamental | These descriptions may be useful for implementing the fundamental | |||
| algorithms without using any of the specialized methods that were | algorithms without using any of the specialized methods that were | |||
| developed in following years. Only elliptic curves defined over | developed in following years. Only elliptic curves defined over | |||
| fields of characteristic greater than three are in scope; these | fields of characteristic greater than three are in scope; these | |||
| curves are those used in Suite B. | curves are those used in Suite B. | |||
| Status of this Memo | Status of this Memo | |||
| This Internet-Draft is submitted in full conformance with the | This Internet-Draft is submitted in full conformance with the | |||
| provisions of BCP 78 and BCP 79. | provisions of BCP 78 and BCP 79. | |||
| skipping to change at page 1, line 38 ¶ | skipping to change at page 1, line 38 ¶ | |||
| Internet-Drafts are working documents of the Internet Engineering | Internet-Drafts are working documents of the Internet Engineering | |||
| Task Force (IETF). Note that other groups may also distribute | Task Force (IETF). Note that other groups may also distribute | |||
| working documents as Internet-Drafts. The list of current Internet- | working documents as Internet-Drafts. The list of current Internet- | |||
| Drafts is at http://datatracker.ietf.org/drafts/current/. | Drafts is at http://datatracker.ietf.org/drafts/current/. | |||
| Internet-Drafts are draft documents valid for a maximum of six months | Internet-Drafts are draft documents valid for a maximum of six months | |||
| and may be updated, replaced, or obsoleted by other documents at any | and may be updated, replaced, or obsoleted by other documents at any | |||
| time. It is inappropriate to use Internet-Drafts as reference | time. It is inappropriate to use Internet-Drafts as reference | |||
| material or to cite them other than as "work in progress." | material or to cite them other than as "work in progress." | |||
| This Internet-Draft will expire on November 22, 2010. | This Internet-Draft will expire on June 13, 2011. | |||
| Copyright Notice | Copyright Notice | |||
| Copyright (c) 2010 IETF Trust and the persons identified as the | Copyright (c) 2010 IETF Trust and the persons identified as the | |||
| document authors. All rights reserved. | document authors. All rights reserved. | |||
| This document is subject to BCP 78 and the IETF Trust's Legal | This document is subject to BCP 78 and the IETF Trust's Legal | |||
| Provisions Relating to IETF Documents | Provisions Relating to IETF Documents | |||
| (http://trustee.ietf.org/license-info) in effect on the date of | (http://trustee.ietf.org/license-info) in effect on the date of | |||
| publication of this document. Please review these documents | publication of this document. Please review these documents | |||
| skipping to change at page 2, line 16 ¶ | skipping to change at page 2, line 16 ¶ | |||
| the Trust Legal Provisions and are provided without warranty as | the Trust Legal Provisions and are provided without warranty as | |||
| described in the Simplified BSD License. | described in the Simplified BSD License. | |||
| Table of Contents | Table of Contents | |||
| 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4 | 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4 | |||
| 1.1. Conventions Used In This Document . . . . . . . . . . . . 4 | 1.1. Conventions Used In This Document . . . . . . . . . . . . 4 | |||
| 2. Mathematical Background . . . . . . . . . . . . . . . . . . . 5 | 2. Mathematical Background . . . . . . . . . . . . . . . . . . . 5 | |||
| 2.1. Modular Arithmetic . . . . . . . . . . . . . . . . . . . . 5 | 2.1. Modular Arithmetic . . . . . . . . . . . . . . . . . . . . 5 | |||
| 2.2. Group Operations . . . . . . . . . . . . . . . . . . . . . 5 | 2.2. Group Operations . . . . . . . . . . . . . . . . . . . . . 5 | |||
| 2.3. Finite Fields . . . . . . . . . . . . . . . . . . . . . . 7 | 2.3. The Finite Field Fp . . . . . . . . . . . . . . . . . . . 7 | |||
| 3. Elliptic Curve Groups . . . . . . . . . . . . . . . . . . . . 7 | 3. Elliptic Curve Groups . . . . . . . . . . . . . . . . . . . . 7 | |||
| 3.1. Homogeneous Coordinates . . . . . . . . . . . . . . . . . 8 | 3.1. Homogeneous Coordinates . . . . . . . . . . . . . . . . . 8 | |||
| 3.2. Other Coordinates . . . . . . . . . . . . . . . . . . . . 9 | 3.2. Other Coordinates . . . . . . . . . . . . . . . . . . . . 9 | |||
| 3.3. ECC Parameters . . . . . . . . . . . . . . . . . . . . . . 9 | 3.3. ECC Parameters . . . . . . . . . . . . . . . . . . . . . . 9 | |||
| 3.3.1. Discriminant . . . . . . . . . . . . . . . . . . . . . 10 | 3.3.1. Discriminant . . . . . . . . . . . . . . . . . . . . . 10 | |||
| 3.3.2. Security . . . . . . . . . . . . . . . . . . . . . . . 10 | 3.3.2. Security . . . . . . . . . . . . . . . . . . . . . . . 10 | |||
| 4. Elliptic Curve Diffie-Hellman (ECDH) . . . . . . . . . . . . . 11 | 4. Elliptic Curve Diffie-Hellman (ECDH) . . . . . . . . . . . . . 11 | |||
| 4.1. Data Types . . . . . . . . . . . . . . . . . . . . . . . . 11 | 4.1. Data Types . . . . . . . . . . . . . . . . . . . . . . . . 11 | |||
| 4.2. Compact Representation . . . . . . . . . . . . . . . . . . 11 | 4.2. Compact Representation . . . . . . . . . . . . . . . . . . 11 | |||
| 5. Elliptic Curve ElGamal Signatures . . . . . . . . . . . . . . 12 | 5. Elliptic Curve ElGamal Signatures . . . . . . . . . . . . . . 12 | |||
| 5.1. Background . . . . . . . . . . . . . . . . . . . . . . . . 12 | 5.1. Background . . . . . . . . . . . . . . . . . . . . . . . . 12 | |||
| 5.2. Hash Functions . . . . . . . . . . . . . . . . . . . . . . 12 | 5.2. Hash Functions . . . . . . . . . . . . . . . . . . . . . . 12 | |||
| 5.3. KT-IV Signatures . . . . . . . . . . . . . . . . . . . . . 13 | 5.3. KT-IV Signatures . . . . . . . . . . . . . . . . . . . . . 13 | |||
| 5.3.1. Keypair Generation . . . . . . . . . . . . . . . . . . 13 | 5.3.1. Keypair Generation . . . . . . . . . . . . . . . . . . 13 | |||
| 5.3.2. Signature Creation . . . . . . . . . . . . . . . . . . 13 | 5.3.2. Signature Creation . . . . . . . . . . . . . . . . . . 13 | |||
| 5.3.3. Signature Verification . . . . . . . . . . . . . . . . 14 | 5.3.3. Signature Verification . . . . . . . . . . . . . . . . 14 | |||
| 5.4. KT-I Signatures . . . . . . . . . . . . . . . . . . . . . 14 | 5.4. KT-I Signatures . . . . . . . . . . . . . . . . . . . . . 14 | |||
| 5.4.1. Keypair Generation . . . . . . . . . . . . . . . . . . 14 | 5.4.1. Keypair Generation . . . . . . . . . . . . . . . . . . 14 | |||
| 5.4.2. Signature Creation . . . . . . . . . . . . . . . . . . 14 | 5.4.2. Signature Creation . . . . . . . . . . . . . . . . . . 14 | |||
| 5.4.3. Signature Verification . . . . . . . . . . . . . . . . 15 | 5.4.3. Signature Verification . . . . . . . . . . . . . . . . 15 | |||
| 5.5. Converting KT-IV signatures to KT-I signatures . . . . . . 15 | 5.5. Converting KT-IV Signatures to KT-I Signatures . . . . . . 15 | |||
| 5.6. Rationale . . . . . . . . . . . . . . . . . . . . . . . . 16 | 5.6. Rationale . . . . . . . . . . . . . . . . . . . . . . . . 16 | |||
| 6. Converting between integers and octet strings . . . . . . . . 17 | 6. Converting Between Integers and Octet Strings . . . . . . . . 17 | |||
| 6.1. Octet-string-to-integer conversion . . . . . . . . . . . . 17 | 6.1. Octet-String-to-Integer Conversion . . . . . . . . . . . . 17 | |||
| 6.2. Integer-to-octet-string conversion . . . . . . . . . . . . 17 | 6.2. Integer-to-Octet-String Conversion . . . . . . . . . . . . 17 | |||
| 7. Interoperability . . . . . . . . . . . . . . . . . . . . . . . 18 | 7. Interoperability . . . . . . . . . . . . . . . . . . . . . . . 18 | |||
| 7.1. ECDH . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 | 7.1. ECDH . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 | |||
| 7.2. KT-I and ECDSA . . . . . . . . . . . . . . . . . . . . . . 18 | 7.2. KT-I and ECDSA . . . . . . . . . . . . . . . . . . . . . . 18 | |||
| 8. Validating an Implementation . . . . . . . . . . . . . . . . . 19 | 8. Validating an Implementation . . . . . . . . . . . . . . . . . 19 | |||
| 8.1. ECDH . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 | 8.1. ECDH . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 | |||
| 8.2. KT-I . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 | 8.2. KT-I . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 | |||
| 9. Intellectual Property . . . . . . . . . . . . . . . . . . . . 20 | 9. Intellectual Property . . . . . . . . . . . . . . . . . . . . 21 | |||
| 9.1. Disclaimer . . . . . . . . . . . . . . . . . . . . . . . . 21 | 9.1. Disclaimer . . . . . . . . . . . . . . . . . . . . . . . . 21 | |||
| 10. Security Considerations . . . . . . . . . . . . . . . . . . . 21 | 10. Security Considerations . . . . . . . . . . . . . . . . . . . 21 | |||
| 10.1. Subgroups . . . . . . . . . . . . . . . . . . . . . . . . 22 | 10.1. Subgroups . . . . . . . . . . . . . . . . . . . . . . . . 22 | |||
| 10.2. Diffie-Hellman . . . . . . . . . . . . . . . . . . . . . . 22 | 10.2. Diffie-Hellman . . . . . . . . . . . . . . . . . . . . . . 22 | |||
| 10.3. Group Representation and Security . . . . . . . . . . . . 22 | 10.3. Group Representation and Security . . . . . . . . . . . . 23 | |||
| 10.4. Signatures . . . . . . . . . . . . . . . . . . . . . . . . 23 | 10.4. Signatures . . . . . . . . . . . . . . . . . . . . . . . . 23 | |||
| 11. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 23 | 11. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 24 | |||
| 12. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 24 | 12. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 24 | |||
| 13. References . . . . . . . . . . . . . . . . . . . . . . . . . . 24 | 13. References . . . . . . . . . . . . . . . . . . . . . . . . . . 24 | |||
| 13.1. Normative References . . . . . . . . . . . . . . . . . . . 24 | 13.1. Normative References . . . . . . . . . . . . . . . . . . . 24 | |||
| 13.2. Informative References . . . . . . . . . . . . . . . . . . 25 | 13.2. Informative References . . . . . . . . . . . . . . . . . . 26 | |||
| Appendix A. Key Words . . . . . . . . . . . . . . . . . . . . . . 28 | Appendix A. Key Words . . . . . . . . . . . . . . . . . . . . . . 29 | |||
| Appendix B. Random Integer Generation . . . . . . . . . . . . . . 29 | Appendix B. Random Integer Generation . . . . . . . . . . . . . . 30 | |||
| Appendix C. Why Compact Representation Works . . . . . . . . . . 30 | Appendix C. Why Compact Representation Works . . . . . . . . . . 30 | |||
| Appendix D. Example ECC Parameter Set . . . . . . . . . . . . . . 30 | Appendix D. Example ECC Parameter Set . . . . . . . . . . . . . . 31 | |||
| Appendix E. Additive and multiplicative notation . . . . . . . . 31 | Appendix E. Additive and multiplicative notation . . . . . . . . 32 | |||
| Appendix F. Algorithms . . . . . . . . . . . . . . . . . . . . . 31 | Appendix F. Algorithms . . . . . . . . . . . . . . . . . . . . . 32 | |||
| F.1. Affine Coordinates . . . . . . . . . . . . . . . . . . . . 32 | F.1. Affine Coordinates . . . . . . . . . . . . . . . . . . . . 32 | |||
| F.2. Homogeneous Coordinates . . . . . . . . . . . . . . . . . 32 | F.2. Homogeneous Coordinates . . . . . . . . . . . . . . . . . 33 | |||
| Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 33 | Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 34 | |||
| 1. Introduction | 1. Introduction | |||
| ECC is a public-key technology that offers performance advantages at | ECC is a public-key technology that offers performance advantages at | |||
| higher security levels. It includes an Elliptic Curve version of the | higher security levels. It includes an Elliptic Curve version of the | |||
| Diffie-Hellman key exchange protocol [DH1976] and Elliptic Curve | Diffie-Hellman key exchange protocol [DH1976] and Elliptic Curve | |||
| versions of the ElGamal Signature Algorithm [E1985]. The adoption of | versions of the ElGamal Signature Algorithm [E1985]. The adoption of | |||
| ECC has been slower than had been anticipated, perhaps due to the | ECC has been slower than had been anticipated, perhaps due to the | |||
| lack of freely available normative documents and uncertainty over | lack of freely available normative documents and uncertainty over | |||
| intellectual property rights. | intellectual property rights. | |||
| This note contains a description of the fundamental algorithms of ECC | This note contains a description of the fundamental algorithms of ECC | |||
| over fields with characteristic greater than three, based directly on | over finite fields with characteristic greater than three, based | |||
| original references. Its intent is to provide the Internet community | directly on original references. Its intent is to provide the | |||
| with a summary of the basic algorithms that predate any specialized | Internet community with a summary of the basic algorithms that | |||
| or optimized algorithms, which can be used as a normative | predate any specialized or optimized algorithms. The summary is | |||
| specification. The original descriptions and notations were followed | detailed enough for use as a normative reference. The original | |||
| as closely as possible. | descriptions and notations were followed as closely as possible. | |||
| There are several standards that specify or incorporate ECC | There are several standards that specify or incorporate ECC | |||
| algorithms, including the Internet Key Exchange (IKE), ANSI X9.62, | algorithms, including the Internet Key Exchange (IKE), ANSI X9.62, | |||
| and IEEE P1363. The algorithms in this note can interoperate with | and IEEE P1363. The algorithms in this note can interoperate with | |||
| some of the algorithms in these standards, with a suitable choice of | some of the algorithms in these standards, with a suitable choice of | |||
| parameters and options. The specifics are itemized in Section 7. | parameters and options. The specifics are itemized in Section 7. | |||
| The rest of the note is organized as follows. Section 2.1, | The rest of the note is organized as follows. Section 2.1, | |||
| Section 2.2, and Section 2.3 furnish the necessary terminology and | Section 2.2, and Section 2.3 furnish the necessary terminology and | |||
| notation from modular arithmetic, group theory and the theory of | notation from modular arithmetic, group theory and the theory of | |||
| finite fields, respectively. Section 3 defines the groups based on | finite fields, respectively. Section 3 defines the groups based on | |||
| elliptic curves over finite fields of characteristic greater than | elliptic curves over finite fields of characteristic greater than | |||
| three. Section 4 presents the fundamental ECDH algorithm. Section 5 | three. Section 4 presents the fundamental Elliptic Curve Diffie- | |||
| presents elliptic curve versions of the ElGamal signature method. | Hellman (ECDH) algorithm. Section 5 presents elliptic curve versions | |||
| The representation of integers as octet strings is specified in | of the ElGamal signature method. The representation of integers as | |||
| Section 6. Sections 2 through 6, inclusive, contain all of the | octet strings is specified in Section 6. Sections 2 through 6, | |||
| normative text (the text that defines the norm for implementations | inclusive, contain all of the normative text (the text that defines | |||
| conforming to this specification), and all of the following sections | the norm for implementations conforming to this specification), and | |||
| are purely informative. Interoperability is discussed in Section 7. | all of the following sections are purely informative. | |||
| Validation testing is described in Section 8. Section 9 reviews | Interoperability is discussed in Section 7. Validation testing is | |||
| intellectual property issues. Section 10 summarizes security | described in Section 8. Section 9 reviews intellectual property | |||
| considerations. Appendix B describes random number generation, and | issues. Section 10 summarizes security considerations. Appendix B | |||
| other appendices provide clarifying details. | describes random number generation, and other appendices provide | |||
| clarifying details. | ||||
| 1.1. Conventions Used In This Document | 1.1. Conventions Used In This Document | |||
| The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", | The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", | |||
| "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this | "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this | |||
| document are to be interpreted as described in Appendix A. | document are to be interpreted as described in Appendix A. | |||
| 2. Mathematical Background | 2. Mathematical Background | |||
| This section reviews mathematical preliminaries and establishes | This section reviews mathematical preliminaries and establishes | |||
| terminology and notation that is used below. | terminology and notation that are used below. | |||
| 2.1. Modular Arithmetic | 2.1. Modular Arithmetic | |||
| This section reviews modular arithmetic. Two integers x and y are | This section reviews modular arithmetic. Two integers x and y are | |||
| said to be congruent modulo n if x - y is an integer multiple of n. | said to be congruent modulo n if x - y is an integer multiple of n. | |||
| Two integers x and y are coprime when their greatest common divisor | Two integers x and y are coprime when their greatest common divisor | |||
| is 1; in this case, there is no third number z > 1 such that z | is 1; in this case, there is no third number z > 1 such that z | |||
| divides x and z divides y. | divides x and z divides y. | |||
| skipping to change at page 5, line 43 ¶ | skipping to change at page 5, line 43 ¶ | |||
| modulo q is denoted as 1 / x mod q, and can be computed using the | modulo q is denoted as 1 / x mod q, and can be computed using the | |||
| extended euclidean algorithm (see Section 4.5.2 of [K1981v2], for | extended euclidean algorithm (see Section 4.5.2 of [K1981v2], for | |||
| example). | example). | |||
| Algorithms for these operations are well known; for instance, see | Algorithms for these operations are well known; for instance, see | |||
| Chapter 4 of [K1981v2]. | Chapter 4 of [K1981v2]. | |||
| 2.2. Group Operations | 2.2. Group Operations | |||
| This section establishes some terminology and notation for | This section establishes some terminology and notation for | |||
| mathematical groups, which is needed later on. Background references | mathematical groups, which are needed later on. Background | |||
| abound; see [D1966], for example. | references abound; see [D1966], for example. | |||
| A group is a set of elements G together with an operation that | A group is a set of elements G together with an operation that | |||
| combines any two elements in G and returns a third element in G. The | combines any two elements in G and returns a third element in G. The | |||
| operation is denoted as * and its application is denoted as a * b, | operation is denoted as * and its application is denoted as a * b, | |||
| for any two elements a and b in G. The operation is associative, that | for any two elements a and b in G. The operation is associative, that | |||
| is, for all a, b and c in G, a * (b * c) is identical to (a * b) * c. | is, for all a, b and c in G, a * (b * c) is identical to (a * b) * c. | |||
| Repeated application of the group operation N-1 times to the element | Repeated application of the group operation N-1 times to the element | |||
| a is denoted as a^N, for any element a in G and any positive integer | a is denoted as a^N, for any element a in G and any positive integer | |||
| N. That is, a^2, = a * a, a^3 = a * a * a, and so on. The | N. That is, a^2, = a * a, a^3 = a * a * a, and so on. The | |||
| associativity of the group operation ensures that the computation of | associativity of the group operation ensures that the computation of | |||
| a^n is unambiguous; any grouping of the terms gives the same result. | a^n is unambiguous; any grouping of the terms gives the same result. | |||
| The above definition of a group operation uses multiplicative | The above definition of a group operation uses multiplicative | |||
| notation. Sometimes an alternative called additive notation is used, | notation. Sometimes an alternative called additive notation is used, | |||
| in which a * b is denoted as a + b, and a^N is denoted as N * a. In | in which a * b is denoted as a + b, and a^N is denoted as N * a. In | |||
| multiplicative notation, g^N is called exponentiation, while the | multiplicative notation, a^N is called exponentiation, while the | |||
| equivalent operation in additive notation is called scalar | equivalent operation in additive notation is called scalar | |||
| multiplication. In this document, multiplicative notation is used | multiplication. In this document, multiplicative notation is used | |||
| throughout for consistency. Appendix E elucidates the correspondence | throughout for consistency. Appendix E elucidates the correspondence | |||
| between the two notations. | between the two notations. | |||
| Every group has a special element called the identity element, which | Every group has a special element called the identity element, which | |||
| we denote as e. For each element a in G, e * a = a * e = a. By | we denote as e. For each element a in G, e * a = a * e = a. By | |||
| convention, a^0 is equal to the identity element for any a in G. | convention, a^0 is equal to the identity element for any a in G. | |||
| Every group element a has a unique inverse element b such that | Every group element a has a unique inverse element b such that | |||
| skipping to change at page 7, line 15 ¶ | skipping to change at page 7, line 15 ¶ | |||
| Typically there are several group elements that generate H. Any group | Typically there are several group elements that generate H. Any group | |||
| element of the form a^M, with M relatively prime to R, also generates | element of the form a^M, with M relatively prime to R, also generates | |||
| H. Note that a^M is equal to g^(M modulo R) for any non-negative | H. Note that a^M is equal to g^(M modulo R) for any non-negative | |||
| integer M. | integer M. | |||
| Given the element a of order R, and an integer i between 1 and R-1, | Given the element a of order R, and an integer i between 1 and R-1, | |||
| inclusive, the element a^i can be computed by the "square and | inclusive, the element a^i can be computed by the "square and | |||
| multiply" method outlined in Section 2.1 of [M1983] (see also Knuth, | multiply" method outlined in Section 2.1 of [M1983] (see also Knuth, | |||
| Vol. 2, Section 4.6.3.), or other methods. | Vol. 2, Section 4.6.3.), or other methods. | |||
| 2.3. Finite Fields | 2.3. The Finite Field Fp | |||
| This section establishes terminology and notation for finite fields | This section establishes terminology and notation for finite fields | |||
| with prime characteristic. | with prime characteristic. | |||
| When p is a prime number, then the set Zp, with the addition, | When p is a prime number, then the set Zp, with the addition, | |||
| subtraction, multiplication and division operations, is a finite | subtraction, multiplication and division operations, is a finite | |||
| field with characteristic p. Each nonzero element x in Zp has an | field with characteristic p. Each nonzero element x in Zp has an | |||
| inverse 1/x. There is a one-to-one correspondence between the | inverse 1/x. There is a one-to-one correspondence between the | |||
| integers between zero and p-1, inclusive, and the elements of the | integers between zero and p-1, inclusive, and the elements of the | |||
| field. The field Zp is sometimes denoted as Fp or GF(p). | field. The field Zp is sometimes denoted as Fp or GF(p). | |||
| skipping to change at page 10, line 33 ¶ | skipping to change at page 10, line 33 ¶ | |||
| set. The elliptic curve group operation is only defined between two | set. The elliptic curve group operation is only defined between two | |||
| points in the same group. It is an error to apply the group | points in the same group. It is an error to apply the group | |||
| operation to two elements that are from different groups, or to apply | operation to two elements that are from different groups, or to apply | |||
| the group operation to a pair of coordinates that is not a valid | the group operation to a pair of coordinates that is not a valid | |||
| point. (A pair (x,y) of coordinates in Fp is a valid point only when | point. (A pair (x,y) of coordinates in Fp is a valid point only when | |||
| they satisfy the curve equation.) See Section 10.3 for further | they satisfy the curve equation.) See Section 10.3 for further | |||
| information. | information. | |||
| 3.3.1. Discriminant | 3.3.1. Discriminant | |||
| For each elliptic curve group, the discriminant - 16*(4*a^3 + 27*b^2) | For each elliptic curve group, the discriminant -16*(4*a^3 + 27*b^2) | |||
| must be nonzero modulo p [S1986]; this requires that | must be nonzero modulo p [S1986]; this requires that | |||
| 4*a^3 + 27*b^2 != 0 mod p. | 4*a^3 + 27*b^2 != 0 mod p. | |||
| 3.3.2. Security | 3.3.2. Security | |||
| Security is highly dependent on the choice of these parameters. This | Security is highly dependent on the choice of these parameters. This | |||
| section gives normative guidance on acceptable choices. See also | section gives normative guidance on acceptable choices. See also | |||
| Section 10 for informative guidance. | Section 10 for informative guidance. | |||
| skipping to change at page 11, line 13 ¶ | skipping to change at page 11, line 13 ¶ | |||
| p = 2 (mod 3) [MOV1993]. These parameter choices are inferior for | p = 2 (mod 3) [MOV1993]. These parameter choices are inferior for | |||
| cryptographic purposes and SHOULD NOT be used. | cryptographic purposes and SHOULD NOT be used. | |||
| 4. Elliptic Curve Diffie-Hellman (ECDH) | 4. Elliptic Curve Diffie-Hellman (ECDH) | |||
| The Diffie-Hellman (DH) key exchange protocol [DH1976] allows two | The Diffie-Hellman (DH) key exchange protocol [DH1976] allows two | |||
| parties communicating over an insecure channel to agree on a secret | parties communicating over an insecure channel to agree on a secret | |||
| key. It was originally defined in terms of operations in the | key. It was originally defined in terms of operations in the | |||
| multiplicative group of a field with a large prime characteristic. | multiplicative group of a field with a large prime characteristic. | |||
| Massey [M1983] observed that it can be easily generalized so that it | Massey [M1983] observed that it can be easily generalized so that it | |||
| is defined in terms of an arbitrary mathematical group. Miller | is defined in terms of an arbitrary cyclic group. Miller [M1985] and | |||
| [M1985] and Koblitz [K1987] analyzed the DH protocol over an elliptic | Koblitz [K1987] analyzed the DH protocol over an elliptic curve | |||
| curve group. We describe DH following the former reference. | group. We describe DH following the former reference. | |||
| Let G be a group, and g be a generator for that group, and let t | Let G be a group, and g be a generator for that group, and let t | |||
| denote the order of G. The DH protocol runs as follows. Party A | denote the order of G. The DH protocol runs as follows. Party A | |||
| chooses an exponent j between 1 and t-1, inclusive, uniformly at | chooses an exponent j between 1 and t-1, inclusive, uniformly at | |||
| random, computes g^j and sends that element to B. Party B chooses an | random, computes g^j and sends that element to B. Party B chooses an | |||
| exponent k between 1 and t-1, inclusive, uniformly at random, | exponent k between 1 and t-1, inclusive, uniformly at random, | |||
| computes g^k and sends that element to A. Each party can compute | computes g^k and sends that element to A. Each party can compute | |||
| g^(j*k); party A computes (g^k)^j, and party B computes (g^j)^k. | g^(j*k); party A computes (g^k)^j, and party B computes (g^j)^k. | |||
| See Appendix B regarding generation of random integers. | See Appendix B regarding generation of random integers. | |||
| skipping to change at page 12, line 20 ¶ | skipping to change at page 12, line 20 ¶ | |||
| 5. Elliptic Curve ElGamal Signatures | 5. Elliptic Curve ElGamal Signatures | |||
| 5.1. Background | 5.1. Background | |||
| The ElGamal signature algorithm was introduced in 1984 [E1984a] | The ElGamal signature algorithm was introduced in 1984 [E1984a] | |||
| [E1984b] [E1985]. It is based on the discrete logarithm problem, and | [E1984b] [E1985]. It is based on the discrete logarithm problem, and | |||
| was originally defined for the multiplicative group of the integers | was originally defined for the multiplicative group of the integers | |||
| modulo a large prime number. It is straightforward to extend it to | modulo a large prime number. It is straightforward to extend it to | |||
| use other finite groups, such as the multiplicative group of the | use other finite groups, such as the multiplicative group of the | |||
| field GF(2^w) [AMV1990] or an elliptic curve group [A1992]. | finite field GF(2^w) [AMV1990] or an elliptic curve group [A1992]. | |||
| An ElGamal signature consists of a pair of components. There are | An ElGamal signature consists of a pair of components. There are | |||
| many possible generalizations of ElGamal signature methods that have | many possible generalizations of ElGamal signature methods that have | |||
| been obtained by different rearrangements of the equation for the | been obtained by different rearrangements of the equation for the | |||
| second component; see [HMP1994], [HP1994], [NR1994], [A1992], and | second component; see [HMP1994], [HP1994], [NR1994], [A1992], and | |||
| [AMV1990]. These generalizations are independent of the mathematical | [AMV1990]. These generalizations are independent of the mathematical | |||
| group used, and have been described for the multiplicative group | group used, and have been described for the multiplicative group | |||
| modulo a prime number, the multiplicative group of GF(2^w), and | modulo a prime number, the multiplicative group of GF(2^w), and | |||
| elliptic curve groups [HMP1994][NR1994][AMV1990][A1992]. | elliptic curve groups [HMP1994][NR1994][AMV1990][A1992]. | |||
| skipping to change at page 14, line 8 ¶ | skipping to change at page 14, line 8 ¶ | |||
| extremely unlikely that s1 = 0 or h(m) + z * s1 = 0 mod q if | extremely unlikely that s1 = 0 or h(m) + z * s1 = 0 mod q if | |||
| signatures are generated properly.) | signatures are generated properly.) | |||
| 5. Calculate s2 = k / (h(m) + z * s1) mod q. | 5. Calculate s2 = k / (h(m) + z * s1) mod q. | |||
| The signature is the ordered pair (s1, s2). Both signature | The signature is the ordered pair (s1, s2). Both signature | |||
| components are non-negative integers. | components are non-negative integers. | |||
| 5.3.3. Signature Verification | 5.3.3. Signature Verification | |||
| Given the message m, the public key Y, and the signature (s1, s2) | Given the message m, the generator g, the group order q, the public | |||
| verification is as follows: | key Y, and the signature (s1, s2) verification is as follows: | |||
| 1. Check to see that 0 < s1 < q and 0 < s2 < q; if either condition | 1. Check to see that 0 < s1 < q and 0 < s2 < q; if either condition | |||
| is violated, the signature SHALL be rejected. | is violated, the signature SHALL be rejected. | |||
| 2. Compute the non-negative integers u1 and u2, where | 2. Compute the non-negative integers u1 and u2, where | |||
| u1 = h(m) * s2 mod q, and | u1 = h(m) * s2 mod q, and | |||
| u2 = s1 * s2 mod q. | u2 = s1 * s2 mod q. | |||
| skipping to change at page 15, line 39 ¶ | skipping to change at page 15, line 39 ¶ | |||
| u1 = h(m) * s2_inv mod q, and | u1 = h(m) * s2_inv mod q, and | |||
| u2 = s1 * s2_inv mod q. | u2 = s1 * s2_inv mod q. | |||
| 4. Compute the elliptic curve point R' = alpha^u1 * Y^u2. | 4. Compute the elliptic curve point R' = alpha^u1 * Y^u2. | |||
| 5. If the x-coordinate of R' mod q is equal to s1, then the | 5. If the x-coordinate of R' mod q is equal to s1, then the | |||
| signature and message pass the verification; otherwise, they | signature and message pass the verification; otherwise, they | |||
| fail. | fail. | |||
| 5.5. Converting KT-IV signatures to KT-I signatures | 5.5. Converting KT-IV Signatures to KT-I Signatures | |||
| A KT-IV signature for a message m and a public key Y can easily be | A KT-IV signature for a message m and a public key Y can easily be | |||
| converted into a KT-I signature for the same message and public key. | converted into a KT-I signature for the same message and public key. | |||
| If (s1, s2) is a KT-IV signature for a message m, then | If (s1, s2) is a KT-IV signature for a message m, then | |||
| (s1, 1/s2 mod q) is a KT-I signature for the same message [HMP1994]. | (s1, 1/s2 mod q) is a KT-I signature for the same message [HMP1994]. | |||
| The conversion operation uses only public information, and it can be | The conversion operation uses only public information, and it can be | |||
| performed by the creator of the pre-conversion KT-IV signature, the | performed by the creator of the pre-conversion KT-IV signature, the | |||
| verifier of the post-conversion KT-I signature, or by any other | verifier of the post-conversion KT-I signature, or by any other | |||
| entity. | entity. | |||
| skipping to change at page 16, line 35 ¶ | skipping to change at page 16, line 35 ¶ | |||
| The signature method of [KT1994] and Section 5.3 is an EG-IV.1 | The signature method of [KT1994] and Section 5.3 is an EG-IV.1 | |||
| method, with A = m * s, B = - r * s, C = 1. Its signature equation | method, with A = m * s, B = - r * s, C = 1. Its signature equation | |||
| is | is | |||
| m * s = - r * s * z + k (mod q) | m * s = - r * s * z + k (mod q) | |||
| The functions f and g mentioned in Table 1 are merely multiplication, | The functions f and g mentioned in Table 1 are merely multiplication, | |||
| as described under the heading "Fifth generalization". | as described under the heading "Fifth generalization". | |||
| No hash function is shown in the above equations, but as described in | In the above equations, we rely on the implicit conversion of the | |||
| Section 10.4, a hash function should be applied to the message prior | message m from a bit string to an integer. No hash function is shown | |||
| to signing in order to prevent existential forgery attacks. | in these equations, but as described in Section 10.4, a hash function | |||
| should be applied to the message prior to signing in order to prevent | ||||
| existential forgery attacks. | ||||
| Nyberg and Rueppel [NR1994] studied many different ElGamal signature | Nyberg and Rueppel [NR1994] studied many different ElGamal signature | |||
| methods, and defined "strong equivalence" as follows: | methods, and defined "strong equivalence" as follows: | |||
| Two signature methods are called strongly equivalent if the | Two signature methods are called strongly equivalent if the | |||
| signature of the first scheme can be transformed efficiently into | signature of the first scheme can be transformed efficiently into | |||
| signatures of the second scheme and vice versa, without knowledge | signatures of the second scheme and vice versa, without knowledge | |||
| of the private key. | of the private key. | |||
| KT-I and KT-IV signatures are obviously strongly equivalent. | KT-I and KT-IV signatures are obviously strongly equivalent. | |||
| skipping to change at page 17, line 12 ¶ | skipping to change at page 17, line 14 ¶ | |||
| exceptional case and the case that s1=0. The s2=0 check was | exceptional case and the case that s1=0. The s2=0 check was | |||
| suggested by Rivest [R1992] and is discussed in [BS1992]. | suggested by Rivest [R1992] and is discussed in [BS1992]. | |||
| [KT1994] uses "a positive integer q' that does not exceed q" when | [KT1994] uses "a positive integer q' that does not exceed q" when | |||
| computing the signature component s1 from the x-coordinate r_x of the | computing the signature component s1 from the x-coordinate r_x of the | |||
| elliptic curve point R = (r_x, r_y). The value q' is also used | elliptic curve point R = (r_x, r_y). The value q' is also used | |||
| during signature validation when comparing the x-coordinate of a | during signature validation when comparing the x-coordinate of a | |||
| computed elliptic curve point to the value to s1. In this note, we | computed elliptic curve point to the value to s1. In this note, we | |||
| use the simplifying convention that q' = q. | use the simplifying convention that q' = q. | |||
| 6. Converting between integers and octet strings | 6. Converting Between Integers and Octet Strings | |||
| A method for the conversion between integers and octet strings is | A method for the conversion between integers and octet strings is | |||
| specified in this section, following the established conventions of | specified in this section, following the established conventions of | |||
| public key cryptography [R1993]. This method allows integers to be | public key cryptography [R1993]. This method allows integers to be | |||
| represented as octet strings that are suitable for transmission or | represented as octet strings that are suitable for transmission or | |||
| storage. This method SHOULD be used when representing an elliptic | storage. This method SHOULD be used when representing an elliptic | |||
| curve point or an elliptic curve coordinate as they are defined in | curve point or an elliptic curve coordinate as they are defined in | |||
| this note. | this note. | |||
| 6.1. Octet-string-to-integer conversion | 6.1. Octet-String-to-Integer Conversion | |||
| The octet string S shall be converted to an integer x as follows. | The octet string S shall be converted to an integer x as follows. | |||
| Let S1, ..., Sk be the octets of S from first to last. Then the | Let S1, ..., Sk be the octets of S from first to last. Then the | |||
| integer x shall satisfy | integer x shall satisfy | |||
| k | k | |||
| x = SUM 2^(8(k-i)) Si . | x = SUM 2^(8(k-i)) Si . | |||
| i = 1 | i = 1 | |||
| In other words, the first octet of S has the most significance in the | In other words, the first octet of S has the most significance in the | |||
| integer and the last octet of S has the least significance. | integer and the last octet of S has the least significance. | |||
| Note: the integer x satisfies 0 <= x < 2^(8*k). | Note: the integer x satisfies 0 <= x < 2^(8*k). | |||
| 6.2. Integer-to-octet-string conversion | 6.2. Integer-to-Octet-String Conversion | |||
| The integer x shall be converted to an octet string S of length k as | The integer x shall be converted to an octet string S of length k as | |||
| follows. The string S shall satisfy | follows. The string S shall satisfy | |||
| k | k | |||
| y = SUM 2^(8(k-i)) Si . | y = SUM 2^(8(k-i)) Si . | |||
| i = 1 | i = 1 | |||
| where S1, ..., Sk are the octets of S from first to last. | where S1, ..., Sk are the octets of S from first to last. | |||
| skipping to change at page 21, line 7 ¶ | skipping to change at page 21, line 31 ¶ | |||
| +---------------------+------------------+ | +---------------------+------------------+ | |||
| 9. Intellectual Property | 9. Intellectual Property | |||
| Concerns about intellectual property have slowed the adoption of ECC, | Concerns about intellectual property have slowed the adoption of ECC, | |||
| because a number of optimizations and specialized algorithms have | because a number of optimizations and specialized algorithms have | |||
| been patented in recent years. | been patented in recent years. | |||
| All of the normative references for ECDH (as defined in Section 4) | All of the normative references for ECDH (as defined in Section 4) | |||
| were published during or before 1989, and those for KT-I were | were published during or before 1989, and those for KT-I were | |||
| published during or before May, 1994. All of the normative text for | published during or before May 1994. All of the normative text for | |||
| these algorithms is based solely on their respective references. | these algorithms is based solely on their respective references. | |||
| 9.1. Disclaimer | 9.1. Disclaimer | |||
| This document is not intended as legal advice. Readers are advised | This document is not intended as legal advice. Readers are advised | |||
| to consult their own legal advisers if they would like a legal | to consult their own legal advisers if they would like a legal | |||
| interpretation of their rights. | interpretation of their rights. | |||
| The IETF policies and processes regarding intellectual property and | The IETF policies and processes regarding intellectual property and | |||
| patents are outlined in [RFC3979] and [RFC4879] and at | patents are outlined in [RFC3979] and [RFC4879] and at | |||
| skipping to change at page 24, line 12 ¶ | skipping to change at page 24, line 37 ¶ | |||
| This note has no actions for IANA. This section should be removed by | This note has no actions for IANA. This section should be removed by | |||
| the RFC editor before publication as an RFC. | the RFC editor before publication as an RFC. | |||
| 12. Acknowledgements | 12. Acknowledgements | |||
| The author expresses his thanks to the originators of elliptic curve | The author expresses his thanks to the originators of elliptic curve | |||
| cryptography, whose work made this note possible, and all of the | cryptography, whose work made this note possible, and all of the | |||
| reviewers, who provided valuable constructive feedback. Thanks are | reviewers, who provided valuable constructive feedback. Thanks are | |||
| especially due to Howard Pinder, Andrey Jivsov, Alfred Hoenes (who | especially due to Howard Pinder, Andrey Jivsov, Alfred Hoenes (who | |||
| contributed the algorithms in Appendix F), and Dan Harkins. | contributed the algorithms in Appendix F), Dan Harkins, and Tina | |||
| Tsou. | ||||
| 13. References | 13. References | |||
| 13.1. Normative References | 13.1. Normative References | |||
| [AMV1990] Agnew, G., Mullin, R., and S. Vanstone, "Improved Digital | [AMV1990] Agnew, G., Mullin, R., and S. Vanstone, "Improved Digital | |||
| Signature Scheme based on Discrete Exponentiation", | Signature Scheme based on Discrete Exponentiation", | |||
| Electronics Letters Vol. 26, No. 14, July, 1990. | Electronics Letters Vol. 26, No. 14, July, 1990. | |||
| [BC1989] Bender, A. and G. Castagnoli, "On the Implementation of | [BC1989] Bender, A. and G. Castagnoli, "On the Implementation of | |||
| End of changes. 31 change blocks. | ||||
| 59 lines changed or deleted | 63 lines changed or added | |||
This html diff was produced by rfcdiff 1.48. The latest version is available from http://tools.ietf.org/tools/rfcdiff/ | ||||