S TANDARDS FOR E FFICIENT C RYPTOGRAPHY

SEC 1: Elliptic Curve Cryptography

Certicom ResearchContact: secg-talk@lists.certicom.com
September 20, 2000
Version 1.0

c 2000 Certicom Corp.
License to copy this document is granted provided
it is identified as “Standards for Efficient Cryptography (SEC)”,
in all material mentioning or referencing it.

SEC 1 - Contents

Page iContents
1

2

Introduction

1

1.1

Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

1.2

Aim . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

1.3

Compliance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

1.4

Document Evolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2

1.5Intellectual Property . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2

1.6

Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2Mathematical Foundations

3

2.1

Finite Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

2.1.1

The Finite Field F p . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

2.1.2

The Finite Field F 2m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4Elliptic Curves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

2.2.1

Elliptic Curves over F p . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

2.2.2

Elliptic Curves over F 2m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8

Data Types and Conversions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

2.3.1

BitString-to-OctetString Conversion . . . . . . . . . . . . . . . . . . . . . . . .

10

2.3.2

OctetString-to-BitString Conversion . . . . . . . . . . . . . . . . . . . . . . . .

10

2.3.3

EllipticCurvePoint-to-OctetString Conversion . . . . . . . . . . . . . . . . . . .

10

2.3.4

OctetString-to-EllipticCurvePoint Conversion . . . . . . . . . . . . . . . . . . .

11

2.3.5

FieldElement-to-OctetString Conversion . . . . . . . . . . . . . . . . . . . . .

12

2.3.6

OctetString-to-FieldElement Conversion . . . . . . . . . . . . . . . . . . . . .

13

2.3.7

Integer-to-OctetString Conversion . . . . . . . . . . . . . . . . . . . . . . . . .

14

2.3.8

OctetString-to-Integer Conversion . . . . . . . . . . . . . . . . . . . . . . . . .

14

2.3.9

FieldElement-to-Integer Conversion . . . . . . . . . . . . . . . . . . . . . . . .

14

2.2

2.3

3

Cryptographic Components

16

3.1

Elliptic Curve Domain Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

16

3.1.1

Elliptic Curve Domain Parameters over F p . . . . . . . . . . . . . . . . . . . .

16

3.1.2

Elliptic Curve Domain Parameters over F 2m . . . . . . . . . . . . . . . . . . . .

19

Page ii

3.2

Elliptic Curve Key Pairs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

22

3.2.1

Elliptic Curve Key Pair Generation Primitive . . . . . . . . . . . . . . . . . . .

22

3.2.2

Validation of Elliptic Curve Public Keys . . . . . . . . . . . . . . . . . . . . . .

22

3.2.3

Partial Validation of Elliptic Curve Public Keys . . . . . . . . . . . . . . . . . .

24

Elliptic Curve Diffie-Hellman Primitives . . . . . . . . . . . . . . . . . . . . . . . . . .

25

3.3.1

Elliptic Curve Diffie-Hellman Primitive . . . . . . . . . . . . . . . . . . . . . .

25

3.3.2

Elliptic Curve Cofactor Diffie-Hellman Primitive . . . . . . . . . . . . . . . . .

26

3.4

Elliptic Curve MQV Primitive . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

26

3.5

Hash Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

28

3.6

Key Derivation Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

29

3.6.1

ANSI X9.63 Key Derivation Function . . . . . . . . . . . . . . . . . . . . . . .

29

MAC schemes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

30

3.7.1

Scheme Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

31

3.7.2

Key Deployment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

31

3.7.3

Tagging Operation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

31

3.7.4

Tag Checking Operation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

32

Symmetric Encryption Schemes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

32

3.8.1

Scheme Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

34

3.8.2

Key Deployment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

34

3.8.3

Encryption Operation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

34

3.8.4

Decryption Operation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

34

3.3

3.7

3.8

4

5

SEC 1: Elliptic Curve Cryptography Ver. 1.0

Signature Schemes

36

4.1

Elliptic Curve Digital Signature Algorithm . . . . . . . . . . . . . . . . . . . . . . . . .

36

4.1.1

Scheme Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

36

4.1.2

Key Deployment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

37

4.1.3

Signing Operation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

37

4.1.4

Verifying Operation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

38

Encryption Schemes

40

5.1

Elliptic Curve Integrated Encryption Scheme . . . . . . . . . . . . . . . . . . . . . . .

40

5.1.1

41

Scheme Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

SEC 1 - Contents

6

Page iii

5.1.2

Key Deployment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

41

5.1.3

Encryption Operation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

42

5.1.4

Decryption Operation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

43

Key Agreement Schemes

45

6.1

Elliptic Curve Diffie-Hellman Scheme . . . . . . . . . . . . . . . . . . . . . . . . . . .

45

6.1.1

Scheme Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

46

6.1.2

Key Deployment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

46

6.1.3

Key Agreement Operation . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

47

Elliptic Curve MQV Scheme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

47

6.2.1

Scheme Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

48

6.2.2

Key Deployment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

48

6.2.3

Key Agreement Operation . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

49

6.2

A Glossary

50

A.1 Terms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

50

A.2 Acronyms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

55

A.3 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

56

B Commentary59

B.1 Commentary on Section 2 - Mathematical Foundations . . . . . . . . . . . . . . . . . .

59

B.2 Commentary on Section 3 - Cryptographic Components . . . . . . . . . . . . . . . . . .

61

B.2.1

Commentary on Elliptic Curve Domain Parameters . . . . . . . . . . . . . . . .

61

B.2.2

Commentary on Elliptic Curve Key Pairs . . . . . . . . . . . . . . . . . . . . .

63

B.2.3

Commentary on Elliptic Curve Diffie-Hellman Primitives . . . . . . . . . . . .

63

B.2.4

Commentary on the Elliptic Curve MQV Primitive . . . . . . . . . . . . . . . .

64

B.3 Commentary on Section 4 - Signature Schemes . . . . . . . . . . . . . . . . . . . . . .

65

B.3.1

Commentary on the Elliptic Curve Digital Signature Algorithm . . . . . . . . .

65

B.4 Commentary on Section 5 - Encryption Schemes . . . . . . . . . . . . . . . . . . . . .

66

B.4.1

Commentary on the Elliptic Curve Integrated Encryption Scheme . . . . . . . .

67

B.5 Commentary on Section 6 - Key Agreement Schemes . . . . . . . . . . . . . . . . . . .

69

B.5.1

Commentary on the Elliptic Curve Diffie-Hellman Scheme . . . . . . . . . . . .

69

Page iv

SEC 1: Elliptic Curve Cryptography Ver. 1.0

B.5.2

Commentary on the Elliptic Curve MQV Scheme . . . . . . . . . . . . . . . . .

71

B.6 Alignment with Other Standards . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

72

C ASN.1 for Elliptic Curve Cryptography75

C.1 Syntax for Finite Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

75

C.2 Syntax for Elliptic Curve Domain Parameters . . . . . . . . . . . . . . . . . . . . . . .

77

C.3 Syntax for Elliptic Curve Public Keys . . . . . . . . . . . . . . . . . . . . . . . . . . .

80

C.4 Syntax for Elliptic Curve Private Keys . . . . . . . . . . . . . . . . . . . . . . . . . . .

81

C.5 Syntax for Signatures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

82

C.6 Syntax for Key Derivation Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . .

83

C.7 ASN.1 Module . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

84

D References

85

SEC 1 - List of Figures

Page v

List of Tables
1

Representations of F 2m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

52Computing power required to solve ECDLP . . . . . . . . . . . . . . . . . . . . . . . .

60

3Comparable key sizes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

62

4

Alignment with other core ECC standards . . . . . . . . . . . . . . . . . . . . . . . . .

73

List of Figures
1

Converting between Data Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

SEC 1 - 1 Introduction

1

Page 1Introduction

1.1 Overview
This document specifies public-key cryptographic schemes based on elliptic curve cryptography (ECC).
In particular, it specifies:

 signature schemes;
 encryption schemes; and key agreement schemes.
It also describes cryptographic primitives which are used to construct the schemes, and ASN.1 syntax for
identifying the schemes.
The schemes are intended for general application within computer and communications systems.

1.2 Aim
The aim of this document is threefold.
Firstly to facilitate deployment of ECC by completely specifying efficient, well-established, and wellunderstood public-key cryptographic schemes based on ECC.
Secondly to encourage deployment of interoperable implementations of ECC by profiling existing standards like ANSI X9.62 [3], IEEE P1363 [40], and WAP WTLS [87], and draft standards like ANSI
X9.63 [4] and IEEE P1363A [41], but restricting the options allowed in these standards to increase thelikelihood of interoperability and to ensure conformance with all standards possible.
Thirdly to help ensure ongoing detailed analysis of ECC by cryptographers by clearly, completely, andpublicly specifying baseline techniques.

1.3 Compliance
Implementations may claim compliance with the cryptographic schemes specified in this document provided the external interface (input and output) to the schemes is identical to the interface specified here.
Internal computations may be performed as specified here, or may be performed via an equivalent sequence of operations.
Note that this compliance definition implies that conformant implementations must perform all the cryptographic checks included in the scheme specifications in this document. This is important because thechecks are essential to the prevention of subtle attacks.
It is intended to make a validation system available so that implementors can check compliance with thisdocument - see the SECG website, www.secg.org, for further information.

Page 2

SEC 1: Elliptic Curve Cryptography Ver. 1.0

1.4 Document Evolution
This document will be reviewed every five years to ensure it remains up to date with cryptographic
advances. The next scheduled review will therefore take place in September 2005.
Additional intermittent reviews may also be performed from time-to-time as deemed necessary by theStandards for Efficient Cryptography Group.

1.5 Intellectual Property
The reader’s attention is called to the possibility that compliance with this document may require use of
an invention covered by patent rights. By publication of this document, no position is taken with respect
to the validity of this claim or of any patent rights in connection therewith. The patent holder(s) may
have filed with the SECG a statement of willingness to grant a license under these rights on reasonable
and nondiscriminatory terms and conditions to applicants desiring to obtain such a license. Additional
details may be obtained from the patent holder and from the SECG website, www.secg.org.

1.6 Organization
This document is organized as follows.
The main body of the document focuses on the specification of public-key cryptographic schemes basedon ECC. Section 2 describes the mathematical foundations fundamental to the operation of all theschemes. Section 3 provides the cryptographic components used to build the schemes. Sections 4, 5,
and 6 respectively specify signature schemes, encryption schemes, and key agreement schemes based on
ECC.
The appendices to the document provide additional relevant material. Appendix A gives a glossary of
the acronyms and notation used as well as an explanation of the terms used. Appendix B elaborates
some of the details of the main body — discussing implementation guidelines, making security remarks,
and attributing references. Appendix C provides reference ASN.1 syntax for implementations to use to
identify the schemes, and Appendix D lists the references cited in the document.

SEC 1 - 2 Mathematical Foundations

2

Page 3Mathematical Foundations

Use of each of the public-key cryptographic schemes described in this document involves arithmetic
operations on an elliptic curve over a finite field. This section introduces the mathematical concepts
necessary to understand and implement these arithmetic operations.
Section 2.1 discusses finite fields, Section 2.2 discusses elliptic curves over finite fields, and Section 2.3
describes the data types involved and the conventions used to convert between data types.
See Appendix B for a commentary on the contents on this section, including implementation discussion,
security discussion, and references.

2.1 Finite Fields
Abstractly a finite field consists of a finite set of objects called field elements together with the descriptionof two operations - addition and multiplication - that can be performed on pairs of field elements. These
operations must possess certain properties.
It turns out that there is a finite field containing q field elements if and only if q is a power of a prime
number, and furthermore that in fact for each such q there is precisely one finite field. The finite fieldcontaining q elements is denoted by F q .
Here only two types of finite fields F q are used — finite fields F p with q = p, p an odd prime which arecalled prime finite fields, and finite fields F 2m with q = 2m for some m  1 which are called characteristic
2 finite fields.
It is necessary to describe these fields concretely in order to precisely specify cryptographic schemes
based on ECC. Section 2.1.1 describes prime finite fields and Section 2.1.2 describes characteristic 2
finite fields.
2.1.1 The Finite Field F p
The finite field F p is the prime finite field containing p elements. Although there is only one prime finite
field F p for each odd prime p, there are many different ways to represent the elements of F p .
Here the elements of F p should be represented by the set of integers:

f0 1
;

;:::;

p

1g

with addition and multiplication defined as follows: Addition: If a b 2 F p, then a + b = r in F p, where r 2 [0 p 1] is the remainder when the integera + b is divided by p. This is known as addition modulo p and written a + b  r (mod p).
 Multiplication: If a b 2 F p, then a b = s in F p, where s 2 [0 p 1] is the remainder when the integer
ab is divided by p. This is known as multiplication modulo p and written a b  s (mod p).
;

;

;

:

;

:

Page 4

SEC 1: Elliptic Curve Cryptography Ver. 1.0

Addition and multiplication in F p can be calculated efficiently using standard algorithms for ordinary
integer arithmetic. In this representation of F p , the additive identity or zero element is the integer 0, andthe multiplicative identity is the integer 1.
It is convenient to define subtraction and division of field elements just as it is convenient to define
subtraction and division of integers. To do so, the additive inverse (or negative) and multiplicative inverseof a field element must be described:

 Additive inverse: If a 2 F p, then the additive inverse ( a) of a in F p is the unique solution to theequation a + x  0 (mod p).
 Multiplicative inverse: If a 2 F p, a =6 0, then the multiplicative inverse a 1 of a in F p is the uniquesolution to the equation a x  1 (mod p).
:

Additive inverses and multiplicative inverses in F p can be calculated efficiently. Multiplicative inverses
are calculated using the extended Euclidean algorithm. Division and subtraction are defined in terms ofadditive and multiplicative inverses: a b mod p is a + ( b) mod p and a=b mod p is a:(b 1 ) mod p.
Here the prime finite fields F p used should have:dlog2 pe 2 f112 128 160 192 224 256 384 521g
;

;

;

;

;

;

;

:

This restriction is designed to facilitate interoperability, while enabling implementers to deploy implementations which are efficient in terms of computation and communication since p is aligned withword size, and which are capable of furnishing all commonly required security levels. Inclusion ofdlog2 pe = 521 instead of dlog2 pe = 512 is an anomaly chosen to align this document with other standards
efforts - in particular with the U.S. government’s recommended elliptic curve domain parameters [31].
See Appendix B for additional discussion on field selection.
2.1.2 The Finite Field F 2m
The finite field F 2m is the characteristic 2 finite field containing 2m elements. Although there is only
one characteristic 2 finite field F 2m for each power 2m of 2 with m  1, there are many different ways torepresent the elements of F 2m .
Here the elements of F 2m should be represented by the set of binary polynomials of degree m

1 or less:fam 1xm 1 + am 2 xm 2 +  + a1 x + a0 : ai 2 f0 1gg;

with addition and multiplication defined in terms of an irreducible binary polynomial f (x) of degree m,known as the reduction polynomial, as follows: Addition: If a = am 1xm 1 +  + a0 , b = bm 1 xm 1 +  + b0 2 F 2 , then a + b = r in F 2 , wherer = rm 1 xm 1 +  + r0 with ri  ai + bi (mod 2).
mm

SEC 1 - 2 Mathematical Foundations

Page 5

 Multiplication: If a = am 1xm 1 +  + a0 , b = bm 1 xm 1 +  + b0 2 F 2 , then a b = s in F 2 ,where s = sm 1 xm 1 +  + s0 is the remainder when the polynomial ab is divided by f (x) with allm:mcoefficient arithmetic performed modulo 2.

Addition and multiplication in F 2m can be calculated efficiently using standard algorithms for ordinary
integer and polynomial arithmetic. In this representation of F 2m , the additive identity or zero element is
the polynomial 0, and the multiplicative identity is the polynomial 1.
Again it is convenient to define subtraction and division of field elements. To do so the additive inverse(or negative) and multiplicative inverse of a field element must be described:

 Additive inverse: If a 2 F 2 , then the additive inverse ( a) of a in F 2 is the unique solution to themmequation a + x = 0 in F 2m .

 Multiplicative inverse: If a 2 F 2 , a 6= 0, then the multiplicative inverse a 1 of a in F 2 is themmunique solution to the equation a:x = 1 in F 2m .

Additive inverses and multiplicative inverses in F 2m can be calculated efficiently using the extended
Euclidean algorithm. Division and subtraction are defined in terms of additive and multiplicative inverses:
a b in F 2m is a + ( b) in F 2m and a=b in F 2m is a:(b 1) in F 2m .
Here the characteristic 2 finite fields F 2m used should have:m 2 f113; 131; 163; 193; 233; 239; 283; 409; 571g
and addition and multiplication in F 2m should be performed using one of the irreducible binary polynomials of degree m in Table 1. As before this restriction is designed to facilitate interoperability while
enabling implementers to deploy efficient implementations capable of meeting common security requirements.

Field

Reduction Polynomial(s)F 2113f (x) = x113 + x9 + 1

F 2131f (x) = x131 + x8 + x3 + x2 + 1

F 2163f (x) = x163 + x7 + x6 + x3 + 1

F 2193f (x) = x193 + x15 + 1

F 2233f (x) = x233 + x74 + 1

F 2239f (x) = x239 + x36 + 1 or x239 + x158 + 1

F 2283f (x) = x283 + x12 + x7 + x5 + 1

F 2409f (x) = x409 + x87 + 1

F 2571f (x) = x571 + x10 + x5 + x2 + 1
Table 1: Representations of F 2m

Page 6

SEC 1: Elliptic Curve Cryptography Ver. 1.0

The rule used to pick acceptable m’s was: in each interval between integers in the set:

f112 128 160 192 224 256 384 512 1024g
;

;

;

;

;

;

;

;

;

if such an m exists, select the smallest prime m in the interval with the property that there exists a Koblitz
curve whose order is 2 or 4 times a prime over F 2m ; otherwise simply select the smallest prime m in theinterval. (A Koblitz curve is an elliptic curve over F 2m with a; b 2 f0; 1g.) The inclusion of m = 239 is ananomaly chosen since it has already been widely used in practice. The inclusion of m = 283 instead ofm = 277 is an anomaly chosen to align this document with other standards efforts - in particular with the
U.S. government’s recommended elliptic curve domain parameters [31]. Composite m was avoided toalign this specification with other standards efforts and to address concerns about the security of elliptic
curves defined over F 2m with m composite. See Appendix B for additional discussion on field selection.
The rule used to pick acceptable reduction polynomials was: if a degree m binary irreducible trinomial:f (x) = xm + xk + 1 with m > k  1exists, use the irreducible trinomial with k as small as possible; otherwise use the degree m binary irreducible pentanomial:f (x) = xm + xk3 + xk2 + xk1 + 1 with m > k3 > k2 > k1  1with (1) k3 as small as possible, (2) k2 as small as possible given k3 , and (3) k1 as small as possible
given k3 and k2 . These polynomials enable efficient calculation of field operations. The second reduction
polynomial at m = 239 is an anomaly chosen since it has been widely deployed.

2.2 Elliptic Curves
An elliptic curve over F q is defined in terms of the solutions to an equation in F q . The form of theequation defining an elliptic curve over F q differs depending on whether the field is a prime finite field ora characteristic 2 finite field.
Section 2.2.1 describes elliptic curves over prime finite fields, and Section 2.2.2 describes elliptic curves
over characteristic 2 finite fields.
2.2.1 Elliptic Curves over F p
Let F p be a prime finite field so that p is an odd prime number, and let a; b 2 F p satisfy 4:a3 + 27:b2 6 0(mod p). Then an elliptic curve E (F p ) over F p defined by the parameters a; b 2 F p consists of the set ofsolutions or points P = (x; y) for x; y 2 F p to the equation:y2  x3 + a:x + b(mod p)together with an extra point O called the point at infinity. The equation y2  x3 + a:x + b (mod p) is
called the defining equation of E (F p ). For a given point P = (xP ; yP ), xP is called the x-coordinate of P,
and yP is called the y-coordinate of P.

SEC 1 - 2 Mathematical Foundations

Page 7

The number of points on E (F p ) is denoted by #E (F p ). The Hasse Theorem states that:
p+1

p

p

2 p  #E (F p )  p + 1 + 2 p:

It is possible to define an addition rule to add points on E. The addition rule is specified as follows:
1. Rule to add the point at infinity to itself:

O + O = O:
2. Rule to add the point at infinity to any other point:(x; y) + O = O + (x; y) = (x; y) for all (x; y)

2 E (F p):

3. Rule to add two points with the same x-coordinates when the points are either distinct or havey-coordinate 0:(x; y) + (x; y) = O for all (x; y) 2 E (F p )— i.e. the negative of the point (x; y) is(x; y) = (x;y).

4. Rule to add two points with different x-coordinates: Let (x1 ; y1 ) 2 E (F p ) and (x2 ; y2 ) 2 E (F p ) be
two points such that x1 6= x2 . Then (x1 ; y1 ) + (x2 ; y2 ) = (x3 ; y3 ), where:x3  λ2x1

x2(mod p); y3

 λ (x1 x3 ) y1 (mod p) and λ  yx2
:

;

2

y1
x1

(mod p):5. Rule to add a point to itself (double a point): Let (x1 ; y1 ) 2 E (F p ) be a point with y1 6= 0. Then(x1 ; y1 ) + (x1 ; y1 ) = (x3 ; y3 ), where:x3  λ2

2:x1(mod p); y3

 λ (x1 x3 ) y1:

3:x21 + a(mod p); and λ 
2:y1(mod p):The set of points on E (F p ) forms a group under this addition rule. Furthermore the group is abelian meaning that P1 + P2 = P2 + P1 for all points P1 ; P2 2 E (F p ). Notice that the addition rule can always becomputed efficiently using simple field arithmetic.
Cryptographic schemes based on ECC rely on scalar multiplication of elliptic curve points. Given an
integer k and a point P 2 E (F p ), scalar multiplication is the process of adding P to itself k times. The
result of this scalar multiplication is denoted k  P or kP. Scalar multiplication of elliptic curve points
can be computed efficiently using the addition rule together with the double-and-add algorithm or one ofits variants.

Page 8

SEC 1: Elliptic Curve Cryptography Ver. 1.0

2.2.2 Elliptic Curves over F 2m
Let F 2m be a characteristic 2 finite field, and let a; b 2 F 2m satisfy b 6= 0 in F 2m . Then a (non-supersingular)
elliptic curve E (F 2m ) over F 2m defined by the parameters a; b 2 F 2m consists of the set of solutions orpoints P = (x; y) for x; y 2 F 2m to the equation:y2 + x:y = x3 + a:x2 + b in F 2m
together with an extra point O called the point at infinity. (Here the only elliptic curves over F 2m ofinterest are non-supersingular elliptic curves.)
The number of points on E (F 2m ) is denoted by #E (F 2m ). The Hasse Theorem states that:
2m + 1p

p

2 2m  #E (F 2m )  2m + 1 + 2 2m :It is again possible to define an addition rule to add points on E as it was in Section 2.2.1. The addition
rule is specified as follows:
1. Rule to add the point at infinity to itself:

O + O = O:
2. Rule to add the point at infinity to any other point:(x; y) + O = O + (x; y) = (x; y) for all (x; y)

2 E (F p):

3. Rule to add two points with the same x-coordinates when the points are either distinct or havex-coordinate 0:(x; y) + (x; x + y) = O for all (x; y) 2 E (F p )— i.e. the negative of the point (x; y) is(x; y) = (x; x + y).

4. Rule to add two points with different x-coordinates: Let (x1 ; y1 ) 2 E (F 2m ) and (x2 ; y2 ) 2 E (F 2m ) be
two points such that x1 6= x2 . Then (x1 ; y1 ) + (x2 ; y2 ) = (x3 ; y3 ), where:
x3 = λ2 + λ + x1 + x2 + a in F 2m ; y3 = λ:(x1 + x3 ) + x3 + y1 in F 2m ; and λ 

y1 + y2in F 2m :x1 + x2

