RFC 6090

Internet Engineering Task Force (IETF) D. McGrew

Request for Comments: 6090 Cisco Systems

Category: Informational K. Igoe

ISSN: 2070-1721 M. Salter

National Security Agency

February 2011

Fundamental Elliptic Curve Cryptography Algorithms

This note describes the fundamental algorithms of Elliptic Curve

Cryptography (ECC) as they were defined in some seminal references

from 1994 and earlier. These descriptions may be useful for

implementing the fundamental algorithms without using any of the

specialized methods that were developed in following years. Only

elliptic curves defined over fields of characteristic greater than

three are in scope; these curves are those used in Suite B.

This document is not an Internet Standards Track specification; it is

published for informational purposes.

This document is a product of the Internet Engineering Task Force

(IETF). It represents the consensus of the IETF community. It has

received public review and has been approved for publication by the

Internet Engineering Steering Group (IESG). Not all documents

approved by the IESG are a candidate for any level of Internet

Standard; see Section 2 of RFC 5741.

Information about the current status of this document, any errata,

and how to provide feedback on it may be obtained at

http://www.rfc-editor.org/info/rfc6090.

RFC 6090 Fundamental ECC February 2011

# Copyright Notice

Copyright (c) 2011 IETF Trust and the persons identified as the

document authors. All rights reserved.

This document is subject to BCP 78 and the IETF Trust's Legal

Provisions Relating to IETF Documents

(http://trustee.ietf.org/license-info) in effect on the date of

publication of this document. Please review these documents

carefully, as they describe your rights and restrictions with respect

to this document. Code Components extracted from this document must

include Simplified BSD License text as described in Section 4.e of

the Trust Legal Provisions and are provided without warranty as

described in the Simplified BSD License.

# Table of Contents

1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.1. Conventions Used in This Document . . . . . . . . . . . . 4

2. Mathematical Background . . . . . . . . . . . . . . . . . . . 4

2.1. Modular Arithmetic . . . . . . . . . . . . . . . . . . . . 4

2.2. Group Operations . . . . . . . . . . . . . . . . . . . . . 5

2.3. The Finite Field Fp . . . . . . . . . . . . . . . . . . . 6

3. Elliptic Curve Groups . . . . . . . . . . . . . . . . . . . . 7

3.1. Homogeneous Coordinates . . . . . . . . . . . . . . . . . 8

3.2. Other Coordinates . . . . . . . . . . . . . . . . . . . . 9

3.3. ECC Parameters . . . . . . . . . . . . . . . . . . . . . . 9

3.3.1. Discriminant . . . . . . . . . . . . . . . . . . . . . 10

3.3.2. Security . . . . . . . . . . . . . . . . . . . . . . . 10

4. Elliptic Curve Diffie-Hellman (ECDH) . . . . . . . . . . . . . 10

4.1. Data Types . . . . . . . . . . . . . . . . . . . . . . . . 11

4.2. Compact Representation . . . . . . . . . . . . . . . . . . 11

5. Elliptic Curve ElGamal Signatures . . . . . . . . . . . . . . 11

5.1. Background . . . . . . . . . . . . . . . . . . . . . . . . 11

5.2. Hash Functions . . . . . . . . . . . . . . . . . . . . . . 12

5.3. KT-IV Signatures . . . . . . . . . . . . . . . . . . . . . 12

5.3.1. Keypair Generation . . . . . . . . . . . . . . . . . . 12

5.3.2. Signature Creation . . . . . . . . . . . . . . . . . . 13

5.3.3. Signature Verification . . . . . . . . . . . . . . . . 13

5.4. KT-I Signatures . . . . . . . . . . . . . . . . . . . . . 14

5.4.1. Keypair Generation . . . . . . . . . . . . . . . . . . 14

5.4.2. Signature Creation . . . . . . . . . . . . . . . . . . 14

5.4.3. Signature Verification . . . . . . . . . . . . . . . . 14

5.5. Converting KT-IV Signatures to KT-I Signatures . . . . . . 15

5.6. Rationale . . . . . . . . . . . . . . . . . . . . . . . . 15

6. Converting between Integers and Octet Strings . . . . . . . . 16

6.1. Octet-String-to-Integer Conversion . . . . . . . . . . . . 17

6.2. Integer-to-Octet-String Conversion . . . . . . . . . . . . 17

Copyright (c) 2011 IETF Trust and the persons identified as the

document authors. All rights reserved.

This document is subject to BCP 78 and the IETF Trust's Legal

Provisions Relating to IETF Documents

(http://trustee.ietf.org/license-info) in effect on the date of

publication of this document. Please review these documents

carefully, as they describe your rights and restrictions with respect

to this document. Code Components extracted from this document must

include Simplified BSD License text as described in Section 4.e of

the Trust Legal Provisions and are provided without warranty as

described in the Simplified BSD License.

1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.1. Conventions Used in This Document . . . . . . . . . . . . 4

2. Mathematical Background . . . . . . . . . . . . . . . . . . . 4

2.1. Modular Arithmetic . . . . . . . . . . . . . . . . . . . . 4

2.2. Group Operations . . . . . . . . . . . . . . . . . . . . . 5

2.3. The Finite Field Fp . . . . . . . . . . . . . . . . . . . 6

3. Elliptic Curve Groups . . . . . . . . . . . . . . . . . . . . 7

3.1. Homogeneous Coordinates . . . . . . . . . . . . . . . . . 8

3.2. Other Coordinates . . . . . . . . . . . . . . . . . . . . 9

3.3. ECC Parameters . . . . . . . . . . . . . . . . . . . . . . 9

3.3.1. Discriminant . . . . . . . . . . . . . . . . . . . . . 10

3.3.2. Security . . . . . . . . . . . . . . . . . . . . . . . 10

4. Elliptic Curve Diffie-Hellman (ECDH) . . . . . . . . . . . . . 10

4.1. Data Types . . . . . . . . . . . . . . . . . . . . . . . . 11

4.2. Compact Representation . . . . . . . . . . . . . . . . . . 11

5. Elliptic Curve ElGamal Signatures . . . . . . . . . . . . . . 11

5.1. Background . . . . . . . . . . . . . . . . . . . . . . . . 11

5.2. Hash Functions . . . . . . . . . . . . . . . . . . . . . . 12

5.3. KT-IV Signatures . . . . . . . . . . . . . . . . . . . . . 12

5.3.1. Keypair Generation . . . . . . . . . . . . . . . . . . 12

5.3.2. Signature Creation . . . . . . . . . . . . . . . . . . 13

5.3.3. Signature Verification . . . . . . . . . . . . . . . . 13

5.4. KT-I Signatures . . . . . . . . . . . . . . . . . . . . . 14

5.4.1. Keypair Generation . . . . . . . . . . . . . . . . . . 14

5.4.2. Signature Creation . . . . . . . . . . . . . . . . . . 14

5.4.3. Signature Verification . . . . . . . . . . . . . . . . 14

5.5. Converting KT-IV Signatures to KT-I Signatures . . . . . . 15

5.6. Rationale . . . . . . . . . . . . . . . . . . . . . . . . 15

6. Converting between Integers and Octet Strings . . . . . . . . 16

6.1. Octet-String-to-Integer Conversion . . . . . . . . . . . . 17

6.2. Integer-to-Octet-String Conversion . . . . . . . . . . . . 17

RFC 6090 Fundamental ECC February 2011

7. Interoperability . . . . . . . . . . . . . . . . . . . . . . . 17

7.1. ECDH . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

7.2. KT-I and ECDSA . . . . . . . . . . . . . . . . . . . . . . 18

8. Validating an Implementation . . . . . . . . . . . . . . . . . 18

8.1. ECDH . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

8.2. KT-I . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

9. Intellectual Property . . . . . . . . . . . . . . . . . . . . 20

9.1. Disclaimer . . . . . . . . . . . . . . . . . . . . . . . . 20

10. Security Considerations . . . . . . . . . . . . . . . . . . . 21

10.1. Subgroups . . . . . . . . . . . . . . . . . . . . . . . . 21

10.2. Diffie-Hellman . . . . . . . . . . . . . . . . . . . . . . 22

10.3. Group Representation and Security . . . . . . . . . . . . 22

10.4. Signatures . . . . . . . . . . . . . . . . . . . . . . . . 23

11. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 23

12. References . . . . . . . . . . . . . . . . . . . . . . . . . . 23

12.1. Normative References . . . . . . . . . . . . . . . . . . . 23

12.2. Informative References . . . . . . . . . . . . . . . . . . 25

Appendix A. Key Words . . . . . . . . . . . . . . . . . . . . . . 29

Appendix B. Random Integer Generation . . . . . . . . . . . . . . 29

Appendix C. Why Compact Representation Works . . . . . . . . . . 30

Appendix D. Example ECC Parameter Set . . . . . . . . . . . . . . 31

Appendix E. Additive and Multiplicative Notation . . . . . . . . 32

Appendix F. Algorithms . . . . . . . . . . . . . . . . . . . . . 32

F.1. Affine Coordinates . . . . . . . . . . . . . . . . . . . . 32

F.2. Homogeneous Coordinates . . . . . . . . . . . . . . . . . 33

# 1. Introduction

ECC is a public-key technology that offers performance advantages at

higher security levels. It includes an elliptic curve version of the

Diffie-Hellman key exchange protocol [DH1976] and elliptic curve

versions of the ElGamal Signature Algorithm [E1985]. The adoption of

ECC has been slower than had been anticipated, perhaps due to the

lack of freely available normative documents and uncertainty over

intellectual property rights.

This note contains a description of the fundamental algorithms of ECC

over finite fields with characteristic greater than three, based

directly on original references. Its intent is to provide the

Internet community with a summary of the basic algorithms that

predate any specialized or optimized algorithms. The summary is

detailed enough for use as a normative reference. The original

descriptions and notations were followed as closely as possible.

There are several standards that specify or incorporate ECC

algorithms, including the Internet Key Exchange (IKE), ANSI X9.62,

and IEEE P1363. The algorithms in this note can interoperate with

7. Interoperability . . . . . . . . . . . . . . . . . . . . . . . 17

7.1. ECDH . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

7.2. KT-I and ECDSA . . . . . . . . . . . . . . . . . . . . . . 18

8. Validating an Implementation . . . . . . . . . . . . . . . . . 18

8.1. ECDH . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

8.2. KT-I . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

9. Intellectual Property . . . . . . . . . . . . . . . . . . . . 20

9.1. Disclaimer . . . . . . . . . . . . . . . . . . . . . . . . 20

10. Security Considerations . . . . . . . . . . . . . . . . . . . 21

10.1. Subgroups . . . . . . . . . . . . . . . . . . . . . . . . 21

10.2. Diffie-Hellman . . . . . . . . . . . . . . . . . . . . . . 22

10.3. Group Representation and Security . . . . . . . . . . . . 22

10.4. Signatures . . . . . . . . . . . . . . . . . . . . . . . . 23

11. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 23

12. References . . . . . . . . . . . . . . . . . . . . . . . . . . 23

12.1. Normative References . . . . . . . . . . . . . . . . . . . 23

12.2. Informative References . . . . . . . . . . . . . . . . . . 25

Appendix A. Key Words . . . . . . . . . . . . . . . . . . . . . . 29

Appendix B. Random Integer Generation . . . . . . . . . . . . . . 29

Appendix C. Why Compact Representation Works . . . . . . . . . . 30

Appendix D. Example ECC Parameter Set . . . . . . . . . . . . . . 31

Appendix E. Additive and Multiplicative Notation . . . . . . . . 32

Appendix F. Algorithms . . . . . . . . . . . . . . . . . . . . . 32

F.1. Affine Coordinates . . . . . . . . . . . . . . . . . . . . 32

F.2. Homogeneous Coordinates . . . . . . . . . . . . . . . . . 33

ECC is a public-key technology that offers performance advantages at

higher security levels. It includes an elliptic curve version of the

Diffie-Hellman key exchange protocol [DH1976] and elliptic curve

versions of the ElGamal Signature Algorithm [E1985]. The adoption of

ECC has been slower than had been anticipated, perhaps due to the

lack of freely available normative documents and uncertainty over

intellectual property rights.

This note contains a description of the fundamental algorithms of ECC

over finite fields with characteristic greater than three, based

directly on original references. Its intent is to provide the

Internet community with a summary of the basic algorithms that

predate any specialized or optimized algorithms. The summary is

detailed enough for use as a normative reference. The original

descriptions and notations were followed as closely as possible.

There are several standards that specify or incorporate ECC

algorithms, including the Internet Key Exchange (IKE), ANSI X9.62,

and IEEE P1363. The algorithms in this note can interoperate with

RFC 6090 Fundamental ECC February 2011

some of the algorithms in these standards, with a suitable choice of

parameters and options. The specifics are itemized in Section 7.

The rest of the note is organized as follows. Sections 2.1, 2.2, and

2.3 furnish the necessary terminology and notation from modular

arithmetic, group theory, and the theory of finite fields,

respectively. Section 3 defines the groups based on elliptic curves

over finite fields of characteristic greater than three. Section 4

presents the fundamental Elliptic Curve Diffie-Hellman (ECDH)

algorithm. Section 5 presents elliptic curve versions of the ElGamal

signature method. The representation of integers as octet strings is

specified in Section 6. Sections 2 through 6, inclusive, contain all

of the normative text (the text that defines the norm for

implementations conforming to this specification), and all of the

following sections are purely informative. Interoperability is

discussed in 7">Section 7. Validation testing is described in

Section 8. Section 9 reviews intellectual property issues.

Section 10 summarizes security considerations. Appendix B describes

random number generation, and other appendices provide clarifying

details.

## 1.1. Conventions Used in This Document

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",

"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this

document are to be interpreted as described in Appendix A.

# 2. Mathematical Background

This section reviews mathematical preliminaries and establishes

terminology and notation that are used below.

## 2.1. Modular Arithmetic

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.

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

divides x and z divides y.

The set Zq = { 0, 1, 2, ..., q-1 } is closed under the operations of

modular addition, modular subtraction, modular multiplication, and

modular inverse. These operations are as follows.

For each pair of integers a and b in Zq, a + b mod q is equal to

a + b if a + b < q, and is equal to a + b - q otherwise.

some of the algorithms in these standards, with a suitable choice of

parameters and options. The specifics are itemized in Section 7.

The rest of the note is organized as follows. Sections 2.1, 2.2, and

2.3 furnish the necessary terminology and notation from modular

arithmetic, group theory, and the theory of finite fields,

respectively. Section 3 defines the groups based on elliptic curves

over finite fields of characteristic greater than three. Section 4

presents the fundamental Elliptic Curve Diffie-Hellman (ECDH)

algorithm. Section 5 presents elliptic curve versions of the ElGamal

signature method. The representation of integers as octet strings is

specified in Section 6. Sections 2 through 6, inclusive, contain all

of the normative text (the text that defines the norm for

implementations conforming to this specification), and all of the

following sections are purely informative. Interoperability is

discussed in 7">Section 7. Validation testing is described in

Section 8. Section 9 reviews intellectual property issues.

Section 10 summarizes security considerations. Appendix B describes

random number generation, and other appendices provide clarifying

details.

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",

"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this

document are to be interpreted as described in Appendix A.

This section reviews mathematical preliminaries and establishes

terminology and notation that are used below.

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.

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

divides x and z divides y.

The set Zq = { 0, 1, 2, ..., q-1 } is closed under the operations of

modular addition, modular subtraction, modular multiplication, and

modular inverse. These operations are as follows.

For each pair of integers a and b in Zq, a + b mod q is equal to

a + b if a + b < q, and is equal to a + b - q otherwise.

RFC 6090 Fundamental ECC February 2011

For each pair of integers a and b in Zq, a - b mod q is equal to

a - b if a - b >= 0, and is equal to a - b + q otherwise.

For each pair of integers a and b in Zq, a * b mod q is equal to

the remainder of a * b divided by q.

For each integer x in Zq that is coprime with q, the inverse of x

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

example).

Algorithms for these operations are well known; for instance, see

Chapter 4 of [K1981v2].

## 2.2. Group Operations

This section establishes some terminology and notation for

mathematical groups, which are needed later on. Background

references abound; see [D1966], for example.

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

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

associativity of the group operation ensures that the computation of

a^n is unambiguous; any grouping of the terms gives the same result.

The above definition of a group operation uses multiplicative

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

multiplicative notation, a^N is called exponentiation, while the

equivalent operation in additive notation is called scalar

multiplication. In this document, multiplicative notation is used

throughout for consistency. Appendix E elucidates the correspondence

between the two notations.

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

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

a * b = b * a = e. The inverse of a is denoted as a^-1 in

multiplicative notation. (In additive notation, the inverse of a is

denoted as -a.)

For each pair of integers a and b in Zq, a - b mod q is equal to

a - b if a - b >= 0, and is equal to a - b + q otherwise.

For each pair of integers a and b in Zq, a * b mod q is equal to

the remainder of a * b divided by q.

For each integer x in Zq that is coprime with q, the inverse of x

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

example).

