< 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/