5. Rule to add a point to itself (double a point): Let (x1 ; y1 ) 2 E (F 2m ) be a point with x1 6= 0. Then(x1 ; y1 ) + (x1 ; y1 ) = (x3 ; y3 ), where:y1x3 = λ2 + λ + a in F 2m ; y3 = x21 + (λ + 1):x3 in F 2m ; and λ = x1 + in F 2m :x1
The set of points on E (F 2m ) forms an abelian group under this addition rule. Notice that the addition rulecan always be computed efficiently using simple field arithmetic.
Cryptographic schemes based on ECC rely on scalar multiplication of elliptic curve points. As before
given an integer k and a point P 2 E (F 2m ), scalar multiplication is the process of adding P to itself ktimes. The result of this scalar multiplication is denoted k  P or kP.

SEC 1 - 2 Mathematical Foundations

Page 9

2.3 Data Types and Conversions
The schemes specified in this document involve operations using several different data types. This section
lists the different data types and describes how to convert one data type to another.
Five data types are employed in this document: three types associated with elliptic curve arithmetic integers, field elements, and elliptic curve points - as well as octet strings which are used to communicate
and store information, and bit strings which are used by some of the primitives.
Throughout this document the above data types are regarded as abstract data types consisting of distinct
sets of elements - so that, for example, an octet string is regarded as distinct from a bit string. This
formalism helps to clarify the requirements placed on implementations and helps avoid subtle coding
errors.
Frequently it is necessary to convert one of the data types into another - for example to represent anelliptic curve point as an octet string. The remainder of this section is devoted to describing how thenecessary conversions should be performed.
Figure 1 illustrates which conversions are needed and where they are described.

Bit Strings

EC Points

2.3.2

2.3.3

2.3.1

2.3.4
Octet Strings

2.3.8

2.3.5
2.3.7

Integers

2.3.6
2.3.9

Figure 1: Converting between Data Types

Field Elements

Page 10

SEC 1: Elliptic Curve Cryptography Ver. 1.0

2.3.1 BitString-to-OctetString Conversion
Bit strings should be converted to octet strings as described in this section. Informally the idea is to pad
the bit string with 0’s on the left to make its length a multiple of 8, then chop the result up into octets.
Formally the conversion routine is specified as follows:
Input: A bit string B of length blen bits.

Output: An octet string M of length mlen = dblen=8e octets.
Actions: Convert the bit string B = B0 B1 : : : Bblen 1 to an octet string M = M0 M1 : : : Mmlen 1 as follows:
1. For 0 < i  mlen

1, let:Mi = Bblen 8 8(mlen 1 i) Bblen 7 8(mlen 1 i) : : : Bblen 1 8(mlen 1 i) :2. Let M0 have its leftmost 8(mlen)
set to B0 B1 : : : B8 8(mlen)+blen 1 .

blen bits set to 0, and its rightmost 8(8(mlen)blen) bits

3. Output M.
2.3.2 OctetString-to-BitString Conversion
Octet strings should be converted to bit strings as described in this section. Informally the idea is simply
to view the octet string as a bit string instead. Formally the conversion routine is specified as follows:
Input: An octet string M of length mlen octets.
Output: A bit string B of length blen = 8(mlen) bits.
Actions: Convert the octet string M = M0 M1 : : : Mmlen 1 to a bit string B = B0 B1 : : : Bblen 1 as follows:
1. For 0  i  mlen

1, set:B8i B8i+1 : : : B8i+7 = Mi :2. Output B.
2.3.3 EllipticCurvePoint-to-OctetString Conversion
Elliptic curve points should be converted to octet strings as described in this section. Informally, if point
compression is being used, the idea is that the compressed y-coordinate is placed in the leftmost octetof the octet string along with an indication that point compression is on, and the x-coordinate is placedin the remainder of the octet string; otherwise if point compression is off, the leftmost octet indicatesthat point compression is off, and remainder of the octet string contains the x-coordinate followed by the
y-coordinate. Formally the conversion routine is specified as follows:
Setup: Decide whether or not to represent points using point compression.

SEC 1 - 2 Mathematical Foundations

Page 11

Input: A point P on an elliptic curve over F q defined by the field elements a; b.

Output: An octet string M of length mlen octets where mlen = 1 if P = O , mlen = d(log2 q)=8e + 1 if
P 6= O and point compression is used, and mlen = 2d(log2 q)=8e + 1 if P 6= O and point compression is
not used.
Actions: Convert P to an octet string M = M0 M1 : : : Mmlen 1 as follows:
1. If P = O , output M = 0016 .
2. If P = (xP ; yP ) 6= O and point compression is being used, proceed as follows:
2.1. Convert the field element xP to an octet string X of length d(log2 q)=8e octets using the conversion routine specified in Section 2.3.5.
2.2. Derive from yP a single bit ỹP as follows (this allows the y-coordinate to be represented
compactly using a single bit):
2.2.1. If q = p is an odd prime, set ỹP = yP (mod 2).
2.2.2. If q = 2m , set ỹP = 0 if xP = 0, otherwise compute z = zm 1 xm 1 +  + z1 x + z0 suchthat z = yP :xP 1 and set ỹP = z0 .
2.3. If ỹP = 0, assign the value 0216 to the single octet Y . If ỹP = 1, assign the value 0316 to thesingle octet Y .
2.4. Output M = Y k X .

3. If P = (xP ; yP ) 6= O and point compression is not being used, proceed as follows:
3.1. Convert the field element xP to an octet string X of length d(log2 q)=8e octets using the conversion routine specified in Section 2.3.5.
3.2. Convert the field element yP to an octet string Y of length d(log2 q)=8e octets using the conversion routine specified in Section 2.3.5.

3.3. Output M = 0416 k X k Y .

2.3.4 OctetString-to-EllipticCurvePoint Conversion
Octet strings should be converted to elliptic curve points as described in this section. Informally theidea is that, if the octet string represents a compressed point, the compressed y-coordinate is recoveredfrom the leftmost octet, the x-coordinate is recovered from the remainder of the octet string, and then the
point compression process is reversed; otherwise the leftmost octet of the octet string is removed, the xcoordinate is recovered from the left half of the remaining octet string, and the y-coordinate is recoveredfrom the right half of the remaining octet string. Formally the conversion routine is specified as follows:
Input: An elliptic curve over F q defined by the field elements a; b, and an octet string M which iseither the single octet 0016 , an octet string of length mlen = d(log2 q)=8e + 1, or an octet string of length
mlen = 2d(log2 q)=8e + 1.

Page 12

SEC 1: Elliptic Curve Cryptography Ver. 1.0

Output: An elliptic curve point P, or ‘invalid’.
Actions: Convert M to an elliptic curve point P as follows:
1. If M = 0016 , output P = O .
2. If M has length d(log2 q)=8e + 1 octets, proceed as follows:
2.1. Parse M = Y k X as a single octet Y followed by d(log2 q)=8e octets X .
2.2. Convert X to a field element xP of F q using the conversion routine specified in Section 2.3.6.
Output ‘invalid’ and stop if the routine outputs ‘invalid’.
2.3. If Y = 02, set ỹP = 0, and if Y = 03, set ỹP = 1. Otherwise output ‘invalid’ and stop.
2.4. Derive from xP and ỹP an elliptic curve point P = (xP ; yP ), where:

2.4.1. If q = p is an odd prime, compute the field element α  xP 3 + a:xP + b (mod p), andcompute a square root β of α modulo p. Output ‘invalid’ and stop if there are no squareroots of α modulo p, otherwise set yP = β if β  ỹP (mod 2), and set yP = p β if β 6 ỹP(mod 2).
m 1

2.4.2. If q = 2m and xP = 0, output yP = b2
in F 2m .
2.4.3. If q = 2m and xP 6= 0, compute the field element β = xP + a + b:xP 2 in F 2m , and find anelement z = zm 1 xm 1 +  + z1 x + z0 such that z2 + z = β in F 2m . Output ‘invalid’ andstop if no such z exists, otherwise set yP = xP :z in F 2m if z0 = ỹP , and set yP = xP :(z + 1)
in F 2m if z0 6= ỹP .
2.5. Output P = (xP ; yP ).
3. If M has length 2d(log2 q)=8e + 1 octets, proceed as follows:
3.1. Parse M = W k X k Y as a single octet W followed by d(log2 q)=8e octets X followed byd(log2 q)=8e octets Y .

3.2. Check that W = 0416 . If W 6= 0416 , output ‘invalid’ and stop.

3.3. Convert X to a field element xP of F q using the conversion routine specified in Section 2.3.6.
Output ‘invalid’ and stop if the routine outputs ‘invalid’.
3.4. Convert Y to a field element yP of F q using the conversion routine specified in Section 2.3.6.
Output ‘invalid’ and stop if the routine outputs ‘invalid’.
3.5. Check that P = (xP ; yP ) satisfies the defining equation of the elliptic curve.
3.6. Output P = (xP ; yP ).
2.3.5 FieldElement-to-OctetString Conversion
Field elements should be converted to octet strings as described in this section. Informally the idea isthat, if the field is F p , convert the integer to an octet string, and if the field is F 2m , view the coefficients

SEC 1 - 2 Mathematical Foundations

Page 13of the polynomial as a bit string with the highest degree term on the left and convert the bit string to an
octet string. Formally the conversion routine is specified as follows:
Input: An element a of the field F q .

Output: An octet string M of length mlen = dlog2 q=8e octets.
Actions: Convert a to an octet string M = M0 M1 : : : Mmlen 1 as follows:
1. If q = p is an odd prime, then a is an integer in the interval [0; pconversion routine specified in Section 2.3.7. Output M.

1]. Convert a to M using the

2. If q = 2m , then a = am 1 xm 1 +  + a1 x + a0 is a binary polynomial. Convert a to M as follows:
2.1. For 0 < i  mlen

1, let:Mi = a7+8(mlen 1 i) a6+8(mlen 1 i) : : : a8(mlen 1 i) :2.2. Let M0 have its leftmost 8(mlen)
set to am 1 am 2 : : : a8(mlen) 8 .

m bits set to 0, and its rightmost 8(8(mlen)m) bits

2.3. Output M.
2.3.6 OctetString-to-FieldElement Conversion
Octet strings should be converted to field elements as described in this section. Informally the idea isthat, if the field is F p , convert the octet string to an integer, and if the field is F 2m , use the bits of the octet
string as the coefficients of the binary polynomial with the rightmost bit as the constant term. Formallythe conversion routine is specified as follows:
Input: An indication of the field F q used and an octet string M of length mlen = dlog2 q=8e octets.
Output: An element a in F q , or ‘invalid’.
Actions: Convert M = M0 M1 : : : Mmlen 1 with Mi = Mi0 Mi1 : : : Mi7 to a field element a as follows:
1. If q = p is an odd prime, then a needs to be an integer in the interval [0; p 1]. Convert M to an
integer a using the conversion routine specified in Section 2.3.8. Output ‘invalid’ and stop if a does
not lie in the interval [0; p 1], otherwise output a.
2. If q = 2m , then a needs to be a binary polynomial of degree m
to be a = am 1 xm 1 +  + a1 x + a0 with:

1 or less. Set the field element a

7 i+8(bi=8c)

ai = Mmlen 1 bi=8c :Output ‘invalid’ and stop if the leftmost 8(mlen)m bits of M0 are not all 0, otherwise output a.

Page 14

SEC 1: Elliptic Curve Cryptography Ver. 1.0

2.3.7 Integer-to-OctetString Conversion
Integers should be converted to octet strings as described in this section. Informally the idea is to represent
the integer in binary then convert the resulting bit string to an octet string. Formally the conversion routineis specified as follows:
Input: A non-negative integer x together with the desired length mlen of the octet string. It must be thecase that:28(mlen) > x:
Output: An octet string M of length mlen octets.

Actions: Convert x = xmlen 1 28(mlen 1) + xmlen 2 28(mlen 2) +  + x1 28 + x0 represented in base 28 = 256
to an octet string M = M0 M1 : : : Mmlen 1 as follows:
1. For 0  i  mlen

1, set:Mi = xmlen 1 i :2. Output M.
2.3.8 OctetString-to-Integer Conversion
Octet strings should be converted to integers as described in this section. Informally the idea is simply
to view the octet string as the base 256 representation of the integer. Formally the conversion routine is
specified as follows:
Input: An octet string M of length mlen octets.
Output: An integer x.
Actions: Convert M = M0 M1 : : : Mmlen 1 to an integer x as follows:
1. View Mi as an integer in the range [0; 255] and set:mlen 1x=∑ 28(mlen 1 i)Mi:

i=0

2. Output x.
2.3.9 FieldElement-to-Integer Conversion
Field elements should be converted to integers as described in this section. Informally the idea is that,
if the field is F p no conversion is required, and if the field is F 2m first convert the binary polynomial toan octet string then convert the octet string to an integer. Formally the conversion routine is specified asfollows:

SEC 1 - 2 Mathematical Foundations

Page 15

Input: An element a of the field F q .
Output: An integer x.
Actions: Convert the field element a to an integer x as follows:
1. If q = p is an odd prime, then a must be an integer in the interval [0; p
2. If q = 2m , then a must be a binary polynomial of degree m + a1 x + a0 . Set:m 1

x = ∑ 2i ai :i =0

Output x.

1]. Output x = a.

1 — i.e. a = am 1 xm 1 + am 2 xm 2 +Page 163

SEC 1: Elliptic Curve Cryptography Ver. 1.0

Cryptographic Components

This section describes the various cryptographic components that are used to build signature schemes,
encryption schemes, and key agreement schemes later in this document.
See Appendix B for a commentary on the contents on this section, including implementation discussion,
security discussion, and references.

3.1 Elliptic Curve Domain Parameters
The operation of each of the public-key cryptographic schemes described in this document involves
arithmetic operations on an elliptic curve over a finite field determined by some elliptic curve domain
parameters.
This section addresses the provision of elliptic curve domain parameters. It describes what elliptic curve
domain parameters are, how they should be generated, and how they should be validated.
Two types of elliptic curve domain parameters may be used: elliptic curve domain parameters over F p ,and elliptic curve domain parameters over F 2m . Section 3.1.1 describes elliptic curve domain parameters
over F p , and Section 3.1.2 describes elliptic curve domain parameters over F 2m .
3.1.1 Elliptic Curve Domain Parameters over F p
Elliptic curve domain parameters over F p are a sextuple:
T = ( p ; a ; b ; G; n ; h )consisting of an integer p specifying the finite field F p , two elements a; b 2 F p specifying an elliptic curve
E (F p ) defined by the equation:
E : y2  x3 + a:x + b(mod p);a base point G = (xG ; yG ) on E (F p ), a prime n which is the order of G, and an integer h which is thecofactor h = #E (F p )=n.
Elliptic curve domain parameters over F p precisely specify an elliptic curve and base point. This isnecessary to precisely define public-key cryptographic schemes based on ECC.
Section 3.1.1.1 describes how to generate elliptic curve domain parameters over F p , and Section 3.1.1.2
describes how to validate elliptic curve domain parameters over F p .
3.1.1.1 Elliptic Curve Domain Parameters over F p Generation Primitive
Elliptic curve domain parameters over F p should be generated as follows:
Input: The approximate security level in bits required from the elliptic curve domain parameters — thismust be an integer t 2 f56; 64; 80; 96; 112; 128; 192; 256g.

SEC 1 - 3 Cryptographic Components

Page 17

Output: Elliptic curve domain parameters over F p :T = ( p ; a ; b ; G; n ; h )such that taking logarithms on the associated elliptic curve is believed to require approximately 2t operations.
Actions: Generate elliptic curve domain parameters over F p as follows:
1. Select a prime p such that dlog2 pe = 2t if t 6= 256 and such that dlog2 pe = 521 if t = 256 todetermine the finite field F p .
2. Select elements a; b 2 F p to determine the elliptic curve E (F p ) defined by the equation:
E : y2  x3 + a:x + b(mod p);a base point G = (xG ; yG ) on E (F p ), a prime n which is the order of G, and an integer h which isthe cofactor h = #E (F p )=n, subject to the following constraints:

 4 a3 + 27 b2 6 0 (mod p).
 #E (F p ) 6= p.
 pB 6 1 (mod n) for any 1  B
 h  4.
:

:

<

20.

3. Output T = ( p; a; b; G; n; h).
This primitive allows any of the known curve selection methods to be used — for example the methods
based on complex multiplication and the methods based on general point counting algorithms. However
to foster interoperability it is strongly recommended that implementers use one of the elliptic curve
domain parameters over F p specified in SEC 2 [83]. See Appendix B for further discussion.
3.1.1.2 Validation of Elliptic Curve Domain Parameters over F p
Frequently it is either necessary or desirable for an entity using elliptic curve domain parameters over F p
to receive an assurance that the parameters are valid — that is that they satisfy the arithmetic requirementsof elliptic curve domain parameters — either to prevent malicious insertion of insecure parameters, or todetect inadvertent coding or transmission errors.
There are four acceptable methods for an entity U to receive an assurance that elliptic curve domain
parameters over F p are valid. Only one of the methods must be supplied, although in many cases greater
security may be obtained by carrying out more than one of the methods.
The four acceptable methods are:
1. U performs validation of the elliptic curve domain parameters over F p itself using the validation
primitive described in Section 3.1.1.2.1.

Page 18

SEC 1: Elliptic Curve Cryptography Ver. 1.0

2. U generates the elliptic curve domain parameters over F p itself using a trusted system using theprimitive specified in Section 3.1.1.1.
3. U receives assurance in an authentic manner that a party trusted with respect to U ’s use of theelliptic curve domain parameters over F p has performed validation of the parameters using thevalidation primitive described in Section 3.1.1.2.1.
4. U receives assurance in an authentic manner that a party trusted with respect to U ’s use of theelliptic curve domain parameters over F p generated the parameters using a trusted system using
the primitive specified in Section 3.1.1.1.
Usually when U accepts another party’s assurance that elliptic curve domain parameters are valid, theother party is a CA.
3.1.1.2.1 Elliptic Curve Domain Parameters over F p Validation Primitive
The elliptic curve domain parameters over F p validation primitive should be used to check elliptic curve
domain parameters over F p are valid as follows:
Input: Elliptic curve domain parameters over F p :T = ( p; a; b; G; n; h);along with an integer t 2 f56; 64; 80; 96; 112; 128; 192; 256g which is the approximate security level inbits required from the elliptic curve domain parameters.
Output: An indication of whether the elliptic curve domain parameters are valid or not — either ‘valid’or ‘invalid’.
Actions: Validate the elliptic curve domain parameters over F p as follows:
1. Check that p is an odd prime such that dlog2 pe = 2t if t 6= 256 or such that dlog2 pe = 521 if
t = 256.
2. Check that a, b, xG , and yG are integers in the interval [0; p
3. Check that 4:a3 + 27:b2 6 0(mod p).

4. Check that yG 2  xG 3 + a:xG + b
5. Check that n is prime.

1].

(mod p).

p

6. Check that h  4, and that h = b( p + 1)2 =nc.
7. Check that nG = O .
8. Check that qB 6 1

(mod n) for any 1B<20, and that nh 6= p.

SEC 1 - 3 Cryptographic Components

Page 19

9. If any of the checks fail, output ‘invalid’, otherwise output ‘valid’.
Step 8 above excludes the known weak classes of curves which are susceptible to either the MenezesOkamoto-Vanstone attack, or the Frey-Ruck attack, or the Semaev-Smart-Satoh-Araki attack. See Appendix B for further discussion.
If the elliptic curve domain parameters have been generated verifiably at random using SHA-1 as described in ANSI X9.62 [3], it may also be checked that a and b have been correctly derived from therandom seed.
3.1.2 Elliptic Curve Domain Parameters over F 2m
Elliptic curve domain parameters over F 2m are a septuple:
T = (m; f (x); a; b; G; n; h)consisting of an integer m specifying the finite field F 2m , an irreducible binary polynomial f (x) of degree
m specifying the representation of F 2m , two elements a; b 2 F 2m specifying the elliptic curve E (F 2m )defined by the equation:y2 + x:y = x3 + a:x2 + b in F 2m ;a base point G = (xG ; yG ) on E (F 2m ), a prime n which is the order of G, and an integer h which is thecofactor h = #E (F 2m )=n.
Elliptic curve domain parameters over F 2m precisely specify an elliptic curve and base point. This isnecessary to precisely define public-key cryptographic schemes based on ECC.
Section 3.1.2.1 describes how to generate elliptic curve domain parameters over F 2m , and Section 3.1.2.2
describes how to validate elliptic curve domain parameters over F 2m .
3.1.2.1 Elliptic Curve Domain Parameters over F 2m Generation Primitive
Elliptic curve domain parameters over F 2m should be generated as follows:
Input: The approximate security level in bits required from the elliptic curve domain parameters — thismust be an integer t 2 f56; 64; 80; 96; 112; 128; 192; 256g.
Output: Elliptic curve domain parameters over F 2m :T = (m; f (x); a; b; G; n; h)such that taking logarithms on the associated elliptic curve is believed to require approximately 2t operations.
Actions: Generate elliptic curve domain parameters over F 2m as follows:
1. Let t 0 denote the smallest integer greater than t in the set f64; 80; 96; 112; 128; 192; 256; 512g. Selectm 2 f113; 131; 163; 193; 233; 239; 283; 409; 571g such that 2t < m < 2t 0 to determine the finite field
F 2m .

Page 20

SEC 1: Elliptic Curve Cryptography Ver. 1.0

2. Select a binary irreducible polynomial f (x) of degree m from Table 1 in Section 2.1.2 to determine
the representation of F 2m .
3. Select elements a; b 2 F 2m to determine the elliptic curve E (F 2m ) defined by the equation:
E : y2 + x:y = x3 + a:x2 + b in F 2m ;a base point G = (xG ; yG ) on E (F 2m ), a prime n which is the order of G, and an integer h which isthe cofactor h = #E (F 2m )=n, subject to the following constraints:

 b 6= 0 in F 2 .
 #E (F 2 ) 6= 2m.
 2mB 6 1 (mod n) for any 1  B
 h  4.
m

m

<

20.

4. Output T = (m; f (x); a; b; G; n; h).
This primitive also allows any of the known curve selection methods to be used. However to foster
interoperability it is strongly recommended that implementers use one of the recommended elliptic curve
domain parameters over F 2m specified in SEC 2 [83]. See Appendix B for further discussion.
3.1.2.2 Validation of Elliptic Curve Domain Parameters over F 2m
Frequently it is either necessary or desirable for an entity using elliptic curve domain parameters over F 2m
to receive an assurance that the parameters are valid — that is that they satisfy the arithmetic requirementsof elliptic curve domain parameters — either to prevent malicious insertion of insecure parameters, or todetect inadvertent coding or transmission errors.
There are four acceptable methods for an entity U to receive an assurance that elliptic curve domain
parameters over F 2m are valid. Only one of the methods must be supplied, although in many cases greater
security may be obtained by carrying out more than one of the methods.
The four acceptable methods are:
1. U performs validation of the elliptic curve domain parameters over F 2m itself using the validation
primitive described in Section 3.1.2.2.1.
2. U generates the elliptic curve domain parameters over F 2m itself using a trusted system using theprimitive specified in Section 3.1.2.1.
3. U receives assurance in an authentic manner that a party trusted with respect to U ’s use of theelliptic curve domain parameters over F 2m has performed validation of the parameters using thevalidation primitive described in Section 3.1.1.2.1.
4. U receives assurance in an authentic manner that a party trusted with respect to U ’s use of theelliptic curve domain parameters over F 2m generated the parameters using a trusted system using
the primitive specified in Section 3.1.2.1.

SEC 1 - 3 Cryptographic Components

Page 213.1.2.2.1 Elliptic Curve Domain Parameters over F 2m Validation Primitive
The elliptic curve domain parameters over F 2m validation primitive should be used to check elliptic curve
domain parameters over F 2m are valid as follows:
Input: Elliptic curve domain parameters over F 2m :T = (m; f (x); a; b; G; n; h)along with an integer t 2 f56; 64; 80; 96; 112; 128; 192; 256g which is the approximate security level inbits required from the elliptic curve domain parameters.
Output: An indication of whether the elliptic curve domain parameters are valid or not — either ‘valid’or ‘invalid’.
Actions: Validate the elliptic curve domain parameters over F 2m as follows:
1. Let t 0 denote the smallest integer greater than t in the set f64; 80; 96; 112; 128; 192; 256; 512g.
Check that m is an integer in the set f113; 131; 163; 193; 233; 239; 283; 409; 571g such that 2t <m < 2t 0.
2. Check that f (x) is a binary irreducible polynomial of degree m which is listed in Table 1 in Section 2.1.2.
3. Check that a, b, xG , and yG are binary polynomials of degree m