Algorithms for these operations are well known; for instance, see

Chapter 4 of [K1981v2].

This section establishes some terminology and notation for

mathematical groups, which are needed later on. Background

references abound; see [D1966], for example.

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

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

associativity of the group operation ensures that the computation of

a^n is unambiguous; any grouping of the terms gives the same result.

The above definition of a group operation uses multiplicative

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

multiplicative notation, a^N is called exponentiation, while the

equivalent operation in additive notation is called scalar

multiplication. In this document, multiplicative notation is used

throughout for consistency. Appendix E elucidates the correspondence

between the two notations.

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

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

a * b = b * a = e. The inverse of a is denoted as a^-1 in

multiplicative notation. (In additive notation, the inverse of a is

denoted as -a.)

RFC 6090 Fundamental ECC February 2011

For any positive integer X, a^(-X) is defined to be (a^-1)^(X).

Using this convention, exponentiation behaves as one would expect,

namely for any integers X and Y:

a^(X+Y) = (a^X)*(a^Y)

(a^X)^Y = a^(XY) = (a^Y)^X.

In cryptographic applications, one typically deals with finite groups

(groups with a finite number of elements), and for such groups, the

number of elements of the group is also called the order of the

group. A group element a is said to have finite order if a^X = e for

some positive integer X, and the order of a is the smallest such X.

If no such X exists, a is said to have infinite order. All elements

of a finite group have a finite order, and the order of an element is

always a divisor of the group order.

If a group element a has order R, then for any integers X and Y,

a^X = a^(X mod R),

a^X = a^Y if and only if X is congruent to Y mod R,

the set H = { a, a^2, a^3, ... , a^R=e } forms a subgroup of G,

called the cyclic subgroup generated by a, and a is said to be a

generator of H.

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 H. Note that a^M is equal to g^(M modulo R) for any non-

negative integer M.

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

multiply" method outlined in Section 2.1 of [M1983] (see also Knuth,

Vol. 2, Section 4.6.3), or other methods.

## 2.3. The Finite Field Fp

This section establishes terminology and notation for finite fields

with prime characteristic.

When p is a prime number, then the set Zp, with the addition,

subtraction, multiplication, and division operations, is a finite

field with characteristic p. Each nonzero element x in Zp has an

inverse 1/x. There is a one-to-one correspondence between 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).

For any positive integer X, a^(-X) is defined to be (a^-1)^(X).

Using this convention, exponentiation behaves as one would expect,

namely for any integers X and Y:

a^(X+Y) = (a^X)*(a^Y)

(a^X)^Y = a^(XY) = (a^Y)^X.

In cryptographic applications, one typically deals with finite groups

(groups with a finite number of elements), and for such groups, the

number of elements of the group is also called the order of the

group. A group element a is said to have finite order if a^X = e for

some positive integer X, and the order of a is the smallest such X.

If no such X exists, a is said to have infinite order. All elements

of a finite group have a finite order, and the order of an element is

always a divisor of the group order.

If a group element a has order R, then for any integers X and Y,

a^X = a^(X mod R),

a^X = a^Y if and only if X is congruent to Y mod R,

the set H = { a, a^2, a^3, ... , a^R=e } forms a subgroup of G,

called the cyclic subgroup generated by a, and a is said to be a

generator of H.

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 H. Note that a^M is equal to g^(M modulo R) for any non-

negative integer M.

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

multiply" method outlined in Section 2.1 of [M1983] (see also Knuth,

Vol. 2, Section 4.6.3), or other methods.

This section establishes terminology and notation for finite fields

with prime characteristic.

When p is a prime number, then the set Zp, with the addition,

subtraction, multiplication, and division operations, is a finite

field with characteristic p. Each nonzero element x in Zp has an

inverse 1/x. There is a one-to-one correspondence between 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).

RFC 6090 Fundamental ECC February 2011

Equations involving field elements do not explicitly denote the "mod

p" operation, but it is understood to be implicit. For example, the

statement that x, y, and z are in Fp and

z = x + y

is equivalent to the statement that x, y, and z are in the set

{ 0, 1, ..., p-1 } and

z = x + y mod p.

# 3. Elliptic Curve Groups

This note only covers elliptic curves over fields with characteristic

greater than three; these are the curves used in Suite B [SuiteB].

For other fields, the definition of the elliptic curve group would be

different.

An elliptic curve over a field Fp is defined by the curve equation

y^2 = x^3 + a*x + b,

where x, y, a, and b are elements of the field Fp [M1985], and the

discriminant is nonzero (as described in Section 3.3.1). A point on

an elliptic curve is a pair (x,y) of values in Fp that satisfies the

curve equation, or it is a special point (@,@) that represents the

identity element (which is called the "point at infinity"). The

order of an elliptic curve group is the number of distinct points.

Two elliptic curve points (x1,y1) and (x2,y2) are equal whenever

x1=x2 and y1=y2, or when both points are the point at infinity. The

inverse of the point (x1,y1) is the point (x1,-y1). The point at

infinity is its own inverse.

The group operation associated with the elliptic curve group is as

follows [BC1989]. To an arbitrary pair of points P and Q specified

by their coordinates (x1,y1) and (x2,y2), respectively, the group

operation assigns a third point P*Q with the coordinates (x3,y3).

These coordinates are computed as follows:

(x3,y3) = (@,@) when P is not equal to Q and x1 is equal to x2.

x3 = ((y2-y1)/(x2-x1))^2 - x1 - x2 and

y3 = (x1-x3)*(y2-y1)/(x2-x1) - y1 when P is not equal to Q and

x1 is not equal to x2.

(x3,y3) = (@,@) when P is equal to Q and y1 is equal to 0.

Equations involving field elements do not explicitly denote the "mod

p" operation, but it is understood to be implicit. For example, the

statement that x, y, and z are in Fp and

z = x + y

is equivalent to the statement that x, y, and z are in the set

{ 0, 1, ..., p-1 } and

z = x + y mod p.

This note only covers elliptic curves over fields with characteristic

greater than three; these are the curves used in Suite B [SuiteB].

For other fields, the definition of the elliptic curve group would be

different.

An elliptic curve over a field Fp is defined by the curve equation

y^2 = x^3 + a*x + b,

where x, y, a, and b are elements of the field Fp [M1985], and the

discriminant is nonzero (as described in Section 3.3.1). A point on

an elliptic curve is a pair (x,y) of values in Fp that satisfies the

curve equation, or it is a special point (@,@) that represents the

identity element (which is called the "point at infinity"). The

order of an elliptic curve group is the number of distinct points.

Two elliptic curve points (x1,y1) and (x2,y2) are equal whenever

x1=x2 and y1=y2, or when both points are the point at infinity. The

inverse of the point (x1,y1) is the point (x1,-y1). The point at

infinity is its own inverse.

The group operation associated with the elliptic curve group is as

follows [BC1989]. To an arbitrary pair of points P and Q specified

by their coordinates (x1,y1) and (x2,y2), respectively, the group

operation assigns a third point P*Q with the coordinates (x3,y3).

These coordinates are computed as follows:

(x3,y3) = (@,@) when P is not equal to Q and x1 is equal to x2.

x3 = ((y2-y1)/(x2-x1))^2 - x1 - x2 and

y3 = (x1-x3)*(y2-y1)/(x2-x1) - y1 when P is not equal to Q and

x1 is not equal to x2.

(x3,y3) = (@,@) when P is equal to Q and y1 is equal to 0.

RFC 6090 Fundamental ECC February 2011

x3 = ((3*x1^2 + a)/(2*y1))^2 - 2*x1 and

y3 = (x1-x3)*(3*x1^2 + a)/(2*y1) - y1 if P is equal to Q and y1 is

not equal to 0.

In the above equations, a, x1, x2, x3, y1, y2, and y3 are elements of

the field Fp; thus, computation of x3 and y3 in practice must reduce

the right-hand-side modulo p. Pseudocode for the group operation is

provided in Appendix F.1.

The representation of elliptic curve points as a pair of integers in

Zp is known as the affine coordinate representation. This

representation is suitable as an external data representation for

communicating or storing group elements, though the point at infinity

must be treated as a special case.

Some pairs of integers are not valid elliptic curve points. A valid

pair will satisfy the curve equation, while an invalid pair will not.

## 3.1. Homogeneous Coordinates

An alternative way to implement the group operation is to use

homogeneous coordinates [K1987] (see also [KMOV1991]). This method

is typically more efficient because it does not require a modular

inversion operation.

An elliptic curve point (x,y) (other than the point at infinity

(@,@)) is equivalent to a point (X,Y,Z) in homogeneous coordinates

whenever x=X/Z mod p and y=Y/Z mod p.

Let P1=(X1,Y1,Z1) and P2=(X2,Y2,Z2) be points on an elliptic curve,

and suppose that the points P1 and P2 are not equal to (@,@), P1 is

not equal to P2, and P1 is not equal to P2^-1. Then the product

P3=(X3,Y3,Z3) = P1 * P2 is given by

X3 = v * (Z2 * (Z1 * u^2 - 2 * X1 * v^2) - v^3) mod p

Y3 = Z2 * (3 * X1 * u * v^2 - Y1 * v^3 - Z1 * u^3) + u * v^3 mod p

Z3 = v^3 * Z1 * Z2 mod p

where u = Y2 * Z1 - Y1 * Z2 mod p and v = X2 * Z1 - X1 * Z2 mod p.

When the points P1 and P2 are equal, then (X1/Z1, Y1/Z1) is equal to

(X2/Z2, Y2/Z2), which is true if and only if u and v are both equal

to zero.

x3 = ((3*x1^2 + a)/(2*y1))^2 - 2*x1 and

y3 = (x1-x3)*(3*x1^2 + a)/(2*y1) - y1 if P is equal to Q and y1 is

not equal to 0.

In the above equations, a, x1, x2, x3, y1, y2, and y3 are elements of

the field Fp; thus, computation of x3 and y3 in practice must reduce

the right-hand-side modulo p. Pseudocode for the group operation is

provided in Appendix F.1.

The representation of elliptic curve points as a pair of integers in

Zp is known as the affine coordinate representation. This

representation is suitable as an external data representation for

communicating or storing group elements, though the point at infinity

must be treated as a special case.

Some pairs of integers are not valid elliptic curve points. A valid

pair will satisfy the curve equation, while an invalid pair will not.

An alternative way to implement the group operation is to use

homogeneous coordinates [K1987] (see also [KMOV1991]). This method

is typically more efficient because it does not require a modular

inversion operation.

An elliptic curve point (x,y) (other than the point at infinity

(@,@)) is equivalent to a point (X,Y,Z) in homogeneous coordinates

whenever x=X/Z mod p and y=Y/Z mod p.

Let P1=(X1,Y1,Z1) and P2=(X2,Y2,Z2) be points on an elliptic curve,

and suppose that the points P1 and P2 are not equal to (@,@), P1 is

not equal to P2, and P1 is not equal to P2^-1. Then the product

P3=(X3,Y3,Z3) = P1 * P2 is given by

X3 = v * (Z2 * (Z1 * u^2 - 2 * X1 * v^2) - v^3) mod p

Y3 = Z2 * (3 * X1 * u * v^2 - Y1 * v^3 - Z1 * u^3) + u * v^3 mod p

Z3 = v^3 * Z1 * Z2 mod p

where u = Y2 * Z1 - Y1 * Z2 mod p and v = X2 * Z1 - X1 * Z2 mod p.

When the points P1 and P2 are equal, then (X1/Z1, Y1/Z1) is equal to

(X2/Z2, Y2/Z2), which is true if and only if u and v are both equal

to zero.

RFC 6090 Fundamental ECC February 2011

The product P3=(X3,Y3,Z3) = P1 * P1 is given by

X3 = 2 * Y1 * Z1 * (w^2 - 8 * X1 * Y1^2 * Z1) mod p

Y3 = 4 * Y1^2 * Z1 * (3 * w * X1 - 2 * Y1^2 * Z1) - w^3 mod p

Z3 = 8 * (Y1 * Z1)^3 mod p

where w = 3 * X1^2 + a * Z1^2 mod p. In the above equations, a, u,

v, w, X1, X2, X3, Y1, Y2, Y3, Z1, Z2, and Z3 are integers in the set

Fp. Pseudocode for the group operation in homogeneous coordinates is

provided in Appendix F.2.

When converting from affine coordinates to homogeneous coordinates,

it is convenient to set Z to 1. When converting from homogeneous

coordinates to affine coordinates, it is necessary to perform a

modular inverse to find 1/Z mod p.

## 3.2. Other Coordinates

Some other coordinate systems have been described; several are

documented in [CC1986], including Jacobi coordinates.

## 3.3. ECC Parameters

In cryptographic contexts, an elliptic curve parameter set consists

of a cyclic subgroup of an elliptic curve together with a preferred

generator of that subgroup. When working over a prime order finite

field with characteristic greater than three, an elliptic curve group

is completely specified by the following parameters:

The prime number p that indicates the order of the field Fp.

The value a used in the curve equation.

The value b used in the curve equation.

The generator g of the subgroup.

The order n of the subgroup generated by g.

An example of an ECC parameter set is provided in Appendix D.

Parameter generation is out of scope for this note.

Each elliptic curve point is associated with a particular parameter

set. The elliptic curve group operation is only defined between two

points in the same group. It is an error to apply the group

The product P3=(X3,Y3,Z3) = P1 * P1 is given by

X3 = 2 * Y1 * Z1 * (w^2 - 8 * X1 * Y1^2 * Z1) mod p

Y3 = 4 * Y1^2 * Z1 * (3 * w * X1 - 2 * Y1^2 * Z1) - w^3 mod p

Z3 = 8 * (Y1 * Z1)^3 mod p

where w = 3 * X1^2 + a * Z1^2 mod p. In the above equations, a, u,

v, w, X1, X2, X3, Y1, Y2, Y3, Z1, Z2, and Z3 are integers in the set

Fp. Pseudocode for the group operation in homogeneous coordinates is

provided in Appendix F.2.

When converting from affine coordinates to homogeneous coordinates,

it is convenient to set Z to 1. When converting from homogeneous

coordinates to affine coordinates, it is necessary to perform a

modular inverse to find 1/Z mod p.

Some other coordinate systems have been described; several are

documented in [CC1986], including Jacobi coordinates.

In cryptographic contexts, an elliptic curve parameter set consists

of a cyclic subgroup of an elliptic curve together with a preferred

generator of that subgroup. When working over a prime order finite

field with characteristic greater than three, an elliptic curve group

is completely specified by the following parameters:

The prime number p that indicates the order of the field Fp.

The value a used in the curve equation.

The value b used in the curve equation.

The generator g of the subgroup.

The order n of the subgroup generated by g.

An example of an ECC parameter set is provided in Appendix D.

Parameter generation is out of scope for this note.

Each elliptic curve point is associated with a particular parameter

set. The elliptic curve group operation is only defined between two

points in the same group. It is an error to apply the group

RFC 6090 Fundamental ECC February 2011

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

point. (A pair (x,y) of coordinates in Fp is a valid point only when

it satisfies the curve equation.) See Section 10.3 for further

information.

### 3.3.1. Discriminant

For each elliptic curve group, the discriminant -16*(4*a^3 + 27*b^2)

must be nonzero modulo p [S1986]; this requires that

4*a^3 + 27*b^2 != 0 mod p.

### 3.3.2. Security

Security is highly dependent on the choice of these parameters. This

section gives normative guidance on acceptable choices. See also

Section 10 for informative guidance.

The order of the group generated by g MUST be divisible by a large

prime, in order to preclude easy solutions of the discrete logarithm

problem [K1987].

With some parameter choices, the discrete log problem is

significantly easier to solve. This includes parameter sets in which

b = 0 and p = 3 (mod 4), and parameter sets in which a = 0 and

p = 2 (mod 3) [MOV1993]. These parameter choices are inferior for

cryptographic purposes and SHOULD NOT be used.

# 4. Elliptic Curve Diffie-Hellman (ECDH)

The Diffie-Hellman (DH) key exchange protocol [DH1976] allows two

parties communicating over an insecure channel to agree on a secret

key. It was originally defined in terms of operations in the

multiplicative group of a field with a large prime characteristic.

Massey [M1983] observed that it can be easily generalized so that it

is defined in terms of an arbitrary cyclic group. Miller [M1985] and

Koblitz [K1987] analyzed the DH protocol over an elliptic curve

group. We describe DH following the former reference.

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

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 exponent k between 1 and t-1, inclusive, uniformly at random,

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.

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

point. (A pair (x,y) of coordinates in Fp is a valid point only when

it satisfies the curve equation.) See Section 10.3 for further

information.

For each elliptic curve group, the discriminant -16*(4*a^3 + 27*b^2)

must be nonzero modulo p [S1986]; this requires that

4*a^3 + 27*b^2 != 0 mod p.

Security is highly dependent on the choice of these parameters. This

section gives normative guidance on acceptable choices. See also

Section 10 for informative guidance.

The order of the group generated by g MUST be divisible by a large

prime, in order to preclude easy solutions of the discrete logarithm

problem [K1987].

With some parameter choices, the discrete log problem is

significantly easier to solve. This includes parameter sets in which

b = 0 and p = 3 (mod 4), and parameter sets in which a = 0 and

p = 2 (mod 3) [MOV1993]. These parameter choices are inferior for

cryptographic purposes and SHOULD NOT be used.

The Diffie-Hellman (DH) key exchange protocol [DH1976] allows two

parties communicating over an insecure channel to agree on a secret

key. It was originally defined in terms of operations in the

multiplicative group of a field with a large prime characteristic.

Massey [M1983] observed that it can be easily generalized so that it

is defined in terms of an arbitrary cyclic group. Miller [M1985] and

Koblitz [K1987] analyzed the DH protocol over an elliptic curve

group. We describe DH following the former reference.

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

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 exponent k between 1 and t-1, inclusive, uniformly at random,

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.

RFC 6090 Fundamental ECC February 2011

See Appendix B regarding generation of random integers.

## 4.1. Data Types

Each run of the ECDH protocol is associated with a particular

parameter set (as defined in Section 3.3), and the public keys g^j

and g^k and the shared secret g^(j*k) are elements of the cyclic

subgroup associated with the parameter set.

An ECDH private key z is an integer in Zt, where t is the order of

the subgroup.

## 4.2. Compact Representation

As described in the final paragraph of [M1985], the x-coordinate of

the shared secret value g^(j*k) is a suitable representative for the

entire point whenever exponentiation is used as a one-way function.

In the ECDH key exchange protocol, after the element g^(j*k) has been

computed, the x-coordinate of that value can be used as the shared

secret. We call this compact output.

Following [M1985] again, when compact output is used in ECDH, only

the x-coordinate of an elliptic curve point needs to be transmitted,

instead of both coordinates as in the typical affine coordinate

representation. We call this the compact representation. Its

mathematical background is explained in Appendix C.

ECDH can be used with or without compact output. Both parties in a

particular run of the ECDH protocol MUST use the same method. ECDH

can be used with or without compact representation. If compact

representation is used in a particular run of the ECDH protocol, then

compact output MUST be used as well.

# 5. Elliptic Curve ElGamal Signatures

## 5.1. Background

The ElGamal signature algorithm was introduced in 1984 [E1984a]

[E1984b] [E1985]. It is based on the discrete logarithm problem, and

was originally defined for the multiplicative group of the integers

modulo a large prime number. It is straightforward to extend it to

use other finite groups, such as the multiplicative group of the

finite field GF(2^w) [AMV1990] or an elliptic curve group [A1992].

An ElGamal signature consists of a pair of components. There are

many possible generalizations of ElGamal signature methods that have

been obtained by different rearrangements of the equation for the

second component; see [HMP1994], [HP1994], [NR1994], [A1992], and

See Appendix B regarding generation of random integers.

Each run of the ECDH protocol is associated with a particular

parameter set (as defined in Section 3.3), and the public keys g^j

and g^k and the shared secret g^(j*k) are elements of the cyclic

subgroup associated with the parameter set.

An ECDH private key z is an integer in Zt, where t is the order of

the subgroup.

As described in the final paragraph of [M1985], the x-coordinate of

the shared secret value g^(j*k) is a suitable representative for the

entire point whenever exponentiation is used as a one-way function.

In the ECDH key exchange protocol, after the element g^(j*k) has been

computed, the x-coordinate of that value can be used as the shared

secret. We call this compact output.

Following [M1985] again, when compact output is used in ECDH, only

the x-coordinate of an elliptic curve point needs to be transmitted,

instead of both coordinates as in the typical affine coordinate

representation. We call this the compact representation. Its

mathematical background is explained in Appendix C.

ECDH can be used with or without compact output. Both parties in a

particular run of the ECDH protocol MUST use the same method. ECDH

can be used with or without compact representation. If compact

representation is used in a particular run of the ECDH protocol, then

compact output MUST be used as well.

The ElGamal signature algorithm was introduced in 1984 [E1984a]

[E1984b] [E1985]. It is based on the discrete logarithm problem, and

was originally defined for the multiplicative group of the integers

modulo a large prime number. It is straightforward to extend it to

use other finite groups, such as the multiplicative group of the

finite field GF(2^w) [AMV1990] or an elliptic curve group [A1992].

An ElGamal signature consists of a pair of components. There are

many possible generalizations of ElGamal signature methods that have

been obtained by different rearrangements of the equation for the

second component; see [HMP1994], [HP1994], [NR1994], [A1992], and

RFC 6090 Fundamental ECC February 2011

[AMV1990]. These generalizations are independent of the mathematical

group used, and have been described for the multiplicative group

modulo a prime number, the multiplicative group of GF(2^w), and

elliptic curve groups [HMP1994] [NR1994] [AMV1990] [A1992].

The Digital Signature Algorithm (DSA) [FIPS186] is an important

ElGamal signature variant.

## 5.2. Hash Functions

ElGamal signatures must use a collision-resistant hash function, so

that it can sign messages of arbitrary length and can avoid

existential forgery attacks; see Section 10.4. (This is true for all

ElGamal variants [HMP1994].) We denote the hash function as h().

Its input is a bit string of arbitrary length, and its output is a

non-negative integer.

Let H() denote a hash function whose output is a fixed-length bit

string. To use H in an ElGamal signature method, we define the

mapping between that output and the non-negative integers; this

realizes the function h() described above. Given a bit string m, the

function h(m) is computed as follows:

1. H(m) is evaluated; the result is a fixed-length bit string.

2. Convert the resulting bit string to an integer i by treating its

leftmost (initial) bit as the most significant bit of i, and

treating its rightmost (final) bit as the least significant bit

of i.

## 5.3. KT-IV Signatures

Koyama and Tsuruoka described a signature method based on Elliptic

Curve ElGamal, in which the first signature component is the

x-coordinate of an elliptic curve point reduced modulo q [KT1994].

In this section, we recall that method, which we refer to as KT-IV.

The algorithm uses an elliptic curve group, as described in

Section 3.3, with prime field order p and curve equation parameters a

and b. We denote the generator as alpha, and the order of the

generator as q. We follow [FIPS186] in checking for exceptional

cases.

### 5.3.1. Keypair Generation

The private key z is an integer between 1 and q-1, inclusive,

generated uniformly at random. (See Appendix B regarding random

integers.) The public key is the group element Y = alpha^z. Each

[AMV1990]. These generalizations are independent of the mathematical

group used, and have been described for the multiplicative group

modulo a prime number, the multiplicative group of GF(2^w), and

elliptic curve groups [HMP1994] [NR1994] [AMV1990] [A1992].

The Digital Signature Algorithm (DSA) [FIPS186] is an important

ElGamal signature variant.

ElGamal signatures must use a collision-resistant hash function, so

that it can sign messages of arbitrary length and can avoid

existential forgery attacks; see Section 10.4. (This is true for all

ElGamal variants [HMP1994].) We denote the hash function as h().

Its input is a bit string of arbitrary length, and its output is a

non-negative integer.

Let H() denote a hash function whose output is a fixed-length bit

string. To use H in an ElGamal signature method, we define the

mapping between that output and the non-negative integers; this

realizes the function h() described above. Given a bit string m, the

function h(m) is computed as follows:

1. H(m) is evaluated; the result is a fixed-length bit string.

2. Convert the resulting bit string to an integer i by treating its

leftmost (initial) bit as the most significant bit of i, and

treating its rightmost (final) bit as the least significant bit

of i.

Koyama and Tsuruoka described a signature method based on Elliptic

Curve ElGamal, in which the first signature component is the

x-coordinate of an elliptic curve point reduced modulo q [KT1994].

In this section, we recall that method, which we refer to as KT-IV.

The algorithm uses an elliptic curve group, as described in

Section 3.3, with prime field order p and curve equation parameters a

and b. We denote the generator as alpha, and the order of the

generator as q. We follow [FIPS186] in checking for exceptional

cases.

The private key z is an integer between 1 and q-1, inclusive,

generated uniformly at random. (See Appendix B regarding random

integers.) The public key is the group element Y = alpha^z. Each

RFC 6090 Fundamental ECC February 2011

public key is associated with a particular parameter set as per

Section 3.3.

### 5.3.2. Signature Creation

To compute a KT-IV signature for a message m using the private key z:

1. Choose an integer k uniformly at random from the set of all

integers between 1 and q-1, inclusive. (See Appendix B regarding

random integers.)

2. Calculate R = (r_x, r_y) = alpha^k.

3. Calculate s1 = r_x mod q.

4. Check if h(m) + z * s1 = 0 mod q; if so, a new value of k MUST be

generated and the signature MUST be recalculated. As an option,

one MAY check if s1 = 0; if so, a new value of k SHOULD be