1 or less.

4. Check that b 6= 0 in F 2m .
5. Check that yG 2 + xG :yG = xG 3 + a:xG 2 + b in F 2m .
6. Check that n is prime.

p

7. Check that h  4, and that h = b( 2m + 1)2 =nc.
8. Check that nG = O .
9. Check that 2mB 6 1

(mod n) for any 1B<20, and that nh 6= 2m .

10. If any of the checks fail, output ‘invalid’, otherwise output ‘valid’.
Steps 1 and 9 above excludes the known weak classes of curves which are susceptible to either the
Menezes-Okamoto-Vanstone attack, or the Frey-Ruck attack, or the Semaev-Smart-Satoh-Araki attack,or to attacks based on the Weil descent. See Appendix B for further discussion.
If the elliptic curve domain parameters have been generated verifiably at random using SHA-1 as described in ANSI X9.62 [3], it may also be checked that a and b have been correctly derived from therandom seed.

Page 22

SEC 1: Elliptic Curve Cryptography Ver. 1.0

3.2 Elliptic Curve Key Pairs
All the public-key cryptographic schemes described in this document use key pairs known as elliptic
curve key pairs.
Given some elliptic curve domain parameters T = ( p; a; b; G; n; h) or (m; f (x); a; b; G; n; h), an elliptic
curve key pair (d ; Q) associated with T consists of an elliptic curve secret key d which is an integer in
the interval [1; n 1], and an elliptic curve public key Q = (xQ ; yQ ) which is the point Q = dG.
Section 3.2.1 describes how to generate elliptic curve key pairs, Section 3.2.2 describes how to validate
elliptic curve public keys, and Section 3.2.3 describes how to partially validate elliptic curve public keys.

3.2.1 Elliptic Curve Key Pair Generation Primitive
Elliptic curve key pairs should be generated as follows:
Input: Valid elliptic curve domain parameters T = ( p; a; b; G; n; h) or (m; f (x); a; b; G; n; h).
Output: An elliptic curve key pair (d ; Q) associated with T .
Actions: Generate an elliptic curve key pair as follows:
1. Randomly or pseudorandomly select an integer d in the interval [1; n1].

2. Calculate Q = dG.
3. Output (d ; Q).
3.2.2 Validation of Elliptic Curve Public Keys
Frequently it is either necessary or desirable for an entity using an elliptic curve public key to receive anassurance that the public key is valid — that is that it satisfies the arithmetic requirements of an elliptic
curve public key — either to prevent malicious insertion of an invalid public key to enable attacks likesmall subgroup attacks, or to detect inadvertent coding or transmission errors.
There are four acceptable methods for an entity U to receive an assurance that an elliptic curve public
key is valid. Only one of the methods must be supplied, although in many cases greater security may beobtained by carrying out more than one of the methods.
The four acceptable methods are:
1. U performs validation of the elliptic curve public key itself using the public key validation primitive
described in Section 3.2.2.1.
2. U generates the elliptic curve public key itself using a trusted system.

SEC 1 - 3 Cryptographic Components

Page 23

3. U receives assurance in an authentic manner that a party trusted with respect to U ’s use of theelliptic curve public key has performed validation of the public key using the public key validation
primitive described in Section 3.2.2.1.
4. U receives assurance in an authentic manner that a party trusted with respect to U ’s use of theelliptic curve public key generated the public key using a trusted system.
Usually when U accepts another party’s assurance that an elliptic curve public key is valid, the other party
is a CA who validated the public key during the certification process. Occasionally U may also receive
assurance from another party other than a CA. For example, in the Station-to-Station protocol describedin ANSI X9.63 [4], U receives an ephemeral public key from V . V is trusted with respect to U ’s use of
the public key because U is attempting to establish a key with V and U only combines the public key
with its own ephemeral key pair. It is therefore acceptable in this circumstance for U to accept assurance
from V that the public key is valid because the public key is received in a signed message.
3.2.2.1 Elliptic Curve Public Key Validation Primitive
The elliptic curve public key validation primitive should be used to check an elliptic curve public key isvalid as follows:
Input: Valid elliptic curve domain parameters T = ( p; a; b; G; n; h) or (m; f (x); a; b; G; n; h), and an elliptic curve public key Q = (xQ ; yQ ) associated with T .
Output: An indication of whether the elliptic curve public key is valid or not — either ‘valid’ or ‘invalid’.
Actions: Validate the elliptic curve public key as follows:
1. Check that Q 6= O .
2. If T represents elliptic curve domain parameters over F p , check that xQ and yQ are integers in therange [1; p 1], and that:yQ 2  xQ 3 + a:xQ + b (mod p):
3. If T represents elliptic curve domain parameters over F 2m , check that xQ and yQ are binary polynomials of degree at most m 1, and that:yQ 2 + xQ :yQ = xQ 3 + a:xQ 2 + b in F 2m :4. Check that nQ = O .
5. If any of the checks fail, output ‘invalid’, otherwise output ‘valid’.
In the above routine, steps 1, 2, and 3 check that Q is a point on E other than the point at infinity, andstep 4 checks that Q is a scalar multiple of G.

Page 24

SEC 1: Elliptic Curve Cryptography Ver. 1.0

3.2.3 Partial Validation of Elliptic Curve Public Keys
Sometimes it is sufficient for an entity using an elliptic curve public key to receive an assurance that the
public key is partially valid, rather than ‘fully’ valid — here an elliptic curve public key Q is said to bepartially valid if Q is a point on the associated elliptic curve but it is not necessarily the case that Q = dG
for some d.
The MQV key agreement scheme and the Diffie-Hellman scheme using the cofactor Diffie-Hellman
primitive are both examples of schemes designed to provide security even when entities only check thatthe public keys involved are partially valid. (This feature is desirable because it means that the schemes
enjoy a computational advantage in some circumstances over schemes like the Diffie-Hellman schemewith the ‘standard’ Diffie-Hellman primitive which require ‘fully’ valid public keys. The computational
advantage stems from the fact that public key partial validation is more efficient than public key ‘full’validation.)
There are four acceptable methods for an entity U to receive an assurance that an elliptic curve public
key is partially valid. Only one of the methods must be supplied, although in many cases greater security
may be obtained by carrying out more than one of the methods.
The four acceptable methods are:
1. U performs partial validation of the elliptic curve public key itself using the public key partial
validation primitive described in Section 3.2.3.1.
2. U generates the elliptic curve public key itself using a trusted system.
3. U receives assurance in an authentic manner that a party trusted with respect to U ’s use of theelliptic curve public key has performed partial validation of the public key using the public key
partial validation primitive described in Section 3.2.3.1.
4. U receives assurance in an authentic manner that a party trusted with respect to U ’s use of theelliptic curve public key generated the public key using a trusted system.
3.2.3.1 Elliptic Curve Public Key Partial Validation Primitive
The elliptic curve public key partial validation primitive should be used to check an elliptic curve public
key is partially valid as follows:
Input: Valid elliptic curve domain parameters T = ( p; a; b; G; n; h) or (m; f (x); a; b; G; n; h), and an elliptic curve public key Q = (xQ ; yQ ) associated with T .
Output: An indication of whether the elliptic curve public key is partially valid or not — either ‘valid’or ‘invalid’.
Actions: Partially validate the elliptic curve public key as follows:
1. Check that Q 6= O .

SEC 1 - 3 Cryptographic Components

Page 25

2. If T represents elliptic curve domain parameters over F p , check that xQ and yQ are integers in therange [1; p 1], and that:yQ 2  xQ 3 + a:xQ + b (mod p):
3. If T represents elliptic curve domain parameters over F 2m , check that xQ and yQ are binary polynomials of degree at most m 1, and that:yQ 2 + xQ :yQ = xQ 3 + a:xQ 2 + b in F 2m :4. If any of the checks fail, output ‘invalid’, otherwise output ‘valid’.
In the above routine, steps 1, 2, and 3 check that Q is a point on E other than the point at infinity.

3.3 Elliptic Curve Diffie-Hellman Primitives
This section specifies the elliptic curve Diffie-Hellman primitives which are the basis for the operationof the Elliptic Curve Integrated Encryption Scheme in Section 5.1, and the elliptic curve Diffie-Hellman
scheme in Section 6.1.
Two primitives are specified: the elliptic curve Diffie-Hellman primitive and the elliptic curve cofactor
Diffie-Hellman primitive. The basic idea of both primitives is the same — to generate a shared secretvalue from a private key owned by one entity U and a public key owned by another entity V so that if
both entities execute the primitive with corresponding keys as input they will recover the same sharedsecret value.
However the two primitives are subtlely different: the elliptic curve Diffie-Hellman primitive is thestraightforward analogue of the well-known Diffie-Hellman key agreement method, whereas the elliptic curve cofactor Diffie-Hellman primitive incorporates the cofactor into the calculation of the sharedsecret value to provide efficient resistance to attacks like small subgroup attacks.
The elliptic curve Diffie-Hellman primitive is specified in Section 3.3.1, and the elliptic curve cofactor
Diffie-Hellman primitive is specified in Section 3.3.2.
3.3.1 Elliptic Curve Diffie-Hellman Primitive
U should employ the following process to calculate a shared secret value with V using the elliptic curve
Diffie-Hellman primitive:
Input: The elliptic curve Diffie-Hellman primitive takes as input:
1. Valid elliptic curve domain parameters T = ( p; a; b; G; n; h) or (m; f (x); a; b; G; n; h).
2. An elliptic curve private key dU associated with T owned by U .
3. An elliptic curve public key QV associated with T purportedly owned by V .

Page 26

SEC 1: Elliptic Curve Cryptography Ver. 1.0

The public key QV should be valid.
Output: A shared secret field element z, or ‘invalid’.
Actions: Calculate a shared secret value as follows:
1. Compute the elliptic curve point P = (xP ; yP ) = dU QV .
2. Check that P 6= O . If P = O , output ‘invalid’ and stop.
3. Output z = xP as the shared secret field element.
3.3.2 Elliptic Curve Cofactor Diffie-Hellman Primitive
U should employ the following process to calculate a shared secret value with V using the elliptic curve
cofactor Diffie-Hellman primitive:
Input: The elliptic curve cofactor Diffie-Hellman primitive takes as input:
1. Valid elliptic curve domain parameters T = ( p; a; b; G; n; h) or (m; f (x); a; b; G; n; h).
2. An elliptic curve private key dU associated with T owned by U .
3. An elliptic curve public key QV associated with T purportedly owned by V .
The public key QV should at a minimum be partially valid.
Output: A shared secret field element z, or ‘invalid’.
Actions: Calculate a shared secret value as follows:
1. Compute the elliptic curve point P = (xP ; yP ) = hdU QV .
2. Check that P 6= O . If P = O , output ‘invalid’ and stop.
3. Output z = xP as the shared secret field element.

3.4 Elliptic Curve MQV Primitive
This section specifies the elliptic curve MQV primitive which is the basis for the operation of the elliptic
curve MQV scheme specified in Section 6.2.
The basic idea of this primitive is to generate a shared secret value from two elliptic curve key pairs
owned by one entity U and two elliptic curve public keys owned by another entity V so that if both
entities execute the primitive with corresponding keys as input they will recover the same shared secretvalue.

SEC 1 - 3 Cryptographic Components

Page 27

U should employ the following process to calculate a shared secret value with V using the elliptic curve
MQV primitive:
Input: The elliptic curve MQV primitive takes as input:
1. Valid elliptic curve domain parameters T = ( p; a; b; G; n; h) or (m; f (x); a; b; G; n; h).
2. Two elliptic curve key pairs (d1;U ; Q1;U ) and (d2;U ; Q2;U ) associated with T owned by U .
3. Two elliptic curve public keys Q1;V and Q2;V associated with T purportedly owned by V .
The public keys Q1;V and Q2;V should at a minimum be partially valid.
Output: A shared secret field element z, or ‘invalid’.
Actions: Calculate a shared secret value as follows:
1. Set q = p if T = ( p; a; b; G; n; h), or q = 2m if T = (m; f (x); a; b; G; n; h).
2. Compute an integer Q2;U using Q2;U = (xQ ; yQ ) as follows:
2.1. Convert xQ to an integer x using the conversion routine specified in Section 2.3.9.
2.2. Calculate:xx2.3. Calculate:
3. Compute the integer:(mod 2d(log2 n) 2e ):=Q2;U = x + 2d(log2 n)=2e :s  d2;U + Q2;U :d1;U(mod n):4. Compute an integer Q2;V using Q2;V = (xQ 0 ; yQ 0 ) as follows:
4.1. Convert xQ 0 to an integer x0 using the conversion routine specified in Section 2.3.9.
4.2. Calculate:x0  x0

4.3. Calculate:(mod 2d(log2 n) 2e ):=Q2;V = x0 + 2d(log2 n)=2e :5. Compute the elliptic curve point:
P = (xP ; yP ) = hs  (Q2;V + Q2;V Q1;V ):6. Check that P 6= O . If P = O , output ‘invalid’ and stop.
7. Output z = xP as the shared secret field element.

Page 28

SEC 1: Elliptic Curve Cryptography Ver. 1.0

3.5 Hash Functions
This section specifies the cryptographic hash functions supported in this document.
The hash functions are used by the key derivation functions specified in Section 3.6, and by the Elliptic
Curve Digital Signature Algorithm specified in Section 4.1.
The hash functions will be used to calculate the hash value associated with an octet string.
The list of supported hash functions at this time is:
SHA-1
SHA-1 is specified in FIPS 180-1 [30]. It maps octet strings of length less than 261 octets to hash values
which are octet strings of length 20 octets. (Although only one hash function is supported at this time, itis planned that support for SHA-2 will be added as SHA-2 passes through the standardization proceduresof ANSI and NIST so that a hash function which offers more than 80 bits of security is available toimplementers.)
For clarity in the remainder of this section, the generic operation of the hash functions is described sothat their use can be precisely specified later on.
Hash values should be calculated as follows:
Setup: Select one of the approved hash functions. Let Hash denote the hash function chosen, hashlen
denote the length in octets of hash values computed using Hash, and hashmaxlen denote the maximum
length in octets of messages that can be hashed using Hash.
Input: The input to the hash function is an octet string M.
Output: The hash value H which is an octet string of length hashlen octets, or ‘invalid’.
Actions: Calculate the hash value H as follows:
1. Check that M is less than hashmaxlen octets long — i.e. check that:

jjMjj

<

hashmaxlen:

If jjM jj  hashmaxlen, output ‘invalid’ and stop.
2. Convert M to a bit string M using the conversion routine specified in Section 2.3.2.
3. Calculate the hash value H corresponding to M using the selected hash function:
H = Hash(M ):4. Convert H to an octet string H using the conversion routine specified in Section 2.3.1.
5. Output H.

SEC 1 - 3 Cryptographic Components

Page 29

3.6 Key Derivation Functions
This section specifies the key derivation functions supported in this document.
The key derivation functions are used by the Elliptic Curve Integrated Encryption Scheme specified in
Section 5.1, and the key agreement schemes specified in Section 6.
The key derivation functions will be used to derive keying data from a shared secret octet string.
The list of supported key derivation functions at this time is:
ANSI-X9.63-KDF
ANSI-X9.63-KDF is the simple hash function construct described in ANSI X9.63 [4]. This key derivation
function is described in Section 3.6.1 — partly for completeness since at the time of this edition ANSI
X9.63 is only a draft standard, and partly so that the use of the key derivation function can be precisely
described later on. Support for other key derivation functions may be added to future editions of thisdocument.
3.6.1 ANSI X9.63 Key Derivation Function
Keying data should be calculated using ANSI-X9.63-KDF as follows:
Setup: Select one of the approved hash functions listed in Section 3.5. Let Hash denote the hash function
chosen, hashlen denote the length in octets of hash values computed using Hash, and hashmaxlen denotethe maximum length in octets of messages that can be hashed using Hash.
Input: The input to the key derivation function is:
1. An octet string Z which is the shared secret value.
2. An integer keydatalen which is the length in octets of the keying data to be generated.
3. (Optional) An octet string SharedIn f o which consists of some data shared by the entities intended
to share the shared secret value Z.
Output: The keying data K which is an octet string of length keydatalen octets, or ‘invalid’.
Actions: Calculate the keying data K as follows:
1. Check that jjZ jj + jjSharedIn f ojj + 4 < hashmaxlen. If jjZ jj + jjSharedIn f ojj + 4  hashmaxlen,
output ‘invalid’ and stop.
2. Check that keydatalen < hashlen  (232and stop.

1). If keydatalen  hashlen  (232

3. Initiate a 4 octet, big-endian octet string Counter as 0000000116 .

1), output ‘invalid’Page 30

SEC 1: Elliptic Curve Cryptography Ver. 1.0

4. For i = 1 to dkeydatalen=hashlene, do the following:
4.1. Compute:

Ki = Hash(Z k Counter k [SharedIn f o])using the selected hash function from the list of approved hash functions in Section 3.5.
4.2. Increment Counter.
4.3. Increment i.
5. Set K to be the leftmost keydatalen octets of:K1 k K2 k : : : k Kdkeydatalen=hashlene :6. Output K.

3.7 MAC schemes
This section specifies the MAC schemes supported in this document.
The MAC schemes will be used by the Elliptic Curve Integrated Encryption Scheme specified in Section 5.1.
MAC schemes are designed to be used by two entities — a sender U and a recipient V — when U wants
to send a message M to V in an authentic manner and V wants to verify the authenticity of M.
Here the MAC schemes are described in terms of a tagging operation, a tag checking operation, andassociated setup and key deployment procedures. U and V should use the schemes as follows when theywant to communicate. First U and V should use the setup and key deployment procedures to establish
which options to use the scheme with, and to create a shared secret key K to control the tagging and tag
checking operations. Then each time U wants to send a message M to V , U should apply the tagging
operation to M under the shared secret key K to compute the tag D on M, and convey M and D to V .
Finally when V receives M and D, V should apply the tag checking operation to M and D under K toverify the authenticity of M. If the tag checking operation outputs ‘valid’, V concludes that M is indeed
authentic.
Loosely speaking, MAC schemes are designed so that it is hard for an adversary to forge valid message
and tag pairs so that the schemes provide data origin authentication and data integrity.
The list of supported MAC schemes at this time is:
HMAC–SHA-1–160 with 20 octet or 160 bit keys
HMAC–SHA-1–80 with 20 octet or 160 bit keys
Both these MAC schemes are specified in IETF RFC 2104 [58] and ANSI X9.71 [5] based on the hashfunction SHA-1 specified in FIPS 180-1 [30]. Following the notation suggested in [58], here HMAC–
Hash–x denotes the HMAC function used in conjunction with the hash function Hash to produce message

SEC 1 - 3 Cryptographic Components

Page 31

tags of length x=8 octets or x bits. Both the supported MAC schemes are designed to be existentiallyunforgeable in the presence of an adversary capable of launching chosen-message attacks.
(Note that this document does not suggest that other MAC schemes should not be used elsewhere in asystem — it merely says that only the MAC schemes listed above should be used to build ECIES.)
For clarity in the remainder of this section, the generic operation of the MAC schemes by U and V
is described so that the use of the schemes can be specified precisely later on. The setup procedure
is described in Section 3.7.1, the key deployment procedure is specified in Section 3.7.2, the tagging
operation is specified in Section 3.7.3, and the tag checking operation is specified in Section 3.7.4.
3.7.1 Scheme Setup
U and V should perform the following setup procedure to use a MAC scheme:
1. U and V should establish which of the supported MAC schemes to use. Let MAC denote the MAC
scheme chosen, mackeylen denote the length in octets of the keys used by the scheme, and maclen
denote the length in octets of the tags produced by the scheme.
3.7.2 Key Deployment
U and V should perform the following key deployment procedure to use the MAC scheme:
1. U and V should establish a shared secret key K of length mackeylen octets. K should be chosenrandomly or pseudorandomly.
3.7.3 Tagging Operation
U should tag messages to send to V using the keys and parameters established during the setup procedureand the key deployment procedure as follows:
Input: An octet string M which is the data to be tagged.
Output: An octet string D of length maclen octets which is the tag on M, or ‘invalid’.
Actions: Compute the tag D on M as follows:
1. Convert M to a bit string M and K to a bit string K using the conversion routine specified in
Section 2.3.2.
2. Calculate the tag D on M using the selected MAC scheme under the shared secret key K:
D = MACK (M ):If the MAC scheme outputs ‘invalid’, output ‘invalid’ and stop.

Page 32

SEC 1: Elliptic Curve Cryptography Ver. 1.0

3. Convert D to an octet string D using the conversion routine specified in Section 2.3.1
4. Output the octet string D of length maclen octets.
3.7.4 Tag Checking Operation
V should check the authenticity of tagged messages from U using the keys and parameters establishedduring the setup procedure and the key deployment procedure as follows:
Input: The input to the tag checking operation is:
1. An octet string M which is the message.
2. An octet string D which is the purported tag on M.
Output: An indication of whether the tagged message is valid or not — either ‘valid’ or ‘invalid’.
Actions: Check the tag D on M as follows:
1. Convert M to a bit string M, D to a bit string D, and K to a bit string K using the conversion routine
specified in Section 2.3.2.
2. Calculate the tag D0 on M using the selected MAC scheme under the shared secret key K:
D0 = MACK (M ):If the MAC scheme outputs ‘invalid’, output ‘invalid’ and stop.
3. Compare D0 and D. If D0 = D, output ‘valid’, and if D0 6= D, output ‘invalid’.

3.8 Symmetric Encryption Schemes
This section specifies the symmetric encryption schemes supported in this document.
The symmetric encryption schemes will be used by the Elliptic Curve Integrated Encryption Scheme
specified in Section 5.1.
Symmetric encryption schemes are designed to be used by two entities — a sender U and a recipient V— when U wants to send a message M to V confidentially, and V wants to recover M.
Here symmetric encryption schemes are described in terms of an encryption operation, a decryption operation, and associated setup and key deployment procedures. U and V should use the scheme as follows
when they want to communicate. First U and V should use the setup and key deployment procedures toestablish which options to use the scheme with, and to create a shared secret key K to control the encryption and decryption operations. Then each time U wants to send a message M to V , U should apply theencryption operation to M under the shared secret key K to compute the encryption or ciphertext C of M,

SEC 1 - 3 Cryptographic Components

Page 33and convey C to V . Finally when V receives C, V should apply the decryption operation to C under K torecover the message M.
Loosely speaking, symmetric encryption schemes are designed so that it is hard for an adversary torecover information about messages (other than their length) from their ciphertexts. Thus they provide
data confidentiality.
The list of supported symmetric encryption schemes at this time is:
3-key TDES in CBC mode
XOR encryption scheme(Although only the two encryption schemes above are supported at this time, it is planned that support
for AES will be added as AES passes through the standardization procedures of ANSI and NIST.)(Note that the XOR encryption scheme should be used with care ... here it is recommended specificallyfor use with the elliptic curve integrated encryption scheme. Implementors considering its use in othercircumstances should be aware that it is only designed to provide semantic security when used to encrypta single message in the presence of adversaries capable of launching only passive attacks.)
3-key TDES in CBC mode is specified in ANSI X9.52 [2]. Here it is considered to use shared secret keysof length 24 octets or 192 bits — which are split up into 3 subkeys K1 , K2 , and K3 by interpreting theleftmost 8 octets or 64 bits as K1 , the middle 8 octets or 64 bits as K2 , and the rightmost 8 octets or 64
bits as K3 , and replacing the appropriate bits of K1 , K2 , and K3 with parity bits. Furthermore here the 8octet or 64 bit IV for TDES in CBC mode should always take the value 000000000000000016.
The XOR encryption scheme is the simple encryption scheme in which encryption consists of XORing
the key and the message, and decryption consists of XORing the key and the ciphertext to recover themessage. The XOR scheme is commonly used either with truly random keys when it is known as the‘one-time pad’, or with pseudorandom keys as a component in the construction of stream ciphers. The
XOR encryption scheme uses keys which are the same length as the message to be encrypted or the
ciphertext to be decrypted.
3-key TDES in CBC mode is designed to provide semantic security in the presence of adversaries launching chosen-plaintext and chosen-ciphertext attacks. The XOR encryption scheme is designed to provide
semantic security when used to encrypt a single message in the presence of adversaries capable of launching only passive attacks. (Although this limits use of the XOR encryption scheme in general, it is sufficient for the purposes of building ECIES. The same is true of TDES with a fixed IV .)(Note that this document does not suggest that other symmetric encryption schemes should not be used
elsewhere in a system — it merely says that only the symmetric encryption schemes listed above should
be used to build ECIES.)
For clarity in the remainder of this section, the generic operation of the symmetric encryption schemes
by U and V is described so that the use of the schemes can be specified precisely later on. The setup
procedure is described in Section 3.8.1, the key deployment procedure is specified in Section 3.8.2,
the encryption operation is specified in Section 3.8.3, and the decryption operation is specified in Section 3.8.4.

Page 34

SEC 1: Elliptic Curve Cryptography Ver. 1.0

3.8.1 Scheme Setup
U and V should perform the following setup procedure to use a symmetric encryption scheme:
1. U and V should establish which of the supported symmetric encryption schemes to use. Let ENC
denote the encryption scheme chosen, and enckeylen denote the length in octets of the keys usedby the scheme.
3.8.2 Key Deployment
U and V should perform the following key deployment procedure to use the symmetric encryption
scheme:1. U and V should establish a shared secret key K of length enckeylen octets. K should be chosenrandomly or pseudorandomly.
3.8.3 Encryption Operation
U should encrypt messages to send to V using the keys and parameters established during the setup
procedure and the key deployment procedure as follows:
Input: An octet string M which is the data to be encrypted.
Output: An octet string C which is the ciphertext corresponding to M, or ‘invalid’.
Actions: Compute the ciphertext C as follows:
1. Convert M to a bit string M and K to a bit string K using the conversion routine specified in
Section 2.3.2.
2. Calculate the encryption C of M using the encryption operation of the selected symmetric encryption scheme under the shared secret key K. If the encryption operation outputs ‘invalid’, output‘invalid’ and stop.
3. Convert C to an octet string C using the conversion routine specified in Section 2.3.1.
4. Output the octet string C.
3.8.4 Decryption Operation
V should decrypt ciphertext from U using the keys and parameters established during the setup procedureand the key deployment procedure as follows:
Input: An octet string C which is the ciphertext.

SEC 1 - 3 Cryptographic Components

Page 35

Output: An octet string M which is the decryption of C, or ‘invalid’.
Actions: Decrypt C as follows:
1. Convert C to a bit string C and K to a bit string K using the conversion routine specified in Section 2.3.2.
2. Calculate the decryption M of C using the decryption operation of the selected symmetric encryption scheme under the shared secret key K. If the decryption operation outputs ‘invalid’, output‘invalid’ and stop.
3. Convert M to an octet string M using the conversion routine specified in Section 2.3.1.
4. Output the octet string M.

Page 36

4

SEC 1: Elliptic Curve Cryptography Ver. 1.0

Signature Schemes

This section specifies the signature schemes based on ECC supported in this document.
Signature schemes are designed to be used by two entities — a signer U and a verifier V — when U
wants to send a message M in an authentic manner and V wants to verify the authenticity of M.
Here signature schemes are described in terms of a signing operation, a verifying operation, and associated setup and key deployment procedures. U and V should use the schemes as follows when theywant to communicate. First U and V should use the setup procedure to establish which options to use thescheme with, then U should use the key deployment procedure to select a key pair and V should obtain
U ’s public key — U will use the key pair to control the signing operation, and V will use the public key
to control the verifying operation. Then each time U wants to send a message M, U should apply thesigning operation to M under its key pair to obtain a signature S on M, form a signed message from M andS, and convey the signed message to V . Finally when V receives the signed message, V should apply theverifying operation to the signed message under U ’s public key to verify its authenticity. If the verifying
operation outputs ‘valid’, V concludes the signed message is indeed authentic.
There are two types of signature schemes, depending on the form of the signed message U must convey toV : signature schemes with appendix in which U must convey both M and S to V , and signature schemeswith message recovery in which M can be recovered from S, so U need convey only S to V .
Loosely speaking signature schemes are designed so that it is hard for an adversary who does not know
U ’s secret key to forge valid signed messages so that the schemes provide data origin authentication, data
integrity, and non-repudiation.
The only signature scheme supported at this time is the Elliptic Curve Digital Signature Algorithm(ECDSA). ECDSA is specified in Section 4.1.
See Appendix B for a commentary on the contents on this section, including implementation discussion,
security discussion, and references.

4.1 Elliptic Curve Digital Signature Algorithm
The Elliptic Curve Digital Signature Algorithm (ECDSA) is a signature scheme with appendix basedon ECC. It is designed to be existentially unforgeable, even in the presence of an adversary capable oflaunching chosen-message attacks.
The setup procedure for ECDSA is specified in Section 4.1.1, the key deployment procedure is specified
in Section 4.1.2, the signing operation is specified in Section 4.1.3, and the verifying operation is specified
in Section 4.1.4.

4.1.1 Scheme Setup
U and V should perform the following setup procedure to prepare to use ECDSA:SEC 1 - 4 Signature Schemes

Page 37

1. U should establish which of the hash functions supported in Section 3.5 to use when generating
signatures. Let Hash denote the hash function chosen, and hashlen denote the length in octets of
the hash values produced using Hash.
2. U should establish elliptic curve domain parameters T = ( p; a; b; G; n; h) or (m; f (x); a; b; G; n; h)at the desired security level. The elliptic curve domain parameters T should be generated using
the primitive specified in Section 3.1.1.1 or the primitive specified in Section 3.1.2.1. U should
receive an assurance that the elliptic curve domain parameters T are valid using one of the methods
specified in Section 3.1.1.2 or Section 3.1.2.2.
3. V should obtain in an authentic manner the hash function Hash and elliptic curve domain parameters T established by U .
V may also wish to receive an assurance that the elliptic curve domain parameters T are valid using oneof the methods specified in Section 3.1.1.2 or Section 3.1.2.2.
4.1.2 Key Deployment
U and V should perform the following key deployment procedure to prepare to use ECDSA:
1. U should establish an elliptic curve key pair (dU ; QU ) associated with T to use with the signaturescheme. The key pair should be generated using the primitive specified in Section 3.2.1.
2. V should obtain in an authentic manner the elliptic curve public key QU selected by U .
V may wish to receive an assurance that the elliptic curve public key QU is valid using one of the methods
specified in Section 3.2.2.
4.1.3 Signing Operation
U should sign messages using ECDSA using the keys and parameters established during the setup procedure and the key deployment procedure as follows:
Input: The signing operation takes as input an octet string M which is the message to be signed.
Output: A signature S = (r; s) on M consisting of a pair of integers r and s, or ‘invalid’.
Actions: Generate a signature S on M as follows:
1. Select an ephemeral elliptic curve key pair (k; R) with R = (xR ; yR ) associated with the elliptic
curve domain parameters T established during the setup procedure using the key pair generation
primitive specified in Section 3.2.1.
2. Convert the field element xR to an integer xR using the conversion routine specified in Section 2.3.9.

Page 38
3. Set r  xR

SEC 1: Elliptic Curve Cryptography Ver. 1.0(mod n). If r = 0, return to step 1.

4. Use the hash function selected during the setup procedure to compute the hash value:
H = Hash(M )of length hashlen octets as specified in Section 3.5. If the hash function outputs ‘invalid’, output‘invalid’ and stop.
5. Derive an integer e from H as follows:
5.1. Convert the octet string H to a bit string H using the conversion routine specified in Section 2.3.2.

5.2. Set E = H if dlog2 ne  8(hashlen), and set E equal to the leftmost dlog2 ne bits of H if
dlog2 ne < 8(hashlen).

5.3. Convert the bit string E to an octet string E using the conversion routine specified in Section 2.3.1.
5.4. Convert the octet string E to an integer e using the conversion routine specified in Section 2.3.8.
6. Compute:s  k 1 :(e + r:dU )(mod n):If s = 0, return to step 1.
7. Output S = (r; s).
4.1.4 Verifying Operation
V should verify signed messages from U using ECDSA using the keys and parameters established during
the setup procedure and the key deployment procedure as follows:
Input: The verifying operation takes as input:
1. An octet string M which is the message.
2. U ’s purported signature S = (r; s) on M.
Output: An indication of whether the purported signature on M is valid or not — either ‘valid’ or‘invalid’.
Actions: Verify the purported signature S on M as follows:
1. If r and s are not both integers in the interval [1; n1], output ‘invalid’ and stop.

SEC 1 - 4 Signature Schemes

Page 39

2. Use the hash function established during the setup procedure to compute the hash value:
H = Hash(M )of length hashlen octets as specified in Section 3.5. If the hash function outputs ‘invalid’, output‘invalid’ and stop.
3. Derive an integer e from H as follows:
3.1. Convert the octet string H to a bit string H using the conversion routine specified in Section 2.3.2.

3.2. Set E = H if dlog2 ne  8(hashlen), and set E equal to the leftmost dlog2 ne bits of H if
dlog2 ne < 8(hashlen).

3.3. Convert the bit string E to an octet string E using the conversion routine specified in Section 2.3.1.
3.4. Convert the octet string E to an integer e using the conversion routine specified in Section 2.3.8.
4. Compute:u1  e:s 1(mod n)and u2  r:s 1(mod n):5. Compute:R = (xR ; yR ) = u1 G + u2 QU :If R = O , output ‘invalid’ and stop.
6. Convert the field element xR to an integer xR using the conversion routine specified in Section 2.3.9.
7. Set v  xR(mod n).

8. Compare v and r — if v = r, output ‘valid’, and if v 6= r, output ‘invalid’.

Page 405

SEC 1: Elliptic Curve Cryptography Ver. 1.0

Encryption Schemes

This section specifies the public-key encryption schemes based on ECC supported in this document.
Public-key encryption schemes are designed to be used by two entities — a sender U and a recipient V— when U wants to send a message M to V confidentially, and V wants to recover M.
Here public-key encryption schemes are described in terms of an encryption operation, a decryption
operation, and associated setup and key deployment procedures. U and V should use the scheme asfollows when they want to communicate. First U and V should use the setup procedure to establish
which options to use the scheme with, then V should use the key deployment procedure to select a key
pair and U should obtain V ’s public key — U will use V ’s public key to control the encryption procedure,
and V will use its key pair to control the decryption operation. Then each time U wants to send a message
M to V , U should apply the encryption operation to M under V ’s public key to compute an encryption
or ciphertext C of M, and convey C to V . Finally when V receives C, V should apply the decryption
operation to C under its key pair to recover the message M.
Loosely speaking public-key encryption schemes are designed so that it is hard for an adversary whodoes not possess V ’s secret key to recover information about messages (other than their length) fromtheir ciphertexts. Thus the schemes provide data confidentiality.
The public-key encryption schemes specified in this section may be used to encrypt messages of any kind.
They may be used to transport keying data from U to V , or to encrypt information data directly. This
flexibility allows the schemes to be applied in a broad range of cryptographic systems. Nonetheless it isenvisioned that the majority of applications will apply the schemes for key transport, and subsequently
use the transported key in conjunction with a symmetric bulk encryption scheme to encrypt information
data. This is the traditional usage for public-key encryption schemes.
The only public-key encryption scheme supported at this time is the Elliptic Curve Integrated Encryption
Scheme (ECIES). ECIES is specified in Section 5.1.
See Appendix B for a commentary on the contents on this section, including implementation discussion,
security discussion, and references.

5.1 Elliptic Curve Integrated Encryption Scheme
The Elliptic Curve Integrated Encryption Scheme (ECIES) is a public-key encryption scheme basedon ECC. It is designed to be semantically secure in the presence of an adversary capable of launching
chosen-plaintext and chosen-ciphertext attacks.
(Note that the Elliptic Curve Integrated Encryption Scheme has a complex naming history. It is occasionally known instead as the Elliptic Curve Augmented Encryption Scheme or simply the Elliptic Curve
Encryption Scheme.)
The setup procedure for ECIES is specified in Section 5.1.1, the key deployment procedure is specified
in Section 5.1.2, the encryption operation is specified in Section 5.1.3, and the decryption operation is
specified in Section 5.1.4.

SEC 1 - 5 Encryption Schemes

Page 415.1.1 Scheme Setup
U and V should perform the following setup procedure to prepare to use ECIES:
1. V should establish which of the key derivation functions supported in Section 3.6 to use, andselect any options involved in the operation of the key derivation function. Let KDF denote thekey derivation function chosen. (In this edition the only possibility is ANSI-X9.63-KDF with theoption SHA-1.)
2. V should establish which of the MAC schemes supported in Section 3.7 to use, and select any
options involved in the operation of the MAC scheme. Let MAC denote the MAC scheme chosen,mackeylen denote the length in octets of the keys used by MAC, and maclen denote the length inoctets of tags produced by MAC.
3. V should establish which of the symmetric encryption schemes supported in Section 3.8 to use,and select any options involved in the operation of the encryption scheme. Let ENC denote theencryption scheme chosen, and enckeylen denote the length in octets of the keys used by ENC.
4. V should establish whether to use the ‘standard’ elliptic curve Diffie-Hellman primitive specified
in Section 3.3.1, or the elliptic curve cofactor Diffie-Hellman primitive specified in Section 3.3.2.
5. V should establish elliptic curve domain parameters T = ( p; a; b; G; n; h) or (m; f (x); a; b; G; n; h)at the desired security level. The elliptic curve domain parameters T should be generated using
the primitive specified in Section 3.1.1.1 or the primitive specified in Section 3.1.2.1. V should
receive an assurance that the elliptic curve domain parameters T are valid using one of the methods
specified in Section 3.1.1.2 or Section 3.1.2.2.
6. U should obtain in an authentic manner the selections made by V — the key derivation function
KDF, the MAC scheme MAC, the symmetric encryption scheme ENC, the elliptic curve domain
parameters T , and an indication whether to use the ‘standard’ elliptic curve Diffie-Hellman primitive or the cofactor Diffie-Hellman. U should also receive an assurance that the elliptic curve
domain parameters T are valid using one of the methods specified in Section 3.1.1.2 or Section 3.1.2.2.
7. U should establish whether or not to represent elliptic curve points using point compression.
5.1.2 Key Deployment
U and V should perform the following key deployment procedure to prepare to use ECIES:
1. V should establish an elliptic curve key pair (dV ; QV ) associated with the elliptic curve domain
parameters T established during the setup procedure. The key pair should be generated using theprimitive specified in Section 3.2.1.

Page 42

SEC 1: Elliptic Curve Cryptography Ver. 1.0

2. U should obtain in an authentic manner the elliptic curve public key QV selected by V . If the‘standard’ elliptic curve Diffie-Hellman primitive is being used, U should receive an assurance that
QV is valid using one of the methods specified in Section 3.2.2, and if the elliptic curve cofactor
Diffie-Hellman primitive is being used, U should receive an assurance that QV is at least partiallyvalid using one of the methods specified in Section 3.2.2 or Section 3.2.3.
5.1.3 Encryption Operation
U should encrypt messages using ECIES using the keys and parameters established during the setup
procedure and the key deployment procedure as follows:
Input: The input to the encryption operation is:
1. An octet string M which is the message to be encrypted.
2. (Optional) Two octet strings SharedIn f o1 and SharedIn f o2 which consist of some data shared by
U and V .
Output: An octet string C which is an encryption of M, or ‘invalid’.
Actions: Encrypt M as follows:
1. Select an ephemeral elliptic curve key pair (k; R) with R = (xR ; yR ) associated with the elliptic curve
domain parameters T established during the setup procedure. Generate the key pair using the key
pair generation primitive specified in Section 3.2.1.
2. Convert R to an octet string R using the conversion routine specified in Section 2.3.3. Decide
whether or not to represent R using point compression according to the convention establishedduring the setup procedure.
3. Use one of the Diffie-Hellman primitives specified in Section 3.3 to derive a shared secret field
element z 2 F q from the ephemeral secret key k and V ’s public key QV obtained during the key
deployment procedure. If the Diffie-Hellman primitive outputs ‘invalid’, output ‘invalid’ and stop.
Decide whether to use the ‘standard’ elliptic curve Diffie-Hellman primitive or the elliptic curve
cofactor Diffie-Hellman primitive according to the convention established during the setup procedure.
4. Convert z 2 F q to an octet string Z using the conversion routine specified in Section 2.3.5.
5. Use the key derivation function KDF established during the setup procedure to generate keying
data K of length enckeylen + mackeylen octets from Z and [SharedIn f o1]. If the key derivation
function outputs ‘invalid’, output ‘invalid’ and stop.
6. Parse the leftmost enckeylen octets of K as an encryption key EK and the rightmost mackeylen
octets of K as a MAC key MK.

SEC 1 - 5 Encryption Schemes

Page 43

7. Use the encryption operation of the symmetric encryption scheme ENC established during the
setup procedure to encrypt M under EK as ciphertext EM. If the encryption scheme outputs ‘invalid’, output ‘invalid’ and stop.
8. Use the tagging operation of the MAC scheme MAC established during the setup procedure tocompute the tag D on EM k [SharedIn f o2] under MK. If the MAC scheme outputs ‘invalid’, output‘invalid’ and stop.
9. Output C = R k EM k D.
5.1.4 Decryption Operation
V should decrypt ciphertext using ECIES using the keys and parameters established during the setup
procedure and the key deployment procedure as follows:
Input: The input to the decryption operation is:
1. An octet string C which is the ciphertext.
2. (Optional) Two octet strings SharedIn f o1 and SharedIn f o2 which consist of some data shared by
U and V .
Output: An octet string M which is the decryption of C, or ‘invalid’.
Actions: Decrypt C as follows:
1. If the leftmost octet of C is 0216 or 0316 , parse the leftmost dlog2 qe + 1 octets of C as an octet
string R, the rightmost maclen octets of C as an octet string D, and the remaining octets of C as anoctet string EM. If the leftmost octet of C is 0416 , parse the leftmost 2dlog2 qe + 1 octets of C as anoctet string R, the rightmost maclen octets of C as an octet string D, and the remaining octets of C
as an octet string EM. If the leftmost octet of C is not 0216 , 0316 , or 0416 , output ‘invalid’ and stop.
2. Convert the octet string R to an elliptic curve point R = (xR ; yR ) associated with the elliptic curve
domain parameters T established during the setup procedure using the conversion routine specified
in Section 2.3.4. If the conversion routine outputs ‘invalid’, output ‘invalid’ and stop.
3. If the ‘standard’ elliptic curve Diffie-Hellman primitive is being used, receive an assurance that
R is a valid elliptic curve public key using one of the methods specified in Section 3.2.2. If theelliptic curve cofactor Diffie-Hellman primitive is being used, receive an assurance that R is atleast a partially valid elliptic curve public key using one of the methods specified in Section 3.2.2
Section 3.2.3. If an appropriate assurance is not obtained, output ‘invalid’ and stop.
4. Use one of the Diffie-Hellman primitives specified in Section 3.3 to derive a shared secret field
element z 2 F q from V ’s secret key dV established during the key deployment procedure and the
public key R. If the Diffie-Hellman primitive outputs ‘invalid’, output ‘invalid’ and stop. DecidePage 44

SEC 1: Elliptic Curve Cryptography Ver. 1.0

whether to use the ‘standard’ elliptic curve Diffie-Hellman primitive or the elliptic curve cofactor
Diffie-Hellman primitive according to the convention established during the setup procedure.
5. Convert z 2 F q to an octet string Z using the conversion routine specified in Section 2.3.5.
6. Use the key derivation function KDF established during the setup procedure to generate keying
data K of length enckeylen + mackeylen octets from Z and [SharedIn f o1]. If the key derivation
function outputs ‘invalid’, output ‘invalid’ and stop.
7. Parse the leftmost enckeylen octets of K as an encryption key EK and the rightmost mackeylen
octets of K as a MAC key MK.
8. Use the tag checking operation of the MAC scheme MAC established during the setup procedure
to check that D is the tag on EM k [SharedIn f o2] under MK. If the MAC scheme outputs ‘invalid’,
output ‘invalid’ and stop.
9. Use the decryption operation of the symmetric encryption scheme ENC established during the
setup procedure to decrypt EM under EK as M. If the encryption scheme outputs ‘invalid’, output‘invalid’ and stop.
10. Output M.
Note that when implementing the above decryption operation on a constrained device, it may be desirable
to perform the symmetric decryption operation (step 9) before the tag checking operation (step 8). Thisvariant is allowed. However implementers of this variant should guard against the possibility that theoutput of step 9 is available to attackers regardless of the output of step 8.

SEC 1 - 6 Key Agreement Schemes

6

Page 45

Key Agreement Schemes

This section specifies the key agreement schemes based on ECC supported in this document.
Key agreement schemes are designed to be used by two entities — an entity U and an entity V — when U
and V want to establish shared keying data that they can later use to control the operation of a symmetric
cryptographic scheme.
Here key agreement schemes are described in terms of a key agreement operation, and associated setup
and key deployment procedures. U and V should use the schemes as follows when they want to establish
keying data. First U and V should use the setup procedure to establish which options to use the scheme
with, then they should use the key deployment procedure to select key pairs and exchange public keys.
Finally when U and V want to establish keying data they should simultaneously use the key agreement
operation. Provided U and V operate the key agreement operation with corresponding keys as inputs,
they will obtain the same keying data.
Note that this document does not address how specific keys should be derived from keying data established using a key agreement scheme. This detail is left to be determined on an application by applicationbasis. Some applications may wish simply to use the keying data directly as a key, others may wish to
split the keying data into more than one key, and others may wish to process the keying data to exclude
weak keys.
Key agreement schemes are designed to meet a wide variety of security goals depending on how they
are applied — security goals that the schemes described here are designed to provide include unilateralimplicit key authentication, mutual implicit key authentication, known-key security, and forward secrecy,in the presence of adversaries capable of launching both passive and active attacks.
Two key agreement schemes are supported at this time: the elliptic curve Diffie-Hellman scheme, and theelliptic curve MQV scheme. The elliptic curve Diffie-Hellman scheme is specified in Section 6.1, andthe elliptic curve MQV scheme is specified in Section 6.2.
See Appendix B for a commentary on the contents on this section, including implementation discussion,
security discussion, and references.

6.1 Elliptic Curve Diffie-Hellman Scheme
The elliptic curve Diffie-Hellman scheme is a key agreement scheme based on ECC. It is designed toprovide a variety of security goals depending on its application — goals it can provide include unilateralimplicit key authentication, mutual implicit key authentication, known-key security, and forward secrecy— depending on issues like whether or not public keys are exchanged in an authentic manner, and whether
key pairs are ephemeral or static. See Appendix B for a further discussion.
The setup procedure for the elliptic curve Diffie-Hellman scheme is specified in Section 6.1.1, the key
deployment procedure is specified in Section 6.1.2, and the key agreement operation is specified in Section 6.1.3.

Page 46

SEC 1: Elliptic Curve Cryptography Ver. 1.0

6.1.1 Scheme Setup
U and V should perform the following setup procedure to prepare to use the elliptic curve Diffie-Hellman
scheme:1. U and V should establish which of the key derivation functions supported in Section 3.6 to use,and select any options involved in the operation of the key derivation function. Let KDF denotethe key derivation function chosen.
2. U and V should establish whether to use the ‘standard’ elliptic curve Diffie-Hellman primitive
specified in Section 3.3.1, or the elliptic curve cofactor Diffie-Hellman primitive specified in Section 3.3.2.
3. U and V should establish at the desired security level elliptic curve domain parameters T =( p; a; b; G; n; h) or (m; f (x); a; b; G; n; h). The elliptic curve domain parameters T should be generated using the primitive specified in Section 3.1.1.1 or the primitive specified in Section 3.1.2.1.
Both U and V should receive an assurance that the elliptic curve domain parameters T are valid
using one of the methods specified in Section 3.1.1.2 or Section 3.1.2.2.
6.1.2 Key Deployment
U and V should perform the following key deployment procedure to prepare to use the elliptic curve
Diffie-Hellman scheme:
1. U should establish an elliptic curve key pair (dU ; QU ) associated with the elliptic curve domain
parameters T established during the setup procedure. The key pair should be generated using theprimitive specified in Section 3.2.1.
2. V should establish an elliptic curve key pair (dV ; QV ) associated with the elliptic curve domain
parameters T established during the setup procedure. The key pair should be generated using theprimitive specified in Section 3.2.1.
3. U and V should exchange their public keys QU and QV .
4. If the ‘standard’ elliptic curve Diffie-Hellman primitive is being used, U should receive an assurance that QV is valid using one of the methods specified in Section 3.2.2, and if the elliptic curve
cofactor Diffie-Hellman primitive is being used, U should receive an assurance that QV is at least
partially valid using one of the methods specified in Section 3.2.2 or Section 3.2.3.
5. If the ‘standard’ elliptic curve Diffie-Hellman primitive is being used, V should receive an assurance that QU is valid using one of the methods specified in Section 3.2.2, and if the elliptic curve
cofactor Diffie-Hellman primitive is being used, V should receive an assurance that QU is at least
partially valid using one of the methods specified in Section 3.2.2 or Section 3.2.3.