generated and the signature SHOULD be recalculated. (It is

extremely unlikely that s1 = 0 or h(m) + z * s1 = 0 mod q if

signatures are generated properly.)

5. Calculate s2 = k/(h(m) + z*s1) mod q.

The signature is the ordered pair (s1, s2). Both signature

components are non-negative integers.

### 5.3.3. Signature Verification

Given the message m, the generator g, the group order q, the public

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

is violated, the signature SHALL be rejected.

2. Compute the non-negative integers u1 and u2, where

u1 = h(m) * s2 mod q, and

u2 = s1 * s2 mod q.

3. Compute the elliptic curve point R' = alpha^u1 * Y^u2.

4. If the x-coordinate of R' mod q is equal to s1, then the

signature and message pass the verification; otherwise, they

fail.

public key is associated with a particular parameter set as per

Section 3.3.

To compute a KT-IV signature for a message m using the private key z:

1. Choose an integer k uniformly at random from the set of all

integers between 1 and q-1, inclusive. (See Appendix B regarding

random integers.)

2. Calculate R = (r_x, r_y) = alpha^k.

3. Calculate s1 = r_x mod q.

4. Check if h(m) + z * s1 = 0 mod q; if so, a new value of k MUST be

generated and the signature MUST be recalculated. As an option,

one MAY check if s1 = 0; if so, a new value of k SHOULD be

generated and the signature SHOULD be recalculated. (It is

extremely unlikely that s1 = 0 or h(m) + z * s1 = 0 mod q if

signatures are generated properly.)

5. Calculate s2 = k/(h(m) + z*s1) mod q.

The signature is the ordered pair (s1, s2). Both signature

components are non-negative integers.

Given the message m, the generator g, the group order q, the public

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

is violated, the signature SHALL be rejected.

2. Compute the non-negative integers u1 and u2, where

u1 = h(m) * s2 mod q, and

u2 = s1 * s2 mod q.

3. Compute the elliptic curve point R' = alpha^u1 * Y^u2.

4. If the x-coordinate of R' mod q is equal to s1, then the

signature and message pass the verification; otherwise, they

fail.

RFC 6090 Fundamental ECC February 2011

## 5.4. KT-I Signatures

Horster, Michels, and Petersen categorized many different ElGamal

signature methods, demonstrated their equivalence, and showed how to

convert signatures of one type to another type [HMP1994]. In their

terminology, the signature method of Section 5.3 and [KT1994] is a

Type IV method, which is why it is denoted as KT-IV.

A Type I KT signature method has a second component that is computed

in the same manner as that of the Digital Signature Algorithm. In

this section, we describe this method, which we refer to as KT-I.

### 5.4.1. Keypair Generation

Keypairs and keypair generation are exactly as in Section 5.3.1.

### 5.4.2. Signature Creation

To compute a KT-I signature for a message m using the private key z:

1. Choose an integer k uniformly at random from the set of all

integers between 1 and q-1, inclusive. (See Appendix B regarding

random integers.)

2. Calculate R = (r_x, r_y) = alpha^k.

3. Calculate s1 = r_x mod q.

4. Calculate s2 = (h(m) + z*s1)/k mod q.

5. As an option, one MAY check if s1 = 0 or s2 = 0. If either

s1 = 0 or s2 = 0, a new value of k SHOULD be generated and the

signature SHOULD be recalculated. (It is extremely unlikely that

s1 = 0 or s2 = 0 if signatures are generated properly.)

The signature is the ordered pair (s1, s2). Both signature

components are non-negative integers.

### 5.4.3. Signature Verification

Given the message m, the public 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

is violated, the signature SHALL be rejected.

2. Compute s2_inv = 1/s2 mod q.

Horster, Michels, and Petersen categorized many different ElGamal

signature methods, demonstrated their equivalence, and showed how to

convert signatures of one type to another type [HMP1994]. In their

terminology, the signature method of Section 5.3 and [KT1994] is a

Type IV method, which is why it is denoted as KT-IV.

A Type I KT signature method has a second component that is computed

in the same manner as that of the Digital Signature Algorithm. In

this section, we describe this method, which we refer to as KT-I.

Keypairs and keypair generation are exactly as in Section 5.3.1.

To compute a KT-I signature for a message m using the private key z:

1. Choose an integer k uniformly at random from the set of all

integers between 1 and q-1, inclusive. (See Appendix B regarding

random integers.)

2. Calculate R = (r_x, r_y) = alpha^k.

3. Calculate s1 = r_x mod q.

4. Calculate s2 = (h(m) + z*s1)/k mod q.

5. As an option, one MAY check if s1 = 0 or s2 = 0. If either

s1 = 0 or s2 = 0, a new value of k SHOULD be generated and the

signature SHOULD be recalculated. (It is extremely unlikely that

s1 = 0 or s2 = 0 if signatures are generated properly.)

The signature is the ordered pair (s1, s2). Both signature

components are non-negative integers.

Given the message m, the public 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

is violated, the signature SHALL be rejected.

2. Compute s2_inv = 1/s2 mod q.

RFC 6090 Fundamental ECC February 2011

3. Compute the non-negative integers u1 and u2, where

u1 = h(m) * s2_inv mod q, and

u2 = s1 * s2_inv mod q.

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

signature and message pass the verification; otherwise, they

fail.

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

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

(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

performed by the creator of the pre-conversion KT-IV signature, the

verifier of the post-conversion KT-I signature, or by any other

entity.

An implementation MAY use this method to compute KT-I signatures.

## 5.6. Rationale

This subsection is not normative for this specification and is

provided only as background information.

[HMP1994] presents many generalizations of ElGamal signatures.

Equation (5) of that reference shows the general signature equation

A = x_A * B + k * C (mod q)

where x_A is the private key, k is the secret value, and A, B, and C

are determined by the Type of the equation, as shown in Table 1 of

[HMP1994]. DSA [FIPS186] is an EG-I.1 signature method (as is KT-I),

with A = m, B = -r, and C = s. (Here we use the notation of

[HMP1994] in which the first signature component is r and the second

signature component is s; in KT-I and KT-IV these components are

denoted as s1 and s2, respectively. The private key x_A corresponds

to the private key z.) Its signature equation is

m = -r * z + s * k (mod q).

3. Compute the non-negative integers u1 and u2, where

u1 = h(m) * s2_inv mod q, and

u2 = s1 * s2_inv mod q.

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

signature and message pass the verification; otherwise, they

fail.

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.

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].

The conversion operation uses only public information, and it can be

performed by the creator of the pre-conversion KT-IV signature, the

verifier of the post-conversion KT-I signature, or by any other

entity.

An implementation MAY use this method to compute KT-I signatures.

This subsection is not normative for this specification and is

provided only as background information.

[HMP1994] presents many generalizations of ElGamal signatures.

Equation (5) of that reference shows the general signature equation

A = x_A * B + k * C (mod q)

where x_A is the private key, k is the secret value, and A, B, and C

are determined by the Type of the equation, as shown in Table 1 of

[HMP1994]. DSA [FIPS186] is an EG-I.1 signature method (as is KT-I),

with A = m, B = -r, and C = s. (Here we use the notation of

[HMP1994] in which the first signature component is r and the second

signature component is s; in KT-I and KT-IV these components are

denoted as s1 and s2, respectively. The private key x_A corresponds

to the private key z.) Its signature equation is

m = -r * z + s * k (mod q).

RFC 6090 Fundamental ECC February 2011

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 is

m * s = -r * s * z + k (mod q)

The functions f and g mentioned in Table 1 of [HMP1994] are merely

multiplication, as described under the heading "Fifth

generalization".

In the above equations, we rely on the implicit conversion of the

message m from a bit string to an integer. No hash function is shown

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

methods and defined "strong equivalence" as follows:

Two signature methods are called strongly equivalent if the

signature of the first scheme can be transformed efficiently into

signatures of the second scheme and vice versa, without knowledge

of the private key.

KT-I and KT-IV signatures are obviously strongly equivalent.

A valid signature with s2=0 leaks the secret key, since in that case

z = -h(m) / s1 mod q. We follow [FIPS186] in checking for this

exceptional case and the case that s1=0. The s2=0 check was

suggested by Rivest [R1992] and is discussed in [BS1992].