SEC 1 - 6 Key Agreement Schemes

Page 47

6.1.3 Key Agreement Operation
U and V should perform the key agreement operation described in this section to establish keying datausing the elliptic curve Diffie-Hellman scheme. For clarity U ’s use of the operation is described. V ’s useof the operation is analogous, but with the roles of U and V reversed.
U should establish keying data with V using the keys and parameters established during the setup procedure and the key deployment procedure as follows:
Input: The input to the key agreement operation is:
1. An integer keydatalen which is the number of octets of keying data required.
2. (Optional) An octet string SharedIn f o which consists of some data shared by U and V .
Output: An octet string K which is the keying data of length keydatalen octets, or ‘invalid’.
Actions: Establish keying data as follows:
1. Use one of the Diffie-Hellman primitives specified in Section 3.3 to derive a shared secret field
element z 2 F q from U ’s secret key dU established during the key deployment procedure and V ’s
public key QV obtained during the key deployment procedure. If the Diffie-Hellman primitive
outputs ‘invalid’, output ‘invalid’ and stop. Decide whether to use the ‘standard’ elliptic curve
Diffie-Hellman primitive or the elliptic curve cofactor Diffie-Hellman primitive according to theconvention established during the setup procedure.
2. Convert z 2 F q to an octet string Z using the conversion routine specified in Section 2.3.5.
3. Use the key derivation function KDF established during the setup procedure to generate keying
data K of length keydatalen octets from Z and [SharedIn f o]. If the key derivation function outputs‘invalid’, output ‘invalid’ and stop.
4. Output K.

6.2 Elliptic Curve MQV Scheme
The elliptic curve MQV scheme is a key agreement scheme based on ECC. It is designed to provide avariety of security goals depending on its application — goals it can provide include mutual implicit key
authentication, known-key security, and forward secrecy — depending on issues like whether or not U
and V both contribute ephemeral key pairs. See Appendix B for a further discussion.
The setup procedure for the elliptic curve MQV scheme is specified in Section 6.2.1, the key deployment
procedure is specified in Section 6.2.2, and the key agreement operation is specified in Section 6.2.3.

Page 48

SEC 1: Elliptic Curve Cryptography Ver. 1.0

6.2.1 Scheme Setup
U and V should perform the following setup procedure to prepare to use the elliptic curve MQV scheme:
1. U and V should establish which of the key derivation functions supported in Section 3.6 to use,and select any options involved in the operation of the key derivation function. Let KDF denotethe key derivation function chosen.
2. U and V should establish at the desired security level elliptic curve domain parameters T =( p; a; b; G; n; h) or (m; f (x); a; b; G; n; h). The elliptic curve domain parameters T should be generated using the primitive specified in Section 3.1.1.1 or the primitive specified in Section 3.1.2.1.
Both U and V should receive an assurance that the elliptic curve domain parameters T are valid
using one of the methods specified in Section 3.1.1.2 or Section 3.1.2.2.

6.2.2 Key Deployment
U and V should perform the following key deployment procedure to prepare to use the elliptic curve
MQV scheme:
1. U should establish two elliptic curve key pairs (d1;U ; Q1;U ) and (d2;U ; Q2;U ) associated with theelliptic curve domain parameters T established during the setup procedure. The key pairs shouldboth be generated using the primitive specified in Section 3.2.1.
2. V should establish two elliptic curve key pairs (d1;V ; Q1;V ) and (d2;V ; Q2;V ) associated with theelliptic curve domain parameters T established during the setup procedure. The key pairs shouldboth be generated using the primitive specified in Section 3.2.1.
3. U should obtain in an authentic manner the first elliptic curve public key Q1;V selected by V . U
should receive an assurance that Q1;V is valid using one of the methods specified in Section 3.2.2.
4. V should obtain in an authentic manner the first elliptic curve public key Q1;U selected by U . V
should receive an assurance that Q1;U is valid using one of the methods specified in Section 3.2.2.
5. U and V should exchange their second public keys Q2;U and Q2;V .
6. U should receive an assurance that Q2;V is at least partially valid using one of the methods specified
in Section 3.2.2 or Section 3.2.3.
7. V should receive an assurance that Q2;U is at least partially valid using one of the methods specified
in Section 3.2.2 or Section 3.2.3.

SEC 1 - 6 Key Agreement Schemes

Page 49

6.2.3 Key Agreement Operation
U and V should perform the key agreement operation described in this section to establish keying datausing the elliptic curve MQV scheme. For clarity U ’s use of the operation is described. V ’s use of theoperation is analogous, but with the roles of U and V reversed.
U should establish keying data with V using the keys and parameters established during the setup procedure and the key deployment procedure as follows:
Input: The input to the key agreement operation is:
1. An integer keydatalen which is the number of octets of keying data required.
2. (Optional) An octet string SharedIn f o which consists of some data shared by U and V .
Output: An octet string K which is the keying data of length keydatalen octets, or ‘invalid’.
Actions: Establish keying data as follows:
1. Use the elliptic curve MQV primitive specified in Section 3.4 to derive a shared secret field elementz 2 F q from U ’s key pairs (d1;U ; Q1;U ) and (d2;U ; Q2;U ) established during the key deployment
procedure and V ’s public keys Q1;V and Q2;V obtained during the key deployment procedure. If the
MQV primitive outputs ‘invalid’, output ‘invalid’ and stop.
2. Convert z 2 F q to an octet string Z using the conversion routine specified in Section 2.3.5.
3. Use the key derivation function KDF established during the setup procedure to generate keying
data K of length keydatalen octets from Z and [SharedIn f o]. If the key derivation function outputs‘invalid’, output ‘invalid’ and stop.
4. Output K.

Page 50A

SEC 1: Elliptic Curve Cryptography Ver. 1.0

Glossary

This section supplies a glossary to the terms and notation used in this document.
The section is organized as follows. Section A.1 lists the terms used in this document, Section A.2 lists
the acronyms used, and Section A.3 specifies the notation used.

A.1

Terms

Terms used in this document include:
active attack

The ability of an adversary of a cryptographic scheme to subvert
communications between entities by deleting, injecting, substituting, or generally subverting messages in any way.

addition rule

An addition rule describes the addition of two elliptic curve points
P1 and P2 to produce a third elliptic curve point P3 . See Section 2.2.

base point

A distinguished point G on an elliptic curve.

binary polynomial

A polynomial whose coefficients are either 0’s or 1’s.

bit string

A bit string is an ordered sequence of 0’s and 1’s.

certificate

The public key and identity of an entity together with some otherinformation, rendered unforgeable by signing this information withthe secret key of a Certification Authority.

Certification
Authority

A Center trusted by one or more entities to create and assign certificates.

characteristic 2 finitefield

A finite field containing 2m elements, where m  1 is an integer.

chosen-ciphertext
attackThe ability of an adversary of an encryption scheme to obtain thedecryptions of ciphertexts of its choice in an attempt to compromise
the scheme.

chosen-message
attackThe ability of an adversary of a signature scheme to obtain signatures on messages of its choice in an attempt to compromise thescheme. Or, similarly the ability of an adversary of a MAC scheme
to obtain tags on messages of its choice in an attempt to compromise
the scheme.

chosen-plaintext
attackThe ability of an adversary of an encryption scheme to obtain theencryptions of plaintexts of its choice in an attempt to compromise
the scheme.

ciphertext

The result of applying an encryption operation to a message.

SEC 1 - A Glossary

Page 51

cryptographic scheme

A cryptographic scheme consists of an unambiguous specificationof a set of operations capable of providing a security service whenproperly implemented and maintained.

data confidentiality

The assurance that data is unintelligible to unauthorized parties.

data integrity

The assurance that data has not been modified by unauthorized parties.

data origin
authentication

The assurance that the purported origin of data is correct.

elliptic curve

An elliptic curve over F q is a set of points which satisfy a certain
equation specified by two parameters, a and b, which are elementsof the field F q . See Section 2.2.

elliptic curve domain
parameters

Elliptic curve domain parameters are comprised of a field size q, a
reduction polynomial f (x) in the case q = 2m , two elements a, b in
F q which define an elliptic curve E over F q , a point G of prime orderin E (F q ), the order n of G, and the cofactor h. See Section 3.1.

elliptic curve key pair

Given particular elliptic curve domain parameters, an elliptic curve
key pair (d ; Q) consists of an elliptic curve secret key d and thecorresponding elliptic curve public key Q.

elliptic curve point

If E is an elliptic curve defined over F q , then an elliptic curve point
P is either a pair of field elements (xP ; yP ) (where xP ; yP 2 F q ) suchthat the values x = xP and y = yP satisfy the equation defining E, ora special point O called the point at infinity.

elliptic curve public
key

Given particular elliptic curve domain parameters, and an elliptic
curve secret key d, the corresponding elliptic curve public key Q isthe elliptic curve point Q = dG, where G is the base point.

elliptic curve secretkey

Given particular elliptic curve domain parameters, an elliptic curve
secret key d is an integer in the interval [1; n 1], where n is theprime order of the base point G.

encryption scheme

An encryption scheme is a cryptographic scheme consisting of an
encryption operation and a decryption operation which is capable ofproviding data confidentiality.

entityA party involved in the operation of a cryptographic system.

ephemeral

Ephemeral data is relatively short-lived. Usually ephemeral data
refers to data specific to a particular execution of a cryptographic
scheme.

Page 52

SEC 1: Elliptic Curve Cryptography Ver. 1.0

existentiallyunforgeable

A signature scheme is existentially unforgeable if it is infeasible foran adversary to forge a signature on any message that has not previously been signed by the scheme’s legitimate user. Similarly a MAC
scheme is existentially unforgeable if it is infeasible for an adversary
to forge the tag on any message that has not previously been taggedby one of the scheme’s legitimate users.

forward secrecy

The assurance that a session key established between some parties
will not be compromised by the compromise of some of the parties’ static secret keys in the future. Also known as perfect forward
secrecy.

hash function(cryptographic hashfunction)

A cryptographic hash function is a function which maps bit strings
from a large (possibly very large) domain into a smaller range. The
function possesses the following properties: it is computationallyinfeasible to find any input which maps to a randomly given output,
and nobody can exhibit a pair of distinct inputs which map to thesame output.

implicit key
authentication

A key establishment scheme provides implicit key authentication if
only authorized parties are possibly capable of computing any session key.

irreducible binary
polynomial

A binary polynomial f (x) is irreducible if it does not factor over F 2
as a product of two or more binary polynomials, each of degree lessthan the degree of f (x).

key(cryptographic key)

A parameter that determines the execution of a cryptographic operation such as the transformation from plaintext to ciphertext and viceversa, the synchronized generation of keying material, or a digital
signature computation or validation.

key agreement scheme

A key agreement scheme is a key establishment scheme in which
the keying data established is a function of contributions provided
by each party to the scheme in such a way that no party can predetermine the value of the keying data.

key derivation
function

A key derivation function is a function which takes as input a sharedsecret value and outputs keying data suitable for later cryptographicuse.

key establishment
schemeA key establishment scheme is a cryptographic scheme which reveals only to its legitimate users keying data suitable for subsequent
cryptographic use by cryptographic schemes.

keying data

Data suitable for use as cryptographic keys.

SEC 1 - A Glossary

Page 53

known-key security

The assurance that a session key established by an execution of a key
establishment scheme will not be compromised by the compromiseof other session keys.

MAC scheme

A MAC scheme is a cryptographic scheme consisting of a message
tagging operation and a tag checking operation which is capable ofproviding data origin authentication and data integrity.

non-repudiation

The assurance that the origin and integrity of data can be proved toa third party.

octet

An octet is a bit string of length 8. An octet is represented by a hexadecimal string of length 2. The first hexadecimal digit represents
the four leftmost bits of the octet, and the second hexadecimal digit
represents the four rightmost bits of the octet. For example, 9D represents the bit string 10011101. An octet also represents an integer
in the interval [0; 255]. For example, 9D represents the integer 157.

octet string

An octet string is an ordered sequence of octets.

order of a curve

The order of an elliptic curve E defined over the field F q is the number of points on the elliptic curve E, including O . This is denoted by#E (F q ).

order of a point

The order of a point P is the smallest positive integer n such thatnP = O (the point at infinity).

partially valid elliptic
curve public key

An elliptic curve public key Q = (xQ ; yQ ) is partially valid if the values x = xQ and y = yQ satisfy the defining equation of the associatedelliptic curve E, but it is not necessarily the case that Q = dG forsome d. The elliptic curve public key partial validation primitive in
Section 3.2.3.1 checks whether or not an elliptic curve public key ispartially valid.

passive attack

The ability of an adversary of a cryptographic scheme merely toobserve entities communicating using the scheme.

pentanomial

A binary polynomial of the form xm + xk3 + xk2 + xk1 + 1, where 1 
k1 < k2 < k3  m 1.

plaintext

A message to be encrypted; the opposite of ciphertext.

point compression

Point compression allows a point P = (xP ; yP ) to be represented
compactly using xP and a single additional bit ỹP derived from xPand yP . See Section 2.3.

prime finite fieldA finite field containing p elements, where p is an odd prime number.

Page 54

SEC 1: Elliptic Curve Cryptography Ver. 1.0

primitive(cryptographic
primitive)

A cryptographic primitive is an operation not by itself capable ofproviding a security service, but which can be incorporated in a cryptographic scheme.

public key

In a public-key scheme, that key of an entity’s key pair which can be
publicly known.

public-key
cryptographic scheme

A cryptographic scheme in which each operation is controlled by
one of two keys; either the public key or the private key. The two
keys have the property that, given the public key, it is computationally infeasible to derive the private key. Also known as an asymmetric cryptographic scheme.

reduction polynomial

The irreducible binary polynomial f (x) of degree m that is used todetermine a representation of F 2m .

scalar multiplication

If k is a positive integer, then k  P or kP denotes the point obtainedby adding together k copies of the point P. The process of computing
kP from P and k is called scalar multiplication.

secret key

In a public-key system, that key of an entity’s key pair which must
be known only by that entity. Also known as a private key.

semantically secure

An encryption scheme is semantically secure if it is infeasible for anadversary to learn anything from ciphertext about the corresponding
plaintext apart from the length of the plaintext.

session key

A key (usually short-lived) established using a key establishment
scheme.

shared secret value

An intermediate value in a key establishment scheme from which
keying data is derived.

signature scheme

A signature scheme is a cryptographic scheme consisting of a signing operation and a verifying operation which is capable of providing data origin authentication, data integrity, and non-repudiation.

staticStatic data is relatively long-lived. Usually static data refers to data
common to a number of executions of a cryptographic scheme.

symmetric
cryptographic scheme

A cryptographic scheme in which each operation is controlled by thesame key.

trinomial

A binary polynomial of the form xm + xk + 1, where 1  k  munknown key-shareresilience

The assurance that all the parties who share a session key are aware
which parties they share the key with.

1.

SEC 1 - A Glossary

A.2

Page 55

valid elliptic curve
domain parameters

Elliptic curve domain parameters are valid if they satisfy the arithmetic requirements of elliptic curve domain parameters. Equivalently elliptic curve domain parameters are valid if they have been
generated as specified in Section 3.1.1.1 or 3.1.2.1. The elliptic
curve domain parameter validation primitives in Sections 3.1.1.2.1
and 3.1.2.2.1 check whether or not elliptic curve domain parameters
are valid.

valid elliptic curve
public key

An elliptic curve public key Q = (xQ ; yQ ) is valid if it satisfies thearithmetic requirements of an elliptic curve public key — namelythat Q = dG for some d in the interval [1; n 1] where G is the basepoint of the associated elliptic curve domain parameters and n is
the order of G. The elliptic curve public key validation primitive in
Section 3.2.2.1 checks whether or not an elliptic curve public key isvalid.

x-coordinate

The x-coordinate of an elliptic curve point P = (xP ; yP ) is xP .

y-coordinate

The y-coordinate of an elliptic curve point P = (xP ; yP ) is yP .

Acronyms

The acronyms used in this document denote:
AES

Advanced Encryption Standard.

ANSI

American National Standards Institute.

ASN.1

Abstract Syntax Notation One.

CA

Certification Authority.

DES

Data Encryption Standard. See [29].

DSA

Digital Signature Algorithm. See [31].

EC

Elliptic Curve.

ECC

Elliptic Curve Cryptography.

ECDH

Elliptic Curve Diffie-Hellman.

ECDLP

Elliptic Curve Discrete Logarithm Problem.

ECDSA

Elliptic Curve Digital Signature Algorithm. See Section 4.1.

ECIES

Elliptic Curve Integrated Encryption Scheme. See Section 5.1.

ECMQV

Elliptic Curve Menezes-Qu-Vanstone.

FSML

Financial Services Markup Language.

Page 56

SEC 1: Elliptic Curve Cryptography Ver. 1.0

FSTC

Financial Services Technology Consortium.

HMAC

Hash-based Message Authentication Code. See [58].

IECInternational Electrotechnical Commission.

IEEE

Institute of Electrical and Electronics Engineers.

IETF

Internet Engineering Task Force.

ISO

International Organization for Standardization.

MQV

Menezes-Qu-Vanstone. See [60].

NIST(U.S.) National Institute of Standards and Technology.

PKI

Public Key Infrastructure.

PKIX

Public Key Infrastructure for the Internet.

SHA-1

Secure Hash Algorithm Revision One. See [30].

SSL

Secure Sockets Layer.

TDES

Triple Data Encryption Standard. See [2].

TLS

Transport Layer Security.

WAP

Wireless Application Protocol.

WTLS

Wireless Transport Layer Security.

A.3

Notation

The notation adopted in this document is:kX kLength in octets of the octet string X .

[X ]Indicates that the inclusion of X is optional.

[x; y]The interval of integers between and including x and y.

bxc

Floor: the largest integer  x. For example, b5c = 5 and b5:3c = 5.

dxe

Ceiling: the smallest integer  x. For example, d5e = 5 and d5:3e =6.

x mod nThe unique remainder r, 0  r  n
example, 23 mod 7 = 2.

C

Ciphertext.

d

An EC private key.

E

An elliptic curve over the field F q defined by a and b.

1, when x is divided by n. For

SEC 1 - A Glossary

Page 57

E (F q )The set of all points on an elliptic curve E defined over F q and including the point at infinity O .

#E (F q )If E is defined over F q , then #E (F q ) denotes the number of points
on the curve (including the point at infinity O ). #E (F q ) is called theorder of the curve E.

F 2m

The finite field containing 2m elements, where m is a positive integer.

Fp

The finite field containing p elements, where p is a prime.

Fq

The finite field containing q elements. In this document attention isrestricted to the cases that q is an odd prime number (p) or a powerof 2 (2m ).

GA distinguished point on an elliptic curve called the base point or
generating point.

gcd(x; y)The greatest common divisor of positive integers x and y.

hh = #E (F q )=n, where n is the order of the base point G. h is called
the co-factor.

k

An EC private key specific to one particular instance of a cryptographic scheme.

K

Keying data.

log2 xThe logarithm of x to the base 2.

m

The degree of the finite field F 2m .

M

A message.

modModulo.

mod f (x)Arithmetic modulo the polynomial f (x).

mod nArithmetic modulo n.

n

The order of the base point G.

O

A special point on an elliptic curve, called the point at infinity. Thisis the additive identity of the elliptic curve group.

p

An odd prime number.

P

An EC point.

q

The number of elements in the field F q .

Q

An EC public key.

R

An EC public key specific to one particular instance of a cryptographic scheme.

S

A digital signature.

Page 58

SEC 1: Elliptic Curve Cryptography Ver. 1.0

T

Elliptic curve domain parameters.

U, V

Entities.

X kY
X Y

Concatenation of two strings X and Y . X and Y are either both bit
strings or both octet strings.
Bitwise exclusive-or of two bit strings X and Y of the same bit
length.

xPThe x-coordinate of a point P.

yP

The y-coordinate of a point P.

ỹP

The representation of the y-coordinate of a point P when point compression is used.

z, or ZA shared secret value. z denotes a shared secret integer or field element, and Z a shared secret bit string or octet string.

Zp

The set of integers modulo p, where p is an odd prime number.

Furthermore positional notation is used to indicate the association of a value to a particular entity. For
example dU denotes an EC private key owned by entity U . Occasionally positional notation is also used
to indicate a counter value associated with some data, or to indicate the base in which a particular value
is being expressed if there is some possibility of ambiguity. For example, Hash1 denotes the value ofHashi when the counter i has value 1, and 0116 denotes that the value 01 is written in hexadecimal.
With the exception of notation that has been well-established in other documents, where possible in thisdocument capital letters are used in variable names that denote bit strings or octet strings, and capitalletters are excluded from variable names that denote field elements or integers. For example, d is used todenote the integer that specifies an EC private key, and M is used to denote the octet string to be signed
using a signature scheme.

SEC 1 - B Commentary

B

Page 59

CommentaryThis section provides a commentary on the main body of this document, including implementation discussion, security discussion, and references.
The aim of this section is to supply implementers with relevant guidance. However the section does not
attempt to provide exhaustive information but rather focuses on giving basic information and including
pointers to references which contain additional material. Furthermore the section concentrates on supplying information specific to ECC rather than providing extensive information on components like SHA-1
and TDES which are specified elsewhere.
The information in this section is current as of September 2000. The information is likely to change overtime, and implementers should therefore survey the state-of-the-art at the time of implementation andcarry out periodic reviews subsequent to deployment.
This section is organized as follows. Sections B.1 through B.5 respectively provide commentary on
Sections 2 through 6 of the main body of this document. Section B.6 supplies information regarding thealignment of this document with other standards efforts which include ECC.

B.1 Commentary on Section 2 - Mathematical Foundations
This section provides a commentary on Section 2 of the main body of this document.
Finite fields and elliptic curves have been studied as mathematical objects for hundreds of years. The
body of literature on these structures is vast. Introductions to finite fields can be found in the books ofJungnickel [49], Lidl and Neiderreiter [61], and McEliece [63]. An introduction to elliptic curves can befound in the book of Silverman [81].
Elliptic curves over finite fields were first proposed for use to build cryptographic schemes in 1985 by
Koblitz [52] and Miller [68]. Excellent treatments focusing on ECC are contained in Blake, Seroussi,
and Smart [12], Koblitz [54], Koblitz, Menezes, and Vanstone [55], and Menezes [64].
The security of all cryptographic schemes based on ECC relies on the elliptic curve discrete logarithm
problem or ECDLP. The ECDLP is stated as follows in the case of interest here - namely when the elliptic
curve in question has order divisible by a large prime n.
Let E be an elliptic curve defined over a finite field F q , and let G 2 E (F q ) be a point on E of large prime
order n. The ECDLP is, given E, G, and a scalar multiple Q of G, to determine an integer l such thatQ = lG.
No general subexponential algorithms are known for the ECDLP. The best general algorithms known
to date are based on the Pollard-ρ method and the Pollard-λpmethod [76]. The Pollard-ρ method takes
about πn=2 steps, and the Pollard-λ method takes about 2 n steps. Both methods can be parallelized
effectively - see [84].

p

Gallant, Lambert, and Vanstone [35], andp Wiener and Zuccherato [89] recently showed that the Pollard-ρ
method can be sped up by a factor of 2. Thus the expected running time of the Pollard-ρ method with

Page 60

this speedup is

SEC 1: Elliptic Curve Cryptography Ver. 1.0

pπn 4 steps.
=

which isThey also showed that this speedup can be enhanced when E is an elliptic curve over F 2ed pedefined over F 2 . In this case they show that the Pollard-ρ method can be sped up by a factor of 2d. For
example, the Koblitz curve E : y2 + xy = x3 + x2 + 1 over F 2163 has the property that #E (F 2163 ) = 2n where
n is a 162-bit prime. As a result of the enhancement to the Pollard-ρ method, the ECDLP in E (F 2163 ) canbe solved in about 277 steps as opposed to the 281 steps required to solve the ECDLP for a random curveof similar order.
Table 2 below illustrates the difficulty of the ECDLP. It contains estimates in MIPS years of the computing
power required to solve the ECDLP on a general curve in software using the improved Pollard-ρ method.
To place Table 2 in context, Odlyzko has estimated that 0:1% of the world’s computing power working
for 1 year will amount to 108 MIPS years in 2004, and 1010 or 1011 MIPS years in 2014 [71]. Table 2 isreproduced from ANSI X9.62 [3]. More details on how the estimates were obtained can be found there.
Size of n (in bits)

pπn 4 MIPS years
=

160

280

186

293

234

2117

354

2177

426

2213

8:5  1011
7:0  1015
1:2  1023
1:3  1041
9:2  1051

Table 2: Computing power required to solve ECDLPThe difficulty of the ECDLP is further illustrated by van Oorschot and Wiener’s 1994 paper [84]. Van
Oorschot and Wiener carried out a detailed study of the feasibility of building special-purpose hardware
to solve the ECDLP. They estimated that for about $10 million a machine with 325,000 processors could
be built that would solve the ECDLP for an elliptic curve E with n  2120 in about 35 days. Hardware
attacks on larger values of n, like n  2160 , appear completely infeasible at this time.
Although no general subexponential algorithms to solve the ECDLP are known, three classes of curves
are susceptible to special-purpose algorithms. Firstly, elliptic curves E over F q with n dividing qB 1
for small B are susceptible to the attacks described by Menezes, Okamoto, and Vanstone [65], and Freyand Ruck [32]. These attacks efficiently reduce the ECDLP on these curves to the traditional discrete
logarithm problem in a small degree extension of F q . Secondly, elliptic curves E over F q with #E (F q ) = q
are susceptible to the attack described by Semaev [80], Smart [82], and Satoh and Araki [77]. This attack
efficiently maps the elliptic curve E into the additive group of F q . Thirdly, elliptic curves E over F 2mwith m composite may be susceptible to attacks based on the Weil descent - see the work of Galbraith
and Smart [34], and Gaudry, Hess, and Smart [36]. These weak classes of curves are excluded in thisdocument.
Additional information on the difficulty of the ECDLP can be found in ANSI X9.62 [3], ANSI X9.63 [4],

SEC 1 - B Commentary

Page 61

Blake, Seroussi, and Smart [12], and Koblitz, Menezes, and Vanstone [55]. A useful source of information on the state-of-the-art in practical attacks on the ECDLP is Certicom’s ECC challenge [21].
The efficiency of cryptographic schemes based on ECC usually rests primarily on the efficiency of field
operation computations and in particular point scalar multiplication computation. Efficient general techniques for computing field operations are well-known and are described, for example, in [51, 63, 67]. A
variety of efficient general techniques for computing point scalar multiplication are known and exploit
tricks like precomputation and switching to projective co-ordinates.
Both field operation computations and point scalar multiplication computation can be accelerated bychoosing particular underlying fields and elliptic curves. Examples of fields amenable to particularly
efficient implementation include F 2m and F p where p is a Mersenne prime - see, for example [6, 7, 8, 31].
Examples of elliptic curves amenable to particularly efficient implementation include Koblitz curves overF 2m [53] which possess an efficiently computable endomorphism.
Additional information on the implementation of efficient finite field operations and point scalar multiplication can be found in Blake, Seroussi, and Smart [12], and Koblitz, Menezes, and Vanstone [55].

B.2 Commentary on Section 3 - Cryptographic Components
This section provides a commentary on Section 3 of the main body of this document.
B.2.1

Commentary on Elliptic Curve Domain Parameters

Elliptic curve domain parameters must be generated during the setup procedure of each of the schemes
specified in this document.
The first step in this process is to determine the security level desired by the application in question.
A number of criteria may affect this determination - factors may include, for example, the value ofthe information which the scheme will be used to protect, the length of time the parameters will be
used for, and the security level of other schemes used in the application. The definitive paper of Blaze,
Diffie, Rivest, Schneier, Shimomura, Thompson, and Wiener [16] provides guidance which may help
implementers make this determination. In particular, the authors of [16] conclude that:
To provide adequate protection against the most serious threats - well-funded commercial
enterprises or government intelligence agencies - keys used to protect data today should be
at least 75 bits long. To protect information adequately for the next 20 years in the face of
expected advances in computing power, keys in newly-deployed systems should be at least
90 bits long.
Table 3 below attempts to provide additional information which may help determine the security level
desired. It lists comparable key sizes for an ‘ideal’ symmetric scheme, an ECC-based scheme, and ascheme such as DSA or RSA based on the integer factorization problem or traditional discrete logarithm

Page 62

SEC 1: Elliptic Curve Cryptography Ver. 1.0

problem. The figures in Table 3 are based on the running times of the best algorithms known in 2000 for
attacking the cryptographic schemes.
Security level(in bits)

Symmetric scheme(key size in bits)

ECC-based scheme(size of n in bits)

DSA/RSA(modulus size in bits)

56

56

112

512

80

80

160

1024

112

112

224

2048

128

128

256

3072

192

192

384

7680

256

256

512

15360

Table 3: Comparable key sizes

Once the desired security level has been selected, there are a number of ways to generate elliptic curve
domain parameters at a given strength. These include: Select an appropriate finite field. Then select an elliptic curve over the field at random, count the
number of points on the curve using Schoof’s algorithm [79], check whether the number of points
is nearly prime, and repeat until appropriate parameters are found.

 Select an appropriate field, then select an appropriate curve order, and generate a curve over thefield with this number of points using techniques based on ‘complex multiplication’ [59].

 Select an appropriate finite field. Then select an elliptic curve over the field from a special familyof curves whose order is easily computable (such as the family of Koblitz curves), compute thenumber of points on this curve, and check whether the number of points is nearly prime.

The first method - known as selecting elliptic curve domain parameters at random - is the most conservative choice because it offers a probabilistic guarantee against future special purpose attacks of asimilar nature to the Menezes-Okamoto-Vanstone and the Semaev-Smart-Satoh-Araki attacks describedin Section B.1. However existing implementations of Schoof’s algorithm are less efficient than implementations of the other parameter selection methods. The second method - known as selecting elliptic
curve domain parameters using complex multiplication - generates parameters more efficiently than thefirst method. The third method - known as selecting elliptic curve domain parameters from a special
family - also generates parameters more efficiently than the first method, and has the added attraction
than some special families of curves (such as the family of Koblitz curves) enable tricks to speedup computations like point scalar multiplication. However despite their efficiency benefits, the second and third
methods should be used with a good deal of caution because they produce parameters which may besusceptible to future special-purpose attacks.

SEC 1 - B Commentary

Page 63

An attractive refinement of the idea of selecting elliptic curve domain parameters at random is the ideaof selecting elliptic curve domain parameters verifiably at random. This involves selecting parameters at
random from a seed in such a way that the parameters cannot be pre-determined. It is appealing because
the seed provides evidence that can be verified by anyone that no ‘trapdoors’ have been placed in theparameters. One method of selecting parameters verifiably at random is specified in ANSI X9.62 [3].
SEC 2 [83] - a companion document to this document - provides a list of precomputed elliptic curve
domain parameters at a variety of commonly required security levels that implementers may use when
implementing the schemes in this document. Use of these precomputed parameters is strongly recommended in order to foster interoperability.
Once elliptic curve domain parameters have been generated, either by the user themselves’ or by a third
party, it is desirable to receive some assurance that the parameters are valid - that is that the parameters
possess the arithmetic properties expected from secure parameters. Parameter validation mitigates against
inadvertent generation of insecure parameters caused by coding errors, and against deliberate attempts totrick users into using insecure parameters.
Additional information on the generation and validation of elliptic curve domain parameters can be foundin ANSI X9.62 [3], ANSI X9.63 [4], and IEEE P1363 [40].
B.2.2

Commentary on Elliptic Curve Key Pairs

Elliptic curve key pairs must be generated during the operation of each of the schemes specified in thisdocument. The key pair generation process requires a secure random or pseudorandom number generator.
Design of secure random and pseudorandom number generators is notoriously difficult and implementersshould therefore take care to pay attention to this aspect of their system design.
Once a key pair has been generated, it is often necessary to convey the public key in an authentic manner
to other entities. One way of achieving this authentic distribution is to have the key certified by a trusted
Certification Authority within a Public Key Infrastructure.
In many schemes it is desirable for an entity to receive assurance that an elliptic curve public key is valid
or partially valid before they use the public key to, say, verify a signature. This process can help prevent
small subgroup attacks and other attacks based on the use of an invalid public key.
A further discussion of the generation and validation of elliptic curve key pairs can be found in ANSI
X9.63 [4].
B.2.3

Commentary on Elliptic Curve Diffie-Hellman Primitives

Both the elliptic curve Diffie-Hellman primitives here generate a field element from a secret key owned
by one entity U and a public key owned by a second entity V in such a way that if both entities executethe primitive with corresponding keys as input, they will both compute the same field element.
The primary security requirement of both the primitives is that an attacker who sees only U and V ’s
public keys should be unable to compute the shared field element. This requirement is equivalent to thePage 64

SEC 1: Elliptic Curve Cryptography Ver. 1.0

requirement that the elliptic curve Diffie-Hellman problem or ECDHP is hard. The ECDHP is stated asfollows.
Let E be an elliptic curve defined over a finite field F q , and let G 2 E (F q ) be a point on E on large prime
order n. The ECDHP is, given E, G, and two scalar multiples Q1 = d1 G and Q2 = d2 G of G, to determine
d1 d2 G.
The ECDHP is closely related to the ECDLP. It is clear that if the ECDLP is easy then so is the ECDHP.
Boneh and Lipton [19] show that for practical purposes the converse is also true - they show that if thebest algorithm for the ECDLP really is fully exponential, then the ECDLP and the ECDHP are equivalent.
Many schemes based on the Diffie-Hellman primitives actually rely on a stronger requirement that theshared field element is not just hard for an attacker to predict, but that the element actually looks random
to the attacker. A discussion of this requirement, and its relationship to the ECDHP, can be found in[17, 20].
So far the discussion of the elliptic curve Diffie-Hellman primitives has been germane to both the ‘standard’ primitive and the cofactor primitive. The remainder of this section explains the difference between
the two primitives.
A direct assault on the ECDHP is not the only way an attacker might assault schemes which use theDiffie-Hellman primitives. Many schemes which use the primitives are also susceptible to small subgroupattacks [48, 62] in which an adversary substitutes V ’s public key with a point of small order in an attempt
to coerce U to calculate a predictable field element using one of the primitives. The consequences ofthese attacks can be severe - in a key agreement scheme, for example, the result can be compromise of asession key shared by U and V , or even compromise of U ’s static secret key.
Two defenses against this attack are recommended here: either validate V ’s public key and use the ‘standard’ Diffie-Hellman primitive (validating V ’s public key checks that V ’s public key has order n andhence prevents the attack), or partially validate V ’s public key and use the cofactor Diffie-Hellman primitive (using the cofactor Diffie-Hellman primitive with a point in a small subgroup will result in calculationof the point at infinity and hence rejection of the key).
Which of the defenses outlined above is appropriate in a given situation will depend on issues like whether
or not interoperability with existing use of the ‘standard’ Diffie-Hellman primitive is desirable (the first
defense interoperates and the second does not), and what the efficiency requirements of the system are(the second defense is usually more efficient than the first).
Additional information on the elliptic curve Diffie-Hellman primitives can be found in ANSI X9.63 [4].
B.2.4

Commentary on the Elliptic Curve MQV Primitive

The elliptic curve MQV primitive generates a field element from two key pairs owned by one entity U
and two public keys owned by a second entity V in such a way that if both entities execute the primitive
with corresponding keys as input, they will both compute the same field element.
Again the primary security requirement of the primtive is that an adversary who sees only U and V ’s
public keys should be unable to compute the shared field element. This requirement is conjectured to be

SEC 1 - B Commentary

Page 65

equivalent to the requirement that the ECDHP is hard - see [60] for a discussion of this conjecture.
Additional information on the elliptic curve MQV primitive can be found in ANSI X9.63 [4].

B.3 Commentary on Section 4 - Signature Schemes
This section provides a commentary on Section 4 of the main body of this document.
B.3.1

Commentary on the Elliptic Curve Digital Signature Algorithm

The ECDSA is a signature scheme with appendix based on ECC. It is designed to be existentially unforgeable, even in the presence of an adversary capable of launching chosen-message attacks. ECDSA isan elliptic curve analog of the U.S. government’s Digital Signature Algorithm or DSA [31]. It was first
proposed in ANSI X9.62 [3].
The ECDSA was chosen for inclusion in this document because it is widely standardized in, for example,
ANSI X9.62 [3], FIPS 186-2 [31] IEEE P1363 [40], and ISO 15946-2 [44]. Its widespread standardization, together with its close relationship to DSA, means that both specification details and implementation
details have been carefully scrutinized. Standardization also leads to the provision of valuable tools like
NIST’s proposed ECDSA validation system which implementers will be able to use to check their codefor errors.
The features of ECDSA outlined above were considered to outweigh at this time the features of othercandidates like the Schnorr scheme [78], which was shown to be provably secure in the random oracle
model based on the ECDLP in [75], or the Nyberg-Rueppel scheme [69, 70], which avoids the need formodular inversion during signature generation and verification and can offer slightly smaller signaturesizes through its message recovery capability. Future consideration may be given to adding support fora signature scheme with features like provable security or added efficiency if significant commercial
interest in these features is forthcoming.
There are a number of known cryptographic attacks on ECDSA. The specification of ECDSA in this document includes provision for preventing all of these attacks. Nonetheless implementers should be awareof the attacks and monitor future advances. The attacks illustrate that it is important that implementationsof ECDSA perform all the security checks specified in the main body of this document. The following is
a list of some of the known attacks:

 Attacks on the ECDLP. The security of ECDSA relies on the difficulty of the ECDLP on the elliptic
curve domain parameters being used - otherwise an attacker may be able to recover U ’s secret key
from U ’s public key and use this information to forge U ’s signature on any message.

 Attacks on key generation. Key generation is involved in both the key deployment procedure andthe signing operation of ECDSA. Secure random or pseudorandom number generation is required
during key generation to prevent, for example, U selecting a predictable secret key. Insecure random and pseudorandom number generators are perhaps the most common cause of cryptographic
attacks on cryptographic systems.

Page 66

SEC 1: Elliptic Curve Cryptography Ver. 1.0

 Attacks on the hash function. The hash function used by ECDSA during the signing operationand the verifying operation must possess a number of properties such as one-wayness and collisionresistance. Otherwise if the hash function is not, say, collision resistant, an attacker may be able tofind a collision (M1 ; M2 ) and forge U ’s signature on M2 after persuading U to sign M1 .

 Attacks based on invalid domain parameters. The security of ECDSA relies on U using valid

domain parameters because, for example, invalid domain parameters may be susceptible to the
Pohlig-Hellman attack [73]. U should therefore receive assurance that the elliptic curve domain
parameters used are valid. V may also desire to check that the elliptic curve domain parameters arevalid to prevent attacks like those described in [15, 22] and to mitigate against the possibility of
repudiation disputes in which U denies liability because U was using invalid domain parameters.

 Attacks based on invalid public keys. It may be desirable for V to check that U ’s public key is valid
to prevent, for example, attacks like those described in [15, 22]. Another reason V may wish tocheck that U ’s public key is valid is to mitigate against the possibility of a repudiation dispute inwhich U denies liability because U was using an invalid public key.

 Vaudenay’s attack. Vaudenay has shown in [86] that ECDSA is susceptible to attack if an attacker
is able to persuade U to use elliptic curve domain parameters with base point order n chosen by theattacker and satisfying dlog2 ne  8(hashlen). This attack can be prevented, for example, throughexclusive use of elliptic curve domain parameters generated by U or by some trusted party, throughuse of verifiably random elliptic curve domain parameters or elliptic curve domain parametersfrom a small well-known family of parameters like parameters associated with Koblitz curves, or
through use of parameters with dlog2 ne > 8(hashlen).

Of course a variety of non-cryptographic attacks on ECDSA are also possible, and implementers shouldtake precautions to avoid, for example, ‘implementation attacks’ such as fault-based attacks [18], poweranalysis attacks [56], and timing-analysis attacks [57].
The operation of ECDSA involves selection by implementers of a number of options. These choices
will typically be made based on concerns like efficiency, interoperability, and on security issues likethose outlined above. In particular, some of the choices involved are selection of elliptic curve domain
parameters, selection of a hash function (SHA-1 is the only hash function currently supported), andselection of parameter and public key validation methods. Selection of elliptic curve domain parameters
will likely involve consideration of issues like those discussed in Sections B.1 and B.2, and selectionof parameter and public key validation methods will likely involve consideration of issues like those
discussed above.
Additional information on ECDSA, including extensive security discussion, can be found in ANSI X9.62[3] and IEEE P1363 [40]. Test vectors for ECDSA can be found in GEC 1 [37].

B.4 Commentary on Section 5 - Encryption Schemes
This section provides a commentary on Section 5 of the main body of this document.

SEC 1 - B Commentary

B.4.1

Page 67

Commentary on the Elliptic Curve Integrated Encryption Scheme

The ECIES is a public-key encryption scheme based on ECC. It is designed to be semantically secure in
the presence of an adversary capable of launching chosen-plaintext and chosen-ciphertext attacks. It was
proposed in [1, 11].
(Note that the specification of ECIES here differs slightly from the description in [1] where it is mandated
that R is included in the input to the key derivation function. This does not affect the applicability of the
security results in [1] to ECIES because elliptic curve domain parameters specify use of a prime ordergroup generated by the base point G. Nevertheless implementations may of course choose to include R
in the input to the key derivation function to achieve complete alignment with [1].)The ECIES was chosen for inclusion in this document because it offers an attractive mix of provablesecurity and efficiency. It was proven secure based on a variant of the Diffie-Hellman problem in [1].
It is as efficient as or more efficient than comparable schemes. The dominant calculations involved inencryption are two point scalar multiplications, and the dominant calculation involved in decryption is asingle point scalar multiplication. ECIES is also being standardized in ANSI X9.63 [4] and IEEE P1363A[41].
The features of ECIES outlined above were considered to make it the most attractive ECC-based publickey encryption scheme for standardization. In particular, of the other possibilities, the elliptic curveanalog of traditional ElGamal encryption [27] does not offer security against chosen-ciphertext attacks,
while the elliptic curve analog of the Cramer-Shoup encryption scheme [23] offers similar security properties but is considerably less efficient.
There are a number of known attacks on ECIES. The specification of ECIES in this document includes
provision for preventing all these attacks. Nonetheless implementers should be aware of the attacks
and monitor future advances. The attacks illustrate that it is important that implementations of ECIES
perform all the security checks specified in the main body of this document. The following is a list ofsome of the known attacks:

 Attacks on the ECDLP or ECDHP. The security of the ECIES relies on the difficulty of the ECDLP

and ECDHP on the elliptic curve domain parameters used - otherwise an attacker who sees an
encrypted message sent from U to V may be able to recover the shared secret value z from R and
QV , and use this information to discover the message.

 Attacks on key generation. Key generation is involved in both the key deployment procedure andthe encryption operation of ECIES. Secure random or pseudorandom number generation is required
during key generation to prevent, for example, V selecting a predictable secret key. Insecure random and pseudorandom number generators are perhaps the most common cause of cryptographic
attacks on cryptographic systems.

 Attacks on the symmetric encryption scheme. The symmetric encryption scheme used by the
ECIES needs to possess only mild security properties to ensure the security of ECIES. (That is
why the XOR encryption scheme may be used by ECIES.) Nonetheless severe compromise of thesymmetric encryption scheme may result in leakage of information about encrypted messages.

Page 68

SEC 1: Elliptic Curve Cryptography Ver. 1.0

 Attacks on the MAC scheme. As was the case for the symmetric encryption scheme, the MAC
scheme used by ECIES needs to possess only mild security properties to ensure the security of
ECIES. Nonetheless severe compromise of the MAC scheme may enable an attacker to launch achosen-ciphertext attack on ECIES.

 Attacks on the key derivation function. The key derivation function used by ECIES must possess anumber of properties to ensure the security of ECIES. If, for example, an attacker is able to predict
some bits of the output of the key derivation function, or if portions of the output of the key derivation function are correlated in some way, an attacker may be able to learn some information about
encrypted messages. These concerns provide some motivation for the use of the TDES symmetricencryption scheme rather than the XOR symmetric encryption scheme when using ECIES to convey long messages since this choice minimizes the amount of output the key derivation function is
asked to produce.

 Attacks based on the use of invalid domain parameters. The security of ECIES relies on V using

valid domain parameters because, for example, invalid domain parameters may be susceptible to
the Pohlig-Hellman attack [73]. V should therefore receive assurance that the elliptic curve domain
parameters used are valid.

 Attacks based on the use of invalid public keys. When the ECIES is used with the standard elliptic

curve Diffie-Hellman primitive, V should check that the public-key R is valid to prevent Lim-Leestyle small subgroup attacks [48, 62] which result in providing an attacker with the ability to learnsome bits of V ’s secret key. Similarly when ECIES is used with the cofactor Diffie-Hellman primitive, V should check that the public-key R is partially valid to prevent the possibility of similar
attacks. (The cofactor Diffie-Hellman primitive is designed specifically to enable efficient prevention of small subgroup attacks.)

Of course a variety of non-cryptographic attacks on ECIES are also possible, and implementers shouldtake precautions to avoid, for example, ‘implementation attacks’ such as fault-based attacks [18], poweranalysis attacks [56], and timing-analysis attacks [57].
The operation of ECIES involves selection by implementers of a number of options. These choices will
typically be made based on concerns like efficiency, interoperability, and on security issues like thoseoutlined above. In particular, some of the choices involved are selection of elliptic curve domain parameters, selection of a key derivation function, selection of a symmetric encryption scheme and MAC
scheme, selection of the standard or cofactor Diffie-Hellman primitive, selection of parameter and public
key validation methods, and selection of appropriate data to include in SharedIn f o1 and SharedIn f o2.
Selection of elliptic curve domain parameters will likely involve consideration of issues like those discussed in Sections B.1 and B.2. Selection of a symmetric encryption scheme will likely be influenced by
the length of messages which are going to be encrypted and the amount of memory available. (When the
TDES encryption scheme is used, messages can be passed into the encryption operation a piece at a time,
whereas when the XOR encryption scheme is used to encrypt variable length messages, the length ofthe message must be known before MAC computation can begin.) Selection of the HMAC–SHA-1–160
scheme or the HMAC–SHA-1–80 scheme will likely be influenced by individual security preferences

SEC 1 - B Commentary

Page 69

and bandwidth requirements. Selection of the standard or cofactor Diffie-Hellman primitive will likely
involve consideration of security concerns like small subgroup attacks and the efficiency requirementsof the application. Selection of parameter and public key validation methods will likely involve consideration of security issues like those discussed above. Selection of appropriate information to includein SharedIn f o1 and SharedIn f o2 will likely depend on the particular application, but common things
to include are, for example, the public key R for alignment with the description of ECIES in [1], or acounter value to mitigate against replay of ciphertexts.
Additional information on ECIES, including extensive security discussion, can be found in ANSI X9.63[4], and the paper of Abdalla, Bellare, and Rogaway [1]. Test vectors for ECIES can be found in GEC 1[37].

B.5 Commentary on Section 6 - Key Agreement Schemes
This section provides a commentary on Section 6 of the main body of this document.
B.5.1

Commentary on the Elliptic Curve Diffie-Hellman Scheme