[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

elliptic curve point R = (r_x, r_y). The value q' is also used

during signature validation when comparing the x-coordinate of a

computed elliptic curve point to the value to s1. In this note, we

use the simplifying convention that q' = q.

# 6. Converting between Integers and Octet Strings

A method for the conversion between integers and octet strings is

specified in this section, following the established conventions of

public key cryptography [R1993]. This method allows integers to be

represented as octet strings that are suitable for transmission or

storage. This method SHOULD be used when representing an elliptic

curve point or an elliptic curve coordinate as they are defined in

this note.

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 is

m * s = -r * s * z + k (mod q)

The functions f and g mentioned in Table 1 of [HMP1994] are merely

multiplication, as described under the heading "Fifth

generalization".

In the above equations, we rely on the implicit conversion of the

message m from a bit string to an integer. No hash function is shown

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

methods and defined "strong equivalence" as follows:

Two signature methods are called strongly equivalent if the

signature of the first scheme can be transformed efficiently into

signatures of the second scheme and vice versa, without knowledge

of the private key.

KT-I and KT-IV signatures are obviously strongly equivalent.

A valid signature with s2=0 leaks the secret key, since in that case

z = -h(m) / s1 mod q. We follow [FIPS186] in checking for this

exceptional case and the case that s1=0. The s2=0 check was

suggested by Rivest [R1992] and is discussed in [BS1992].

[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

elliptic curve point R = (r_x, r_y). The value q' is also used

during signature validation when comparing the x-coordinate of a

computed elliptic curve point to the value to s1. In this note, we

use the simplifying convention that q' = q.

A method for the conversion between integers and octet strings is

specified in this section, following the established conventions of

public key cryptography [R1993]. This method allows integers to be

represented as octet strings that are suitable for transmission or

storage. This method SHOULD be used when representing an elliptic

curve point or an elliptic curve coordinate as they are defined in

this note.

RFC 6090 Fundamental ECC February 2011

## 6.1. Octet-String-to-Integer Conversion

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

integer x shall satisfy

k

x = SUM 2^(8(k-i)) Si .

i = 1

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.

Note: the integer x satisfies 0 <= x < 2^(8*k).

## 6.2. Integer-to-Octet-String Conversion

The integer x shall be converted to an octet string S of length k as

follows. The string S shall satisfy

k

y = SUM 2^(8(k-i)) Si .

i = 1

where S1, ..., Sk are the octets of S from first to last.

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.

# 7. Interoperability

The algorithms in this note can be used to interoperate with some

other ECC specifications. This section provides details for each

algorithm.

## 7.1. ECDH

Section 4 can be used with the Internet Key Exchange (IKE) versions

one [RFC2409] or two [RFC5996]. These algorithms are compatible with

the ECP groups defined by [RFC5903], [RFC5114], [RFC2409], and

[RFC2412]. The group definition in this protocol uses an affine

coordinate representation of the public key. [RFC5903] uses the

compact output of Section 4.2, while [RFC4753] (which was obsoleted

by RFC 5903) does not. Neither of those RFCs use compact

representation. Note that some groups indicate that the curve

parameter "a" is negative; these values are to be interpreted modulo

the order of the field. For example, a parameter of a = -3 is equal

to p - 3, where p is the order of the field. The test cases in

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

integer x shall satisfy

k

x = SUM 2^(8(k-i)) Si .

i = 1

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.

Note: the integer x satisfies 0 <= x < 2^(8*k).

The integer x shall be converted to an octet string S of length k as

follows. The string S shall satisfy

k

y = SUM 2^(8(k-i)) Si .

i = 1

where S1, ..., Sk are the octets of S from first to last.

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.

The algorithms in this note can be used to interoperate with some

other ECC specifications. This section provides details for each

algorithm.

Section 4 can be used with the Internet Key Exchange (IKE) versions

one [RFC2409] or two [RFC5996]. These algorithms are compatible with

the ECP groups defined by [RFC5903], [RFC5114], [RFC2409], and

[RFC2412]. The group definition in this protocol uses an affine

coordinate representation of the public key. [RFC5903] uses the

compact output of Section 4.2, while [RFC4753] (which was obsoleted

by RFC 5903) does not. Neither of those RFCs use compact

representation. Note that some groups indicate that the curve

parameter "a" is negative; these values are to be interpreted modulo

the order of the field. For example, a parameter of a = -3 is equal

to p - 3, where p is the order of the field. The test cases in

RFC 6090 Fundamental ECC February 2011

Section 8 of [RFC5903] can be used to test an implementation; these

cases use the multiplicative notation, as does this note. The KEi

and KEr payloads are equal to g^j and g^k, respectively, with 64 bits

of encoding data prepended to them.

The algorithms in Section 4 can be used to interoperate with the IEEE

[P1363] and ANSI [X9.62] standards for ECDH based on fields of

characteristic greater than three. IEEE P1363 ECDH can be used in a

manner that will interoperate with this note, with the following

options and parameter choices from that specification:

prime curves with a cofactor of 1,

the ECSVDP-DH (Elliptic Curve Secret Value Derivation Primitive,

Diffie-Hellman version),

the Key Derivation Function (KDF) must be the "identity" function

(equivalently, the KDF step should be omitted and the shared

secret value should be output directly).

## 7.2. KT-I and ECDSA

The Digital Signature Algorithm (DSA) is based on the discrete

logarithm problem over the multiplicative subgroup of the finite

field with large prime order [DSA1991] [FIPS186]. The Elliptic Curve

Digital Signature Algorithm (ECDSA) [P1363] [X9.62] is an elliptic

curve version of DSA.

KT-I is mathematically and functionally equivalent to ECDSA, and can

interoperate with the IEEE [P1363] and ANSI [X9.62] standards for

Elliptic Curve DSA (ECDSA) based on fields of characteristic greater

than three. KT-I signatures can be verified using the ECDSA

verification algorithm, and ECDSA signatures can be verified using

the KT-I verification algorithm.

# 8. Validating an Implementation

It is essential to validate the implementation of a cryptographic

algorithm. This section outlines tests that should be performed on

the algorithms defined in this note.

A known answer test, or KAT, uses a fixed set of inputs to test an

algorithm; the output of the algorithm is compared with the expected

output, which is also a fixed value. KATs for ECDH and KT-I are set

out in the following subsections.

Section 8 of [RFC5903] can be used to test an implementation; these

cases use the multiplicative notation, as does this note. The KEi

and KEr payloads are equal to g^j and g^k, respectively, with 64 bits

of encoding data prepended to them.

The algorithms in Section 4 can be used to interoperate with the IEEE

[P1363] and ANSI [X9.62] standards for ECDH based on fields of

characteristic greater than three. IEEE P1363 ECDH can be used in a

manner that will interoperate with this note, with the following

options and parameter choices from that specification:

prime curves with a cofactor of 1,

the ECSVDP-DH (Elliptic Curve Secret Value Derivation Primitive,

Diffie-Hellman version),

the Key Derivation Function (KDF) must be the "identity" function

(equivalently, the KDF step should be omitted and the shared

secret value should be output directly).

The Digital Signature Algorithm (DSA) is based on the discrete

logarithm problem over the multiplicative subgroup of the finite

field with large prime order [DSA1991] [FIPS186]. The Elliptic Curve

Digital Signature Algorithm (ECDSA) [P1363] [X9.62] is an elliptic

curve version of DSA.

KT-I is mathematically and functionally equivalent to ECDSA, and can

interoperate with the IEEE [P1363] and ANSI [X9.62] standards for

Elliptic Curve DSA (ECDSA) based on fields of characteristic greater

than three. KT-I signatures can be verified using the ECDSA

verification algorithm, and ECDSA signatures can be verified using

the KT-I verification algorithm.

It is essential to validate the implementation of a cryptographic

algorithm. This section outlines tests that should be performed on

the algorithms defined in this note.

A known answer test, or KAT, uses a fixed set of inputs to test an

algorithm; the output of the algorithm is compared with the expected

output, which is also a fixed value. KATs for ECDH and KT-I are set

out in the following subsections.

RFC 6090 Fundamental ECC February 2011

A consistency test generates inputs for one algorithm being tested

using a second algorithm that is also being tested, then checks the

output of the first algorithm. A signature creation algorithm can be

tested for consistency against a signature verification algorithm.

Implementations of KT-I should be tested in this way. Their

signature generation processes are non-deterministic, and thus cannot

be tested using a KAT. Signature verification algorithms, on the

other hand, are deterministic and should be tested via a KAT. This

combination of tests provides coverage for all of the operations,

including keypair generation. Consistency testing should also be

applied to ECDH.

## 8.1. ECDH

An ECDH implementation can be validated using the known answer test

cases from [RFC5903] or [RFC5114]. The correspondence between the

notation in RFC 5903 and the notation in this note is summarized in

the following table. (Refer to Sections 3.3 and 4; the generator g

is expressed in affine coordinate representation as (gx, gy)).

+----------------------+---------------------------------------+

| ECDH | RFC 5903 |

+----------------------+---------------------------------------+

| order p of field Fp | p |

| curve coefficient a | -3 |

| curve coefficient b | b |

| generator g | g=(gx, gy) |

| private keys j and k | i and r |

| public keys g^j, g^k | g^i = (gix, giy) and g^r = (grx, gry) |

+----------------------+---------------------------------------+

The correspondence between the notation in RFC 5114 and the notation

in this note is summarized in the following table.

+-----------------------+---------------------------+

| ECDH | RFC 5114 |

+-----------------------+---------------------------+

| order p of field Fp | p |

| curve coefficient a | a |

| curve coefficient b | b |

| generator g | g=(gx, gy) |

| group order n | n |

| private keys j and k | dA and dB |

| public keys g^j, g^k | g^(dA) = (x_qA, y_qA) and |

| | g^(dB) = (x_qB, y_qB) |

| shared secret g^(j*k) | g^(dA*dB) = (x_Z, y_Z) |

+-----------------------+---------------------------+

A consistency test generates inputs for one algorithm being tested

using a second algorithm that is also being tested, then checks the

output of the first algorithm. A signature creation algorithm can be

tested for consistency against a signature verification algorithm.

Implementations of KT-I should be tested in this way. Their

signature generation processes are non-deterministic, and thus cannot

be tested using a KAT. Signature verification algorithms, on the

other hand, are deterministic and should be tested via a KAT. This

combination of tests provides coverage for all of the operations,

including keypair generation. Consistency testing should also be

applied to ECDH.

An ECDH implementation can be validated using the known answer test

cases from [RFC5903] or [RFC5114]. The correspondence between the

notation in RFC 5903 and the notation in this note is summarized in

the following table. (Refer to Sections 3.3 and 4; the generator g

is expressed in affine coordinate representation as (gx, gy)).

+----------------------+---------------------------------------+

| ECDH | RFC 5903 |

+----------------------+---------------------------------------+

| order p of field Fp | p |

| curve coefficient a | -3 |

| curve coefficient b | b |

| generator g | g=(gx, gy) |

| private keys j and k | i and r |

| public keys g^j, g^k | g^i = (gix, giy) and g^r = (grx, gry) |

+----------------------+---------------------------------------+

The correspondence between the notation in RFC 5114 and the notation

in this note is summarized in the following table.

+-----------------------+---------------------------+

| ECDH | RFC 5114 |

+-----------------------+---------------------------+

| order p of field Fp | p |

| curve coefficient a | a |

| curve coefficient b | b |

| generator g | g=(gx, gy) |

| group order n | n |

| private keys j and k | dA and dB |

| public keys g^j, g^k | g^(dA) = (x_qA, y_qA) and |

| | g^(dB) = (x_qB, y_qB) |

| shared secret g^(j*k) | g^(dA*dB) = (x_Z, y_Z) |

+-----------------------+---------------------------+

RFC 6090 Fundamental ECC February 2011

## 8.2. KT-I

A KT-I implementation can be validated using the known answer test

cases from [RFC4754]. The correspondence between the notation in

that RFC and the notation in this note is summarized in the following

table.

+---------------------+------------------+

| KT-I | RFC 4754 |

+---------------------+------------------+

| order p of field Fp | p |

| curve coefficient a | -3 |

| curve coefficient b | b |

| generator alpha | g |

| group order q | q |

| private key z | w |

| public key Y | g^w = (gwx,gwy) |

| random k | ephem priv k |

| s1 | r |

| s2 | s |

| s2_inv | sinv |

| u1 | u = h*sinv mod q |

| u2 | v = r*sinv mod q |

+---------------------+------------------+

# 9. Intellectual Property

Concerns about intellectual property have slowed the adoption of ECC

because a number of optimizations and specialized algorithms have

been patented in recent years.

All of the normative references for ECDH (as defined in Section 4)

were published during or before 1989, and those for KT-I were

published during or before May 1994. All of the normative text for

these algorithms is based solely on their respective references.

## 9.1. Disclaimer

This document is not intended as legal advice. Readers are advised

to consult their own legal advisers if they would like a legal

interpretation of their rights.

The IETF policies and processes regarding intellectual property and

patents are outlined in [RFC3979] and [RFC4879] and at

https://datatracker.ietf.org/ipr/about/.

A KT-I implementation can be validated using the known answer test

cases from [RFC4754]. The correspondence between the notation in

that RFC and the notation in this note is summarized in the following

table.

+---------------------+------------------+

| KT-I | RFC 4754 |

+---------------------+------------------+

| order p of field Fp | p |

| curve coefficient a | -3 |

| curve coefficient b | b |

| generator alpha | g |

| group order q | q |

| private key z | w |

| public key Y | g^w = (gwx,gwy) |

| random k | ephem priv k |

| s1 | r |

| s2 | s |

| s2_inv | sinv |

| u1 | u = h*sinv mod q |

| u2 | v = r*sinv mod q |

+---------------------+------------------+

Concerns about intellectual property have slowed the adoption of ECC

because a number of optimizations and specialized algorithms have

been patented in recent years.

All of the normative references for ECDH (as defined in Section 4)

were published during or before 1989, and those for KT-I were

published during or before May 1994. All of the normative text for

these algorithms is based solely on their respective references.

This document is not intended as legal advice. Readers are advised

to consult their own legal advisers if they would like a legal

interpretation of their rights.

The IETF policies and processes regarding intellectual property and

patents are outlined in [RFC3979] and [RFC4879] and at

https://datatracker.ietf.org/ipr/about/.

RFC 6090 Fundamental ECC February 2011

# 10. Security Considerations

The security level of an elliptic curve cryptosystem is determined by

the cryptanalytic algorithm that is the least expensive for an

attacker to implement. There are several algorithms to consider.

The Pohlig-Hellman method is a divide-and-conquer technique [PH1978].

If the group order n can be factored as

n = q1 * q2 * ... * qz,

then the discrete log problem over the group can be solved by

independently solving a discrete log problem in groups of order q1,

q2, ..., qz, then combining the results using the Chinese remainder

theorem. The overall computational cost is dominated by that of the

discrete log problem in the subgroup with the largest order.

Shanks' algorithm [K1981v3] computes a discrete logarithm in a group

of order n using O(sqrt(n)) operations and O(sqrt(n)) storage. The

Pollard rho algorithm [P1978] computes a discrete logarithm in a

group of order n using O(sqrt(n)) operations, with a negligible

amount of storage, and can be efficiently parallelized [VW1994].

The Pollard lambda algorithm [P1978] can solve the discrete logarithm

problem using O(sqrt(w)) operations and O(log(w)) storage, when the

exponent is known to lie in an interval of width w.

The algorithms described above work in any group. There are

specialized algorithms that specifically target elliptic curve

groups. There are no known subexponential algorithms against general

elliptic curve groups, though there are methods that target certain

special elliptic curve groups; see [MOV1993] and [FR1994].

## 10.1. Subgroups

A group consisting of a nonempty set of elements S with associated

group operation * is a subgroup of the group with the set of elements

G, if the latter group uses the same group operation and S is a

subset of G. For each elliptic curve equation, there is an elliptic

curve group whose group order is equal to the order of the elliptic

curve; that is, there is a group that contains every point on the

curve.

The order m of the elliptic curve is divisible by the order n of the

group associated with the generator; that is, for each elliptic curve

group, m = n * c for some number c. The number c is called the

"cofactor" [P1363]. Each ECC parameter set as in Section 3.3 is

associated with a particular cofactor.

The security level of an elliptic curve cryptosystem is determined by

the cryptanalytic algorithm that is the least expensive for an

attacker to implement. There are several algorithms to consider.

The Pohlig-Hellman method is a divide-and-conquer technique [PH1978].

If the group order n can be factored as

n = q1 * q2 * ... * qz,

then the discrete log problem over the group can be solved by

independently solving a discrete log problem in groups of order q1,

q2, ..., qz, then combining the results using the Chinese remainder

theorem. The overall computational cost is dominated by that of the

discrete log problem in the subgroup with the largest order.

Shanks' algorithm [K1981v3] computes a discrete logarithm in a group

of order n using O(sqrt(n)) operations and O(sqrt(n)) storage. The

Pollard rho algorithm [P1978] computes a discrete logarithm in a

group of order n using O(sqrt(n)) operations, with a negligible

amount of storage, and can be efficiently parallelized [VW1994].

The Pollard lambda algorithm [P1978] can solve the discrete logarithm

problem using O(sqrt(w)) operations and O(log(w)) storage, when the

exponent is known to lie in an interval of width w.

The algorithms described above work in any group. There are

specialized algorithms that specifically target elliptic curve

groups. There are no known subexponential algorithms against general

elliptic curve groups, though there are methods that target certain

special elliptic curve groups; see [MOV1993] and [FR1994].

A group consisting of a nonempty set of elements S with associated

group operation * is a subgroup of the group with the set of elements

G, if the latter group uses the same group operation and S is a

subset of G. For each elliptic curve equation, there is an elliptic

curve group whose group order is equal to the order of the elliptic

curve; that is, there is a group that contains every point on the

curve.

The order m of the elliptic curve is divisible by the order n of the

group associated with the generator; that is, for each elliptic curve

group, m = n * c for some number c. The number c is called the

"cofactor" [P1363]. Each ECC parameter set as in Section 3.3 is

associated with a particular cofactor.

RFC 6090 Fundamental ECC February 2011

It is possible and desirable to use a cofactor equal to 1.

## 10.2. Diffie-Hellman

Note that the key exchange protocol as defined in Section 4 does not

protect against active attacks; Party A must use some method to

ensure that (g^k) originated with the intended communicant B, rather

than an attacker, and Party B must do the same with (g^j).

It is not sufficient to authenticate the shared secret g^(j*k), since

this leaves the protocol open to attacks that manipulate the public

keys. Instead, the values of the public keys g^x and g^y that are

exchanged should be directly authenticated. This is the strategy

used by protocols that build on Diffie-Hellman and that use end-

entity authentication to protect against active attacks, such as

OAKLEY [RFC2412] and the Internet Key Exchange [RFC2409] [RFC4306]

[RFC5996].

When the cofactor of a group is not equal to 1, there are a number of

attacks that are possible against ECDH. See [VW1996], [AV1996], and

[LL1997].

## 10.3. Group Representation and Security

The elliptic curve group operation does not explicitly incorporate

the parameter b from the curve equation. This opens the possibility

that a malicious attacker could learn information about an ECDH

private key by submitting a bogus public key [BMM2000]. An attacker

can craft an elliptic curve group G' that has identical parameters to

a group G that is being used in an ECDH protocol, except that b is

different. An attacker can submit a point on G' into a run of the

ECDH protocol that is using group G, and gain information from the

fact that the group operations using the private key of the device

under attack are effectively taking place in G' instead of G.

This attack can gain useful information about an ECDH private key

that is associated with a static public key, i.e., a public key that

is used in more than one run of the protocol. However, it does not

gain any useful information against ephemeral keys.

This sort of attack is thwarted if an ECDH implementation does not

assume that each pair of coordinates in Zp is actually a point on the

appropriate elliptic curve.

These considerations also apply when ECDH is used with compact

representation (see Appendix C).

It is possible and desirable to use a cofactor equal to 1.

Note that the key exchange protocol as defined in Section 4 does not

protect against active attacks; Party A must use some method to

ensure that (g^k) originated with the intended communicant B, rather

than an attacker, and Party B must do the same with (g^j).

It is not sufficient to authenticate the shared secret g^(j*k), since

this leaves the protocol open to attacks that manipulate the public

keys. Instead, the values of the public keys g^x and g^y that are

exchanged should be directly authenticated. This is the strategy

used by protocols that build on Diffie-Hellman and that use end-

entity authentication to protect against active attacks, such as

OAKLEY [RFC2412] and the Internet Key Exchange [RFC2409] [RFC4306]

[RFC5996].

When the cofactor of a group is not equal to 1, there are a number of

attacks that are possible against ECDH. See [VW1996], [AV1996], and

[LL1997].

The elliptic curve group operation does not explicitly incorporate

the parameter b from the curve equation. This opens the possibility

that a malicious attacker could learn information about an ECDH

private key by submitting a bogus public key [BMM2000]. An attacker

can craft an elliptic curve group G' that has identical parameters to

a group G that is being used in an ECDH protocol, except that b is

different. An attacker can submit a point on G' into a run of the

ECDH protocol that is using group G, and gain information from the

fact that the group operations using the private key of the device

under attack are effectively taking place in G' instead of G.

This attack can gain useful information about an ECDH private key

that is associated with a static public key, i.e., a public key that

is used in more than one run of the protocol. However, it does not

gain any useful information against ephemeral keys.

This sort of attack is thwarted if an ECDH implementation does not

assume that each pair of coordinates in Zp is actually a point on the

appropriate elliptic curve.

These considerations also apply when ECDH is used with compact

representation (see Appendix C).

RFC 6090 Fundamental ECC February 2011

## 10.4. Signatures

Elliptic curve parameters should only be used if they come from a

trusted source; otherwise, some attacks are possible [AV1996]

[V1996].

If no hash function is used in an ElGamal signature system, then the

system is vulnerable to existential forgeries, in which an attacker

who does not know a private key can generate valid signatures for the

associated public key, but cannot generate a signature for a message

of its own choosing. (See [E1985] for instance.) The use of a

collision-resistant hash function eliminates this vulnerability.

In principle, any collision-resistant hash function is suitable for

use in KT signatures. To facilitate interoperability, we recognize

the following hashes as suitable for use as the function H defined in

Section 5.2:

SHA-256, which has a 256-bit output.

SHA-384, which has a 384-bit output.

SHA-512, which has a 512-bit output.

All of these hash functions are defined in [FIPS180-2].

The number of bits in the output of the hash used in KT signatures

should be equal or close to the number of bits needed to represent

the group order.

# 11. Acknowledgements

The author expresses his thanks to the originators of elliptic curve

cryptography, whose work made this note possible, and all of the

reviewers, who provided valuable constructive feedback. Thanks are

especially due to Howard Pinder, Andrey Jivsov, Alfred Hoenes (who

contributed the algorithms in Appendix F), Dan Harkins, and Tina

Tsou.

# 12. References

## 12.1. Normative References

[AMV1990] Agnew, G., Mullin, R., and S. Vanstone, "Improved

Digital Signature Scheme based on Discrete

Exponentiation", Electronics Letters Vol. 26, No. 14,

July, 1990.

Elliptic curve parameters should only be used if they come from a

trusted source; otherwise, some attacks are possible [AV1996]

[V1996].

If no hash function is used in an ElGamal signature system, then the

system is vulnerable to existential forgeries, in which an attacker

who does not know a private key can generate valid signatures for the

associated public key, but cannot generate a signature for a message

of its own choosing. (See [E1985] for instance.) The use of a

collision-resistant hash function eliminates this vulnerability.

In principle, any collision-resistant hash function is suitable for

use in KT signatures. To facilitate interoperability, we recognize

the following hashes as suitable for use as the function H defined in

Section 5.2:

SHA-256, which has a 256-bit output.

SHA-384, which has a 384-bit output.

SHA-512, which has a 512-bit output.

All of these hash functions are defined in [FIPS180-2].

The number of bits in the output of the hash used in KT signatures

should be equal or close to the number of bits needed to represent

the group order.

The author expresses his thanks to the originators of elliptic curve

cryptography, whose work made this note possible, and all of the

reviewers, who provided valuable constructive feedback. Thanks are

especially due to Howard Pinder, Andrey Jivsov, Alfred Hoenes (who

contributed the algorithms in Appendix F), Dan Harkins, and Tina

Tsou.

[AMV1990] Agnew, G., Mullin, R., and S. Vanstone, "Improved

Digital Signature Scheme based on Discrete

Exponentiation", Electronics Letters Vol. 26, No. 14,

July, 1990.

RFC 6090 Fundamental ECC February 2011

[BC1989] Bender, A. and G. Castagnoli, "On the Implementation of

Elliptic Curve Cryptosystems", Advances in Cryptology -

CRYPTO '89 Proceedings, Springer Lecture Notes in

Computer Science (LNCS), volume 435, 1989.

[CC1986] Chudnovsky, D. and G. Chudnovsky, "Sequences of numbers

generated by addition in formal groups and new primality

and factorization tests", Advances in Applied

Mathematics, Volume 7, Issue 4, December 1986.

[D1966] Deskins, W., "Abstract Algebra", MacMillan Company New

York, 1966.

[DH1976] Diffie, W. and M. Hellman, "New Directions in

Cryptography", IEEE Transactions in Information

Theory IT-22, pp. 644-654, 1976.

[FR1994] Frey, G. and H. Ruck, "A remark concerning

m-divisibility and the discrete logarithm in the divisor

class group of curves.", Mathematics of Computation Vol.

62, No. 206, pp. 865-874, 1994.

[HMP1994] Horster, P., Michels, M., and H. Petersen, "Meta-ElGamal

signature schemes", University of Technology Chemnitz-

Zwickau Department of Computer Science, Technical

Report TR-94-5, May 1994.

[K1981v2] Knuth, D., "The Art of Computer Programming, Vol. 2:

Seminumerical Algorithms", Addison Wesley , 1981.

[K1987] Koblitz, N., "Elliptic Curve Cryptosystems", Mathematics

of Computation, Vol. 48, 1987, pp. 203-209, 1987.

[KT1994] Koyama, K. and Y. Tsuruoka, "Digital signature system

based on elliptic curve and signer device and verifier

device for said system", Japanese Unexamined Patent

Application Publication H6-43809, February 18, 1994.

[M1983] Massey, J., "Logarithms in finite cyclic groups -

cryptographic issues", Proceedings of the 4th Symposium

on Information Theory, 1983.

[M1985] Miller, V., "Use of elliptic curves in cryptography",

Advances in Cryptology - CRYPTO '85

Proceedings, Springer Lecture Notes in Computer Science

(LNCS), volume 218, 1985.

[BC1989] Bender, A. and G. Castagnoli, "On the Implementation of

Elliptic Curve Cryptosystems", Advances in Cryptology -

CRYPTO '89 Proceedings, Springer Lecture Notes in

Computer Science (LNCS), volume 435, 1989.

[CC1986] Chudnovsky, D. and G. Chudnovsky, "Sequences of numbers

generated by addition in formal groups and new primality

and factorization tests", Advances in Applied

Mathematics, Volume 7, Issue 4, December 1986.

[D1966] Deskins, W., "Abstract Algebra", MacMillan Company New

York, 1966.

[DH1976] Diffie, W. and M. Hellman, "New Directions in

Cryptography", IEEE Transactions in Information

Theory IT-22, pp. 644-654, 1976.

[FR1994] Frey, G. and H. Ruck, "A remark concerning

m-divisibility and the discrete logarithm in the divisor

class group of curves.", Mathematics of Computation Vol.

62, No. 206, pp. 865-874, 1994.

[HMP1994] Horster, P., Michels, M., and H. Petersen, "Meta-ElGamal

signature schemes", University of Technology Chemnitz-

Zwickau Department of Computer Science, Technical

Report TR-94-5, May 1994.

[K1981v2] Knuth, D., "The Art of Computer Programming, Vol. 2:

Seminumerical Algorithms", Addison Wesley , 1981.

[K1987] Koblitz, N., "Elliptic Curve Cryptosystems", Mathematics

of Computation, Vol. 48, 1987, pp. 203-209, 1987.

[KT1994] Koyama, K. and Y. Tsuruoka, "Digital signature system

based on elliptic curve and signer device and verifier

device for said system", Japanese Unexamined Patent

Application Publication H6-43809, February 18, 1994.

[M1983] Massey, J., "Logarithms in finite cyclic groups -

cryptographic issues", Proceedings of the 4th Symposium

on Information Theory, 1983.

[M1985] Miller, V., "Use of elliptic curves in cryptography",

Advances in Cryptology - CRYPTO '85

Proceedings, Springer Lecture Notes in Computer Science

(LNCS), volume 218, 1985.

RFC 6090 Fundamental ECC February 2011

[MOV1993] Menezes, A., Vanstone, S., and T. Okamoto, "Reducing

Elliptic Curve Logarithms to Logarithms in a Finite

Field", IEEE Transactions on Information Theory Vol. 39,

No. 5, pp. 1639-1646, September, 1993.

[R1993] RSA Laboratories, "PKCS#1: RSA Encryption Standard",

Technical Note version 1.5, 1993.

[S1986] Silverman, J., "The Arithmetic of Elliptic Curves",

Springer-Verlag, New York, 1986.

## 12.2. Informative References

[A1992] Anderson, J., "Response to the proposed DSS",

Communications of the ACM, v. 35, n. 7, p. 50-52,

July 1992.

[AV1996] Anderson, R. and S. Vaudenay, "Minding Your P's and

Q's", Advances in Cryptology - ASIACRYPT '96

Proceedings, Springer Lecture Notes in Computer Science

(LNCS), volume 1163, 1996.

[BMM2000] Biehl, I., Meyer, B., and V. Muller, "Differential fault

analysis on elliptic curve cryptosystems", Advances in

Cryptology - CRYPTO 2000 Proceedings, Springer Lecture

Notes in Computer Science (LNCS), volume 1880, 2000.

[BS1992] Branstad, D. and M. Smid, "Response to Comments on the

NIST Proposed Digital Signature Standard", Advances in

Cryptology - CRYPTO '92 Proceedings, Springer Lecture

Notes in Computer Science (LNCS), volume 740,

August 1992.

[DSA1991] U.S. National Institute of Standards and Technology,

"DIGITAL SIGNATURE STANDARD", Federal Register, Vol. 56,

August 1991.

[E1984a] ElGamal, T., "Cryptography and logarithms over finite

fields", Stanford University, UMI Order No. DA 8420519,

1984.

[E1984b] ElGamal, T., "Cryptography and logarithms over finite

fields", Advances in Cryptology - CRYPTO '84

Proceedings, Springer Lecture Notes in Computer Science

(LNCS), volume 196, 1984.

[MOV1993] Menezes, A., Vanstone, S., and T. Okamoto, "Reducing

Elliptic Curve Logarithms to Logarithms in a Finite

Field", IEEE Transactions on Information Theory Vol. 39,

No. 5, pp. 1639-1646, September, 1993.

[R1993] RSA Laboratories, "PKCS#1: RSA Encryption Standard",

Technical Note version 1.5, 1993.

[S1986] Silverman, J., "The Arithmetic of Elliptic Curves",

Springer-Verlag, New York, 1986.

[A1992] Anderson, J., "Response to the proposed DSS",

Communications of the ACM, v. 35, n. 7, p. 50-52,

July 1992.

[AV1996] Anderson, R. and S. Vaudenay, "Minding Your P's and

Q's", Advances in Cryptology - ASIACRYPT '96

Proceedings, Springer Lecture Notes in Computer Science

(LNCS), volume 1163, 1996.

[BMM2000] Biehl, I., Meyer, B., and V. Muller, "Differential fault

analysis on elliptic curve cryptosystems", Advances in

Cryptology - CRYPTO 2000 Proceedings, Springer Lecture

Notes in Computer Science (LNCS), volume 1880, 2000.

[BS1992] Branstad, D. and M. Smid, "Response to Comments on the

NIST Proposed Digital Signature Standard", Advances in

Cryptology - CRYPTO '92 Proceedings, Springer Lecture

Notes in Computer Science (LNCS), volume 740,

August 1992.

[DSA1991] U.S. National Institute of Standards and Technology,

"DIGITAL SIGNATURE STANDARD", Federal Register, Vol. 56,

August 1991.

[E1984a] ElGamal, T., "Cryptography and logarithms over finite

fields", Stanford University, UMI Order No. DA 8420519,

1984.

[E1984b] ElGamal, T., "Cryptography and logarithms over finite

fields", Advances in Cryptology - CRYPTO '84

Proceedings, Springer Lecture Notes in Computer Science

(LNCS), volume 196, 1984.

RFC 6090 Fundamental ECC February 2011

[E1985] ElGamal, T., "A public key cryptosystem and a signature

scheme based on discrete logarithms", IEEE Transactions

on Information Theory, Vol. 30, No. 4, pp. 469-472,

1985.

[FIPS180-2] U.S. National Institute of Standards and Technology,

"SECURE HASH STANDARD", Federal Information Processing

Standard (FIPS) 180-2, August 2002.

[FIPS186] U.S. National Institute of Standards and Technology,

"DIGITAL SIGNATURE STANDARD", Federal Information

Processing Standard FIPS-186, May 1994.

[HP1994] Horster, P. and H. Petersen, "Verallgemeinerte ElGamal-

Signaturen", Proceedings der Fachtagung SIS '94, Verlag

der Fachvereine, Zurich, 1994.

[K1981v3] Knuth, D., "The Art of Computer Programming, Vol. 3:

Sorting and Searching", Addison Wesley, 1981.

[KMOV1991] Koyama, K., Maurer, U., Vanstone, S., and T. Okamoto,

"New Public-Key Schemes Based on Elliptic Curves over

the Ring Zn", Advances in Cryptology - CRYPTO '91

Proceedings, Springer Lecture Notes in Computer Science

(LNCS), volume 576, 1991.

[L1969] Lehmer, D., "Computer technology applied to the theory

of numbers", M.A.A. Studies in Mathematics, 180-2, 1969.

[LL1997] Lim, C. and P. Lee, "A Key Recovery Attack on Discrete

Log-based Schemes Using a Prime Order Subgroup",

Advances in Cryptology - CRYPTO '97

Proceedings, Springer Lecture Notes in Computer Science

(LNCS), volume 1294, 1997.

[NR1994] Nyberg, K. and R. Rueppel, "Message Recovery for

Signature Schemes Based on the Discrete Logarithm

Problem", Advances in Cryptology - EUROCRYPT '94

Proceedings, Springer Lecture Notes in Computer Science

(LNCS), volume 950, May 1994.

[P1363] "Standard Specifications for Public Key Cryptography",

Institute of Electric and Electronic Engineers

(IEEE), P1363, 2000.

[P1978] Pollard, J., "Monte Carlo methods for index computation

mod p", Mathematics of Computation, Vol. 32, 1978.

[E1985] ElGamal, T., "A public key cryptosystem and a signature

scheme based on discrete logarithms", IEEE Transactions

on Information Theory, Vol. 30, No. 4, pp. 469-472,

1985.

[FIPS180-2] U.S. National Institute of Standards and Technology,

"SECURE HASH STANDARD", Federal Information Processing

Standard (FIPS) 180-2, August 2002.

[FIPS186] U.S. National Institute of Standards and Technology,

"DIGITAL SIGNATURE STANDARD", Federal Information

Processing Standard FIPS-186, May 1994.

[HP1994] Horster, P. and H. Petersen, "Verallgemeinerte ElGamal-

Signaturen", Proceedings der Fachtagung SIS '94, Verlag

der Fachvereine, Zurich, 1994.

[K1981v3] Knuth, D., "The Art of Computer Programming, Vol. 3:

Sorting and Searching", Addison Wesley, 1981.

[KMOV1991] Koyama, K., Maurer, U., Vanstone, S., and T. Okamoto,

"New Public-Key Schemes Based on Elliptic Curves over

the Ring Zn", Advances in Cryptology - CRYPTO '91

Proceedings, Springer Lecture Notes in Computer Science

(LNCS), volume 576, 1991.

[L1969] Lehmer, D., "Computer technology applied to the theory

of numbers", M.A.A. Studies in Mathematics, 180-2, 1969.

[LL1997] Lim, C. and P. Lee, "A Key Recovery Attack on Discrete

Log-based Schemes Using a Prime Order Subgroup",

Advances in Cryptology - CRYPTO '97

Proceedings, Springer Lecture Notes in Computer Science

(LNCS), volume 1294, 1997.

[NR1994] Nyberg, K. and R. Rueppel, "Message Recovery for

Signature Schemes Based on the Discrete Logarithm

Problem", Advances in Cryptology - EUROCRYPT '94

Proceedings, Springer Lecture Notes in Computer Science

(LNCS), volume 950, May 1994.

[P1363] "Standard Specifications for Public Key Cryptography",

Institute of Electric and Electronic Engineers

(IEEE), P1363, 2000.

[P1978] Pollard, J., "Monte Carlo methods for index computation

mod p", Mathematics of Computation, Vol. 32, 1978.

RFC 6090 Fundamental ECC February 2011

[PH1978] Pohlig, S. and M. Hellman, "An Improved Algorithm for

Computing Logarithms over GF(p) and its Cryptographic

Significance", IEEE Transactions on Information

Theory, Vol. 24, pp. 106-110, 1978.

[R1988] Rose, H., "A Course in Number Theory", Oxford

University Press, 1988.

[R1992] Rivest, R., "Response to the proposed DSS",

Communications of the ACM, v. 35, n. 7, p. 41-47,

July 1992.

[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate

Requirement Levels", BCP 14, RFC 2119, March 1997.

[RFC2409] Harkins, D. and D. Carrel, "The Internet Key Exchange

(IKE)", RFC 2409, November 1998.

[RFC2412] Orman, H., "The OAKLEY Key Determination Protocol",

RFC 2412, November 1998.

[RFC3979] Bradner, S., "Intellectual Property Rights in IETF

Technology", BCP 79, RFC 3979, March 2005.

[RFC4086] Eastlake, D., Schiller, J., and S. Crocker, "Randomness

Requirements for Security", BCP 106, RFC 4086,

June 2005.

[RFC4306] Kaufman, C., "Internet Key Exchange (IKEv2) Protocol",

RFC 4306, December 2005.

[RFC4753] Fu, D. and J. Solinas, "ECP Groups For IKE and IKEv2",

RFC 4753, January 2007.

[RFC4754] Fu, D. and J. Solinas, "IKE and IKEv2 Authentication

Using the Elliptic Curve Digital Signature Algorithm

(ECDSA)", RFC 4754, January 2007.

[RFC4879] Narten, T., "Clarification of the Third Party Disclosure

Procedure in RFC 3979", BCP 79, RFC 4879, April 2007.

[RFC5114] Lepinski, M. and S. Kent, "Additional Diffie-Hellman

Groups for Use with IETF Standards", RFC 5114,

January 2008.

[RFC5903] Fu, D. and J. Solinas, "Elliptic Curve Groups modulo a

Prime (ECP Groups) for IKE and IKEv2", RFC 5903,

June 2010.

[PH1978] Pohlig, S. and M. Hellman, "An Improved Algorithm for

Computing Logarithms over GF(p) and its Cryptographic

Significance", IEEE Transactions on Information

Theory, Vol. 24, pp. 106-110, 1978.

[R1988] Rose, H., "A Course in Number Theory", Oxford

University Press, 1988.

[R1992] Rivest, R., "Response to the proposed DSS",

Communications of the ACM, v. 35, n. 7, p. 41-47,

July 1992.

[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate

Requirement Levels", BCP 14, RFC 2119, March 1997.

[RFC2409] Harkins, D. and D. Carrel, "The Internet Key Exchange

(IKE)", RFC 2409, November 1998.

[RFC2412] Orman, H., "The OAKLEY Key Determination Protocol",

RFC 2412, November 1998.

[RFC3979] Bradner, S., "Intellectual Property Rights in IETF

Technology", BCP 79, RFC 3979, March 2005.

[RFC4086] Eastlake, D., Schiller, J., and S. Crocker, "Randomness

Requirements for Security", BCP 106, RFC 4086,

June 2005.

[RFC4306] Kaufman, C., "Internet Key Exchange (IKEv2) Protocol",

RFC 4306, December 2005.

[RFC4753] Fu, D. and J. Solinas, "ECP Groups For IKE and IKEv2",

RFC 4753, January 2007.

[RFC4754] Fu, D. and J. Solinas, "IKE and IKEv2 Authentication

Using the Elliptic Curve Digital Signature Algorithm

(ECDSA)", RFC 4754, January 2007.

[RFC4879] Narten, T., "Clarification of the Third Party Disclosure

Procedure in RFC 3979", BCP 79, RFC 4879, April 2007.

[RFC5114] Lepinski, M. and S. Kent, "Additional Diffie-Hellman

Groups for Use with IETF Standards", RFC 5114,

January 2008.

[RFC5903] Fu, D. and J. Solinas, "Elliptic Curve Groups modulo a

Prime (ECP Groups) for IKE and IKEv2", RFC 5903,

June 2010.

RFC 6090 Fundamental ECC February 2011

[RFC5996] Kaufman, C., Hoffman, P., Nir, Y., and P. Eronen,

"Internet Key Exchange Protocol Version 2 (IKEv2)",

RFC 5996, September 2010.

[SuiteB] U. S. National Security Agency (NSA), "NSA Suite B

Cryptography", <http://www.nsa.gov/ia/programs/

suiteb_cryptography/index.shtml>.

[V1996] Vaudenay, S., "Hidden Collisions on DSS", Advances in

Cryptology - CRYPTO '96 Proceedings, Springer Lecture

Notes in Computer Science (LNCS), volume 1109, 1996.

[VW1994] van Oorschot, P. and M. Wiener, "Parallel Collision

Search with Application to Hash Functions and Discrete

Logarithms", Proceedings of the 2nd ACM Conference on

Computer and communications security, pp. 210-218, 1994.

[VW1996] van Oorschot, P. and M. Wiener, "On Diffie-Hellman key

agreement with short exponents", Advances in Cryptology

- EUROCRYPT '96 Proceedings, Springer Lecture Notes in

Computer Science (LNCS), volume 1070, 1996.

[X9.62] "Public Key Cryptography for the Financial Services

Industry: The Elliptic Curve Digital Signature Algorithm

(ECDSA)", American National Standards Institute (ANSI)

X9.62.

[RFC5996] Kaufman, C., Hoffman, P., Nir, Y., and P. Eronen,

"Internet Key Exchange Protocol Version 2 (IKEv2)",

RFC 5996, September 2010.

[SuiteB] U. S. National Security Agency (NSA), "NSA Suite B

Cryptography", <http://www.nsa.gov/ia/programs/

suiteb_cryptography/index.shtml>.

[V1996] Vaudenay, S., "Hidden Collisions on DSS", Advances in

Cryptology - CRYPTO '96 Proceedings, Springer Lecture

Notes in Computer Science (LNCS), volume 1109, 1996.

[VW1994] van Oorschot, P. and M. Wiener, "Parallel Collision

Search with Application to Hash Functions and Discrete

Logarithms", Proceedings of the 2nd ACM Conference on

Computer and communications security, pp. 210-218, 1994.

[VW1996] van Oorschot, P. and M. Wiener, "On Diffie-Hellman key

agreement with short exponents", Advances in Cryptology

- EUROCRYPT '96 Proceedings, Springer Lecture Notes in

Computer Science (LNCS), volume 1070, 1996.

[X9.62] "Public Key Cryptography for the Financial Services

Industry: The Elliptic Curve Digital Signature Algorithm

(ECDSA)", American National Standards Institute (ANSI)

X9.62.

RFC 6090 Fundamental ECC February 2011

# Appendix A. Key Words

The definitions of these key words are quoted from [RFC2119] and are

commonly used in Internet standards. They are reproduced in this

note in order to avoid a normative reference from after 1994.

1. MUST - This word, or the terms "REQUIRED" or "SHALL", means that

the definition is an absolute requirement of the specification.

2. MUST NOT - This phrase, or the phrase "SHALL NOT", means that the

definition is an absolute prohibition of the specification.

3. SHOULD - This word, or the adjective "RECOMMENDED", means that

there may exist valid reasons in particular circumstances to

ignore a particular item, but the full implications must be

understood and carefully weighed before choosing a different

course.

4. SHOULD NOT - This phrase, or the phrase "NOT RECOMMENDED", means

that there may exist valid reasons in particular circumstances

when the particular behavior is acceptable or even useful, but

the full implications should be understood and the case carefully

weighed before implementing any behavior described with this

label.

5. MAY - This word, or the adjective "OPTIONAL", means that an item

is truly optional. One vendor may choose to include the item

because a particular marketplace requires it or because the

vendor feels that it enhances the product while another vendor

may omit the same item. An implementation which does not include

a particular option MUST be prepared to interoperate with another

implementation which does include the option, though perhaps with

reduced functionality. In the same vein an implementation which

does include a particular option MUST be prepared to interoperate

with another implementation which does not include the option

(except, of course, for the feature the option provides.)

# Appendix B. Random Integer Generation

It is easy to generate an integer uniformly at random between zero

and (2^t)-1, inclusive, for some positive integer t. Generate a

random bit string that contains exactly t bits, and then convert the

bit string to a non-negative integer by treating the bits as the

coefficients in a base-2 expansion of an integer.

The definitions of these key words are quoted from [RFC2119] and are

commonly used in Internet standards. They are reproduced in this

note in order to avoid a normative reference from after 1994.

1. MUST - This word, or the terms "REQUIRED" or "SHALL", means that

the definition is an absolute requirement of the specification.

2. MUST NOT - This phrase, or the phrase "SHALL NOT", means that the

definition is an absolute prohibition of the specification.

3. SHOULD - This word, or the adjective "RECOMMENDED", means that

there may exist valid reasons in particular circumstances to

ignore a particular item, but the full implications must be

understood and carefully weighed before choosing a different

course.

4. SHOULD NOT - This phrase, or the phrase "NOT RECOMMENDED", means

that there may exist valid reasons in particular circumstances

when the particular behavior is acceptable or even useful, but

the full implications should be understood and the case carefully

weighed before implementing any behavior described with this

label.

5. MAY - This word, or the adjective "OPTIONAL", means that an item

is truly optional. One vendor may choose to include the item

because a particular marketplace requires it or because the

vendor feels that it enhances the product while another vendor

may omit the same item. An implementation which does not include

a particular option MUST be prepared to interoperate with another

implementation which does include the option, though perhaps with

reduced functionality. In the same vein an implementation which

does include a particular option MUST be prepared to interoperate

with another implementation which does not include the option

(except, of course, for the feature the option provides.)

It is easy to generate an integer uniformly at random between zero

and (2^t)-1, inclusive, for some positive integer t. Generate a

random bit string that contains exactly t bits, and then convert the

bit string to a non-negative integer by treating the bits as the

coefficients in a base-2 expansion of an integer.

RFC 6090 Fundamental ECC February 2011

It is sometimes necessary to generate an integer r uniformly at

random so that r satisfies a certain property P, for example, lying

within a certain interval. A simple way to do this is with the

rejection method:

1. Generate a candidate number c uniformly at random from a set that

includes all numbers that satisfy property P (plus some other

numbers, preferably not too many)

2. If c satisfies property P, then return c. Otherwise, return to

Step 1.

For example, to generate a number between 1 and n-1, inclusive,

repeatedly generate integers between zero and (2^t)-1, inclusive,

stopping at the first integer that falls within that interval.

Recommendations on how to generate random bit strings are provided in

[RFC4086].

# Appendix C. Why Compact Representation Works

In the affine representation, the x-coordinate of the point P^i does

not depend on the y-coordinate of the point P, for any non-negative

exponent i and any point P. This fact can be seen as follows. When

given only the x-coordinate of a point P, it is not possible to

determine exactly what the y-coordinate is, but the y value will be a

solution to the curve equation

y^2 = x^3 + a*x + b (mod p).

There are at most two distinct solutions y = w and y = -w mod p, and

the point P must be either Q=(x,w) or Q^-1=(x,-w). Thus P^n is equal

to either Q^n or (Q^-1)^n = (Q^n)^-1. These values have the same

x-coordinate. Thus, the x-coordinate of a point P^i can be computed

from the x-coordinate of a point P by computing one of the possible

values of the y coordinate of P, then computing the ith power of P,

and then ignoring the y-coordinate of that result.

In general, it is possible to compute a square root modulo p by using

Shanks' method [K1981v2]; simple methods exist for some values of p.

When p = 3 (mod 4), the square roots of z mod p are w and -w mod p,

where

w = z ^ ((p+1)/4) (mod p);

It is sometimes necessary to generate an integer r uniformly at

random so that r satisfies a certain property P, for example, lying

within a certain interval. A simple way to do this is with the

rejection method:

1. Generate a candidate number c uniformly at random from a set that

includes all numbers that satisfy property P (plus some other

numbers, preferably not too many)

2. If c satisfies property P, then return c. Otherwise, return to

Step 1.

For example, to generate a number between 1 and n-1, inclusive,

repeatedly generate integers between zero and (2^t)-1, inclusive,

stopping at the first integer that falls within that interval.

Recommendations on how to generate random bit strings are provided in

[RFC4086].

In the affine representation, the x-coordinate of the point P^i does

not depend on the y-coordinate of the point P, for any non-negative

exponent i and any point P. This fact can be seen as follows. When

given only the x-coordinate of a point P, it is not possible to

determine exactly what the y-coordinate is, but the y value will be a

solution to the curve equation

y^2 = x^3 + a*x + b (mod p).

There are at most two distinct solutions y = w and y = -w mod p, and

the point P must be either Q=(x,w) or Q^-1=(x,-w). Thus P^n is equal

to either Q^n or (Q^-1)^n = (Q^n)^-1. These values have the same

x-coordinate. Thus, the x-coordinate of a point P^i can be computed

from the x-coordinate of a point P by computing one of the possible

values of the y coordinate of P, then computing the ith power of P,

and then ignoring the y-coordinate of that result.

In general, it is possible to compute a square root modulo p by using

Shanks' method [K1981v2]; simple methods exist for some values of p.

When p = 3 (mod 4), the square roots of z mod p are w and -w mod p,

where

w = z ^ ((p+1)/4) (mod p);

RFC 6090 Fundamental ECC February 2011

this observation is due to Lehmer [L1969]. When p satisfies this

property, y can be computed from the curve equation, and either y = w

or y = -w mod p, where

w = (x^3 + a*x + b)^((p+1)/4) (mod p).

Square roots modulo p only exist for a quadratic residue modulo p,

[R1988]; if z is not a quadratic residue, then there is no number w

such that w^2 = z (mod p). A simple way to verify that z is a

quadratic residue after computing w is to verify that

w * w = z (mod p). If this relation does not hold for the above

equation, then the value x is not a valid x-coordinate for a valid

elliptic curve point. This is an important consideration when ECDH

is used with compact output; see Section 10.3.

The primes used in the P-256, P-384, and P-521 curves described in

[RFC5903] all have the property that p = 3 (mod 4).

# Appendix D. Example ECC Parameter Set

For concreteness, we recall an elliptic curve defined by Solinas and

Fu in [RFC5903] and referred to as P-256, which is believed to

provide a 128-bit security level. We use the notation of

Section 3.3, and express the generator in the affine coordinate

representation g=(gx,gy), where the values gx and gy are in Fp.

p: FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF

a: - 3

b: 5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B

n: FFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551

gx: 6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296

gy: 4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5

Note that p can also be expressed as

p = 2^(256)-2^(224)+2^(192)+2^(96)-1.

this observation is due to Lehmer [L1969]. When p satisfies this

property, y can be computed from the curve equation, and either y = w

or y = -w mod p, where

w = (x^3 + a*x + b)^((p+1)/4) (mod p).

Square roots modulo p only exist for a quadratic residue modulo p,

[R1988]; if z is not a quadratic residue, then there is no number w

such that w^2 = z (mod p). A simple way to verify that z is a

quadratic residue after computing w is to verify that

w * w = z (mod p). If this relation does not hold for the above

equation, then the value x is not a valid x-coordinate for a valid

elliptic curve point. This is an important consideration when ECDH

is used with compact output; see Section 10.3.

The primes used in the P-256, P-384, and P-521 curves described in

[RFC5903] all have the property that p = 3 (mod 4).

For concreteness, we recall an elliptic curve defined by Solinas and

Fu in [RFC5903] and referred to as P-256, which is believed to

provide a 128-bit security level. We use the notation of

Section 3.3, and express the generator in the affine coordinate

representation g=(gx,gy), where the values gx and gy are in Fp.

p: FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF

a: - 3

b: 5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B

n: FFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551

gx: 6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296

gy: 4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5

Note that p can also be expressed as

p = 2^(256)-2^(224)+2^(192)+2^(96)-1.

RFC 6090 Fundamental ECC February 2011

# Appendix E. Additive and Multiplicative Notation

The early publications on elliptic curve cryptography used

multiplicative notation, but most modern publications use additive

notation. This section includes a table mapping between those two

conventions. In this section, a and b are elements of an elliptic

curve group, and N is an integer.

+-------------------------+-----------------------+

| Multiplicative Notation | Additive Notation |

+-------------------------+-----------------------+

| multiplication | addition |

| a * b | a + b |

| squaring | doubling |

| a * a = a^2 | a + a = 2a |

| exponentiation | scalar multiplication |

| a^N = a * a * ... * a | Na = a + a + ... + a |

| inverse | inverse |

| a^-1 | -a |

+-------------------------+-----------------------+

# Appendix F. Algorithms

This section contains a pseudocode description of the elliptic curve

group operation. Text that follows the symbol "//" is to be

interpreted as comments rather than instructions.

## F.1. Affine Coordinates

To an arbitrary pair of elliptic curve points P and Q specified by

their affine coordinates P=(x1,y1) and Q=(x2,y2), the group operation

assigns a third point R = P*Q with the coordinates (x3,y3). These

coordinates are computed as follows:

if P is (@,@),

R = Q

else if Q is (@,@),

R = P

else if P is not equal to Q and x1 is equal to x2,

R = (@,@)

else if P is not equal to Q and x1 is not equal to x2,

x3 = ((y2-y1)/(x2-x1))^2 - x1 - x2 mod p and

y3 = (x1-x3)*(y2-y1)/(x2-x1) - y1 mod p

else if P is equal to Q and y1 is equal to 0,

R = (@,@)

else // P is equal to Q and y1 is not equal to 0

x3 = ((3*x1^2 + a)/(2*y1))^2 - 2*x1 mod p and

y3 = (x1-x3)*(3*x1^2 + a)/(2*y1) - y mod p.

The early publications on elliptic curve cryptography used

multiplicative notation, but most modern publications use additive

notation. This section includes a table mapping between those two

conventions. In this section, a and b are elements of an elliptic

curve group, and N is an integer.

+-------------------------+-----------------------+

| Multiplicative Notation | Additive Notation |

+-------------------------+-----------------------+

| multiplication | addition |

| a * b | a + b |

| squaring | doubling |

| a * a = a^2 | a + a = 2a |

| exponentiation | scalar multiplication |

| a^N = a * a * ... * a | Na = a + a + ... + a |

| inverse | inverse |

| a^-1 | -a |

+-------------------------+-----------------------+

This section contains a pseudocode description of the elliptic curve

group operation. Text that follows the symbol "//" is to be

interpreted as comments rather than instructions.

To an arbitrary pair of elliptic curve points P and Q specified by

their affine coordinates P=(x1,y1) and Q=(x2,y2), the group operation

assigns a third point R = P*Q with the coordinates (x3,y3). These

coordinates are computed as follows:

if P is (@,@),

R = Q

else if Q is (@,@),

R = P

else if P is not equal to Q and x1 is equal to x2,

R = (@,@)

else if P is not equal to Q and x1 is not equal to x2,

x3 = ((y2-y1)/(x2-x1))^2 - x1 - x2 mod p and

y3 = (x1-x3)*(y2-y1)/(x2-x1) - y1 mod p

else if P is equal to Q and y1 is equal to 0,

R = (@,@)

else // P is equal to Q and y1 is not equal to 0

x3 = ((3*x1^2 + a)/(2*y1))^2 - 2*x1 mod p and

y3 = (x1-x3)*(3*x1^2 + a)/(2*y1) - y mod p.

RFC 6090 Fundamental ECC February 2011

From the first and second case, it follows that the point at infinity

is the neutral element of this operation, which is its own inverse.

From the curve equation, it follows that for a given curve point P =

(x,y) distinct from the point at infinity, (x,-y) also is a curve

point, and from the third and the fifth case it follows that this is

the inverse of P, P^-1.

Note: The fifth and sixth case are known as "point squaring".

## F.2. Homogeneous Coordinates

An elliptic curve point (x,y) (other than the point at infinity

(@,@)) is equivalent to a point (X,Y,Z) in homogeneous coordinates

(with X, Y, and Z in Fp and not all three being zero at once)

whenever x=X/Z and y=Y/Z. "Homogenous coordinates" means that two

triples (X,Y,Z) and (X',Y',Z') are regarded as "equal" (i.e.,

representing the same point) if there is some nonzero s in Fp such

that X'=s*X, Y'=s*Y, and Z'=s*Z. The point at infinity (@,@) is

regarded as equivalent to the homogenous coordinates (0,1,0), i.e.,

it can be represented by any triple (0,Y,0) with nonzero Y in Fp.

Let P1=(X1,Y1,Z1) and P2=(X2,Y2,Z2) be points on the elliptic curve,

and let u = Y2 * Z1 - Y1 * Z2 and v = X2 * Z1 - X1 * Z2.

We observe that the points P1 and P2 are equal if and only if u and v

are both equal to zero. Otherwise, if either P1 or P2 are equal to

the point at infinity, v is zero and u is nonzero (but the converse

implication does not hold).

Then, the product P3=(X3,Y3,Z3) = P1 * P2 is given by:

if P1 is the point at infinity,

P3 = P2

else if P2 is the point at infinity,

P3 = P1

else if u is not equal to 0 but v is equal to 0,

P3 = (0,1,0)

else if both u and v are not equal to 0,

X3 = v * (Z2 * (Z1 * u^2 - 2 * X1 * v^2) - v^3)

Y3 = Z2 * (3 * X1 * u * v^2 - Y1 * v^3 - Z1 * u^3) + u * v^3

Z3 = v^3 * Z1 * Z2

else // P2 equals P1, P3 = P1 * P1

w = 3 * X1^2 + a * Z1^2

X3 = 2 * Y1 * Z1 * (w^2 - 8 * X1 * Y1^2 * Z1)

Y3 = 4 * Y1^2 * Z1 * (3 * w * X1 - 2 * Y1^2 * Z1) - w^3

Z3 = 8 * (Y1 * Z1)^3

From the first and second case, it follows that the point at infinity

is the neutral element of this operation, which is its own inverse.

From the curve equation, it follows that for a given curve point P =

(x,y) distinct from the point at infinity, (x,-y) also is a curve

point, and from the third and the fifth case it follows that this is

the inverse of P, P^-1.

Note: The fifth and sixth case are known as "point squaring".

An elliptic curve point (x,y) (other than the point at infinity

(@,@)) is equivalent to a point (X,Y,Z) in homogeneous coordinates

(with X, Y, and Z in Fp and not all three being zero at once)

whenever x=X/Z and y=Y/Z. "Homogenous coordinates" means that two

triples (X,Y,Z) and (X',Y',Z') are regarded as "equal" (i.e.,

representing the same point) if there is some nonzero s in Fp such

that X'=s*X, Y'=s*Y, and Z'=s*Z. The point at infinity (@,@) is

regarded as equivalent to the homogenous coordinates (0,1,0), i.e.,

it can be represented by any triple (0,Y,0) with nonzero Y in Fp.

Let P1=(X1,Y1,Z1) and P2=(X2,Y2,Z2) be points on the elliptic curve,

and let u = Y2 * Z1 - Y1 * Z2 and v = X2 * Z1 - X1 * Z2.

We observe that the points P1 and P2 are equal if and only if u and v

are both equal to zero. Otherwise, if either P1 or P2 are equal to

the point at infinity, v is zero and u is nonzero (but the converse

implication does not hold).

Then, the product P3=(X3,Y3,Z3) = P1 * P2 is given by:

if P1 is the point at infinity,

P3 = P2

else if P2 is the point at infinity,

P3 = P1

else if u is not equal to 0 but v is equal to 0,

P3 = (0,1,0)

else if both u and v are not equal to 0,

X3 = v * (Z2 * (Z1 * u^2 - 2 * X1 * v^2) - v^3)

Y3 = Z2 * (3 * X1 * u * v^2 - Y1 * v^3 - Z1 * u^3) + u * v^3

Z3 = v^3 * Z1 * Z2

else // P2 equals P1, P3 = P1 * P1

w = 3 * X1^2 + a * Z1^2

X3 = 2 * Y1 * Z1 * (w^2 - 8 * X1 * Y1^2 * Z1)

Y3 = 4 * Y1^2 * Z1 * (3 * w * X1 - 2 * Y1^2 * Z1) - w^3

Z3 = 8 * (Y1 * Z1)^3

RFC 6090 Fundamental ECC February 2011

It thus turns out that the point at infinity is the identity element

and for P1=(X,Y,Z) not equal to this point at infinity, P2=(X,-Y,Z)

represents P1^-1.

# Authors' Addresses

David A. McGrew

Cisco Systems

510 McCarthy Blvd.

Milpitas, CA 95035

USA

Phone: (408) 525 8651

EMail: mcgrew@cisco.com

URI: http://www.mindspring.com/~dmcgrew/dam.htm

Kevin M. Igoe

National Security Agency

Commercial Solutions Center

United States of America

EMail: kmigoe@nsa.gov

Margaret Salter

National Security Agency

9800 Savage Rd.

Fort Meade, MD 20755-6709

USA

EMail: msalter@restarea.ncsc.mil

It thus turns out that the point at infinity is the identity element

and for P1=(X,Y,Z) not equal to this point at infinity, P2=(X,-Y,Z)

represents P1^-1.

David A. McGrew

Cisco Systems

510 McCarthy Blvd.

Milpitas, CA 95035

USA

Phone: (408) 525 8651

EMail: mcgrew@cisco.com

URI: http://www.mindspring.com/~dmcgrew/dam.htm

Kevin M. Igoe

National Security Agency

Commercial Solutions Center

United States of America

EMail: kmigoe@nsa.gov

Margaret Salter

National Security Agency

9800 Savage Rd.

Fort Meade, MD 20755-6709

USA

EMail: msalter@restarea.ncsc.mil