The elliptic curve Diffie-Hellman scheme is a key agreement scheme based on ECC. It is designed toprovide a variety of security goals depending on its application - goals it can provide include unilateralimplicit key authentication, mutual implicit key authentication, known-key security, and forward secrecy.
It is the elliptic curve analog of the Diffie-Hellman scheme [25]. It was first proposed in [25, 52, 68].
The elliptic curve Diffie-Hellman scheme was chosen for inclusion in this document because it is wellknown, well-scrutinized, widely-standardized, and versatile. It is standardized in ANSI X9.63 [4], IEEEP1363 [40], and ISO 15946-3 [45]. Examples of the application of the elliptic curve Diffie-Hellman
scheme to achieve a variety of security goals can be found in [10, 14, 26]. ECIES is also an example ofan application of the elliptic curve Diffie-Hellman scheme.
There are a number of known attacks on the elliptic curve Diffie-Hellman scheme. The specificationof the elliptic curve Diffie-Hellman scheme in this document includes provision for preventing all these
attacks. Nonetheless implementers should be aware of the attacks and monitor future advances. The
attacks illustrate that it is important that implementations of the elliptic curve Diffie-Hellman scheme
perform all the security checks specified in the main body of this document. The following is a list ofsome of the known attacks:

 Attacks on the ECDLP or ECDHP. The security of the elliptic curve Diffie-Hellman scheme relieson the difficulty of the ECDLP and ECDHP on the elliptic curve domain parameters used - otherwise an attacker who sees an U to V using the scheme may be able to recover the shared secretvalue z from QU and QV , and use this information to discover the keying data they agreed.

 Attacks on key generation. Key generation is involved in the key deployment procedure of the elliptic curve Diffie-Hellman scheme. Secure random or pseudorandom number generation is required

Page 70

SEC 1: Elliptic Curve Cryptography Ver. 1.0

during key generation to prevent, for example, V selecting a predictable secret key. Insecure random and pseudorandom number generators are perhaps the most common cause of cryptographic
attacks on cryptographic systems.

 Man-in-the-middle attacks. If the elliptic curve Diffie-Hellman scheme is not applied with care,it may be possible for an adversary to attack the scheme by modifying QU or QV when they areexchanged, and as a result prevent the scheme from achieving goals like implicit key authenticationor known-key security. Numerous defenses are commonly employed to prevent such active attacks- including exchanging QU and QV in signed messages, or certifying QU and QV .

 Attacks on the key derivation function. The key derivation function used by the elliptic curve

Diffie-Hellman scheme must possess a number of properties to ensure the security of the scheme.
If, for example, an attacker is able to predict some bits of the output of the key derivation function,or if portions of the output of the key derivation function are correlated in some way, an attacker
may be able to learn some information about the agreed keying data.

 Attacks based on the use of invalid domain parameters. The security of the elliptic curve Diffie-

Hellman scheme relies on U and V using valid domain parameters because, for example, invalid
domain parameters may be susceptible to the Pohlig-Hellman attack [73]. U and V should therefore
receive assurance that the elliptic curve domain parameters used are valid.

 Attacks based on the use of invalid public keys. Because the elliptic curve Diffie-Hellman schemeby its nature requires each entity to combine its private key with another entity’s public key, thescheme is particularly susceptible to attacks based on the use of invalid public keys. The bestknown examples of such attacks are small subgroup attacks [48, 62], which can result in, forexample, an attacker coercing U and V into sharing predictable keying data, or an attacker learningsome bits of U ’s secret key. For this reason, when using the elliptic curve Diffie-Hellman schemewith the standard Diffie-Hellman primitive, U should receive an assurance that V ’s public key isvalid and vice versa, and when using the scheme with the cofactor Diffie-Hellman primitive, Ushould receive an assurance that V ’s public key is partially valid and vice versa.

Of course a variety of non-cryptographic attacks on the elliptic curve Diffie-Hellman scheme are also
possible, and implementers should take precautions to avoid, for example, ‘implementation attacks’ suchas fault-based attacks [18], power-analysis attacks [56], and timing-analysis attacks [57].
The operation of the elliptic curve Diffie-Hellman scheme involves selection by implementers of a number of options. These choices will typically be made based on concerns like efficiency, interoperability,
and on security issues like those outlined above. In particular, some of the choices involved are selectionof elliptic curve domain parameters, selection of a key derivation function, selection of the standard or cofactor Diffie-Hellman primitive, selection of parameter and public key validation methods, and selectionof SharedIn f o, as well as selection of an appropriate application of the scheme to meet the security requirements of the system. Selection of elliptic curve domain parameters will likely involve considerationof issues like those discussed in Section B.1 and B.2. Selection of the standard or cofactor Diffie-Hellman
primitive will likely involve consideration of security concerns like small subgroup attacks and the efficiency requirements of the system. Selection of parameter and public key validation methods will likely

SEC 1 - B Commentary

Page 71

involve consideration of security issues like those discussed above. Selection of appropriate information
to include in SharedIn f o will likely depend on the particular application, but common things to include
are, for example, the identities of U and V , the public keys QU and QV , counter values, and an indication of the symmetric scheme for which the agreed keying data will be used. If a number of fields areincluded in SharedIn f o, it is sensible to check that the encoding of the fields is unique. Selection of an
appropriate application of the scheme will likely depend on issues like what the agreed key will be used
for and whether U and V are both on-line. ANSI X9.63 contains guidance to help implementers makethis selection.
Additional information on the elliptic curve Diffie-Hellman scheme, including extensive security discussion, can be found in ANSI X9.63 [4], and IEEE P1363 [40]. Test vectors for the elliptic curve
Diffie-Hellman scheme can be found in GEC 1 [37].
B.5.2

Commentary on the Elliptic Curve MQV Scheme

Like the elliptic curve Diffie-Hellman scheme, the elliptic curve MQV scheme is a key agreement scheme
based on ECC. It is designed to provide a variety of security goals depending on its application - goals it
can provide include mutual implicit key authentication, known-key security, and forward secrecy. It was
first proposed in [60, 66].
The elliptic curve MQV scheme was chosen for inclusion in this document because it is a particularly
efficient method for achieving mutual implicit key authentication. The dominant calculations involvedin the key agreement operation are 1.5 point scalar multiplies. The elliptic curve MQV scheme is also
standardized in ANSI X9.63 [4], and IEEE P1363 [40].
There are a number of known attacks on the elliptic curve MQV scheme. The specification of the elliptic
curve MQV scheme in this document includes provision for preventing all these attacks. Nonethelessimplementers should be aware of the attacks and monitor future advances. The attacks illustrate that
it is important that implementations of the elliptic curve MQV scheme perform all the security checks
specified in the main body of this document. The following is a list of some of the known attacks:

 Attacks on the ECDLP or ECDHP. The security of the elliptic curve MQV scheme relies on the
difficulty of the ECDLP and ECDHP on the elliptic curve domain parameters used - otherwise an
attacker who sees an U to V using the scheme may be able to recover the shared secret value z from
Q1;U , Q2;U , Q1;V , and Q2;V , and use this information to discover the keying data they agreed.

 Attacks on key generation. Key generation is involved in the key deployment procedure of the el-liptic curve MQV scheme. Secure random or pseudorandom number generation is required during
key generation to prevent, for example, V selecting a predictable secret key. Insecure random andpseudorandom number generators are perhaps the most common cause of cryptographic attacks on
cryptographic systems.

 Attacks on the key derivation function. The key derivation function used by the elliptic curve MQV

scheme must possess a number of properties to ensure the security of the scheme. If, for example,
an attacker is able to predict some bits of the output of the key derivation function, or if portions

Page 72

SEC 1: Elliptic Curve Cryptography Ver. 1.0of the output of the key derivation function are correlated in some way, an attacker may be able tolearn some information about the agreed keying data.

 Attacks based on the use of invalid domain parameters. The security of the elliptic curve MQV

scheme relies on U and V using valid domain parameters because, for example, invalid domain
parameters may be susceptible to the Pohlig-Hellman attack [73]. U and V should therefore receive
assurance that the elliptic curve domain parameters used are valid.

 Unknown key-share attacks. Kaliski [50] has observed that the elliptic curve MQV scheme may

be susceptible to unknown key-share attacks if it is not applied with care. These attacks may
be damaging when the scheme is used to provide symmetric keys in order to both encrypt andauthenticate data. The attacks can be prevented by including data like U and V ’s identities inSharedIn f o, or by performing appropriate key confirmation subsequent to key agreement.

Of course a variety of non-cryptographic attacks on the elliptic curve MQV scheme are also possible, andimplementers should take precautions to avoid, for example, ‘implementation attacks’ such as fault-based
attacks [18], power-analysis attacks [56], and timing-analysis attacks [57].
The operation of the elliptic curve MQV scheme involves selection by implementers of a number of
options. These choices will typically be made based on concerns like efficiency, interoperability, andon security issues like those outlined above. In particular, some of the choices involved are selection of
elliptic curve domain parameters, selection of a key derivation function, selection of parameter and public
key validation methods, and selection of SharedIn f o, as well as selection of an appropriate application of
the scheme to meet the security requirements of the system. Selection of elliptic curve domain parameters
will likely involve consideration of issues like those discussed in Section B.1 and B.2. Selection ofparameter and public key validation methods will likely involve consideration of security issues likethose discussed above. Selection of appropriate information to include in SharedIn f o will likely dependon the particular application, but common things to include are, for example, the identities of U and V ,the public keys Q1;U , Q2;U , Q1;V , and Q2;V , counter values, and an indication of the symmetric scheme
for which the agreed keying data will be used. If a number of fields are included in SharedIn f o, it issensible to check that the encoding of the fields is unique. Selection of an appropriate application of thescheme will likely depend on issues like what the agreed key will be used for and whether U and V areboth on-line. ANSI X9.63 contains guidance to help implementers make this selection.
Additional information on the elliptic curve MQV scheme, including extensive security discussion, canbe found in ANSI X9.63 [4], in IEEE P1363 [40], and in the paper of Law, Menezes, Qu, Solinas, andVanstone [60]. Test vectors for the elliptic curve MQV scheme can be found in GEC 1 [37].

B.6 Alignment with Other Standards
The cryptographic schemes in this document have been selected to conform with as many other standards
efforts on ECC as possible.
Core standards efforts on ECC include ANSI X9.62 [3], ANSI X9.63 [4], FIPS 186-2 [31], IEEEP1363 [40], IEEE P1363A [41], IPSec [38, 72, 28], ISO 14888-3 [42], and ISO 15946 [43, 44, 45].

SEC 1 - B Commentary

Page 73

Table 4 shows which of the schemes specified in this document are included in these efforts. Moredetails are given below.
Standard

Schemes included

ANSI X9.62

ECDSA

ANSI X9.63

ECIES, ECDH, ECMQVFIPS 186-2

ECDSA

IEEE P1363

ECDSA, ECDH, ECMQVIEEE P1363A

ECIES

IPSec

ECDSA, ECDH

ISO 14888-3

ECDSA

ISO 15946

ECDSA, ECDH, ECMQV

Table 4: Alignment with other core ECC standards
The ANSI X9.62 standard specifies ECDSA for use by the financial services industry. It requires ECDSA
to be used with the hash function SHA-1, and with elliptic curve domain parameters with n > 2160
to meet the stringent security requirements of the banking industry. Subject to these constraints andother procedural constraints like the use of an ANSI-approved pseudorandom number generator, thespecification of ECDSA in this document should comply with ANSI X9.62.
The draft ANSI X9.63 standard specifies key agreement and key transport schemes based on ECC for use
by the financial services industry. In particular it specifies various schemes built from ECIES, ECDH, andECMQV. Like ANSI X9.62, it requires various constraints like restriction to the hash function SHA-1, useof elliptic curve domain parameters with n > 2160 , and use of an ANSI-approved pseudorandom number
generator. Subject to these constraints, the specifications of ECDH and ECMQV in this document should
be compatible with ANSI X9.63. The specification of ECIES in this document should be similarlycompatible with ANSI X9.63 when used with the XOR symmetric encryption scheme. (ANSI X9.63
is concerned specifically with key transport of short keys and hence support for a TDES symmetricencryption option is not so desirable there as it is here where longer messages may be encrypted.)
The FIPS 186-2 standard specifies signature schemes for U.S. government use. Three signature schemes
are allowed, including ECDSA as specified in ANSI X9.62. Thus subject to the constraints describedabove in the context of ANSI X9.62, the specification of ECDSA in this document should comply with
FIPS 186-2.
The IEEE P1363 standard has a wide scope encompassing schemes based on the integer factorization problem, the traditional discrete logarithm problem, and the ECDLP. The techniques based on
ECC specified in IEEE P1363 include general descriptions of ECDSA (known in IEEE P1363 as ECSSA), ECDH (known as ECKAS-DH1), and ECMQV (known as ECKAS-MQV). The specifications of
ECDSA, ECDH, and ECMQV in this document should comply with IEEE P1363.

Page 74

SEC 1: Elliptic Curve Cryptography Ver. 1.0

The draft IEEE P1363A standard is a proposed addendum to IEEE P1363. IEEE P1363A includes additional techniques not originally considered for IEEE P1363 due to time constraints. ECIES is included
in IEEE P1363A [41]. The specification of ECIES in this document should comply with IEEE P1363A.
The IPSec standard [38] includes support for a variant of ECDH. The particular variant of ECDH differsfrom ECDH as specified in this document in as much as it uses different octet string point representations. In addition the default elliptic curve domain parameters in IPSec are parameters over F 2m withm composite and they do not use prime order base points. Aside from these technicalities, the specification of ECDH in this document should be broadly compliant with IPSec. Furthermore, draft IPSec
standards [28, 72] have been proposed which extend IPSec to include ECDSA and ECDH as specified inthis document.
The ISO 14888-3 standard specifies very general signature mechanisms. The specification of ECDSA in
this document should comply with ISO 14888-3.
The draft ISO 15946 standards specify cryptographic techniques based on ECC. ISO 15946-2 specifies
a variety of signature schemes including ECDSA. The specification of ECDSA in this document should
comply with ISO 15946-2. ISO 15946-3 specifies a variety of key establishment schemes including
some based on ECDH and ECMQV. The specifications of ECDH and ECMQV in this document should
be compatible with ISO 15946-3.
A variety of standards build on the core standards above. In particular: The FSTC FSML standard [33]allows ECDSA as specified in ANSI X9.62 to be used to sign electronic checks and other electronic
financial documents. The PKIX standard [9] specifies how to use ECDSA as specified in ANSI X9.62
within the PKIX certification framework. The S/MIME standard [13] specifies how to use ECDSA,
ECDH, and ECMQV as specified in ANSI X9.62 and ANSI X9.63 to secure email. The SSL/TLS
ECC standard [24] specifies how to use ECDSA, ECDH, and ECMQV as specified in ANSI X9.62,
ANSI X9.63, and IEEE P1363 in SSL/TLS. The WAP WTLS standard [87] specifies a protocol similarin spirit to SSL/TLS but tailored to the needs of the wireless telecommunications industry. It allows
use of ECDSA and ECDH as specified in IEEE P1363. The WAP WMLScript Crypto API standard[88] specifies application layer cryptographic functions for use by wireless devices. It allows the useof ECDSA as specified in IEEE P1363. From the discussion above on the alignment of this documentwith other core standards, it can be seen that the schemes in this document should be appropriate for use
by implementers of the FSTC FSML standard, the IPSec standards, the PKIX standards, the S/MIME
standards, the SSL/TLS ECC standard, and the WAP standards.

SEC 1 - C ASN.1 for Elliptic Curve Cryptography

C

Page 75

ASN.1 for Elliptic Curve Cryptography

Several different types of information may need to be conveyed during the operation of the schemes
specified in this document. This section suggests ASN.1 syntax which may be used to convey parts ofthis information when suitably encoded via, for example, DER [47]. Section C.1 recommends syntax
to describe finite fields. Section C.2 recommends syntax to describe elliptic curve domain parameters.
Section C.3 recommends syntax to describe elliptic curve public keys. Section C.4 recommends syntax
to describe elliptic curve private keys. Section C.5 recommends syntax to describe signatures. Section
C.6 recommends syntax to encode information for processing by key derivation functions. Section C.7
contains the ASN.1 module that holds the above.
Syntax for other aspects of elliptic curve cryptography, such as object identifiers for specific schemes,
may be added in future versions of this document. The syntax provided here follows the syntax used in
ANSI X9.62 [3], ANSI X9.63 [4], and PKIX [9].

C.1

Syntax for Finite Fields

This section provides the recommended ASN.1 syntax to identify finite fields and field elements. The
identity of a finite field and a specific field element therein may need to be specified, for example, as partof some elliptic curve domain parameters. The syntax follows ANSI X9.62 [3, Section 7.1].
The finite fields of interest in this document are prime fields and characteristic-two fields. A finite field
is identified by a value of type FieldID:
FieldID { FIELD-ID:IOSet } ::= SEQUENCE {-- Finite field
fieldType FIELD-ID.&id({IOSet}),parameters FIELD-ID.&Type({IOSet}{@fieldType})}
The governor FIELD-ID of the parameter FIELD-ID:IOSet is defined as the following open typethat is defined in ITU-T X.681 [46, Annex A].
FIELD-ID ::= TYPE-IDENTIFIER(and hence the dummy argument IOSet must be of said type). The term “open type” means that a‘hole’ is left in both components that are filled at the time of usage. The component relation constraint
fIOSetgf@fieldTypeg binds the argument IOSet to the identifier fieldType.
Only two field types are permitted, namely, prime fields and characteristic-two fields.
FieldTypes FIELD-ID ::= {{ Prime-p
IDENTIFIED BY prime-field } |{ Characteristic-two IDENTIFIED BY characteristic-two-field }}Page 76

SEC 1: Elliptic Curve Cryptography Ver. 1.0

A prime field is specified by the identifier prime-field of type Prime-p (below) comprising an
integer which is the size of the field.
prime-field OBJECT IDENTIFIER ::= { id-fieldType 1 }Prime-p ::= INTEGER-- Field of size p.
The object identifier id-fieldType (above) is the root of a tree containing object identifiers of eachfield type. It is defined as the following arc from ANSI.
id-fieldType OBJECT IDENTIFIER ::= { ansi-X9-62 fieldType(1) }whereansi-X9-62 OBJECT IDENTIFIER ::= {iso(1) member-body(2) us(840) 10045}
A characteristic-two finite field is specified by the identifier characteristic-two-field of type
Characteristic-two (below) comprising the size of the field, the type of basis used to express
elements of the field, and the polynomial used to generate the field (in the case of a polynomial basis).
characteristic-two-field OBJECT IDENTIFIER ::= { id-fieldType 2 }Characteristic-two ::= SEQUENCE {m
INTEGER,-- Field size 2ˆmbasis
CHARACTERISTIC-TWO.&id({BasisTypes}),parameters CHARACTERISTIC-TWO.&Type({BasisTypes}{@basis})}
The type CHARACTERISTIC-TWO (above) is defined by the following.
CHARACTERISTIC-TWO ::= TYPE-IDENTIFIER
The basis types of interest are normal bases (that are not used here), trinomial bases, or pentanomialbases. (See Section 2.1.2 for further information.)
BasisTypes CHARACTERISTIC-TWO::= {{ NULL
IDENTIFIED BY gnBasis } |{ Trinomial
IDENTIFIED BY tpBasis } |{ Pentanomial IDENTIFIED BY ppBasis },}Normal bases are specified by the object identifier gnBasis (below) with NULL parameters. Trinomial bases are specified by the object identifier tpBasis (below) with a parameter Trinomial thatspecifies the degree of the middle term in the defining trinomial. Pentanomial bases are specified by theobject identifier ppBasis (below) with a parameter Pentanomial that specifies the degrees of thethree middle terms in the defining pentanomial.

SEC 1 - C ASN.1 for Elliptic Curve Cryptography

Page 77

gnBasis OBJECT IDENTIFIER ::= { id-characteristic-two-basis 1 }tpBasis OBJECT IDENTIFIER ::= { id-characteristic-two-basis 2 }ppBasis OBJECT IDENTIFIER ::= { id-characteristic-two-basis 3 }The identifier id-characteristic-two-basis (above) is defined as the following.
id-characteristic-two-basis OBJECT IDENTIFIER ::= {characteristic-two-field basisType(3)}The degrees of the polynomials that define the finite fields are specified by the following.
Trinomial ::= INTEGER
Pentanomial ::= SEQUENCE {k1 INTEGER, -- k1 > 0
k2 INTEGER, -- k2 > k1
k3 INTEGER-- k3 > k2}
Finally, a specific field element is represented by the following type
FieldElement ::= OCTET STRING
whose value is the octet string obtained from the conversion routines given in Section 2.3.5.

C.2

Syntax for Elliptic Curve Domain Parameters

Elliptic curve domain parameters may need to be specified, for example, during the setup operation of acryptographic scheme based on elliptic curve cryptography. There are a number of ways of specifying
elliptic curve domain parameters. Here the following syntax is recommended (following [9]) for use in
X.509 certificates and elsewhere.
Parameters{CURVES:IOSet} ::= CHOICE {ecParameters ECParameters,
namedCurve
CURVES.&id({IOSet}),implicitCA
NULL}
The choice of three parameter representation methods (above) allows detailed specification of all required
values using either: The choice ecParameters which explicitly identifies all the parameters, orPage 78

SEC 1: Elliptic Curve Cryptography Ver. 1.0

 The choice namedCurve which implicitly identifies the parameters by reference to a well-known
set of parameters, or The choice implicitCA which indicates that the parameters are inherited from elsewhere.
The three choices described above are completely specified in the remainder of this section.
The choice ecParameters explicitly identifies the elliptic curve domain parameters, if need be, via
the following syntax.
ECParameters ::= SEQUENCE {version INTEGER { ecpVer1(1) } (ecpVer1),
fieldID FieldID {{FieldTypes}},curve
Curve,base
ECPoint,
order
INTEGER,cofactor INTEGER OPTIONAL,...
}
The components of type ECParameters have the following meanings.

 The component version is the version number of the ASN.1 type with a value of 1. The notation

above creates an INTEGER named ecpVer1 and assigns to it the value one. It is used to constrain
version to a single value.

 The component fieldID identifies the finite field over which the elliptic curve is defined and was
discussed in Section C.1.

 The component curve of type Curve (defined below) specifies the elliptic curve.
 The component base of type ECPoint (defined below) specifies the base point on the elliptic
curve curve.

 The component order is the order of the base point base.
 The component cofactor is the order of the curve divided by the order of the base point. In-

clusion of the cofactor is optional – however, it is strongly recommended that that the cofactor be
included in order to facilitate interoperability between implementations.

The type Curve is defined as follows, by specifying the coefficients of the defining equation of theelliptic curve and an optional seed. (If the curve was generated verifiably at random using a seed value
with SHA-1 as specified in ANSI X9.62 [3] then said seed may be included as the seed component so
as to allow a recipient to verify that the curve was indeed so generated using said seed.)SEC 1 - C ASN.1 for Elliptic Curve Cryptography

Page 79

Curve ::= SEQUENCE {aFieldElement,bFieldElement,
seed BIT STRING OPTIONAL}
An elliptic curve point itself is represented by the following type
ECPoint ::= OCTET STRING
whose value is the octet string obtained from the conversion routines given in Section 2.3.3.
The choice namedCurve implicitly identifies the elliptic curve domain parameters by reference to awell-known set of parameters assigned an object identifier.
The class CURVES, defined as follows, is used to specify the namedCurve choice.
CURVES ::= CLASS {&id OBJECT IDENTIFIER UNIQUE}
WITH SYNTAX { ID &id }As an example of the above syntax, the curve sect163k1, defined in SEC 2 [83], is denoted by thesyntax ID sect163k1.
The beauty of the above syntax is that valid values for the choice namedCurve can be constrained.
The following syntax, included here for completeness, may be extended by other standards and implementations to constrain the list of supported named curves. One such extension may be found in SEC 2[83].
SECGCurveNames CURVES ::= {... -- named curves}
The choice implicitlyCA indicates that elliptic curve domain parameters are inherited from elsewhere. This choice must be used with care because it is important that elliptic curve key pairs are boundto the correct parameters so that an attacker is not able to coerce the use of the key pair with a different
set of parameters.
Situations where use of the implicitlyCA choice may be appropriate include applications which
use fixed parameters and applications where user parameters are inherited from Certificate Authority
parameters.

Page 80

C.3

SEC 1: Elliptic Curve Cryptography Ver. 1.0

Syntax for Elliptic Curve Public Keys

Elliptic curve public keys may need to be specified, for example, during the key deployment phase ofa cryptographic scheme based on elliptic curve cryptography. An elliptic curve public key is a point on
an elliptic curve and may be represented in a variety of ways using ASN.1 syntax. Here the following
syntax is recommended (following [9]) for use in X.509 certificates and elsewhere, where public keys are
represented by the ASN.1 type SubjectPublicKeyInfo.
SubjectPublicKeyInfo ::= SEQUENCE {algorithm
AlgorithmIdentifier {{ECPKAlgorithms}},
subjectPublicKey BIT STRING}
The component algorithm specifies the type of public key and associated parameters employed andthe component subjectPublicKey specifies the actual value of said public key.
The parameter type AlgorithmIdentifier above tightly binds together a set of algorithm object
identifiers and their associated parameters types. The type AlgorithmIdentifier is defined asfollows.
AlgorithmIdentifier{ ALGORITHM:IOSet } ::= SEQUENCE {algorithm ALGORITHM.&id({IOSet}),parameters ALGORITHM.&Type({IOSet}{@algorithm})}
The governing type ALGORITHM (above) is defined to be the following object information object.
ALGORITHM ::= CLASS {&id
OBJECT IDENTIFIER UNIQUE,&Type OPTIONAL}
WITH SYNTAX { OID &id [PARMS &Type] }When SubjectPublicKeyInfo is used to specify an elliptic curve public key, the sole parameter inthe reference of type AlgorithmIdentifier refers to the object ecPublicKeyType.
ECPKAlgorithms ALGORITHM ::= {ecPublicKeyType,...
}ecPublicKeyType ALGORITHM ::= {OID id-ecPublicKey PARMS Parameters {{SECGCurveNames}}}

SEC 1 - C ASN.1 for Elliptic Curve Cryptography

Page 81

The object identifier id-ecPublicKey designates an elliptic curve public key. It is defined by thefollowing (after ANSI X9.62 [3, Section 6.1]) to be used whenever an object identifier for an elliptic
curve public key is needed. (Note that this syntax applies to all elliptic curve public keys regardless of
their designated use.)
id-ecPublicKey OBJECT IDENTIFIER ::= { id-publicKeyType 1 }where
id-publicKeyType OBJECT IDENTIFIER ::= { ansi-X9-62 keyType(2) }The component Parameters was defined in Section C.2 and may contain the elliptic curve domain
parameters associated with the public key in question. (Thus the component algorithm indicates that
SubjectPublicKeyInfo not only specifies the elliptic curve public key but also the elliptic curve
domain parameters associated with said public key.)
Finally, SubjectPublicKeyInfo specifies the public key itself when algorithm indicates thatthe public key is an elliptic curve public key.
The elliptic curve public key (a value of type ECPoint that is an OCTET STRING) is mapped to a
subjectPublicKey (a value encoded as type BIT STRING) as follows: The most significant bit of
the value of the OCTET STRING becomes the most significant bit of the value of the BIT STRING
and so on with consecutive bits until the least significant bit of the OCTET STRING becomes the leastsignificant bit of the BIT STRING. Note that when DER-encoding is being used, this means that theraw public key value without prepended DER-encoding tag and length octets is placed in the subjectPublicKey field.

C.4

Syntax for Elliptic Curve Private Keys

An elliptic curve private key may need to be conveyed, for example, during the key deployment operationof a cryptographic scheme in which a Certification Authority generates and distributes the private keys.
An elliptic curve private key is an unsigned integer. The following ASN.1 syntax may be used.
ECPrivateKey{CURVES:IOSet} ::= SEQUENCE {version INTEGER { ecPrivkeyVer1(1) } (ecPrivkeyVer1),
privateKey OCTET STRING,
parameters [0] Parameters{{IOSet}} OPTIONAL,
publicKey [1] BIT STRING OPTIONAL}
where

 The component version specifies the version number of the elliptic curve private key structure.
The syntax above creates the element ecPrivkeyVer1 of type INTEGER whose value is 1.

Page 82

SEC 1: Elliptic Curve Cryptography Ver. 1.0

 The component privateKey is the private key defined to be the octet string of length dlog2 n 8e=(where n is the order of the curve) obtained from the unsigned integer via the encoding of Section
2.3.7.

 The optional component parameters specifies the elliptic curve domain parameters associatedto the private key. The type Parameters was discussed in Section C.2. If the parameters are
known by other means then this component may be NULL or omitted.

 The optional component publicKey contains the elliptic curve public key associated with theprivate key in question. Public keys were discussed in Section C.3. It may be useful to send the
public key along with the private key, especially in a scheme such as MQV that involves calculations with the public key.

Note that omission of the parameters field of ECPrivateKey should be performed with care because it is important that elliptic curve key pairs are bound to the correct parameters so that an attacker is
not able to coerce the use of the key pair with a different set of parameters.
The syntax for ECPrivateKey may be used, for example, to convey elliptic curve private keys using thesyntax for PrivateKeyInfo as defined in PKCS #8 [74]. In this instance, the value of the component
privateKeyAlgorithm within PrivateKeyInfo shall be id-ecPublicKey as discussed in
section C.3 above. Also in this instance, it is recommended that the elliptic curve domain parameters
are placed in the privateKeyAlgorithm field and the parameters field of ecPrivateKey isomitted.

C.5

Syntax for Signatures

Signatures may need to be conveyed from one party to another whenever ECDSA is used to sign amessage. The following syntax is recommended to represent actual signatures for use within X.509
certificates, CRLs (following [9]), and elsewhere. The signature is conveyed using the parameterized
type SIGNED. It comprises the specification of an algorithm of type AlgorithmIdentifier together
with the actual signature
When the signature is generated using ECDSA with SHA-1, the algorithm component shall containthe object identifier ecdsa-with-SHA1 (defined below) and the parameters component shall contain
NULL. (The elliptic curve domain parameters must then be obtained from some other source, for example,
from the signer’s certificate.) In such cases, the ALGORITHM ecdsa-SHA1, defined below, shall beused.
ecdsa-with-SHA1 OBJECT IDENTIFIER ::= { id-ecSigType 1 }ecdsa-SHA1 ALGORITHM ::= { OID ecdsa-with-SHA1 PARMS NULL }id-ecSigType
OBJECT IDENTIFIER ::= { ansi-X9-62 signatures(4) }The actual value of an ECDSA signature computed using SHA-1, that is, a signature identified by
ecdsa-with-SHA1, is encoded as follows.

SEC 1 - C ASN.1 for Elliptic Curve Cryptography

Page 83

ECDSA-Sig-Value ::= SEQUENCE {r INTEGER,s INTEGER}
X.509 certificates and CRLs represent a signature as a bit string; in such cases, the entire encoding ofa value of ECDSA-Sig-Value is the value of said bit string. Note that when DER-encoding is being
used, this means that the entire ECDSA signature including DER-encoding tag and length octets is placedin the signatureValue field.

C.6

Syntax for Key Derivation Functions

This section provides ASN.1 syntax that may be used to encode input to the key derivation functions specified in Section 3.6. Note that the use of ASN.1 syntax for this purpose is optional - however the use of
ASN.1 syntax in this scenario can help to ensure that the encoding of information fields is unambiguous.
The input to the key derivation functions includes an octet string SharedIn f o. SharedIn f o may containan encoding of ASN1SharedInfo as defined below.
ASN1SharedInfo ::= SEQUENCE {keyInfo
AlgorithmIdentifier,entityUInfo [0] OCTET STRING OPTIONAL,
entityVInfo [1] OCTET STRING OPTIONAL,
suppPubInfo [2] OCTET STRING OPTIONAL,
suppPrivInfo [3] OCTET STRING OPTIONAL}
The components of type ASN1SharedInfo have the following meanings:

 keyInfo specifies the symmetric algorithm for which the derived key is to be used.
 entityUInfo, if present, specifies additional information about the scheme’s initiator such as
the entity’s X.501 distinguished name, the entity’s public key, etc.

 entityVInfo, if present, specifies additional information about the scheme’s responder such as
the entity’s X.501 distinguished name, the entity’s public key, etc.

 suppPubInfo, if present, specifies additional public information known to both entities involvedin the operation of the scheme.

 suppPrivInfo, if present, specifies additional private information known to both entities involved in the operation of the scheme.

An example of the use of ASN1SharedInfo can be found in [13].

Page 84

C.7

SEC 1: Elliptic Curve Cryptography Ver. 1.0

ASN.1 Module

The following comprises the ASN.1 module for those items not defined in ANSI X9.62 [3] or ANSI
X9.63 [4].
CERTICOM {iso(1) identified-organization(3) certicom(132) module(1) ver(1)}DEFINITIONS EXPLICIT TAGS ::= BEGIN--- EXPORTS All;---- Import the required type to define private keys.
-IMPORTS Parameters FROM ANSI-X9-62;
certicom-arc OBJECT IDENTIFIER ::= {iso(1) identified-organization(3) certicom(132)}--- Private-key syntax using Parameters from ANSI X9.62.
-ECPrivateKey ::= SEQUENCE {version INTEGER { ecPrivkeyVer1(1) } (ecPrivkeyVer1),
privateKey OCTET STRING,
parameters [0] Parameters OPTIONAL,
publicKey [1] BIT STRING OPTIONAL}
END

SEC 1 -DPage 85

References

This section lists the references cited in this document.

[1] M. Abdalla, M. Bellare, and P. Rogaway. DHAES: An encryption scheme based on the DiffieHellman problem. 1998. Full version of [11]. Available from:http://www-cse.ucsd.edu/users/mihir/[2] ANSI X9.52-1998: Triple Data Encryption Algorithm Modes of Operation. American Bankers Association, 1998.
[3] ANSI X9.62-1998: Public Key Cryptography for the Financial Services Industry: the Elliptic Curve
Digital Signature Algorithm (ECDSA). American Bankers Association, 1999.
[4] ANSI X9.63-199x: Public Key Cryptography for the Financial Services Industry: Key Agreement
and Key Transport Using Elliptic Curve Cryptography. October, 1999. Working Draft.
[5] ANSI X9.71-199x: Keyed Hash Message Authentication Code. March, 1998. Working Draft.
[6] G. Agnew, T. Beth, R. Mullin, and S. Vanstone. Arithmetic operations in GF (2m ). Journal of Cryptology, 6, pages 3–13, 1993.
[7] G. Agnew, R. Mullin, and S. Vanstone. An implementation of elliptic curve cryptosystems overF 2155 . IEEE Journal on Selected Areas in Communications, 11, pages 804–813, 1993.
[8] G. Agnew, R. Mullin, I. Onyszchuk, and S. Vanstone. An implementation for a fast public-key
cryptosystem. Journal of Cryptology, 3, pages 63–79, 1991.
[9] L. Bassham, R. Housley, and W. Polk. Representation of Public Keys and Digital Signatures inInternet X.509 Public Key Infrastructure Certificates. July, 2000. Internet Draft. Available from:http://www.ietf.org/[10] M. Bellare, R. Canetti, and H. Krawczyk. A modular approach to the design and analysis of authentication and key exchange protocols. Proceedings of the 30th Annual Symposium on the Theory ofComputing. 1998.
[11] M. Bellare and P. Rogaway. Minimizing the use of random oracles in authenticated encryption
schemes. In Proceedings of PKS’97, 1997.
[12] I. Blake, G. Seroussi, and N. Smart. Elliptic Curves in Cryptography, Cambridge University Press,
1999.
[13] S. Blake-Wilson and D. Brown. Use of ECC algorithms in CMS. September, 2000. Internet Draft.
Available from: http://www.ietf.org/

Page 86

SEC 1: Elliptic Curve Cryptography Ver. 1.0[14] S. Blake-Wilson, D. Johnson, and A.J. Menezes. Key agreement protocols and their security analysis. In Proceedings of the sixth IMA International Conference on Cryptography and Coding, pages
30–45, 1997.
[15] S. Blake-Wilson and A.J. Menezes. Unknown key-share attacks on the Station-to-Station (STS)protocol. In Public Key Cryptography: PKC ’99, pages 154–170, 1999.
[16] M. Blaze, W. Diffie, R. Rivest, B. Schneier, T. Shimomura, E. Thompson, and M. Wiener. Minimal
key lengths for symmetric ciphers to provide adequate commercial security. January, 1996.
[17] D. Boneh. The decision Diffie-Hellman problem. In Algorithmic Number Theory III, pages 48–63,
1998.
[18] D. Boneh, R.A. DeMillo, and R.J. Lipton. On the importance of checking cryptographic protocols
for faults. In Advances in Cryptology – EUROCRYPT ’97, pages 37–51, 1997.
[19] D. Boneh and R.J. Lipton. Algorithms for black-box fields and their application to cryptography. In
Advances in Cryptology: Crypto ’96, pages 283–297, 1996.
[20] D. Boneh and R. Venkatesan. Hardness of computing the most significant bits of secret keys in
Diffie-Hellman and related schemes. In Advances in Cryptology: Crypto ’96, pages 129–142, 1996.
[21] Certicom. ECC Challenge. Details available from: http://www.certicom.com/chal/[22] M. Chen and E. Hughes. Protocol failures related to order of encryption and signature: computationof discrete logarithms in RSA groups. ACISP ’98. Queensland. 1998.
[23] R. Cramer and V. Shoup. A practical public key cryptosystem provably secure against adaptive
chosen ciphertext attack. In Advances in Cryptology: Crypto ’98, pages 13–25, 1998.
[24] T. Dierks and B. Anderson. ECC Cipher Suites for TLS. March, 1998. Internet Draft. Available
from: http://www.ietf.org/[25] W. Diffie and M. Hellman. New directions in cryptography. IEEE Transactions on Information
Theory, IT-22(6): 644–654, November 1976.
[26] W. Diffie, P.C. van Oorschot, and M.J. Wiener. Authentication and authenticated key exchanges.
Designs, Codes, and Cryptography, 2: 107–125, 1992.
[27] T. ElGamal. A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE
Transactions on Information Theory, IT-31: pages 469–472, 1985.
[28] P. Fahn. IKE authentication using ECDSA. Internet Engineering Task Force, IPSec working group.
Internet Draft. March, 2000. Available from: http://www.ietf.org/[29] FIPS 46-2. Data Encryption Standard. Federal Information Processing Standards Publication 46-2,
1993. Available from: http://csrc.nist.gov/

SEC 1 -Page 87[30] FIPS 180-1. Secure Hash Standard, Federal Information Processing Standards Publication 180-1,
1995. Available from: http://csrc.nist.gov/[31] FIPS 186-2, Digital Signature Standard. Federal Information Processing Standards Publication
186-2, 2000. Available from: http://csrc.nist.gov/[32] G. Frey and H.-G. Ruck. A remark concerning m-divisibility and the discrete logarithm problem inthe divisor class group of curves. Mathematics of Computation, 62, pages 865–874, 1994.
[33] FSML. Financial services markup language. Financial Services Technology Consortium, August,1999. Working Draft.
[34] S.D. Galbraith and N.P. Smart. A cryptographic application of the Weil descent. In Cryptography
and Coding, pages 191-200, 1999.
[35] R. Gallant, R. Lambert, and S.A. Vanstone. Improving the parallelized Pollard lambda search on
binary anomalous curves. Mathematics of Computation, number 69, pages 1699-1705, 2000.
[36] P. Gaudry, F. Hess, and N.P. Smart. Constructive and destructive facets of Weil descent on elliptic
curves. Hewlett Packard Laboratories Technical Report. 2000.
[37] GEC 1. Test Vectors for SEC 1. Standards for Efficient Cryptography Group, September, 2000.
Working Draft. Available from: http://www.secg.org/[38] D. Harkins and D. Carrel. The Internet Key Exchange. Internet Engineering Task Force, Internet
RFC 2409, 1998. Available from: http://www.ietf.org/[39] R. Housley, W. Ford, W. Polk, and D. Solo, Internet X.509 Public Key Infrastructure Certificate and
CRL Profile, Internet Engineering Task Force, Internet RFC 2459, 1999. Available from:http://www.ietf.org/[40] IEEE P1363. Standard Specifications for Public-Key Cryptography. Institute of Electrical and Electronics Engineers, 2000.
[41] IEEE P1363A. Standard Specifications for Public-Key Cryptography: Additional Techniques. May,
2000. Working Draft.
[42] ISO/IEC 14888-3. Information technology - Security techniques - Digital signatures with appendix- Part 3: Certificate-based mechanisms.
[43] ISO/IEC 15946-1. Information technology - Security techniques - Cryptographic techniques basedon elliptic curves - Part 1: General. 1998. Working draft.
[44] ISO/IEC 15946-2. Information technology - Security techniques - Cryptographic techniques basedon elliptic curves - Part 2: Digital signatures. 1998. Working draft.
[45] ISO/IEC 15946-3. Information technology - Security techniques - Cryptographic techniques basedon elliptic curves - Part 3: Key establishment. 1998. Working draft.

Page 88

SEC 1: Elliptic Curve Cryptography Ver. 1.0[46] ITU-T Recommendation X.681. Information Technology - Abstract Syntax Notation One (ASN.1):
Information Object Specification. (equivalent to ISO/IEC 8824-2).
[47] ITU-T Recommendation X.690. Information Technology - ASN.1 Encoding Rules: Specification of
Basic Encoding Rules (BER), Canonical Encoding Rules (CER), and Distinguished Encoding Rules(DER). (equivalent to ISO/IEC 8825-1).
[48] D. Johnson. Diffie-Hellman Key Agreement Small Subgroup Attack, a Contribution to X9F1 by
Certicom. July 16, 1996.
[49] D. Jungnickel. Finite Fields: Structure and Arithmetics, B.I.Wissenschaftsverlag, Mannheim, 1993.
[50] B. Kaliski. MQV vulnerability. Posting to ANSI X9F1 and IEEE P1363 newsgroups. 1998.
[51] D. Knuth. The Art of Computer Programming - Seminumerical Algorithms, volume 2, AddisonWesley, second edition 1981.
[52] N. Koblitz. Elliptic curve cryptosystems. Mathematics of Computation, 48, pages 203–209, 1987.
[53] N. Koblitz. CM-curves with good cryptographic properties. In Advances in Cryptology: Crypto ’91,
pages 279–287, 1992.
[54] N. Koblitz. A Course in Number Theory and Cryptography, Springer-Verlag, second edition, 1994.
[55] N. Koblitz, A.J. Menezes, and S.A. Vanstone. The state of elliptic curve cryptography. Designs,
Codes, and Cryptography, volume 19, pages 173–193, 2000.
[56] P. Kocher, J. Jaffe, B. Jun. Differential power analysis. In Advances in Cryptology – CRYPTO ’99,
pages 388–397, 1999.
[57] P. Kocher. Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems. In
Advances in Cryptology – CRYPTO ’96, pages 104–113, 1996.
[58] H. Krawcyzk, M. Bellare, and R. Canetti, HMAC: Keyed Hashing for Message Authentication.
Internet Engineering Task Force, Internet RFC 2104, 1997. Available from:http://www.ietf.org/[59] G. Lay and H. Zimmer. Constructing elliptic curves with given group order over large finite fields.
Algorithmic Number Theory, pages 250–263, 1994.
[60] L. Law, A. Menezes, M. Qu, J. Solinas, and S. Vanstone. An efficient protocol for authenticated key
agreement. Technical report CORR 98-05, Department of Combinatorics & Optimization, University of Waterloo, March, 1998. Available from:http://www.cacr.math.uwaterloo.ca/[61] R. Lidl and H. Neiderreiter. Finite Fields, Cambridge University Press, 1987.
[62] C.H. Lim and P.J. Lee. A key recovery attack on discrete log-based schemes using a prime ordersubgroup. In Advances in Cryptology: Crypto ’97, pages 249–263, 1997.

SEC 1 -Page 89[63] R.J. McEliece. Finite Fields for Computer Scientists and Engineers, Kluwer Academic Publishers,
1987.
[64] A.J. Menezes. Elliptic Curve Public Key Cryptosystems, Kluwer Academic Publishers, 1993.
[65] A.J. Menezes, T. Okamoto, and S.A. Vanstone. Reducing elliptic curve logarithms to logarithms ina finite field. IEEE Transactions on Information Theory, 39, pages 1639–1646, 1993.
[66] A.J. Menezes, M. Qu, and S.A. Vanstone. Some new key agreement protocols providing implicit
authentication. In Secondnd Workshop on Selected Areas in Cryptography - SAC ’95, May, 1995.
[67] A.J. Menezes, P.C. van Oorschot, and S.A. Vanstone. Handbook of Applied Cryptography, CRC
Press, 1997.
[68] V. Miller. Uses of elliptic curves in cryptography. In Advances in Cryptology: Crypto ’85, pages
417–426, 1985.
[69] K. Nyberg and R. Rueppel. A new signature schem based on DSA giving message recovery. 1st
ACM Conference on Computer and Communications Security, pages 58–61, ACM Press, 1993.
[70] K. Nyberg and R. Rueppel. Message recovery for signature schemes based on the discrete logarithm
problem. Designs, Codes, and Cryptography, 7, pages 61–81, 1996.
[71] A. Odlyzko. The Future of Integer Factorization. CryptoBytes, volume 1, number 2, pages 5–12,
summer 1995.
[72] P. Panjwani and Y. Poeluev. Additional ECC groups for IKE. Internet Engineering Task Force, IPSec
working group. Internet Draft. May, 2000. Available from: http://www.ietf.org/[73] S.C. Pohlig and M.E. Hellman. An improved algorithm for computing logarithms over GF ( p) andits cryptographic significance. IEEE Transactions on Information Theory, 24, pages 106–110, 1978.
[74] PKCS #8. Private-key information syntax standard. RSA Laboratories, November, 1993. Available
from: http://www.rsa.com/rsalabs/pubs/PKCS/[75] D. Pointcheval and J. Stern. Security proofs for signatures. Advances in Cryptology - Eurocrypt ’96,
pages 387–398, 1996.
[76] J. Pollard. Monte Carlo methods for index computation mod p. Mathematics of Computation, 32,
pages 918–924, 1978.
[77] T. Satoh and K. Araki. Fermat quotients and the polynomial time discrete log algorithm for anomalous elliptic curves. Comm. Math. Univ. Sancti Pauli, number 47, pages 81–92, 1998.
[78] C.P. Schnorr. Efficient signature generation by smart cards. Journal of Cryptology, 4, pages 161–
174, 1991.
[79] R. Schoof. Elliptic curves over finite fields and the computation of square roots mod p. Mathematics
of Computation, 44, pages 483–494, 1985.

Page 90

SEC 1: Elliptic Curve Cryptography Ver. 1.0[80] I. Semaev. Evaluation of discrete logarithm in a group of P-torsion points of an elliptic curve incharacteristic P. Mathematics of Computation, number 67, pages 353–356, 1998.
[81] J. Silverman. The Arithmetic of Elliptic Curves, Springer-Verlag, 1985.
[82] N. Smart. The discrete logarithm problem on elliptic curves of trace one. Journal of Cryptology,
volume 12, pages 193–196, 1999.
[83] SEC 2. Recommended Elliptic Curve Domain Parameters. Standards for Efficient Cryptography
Group, September, 2000. Working Draft. Available from: http://www.secg.org/[84] P.C. van Oorschot and M. Wiener. Parallel collision search with applications to hash functions anddiscrete logarithms. 2nd ACM Conference on Computer and Communications Security, pages 210–
218, ACM Press. 1994.
[85] P.C. van Oorschot and M. Wiener. On Diffie-Hellman key agreement with short exponents. In Advances in Cryptology: Eurocrypt ’96, pages 332–343, 1996.
[86] S. Vaudenay. Hidden collisions on DSS. In Advances in Cryptology: Crypto ’96, pages 83–88,
1996.
[87] WAP WTLS. Wireless Application Protocol Wireless Transport Layer Security Specification. Wireless Application Protocol Forum, February, 2000.
[88] WAP WMLScript Crypto API. Wireless Application Protocol WMLScript Crypto Library Specification. Wireless Application Protocol Forum, November, 1999.
[89] M. Wiener and R.J. Zuccherato. Fast attacks on elliptic curve cryptosystems. In Fifth Annual Workshop on Selected Areas in Cryptography: SAC ’98, pages 190–200, 1999.