RFC 6090

Fundamental Elliptic Curve Cryptography Algorithms

📅 published February 2011, from ietf

RFC 6090: Fundamental Elliptic Curve Cryptography Algorithms 🎀

okay bestie, RFC 6090 is giving informational energy 🦋 It's called Fundamental Elliptic Curve Cryptography Algorithms, it came out in February 2011, and its ISSN is 2070-1721. The authors are D. McGrew from Cisco Systems, K. Igoe, and M. Salter from the National Security Agency. The header doesn't list anything it obsoletes or updates, so it's just vibing on its own 💅

Abstract ✨

okay so this note explains the core algorithms of Elliptic Curve Cryptography (ECC) the way they were first defined in some seminal references from 1994 and earlier 📚 The goal is to help you implement those basics without using any of the fancy specialized methods that came out later. The only curves in scope are ones defined over fields of characteristic greater than three, and those are the curves used in Suite B 💜

Status of This Memo 📋

This document is not an Internet Standards Track specification. It's published for informational purposes only 🌸

This document is a product of the Internet Engineering Task Force (IETF). It represents the consensus of the IETF community, got public review, and was approved for publication by the Internet Engineering Steering Group (IESG). Not every document the IESG approves is a candidate for any level of Internet Standard, so check out Section 2 of RFC 5741 for the details 🫶

Info about this doc's current status, any errata, and how to send feedback lives at http://www.rfc-editor.org/info/rfc6090. 🔗

Copyright (c) 2011 IETF Trust and the persons identified as the document authors. All rights reserved.

This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) as they're in effect on the date this document was published. Please read these docs carefully, because they spell out your rights and restrictions for this document 👀 Any Code Components pulled out of this document must include the Simplified BSD License text, as described in Section 4.e of the Trust Legal Provisions, and they come without warranty, as described in the Simplified BSD License.

Table of Contents 🧚

   1.  Introduction . . . . . . . . . . . . . . . . . . . . . . . . .  3
     1.1.  Conventions Used in This Document  . . . . . . . . . . . .  4
   2.  Mathematical Background  . . . . . . . . . . . . . . . . . . .  4
     2.1.  Modular Arithmetic . . . . . . . . . . . . . . . . . . . .  4
     2.2.  Group Operations . . . . . . . . . . . . . . . . . . . . .  5
     2.3.  The Finite Field Fp  . . . . . . . . . . . . . . . . . . .  6
   3.  Elliptic Curve Groups  . . . . . . . . . . . . . . . . . . . .  7
     3.1.  Homogeneous Coordinates  . . . . . . . . . . . . . . . . .  8
     3.2.  Other Coordinates  . . . . . . . . . . . . . . . . . . . .  9
     3.3.  ECC Parameters . . . . . . . . . . . . . . . . . . . . . .  9
       3.3.1.  Discriminant . . . . . . . . . . . . . . . . . . . . . 10
       3.3.2.  Security . . . . . . . . . . . . . . . . . . . . . . . 10
   4.  Elliptic Curve Diffie-Hellman (ECDH) . . . . . . . . . . . . . 10
     4.1.  Data Types . . . . . . . . . . . . . . . . . . . . . . . . 11
     4.2.  Compact Representation . . . . . . . . . . . . . . . . . . 11
   5.  Elliptic Curve ElGamal Signatures  . . . . . . . . . . . . . . 11
     5.1.  Background . . . . . . . . . . . . . . . . . . . . . . . . 11
     5.2.  Hash Functions . . . . . . . . . . . . . . . . . . . . . . 12
     5.3.  KT-IV Signatures . . . . . . . . . . . . . . . . . . . . . 12
       5.3.1.  Keypair Generation . . . . . . . . . . . . . . . . . . 12
       5.3.2.  Signature Creation . . . . . . . . . . . . . . . . . . 13
       5.3.3.  Signature Verification . . . . . . . . . . . . . . . . 13
     5.4.  KT-I Signatures  . . . . . . . . . . . . . . . . . . . . . 14
       5.4.1.  Keypair Generation . . . . . . . . . . . . . . . . . . 14
       5.4.2.  Signature Creation . . . . . . . . . . . . . . . . . . 14
       5.4.3.  Signature Verification . . . . . . . . . . . . . . . . 14
     5.5.  Converting KT-IV Signatures to KT-I Signatures . . . . . . 15
     5.6.  Rationale  . . . . . . . . . . . . . . . . . . . . . . . . 15
   6.  Converting between Integers and Octet Strings  . . . . . . . . 16
     6.1.  Octet-String-to-Integer Conversion . . . . . . . . . . . . 17
     6.2.  Integer-to-Octet-String Conversion . . . . . . . . . . . . 17

   7.  Interoperability . . . . . . . . . . . . . . . . . . . . . . . 17
     7.1.  ECDH . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
     7.2.  KT-I and ECDSA . . . . . . . . . . . . . . . . . . . . . . 18
   8.  Validating an Implementation . . . . . . . . . . . . . . . . . 18
     8.1.  ECDH . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
     8.2.  KT-I . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
   9.  Intellectual Property  . . . . . . . . . . . . . . . . . . . . 20
     9.1.  Disclaimer . . . . . . . . . . . . . . . . . . . . . . . . 20
   10. Security Considerations  . . . . . . . . . . . . . . . . . . . 21
     10.1. Subgroups  . . . . . . . . . . . . . . . . . . . . . . . . 21
     10.2. Diffie-Hellman . . . . . . . . . . . . . . . . . . . . . . 22
     10.3. Group Representation and Security  . . . . . . . . . . . . 22
     10.4. Signatures . . . . . . . . . . . . . . . . . . . . . . . . 23
   11. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 23
   12. References . . . . . . . . . . . . . . . . . . . . . . . . . . 23
     12.1. Normative References . . . . . . . . . . . . . . . . . . . 23
     12.2. Informative References . . . . . . . . . . . . . . . . . . 25
   Appendix A.  Key Words . . . . . . . . . . . . . . . . . . . . . . 29
   Appendix B.  Random Integer Generation . . . . . . . . . . . . . . 29
   Appendix C.  Why Compact Representation Works  . . . . . . . . . . 30
   Appendix D.  Example ECC Parameter Set . . . . . . . . . . . . . . 31
   Appendix E.  Additive and Multiplicative Notation  . . . . . . . . 32
   Appendix F.  Algorithms  . . . . . . . . . . . . . . . . . . . . . 32
     F.1.  Affine Coordinates . . . . . . . . . . . . . . . . . . . . 32
     F.2.  Homogeneous Coordinates  . . . . . . . . . . . . . . . . . 33

1. Introduction 🩷

ECC is a public-key tech that gives you performance advantages at higher security levels 💖 It includes an elliptic curve version of the Diffie-Hellman key exchange protocol [DH1976] and elliptic curve versions of the ElGamal Signature Algorithm [E1985]. ngl, adoption of ECC has been slower than people expected, maybe because there weren't many freely available normative docs and there was uncertainty about intellectual property rights 😭

This note describes the fundamental ECC algorithms over finite fields with characteristic greater than three, based directly on the original references 📖 The point is to give the Internet community a summary of the basic algorithms that came before any specialized or optimized ones. The summary is detailed enough to be used as a normative reference, and the original descriptions and notations were followed as closely as possible 🧁

There are several standards that specify or include ECC algorithms, like the Internet Key Exchange (IKE), ANSI X9.62, and IEEE P1363. The algorithms in this note can interoperate with some of the algorithms in those standards, with a suitable choice of parameters and options. All the specifics are itemized in Section 7 🎀

Here's how the rest of the note is laid out 🗺️ Sections 2.1, 2.2, and 2.3 give you the terminology and notation from modular arithmetic, group theory, and the theory of finite fields, in that order. Section 3 defines the groups based on elliptic curves over finite fields with characteristic greater than three. Section 4 covers the fundamental Elliptic Curve Diffie-Hellman (ECDH) algorithm, and Section 5 covers elliptic curve versions of the ElGamal signature method. Section 6 specifies how integers are represented as octet strings. Sections 2 through 6, inclusive, hold all of the normative text (the stuff that defines the norm for implementations conforming to this spec), and everything after them is purely informative. Section 7 talks about interoperability, Section 8 about validation testing, and Section 9 reviews intellectual property issues. Section 10 sums up security considerations, and Appendix B covers random number generation. The other appendices just provide clarifying details 🦋

1.1. Conventions Used in This Document 📏

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in Appendix A. 🔑

2. Mathematical Background 🧮

This section reviews the math basics and sets up the terminology and notation used below. Let's gooo 🚀

2.1. Modular Arithmetic 🌙

This section reviews modular arithmetic. Two integers x and y are said to be congruent modulo n if x - y is an integer multiple of n. ✨

Two integers x and y are coprime when their greatest common divisor is 1. In that case, there's no third number z > 1 such that z divides x and z divides y. 💅

The set Zq = { 0, 1, 2, ..., q-1 } is closed under the operations of modular addition, modular subtraction, modular multiplication, and modular inverse. Here's how each one works 🍓

  • Modular addition: for each pair of integers a and b in Zq, a + b mod q is equal to a + b if a + b < q, and is equal to a + b - q otherwise.
  • Modular subtraction: for each pair of integers a and b in Zq, a - b mod q is equal to a - b if a - b >= 0, and is equal to a - b + q otherwise.
  • Modular multiplication: for each pair of integers a and b in Zq, a * b mod q is equal to the remainder of a * b divided by q.
  • Modular inverse: for each integer x in Zq that is coprime with q, the inverse of x modulo q is denoted as 1/x mod q, and it can be computed using the extended Euclidean algorithm (see Section 4.5.2 of [K1981v2], for example). 🧠

Algorithms for these operations are well known. For instance, see Chapter 4 of [K1981v2]. 📚

2.2. Group Operations

okay so this section is the groundwork for all the group stuff coming later 🧚 the original points to [D1966] if you want background reading, and honestly that's a solid move 💅

A group is a set of elements G plus an operation that takes any two elements in G and gives back a third element in G 🌸 The operation is written as *, so a * b means the operation applied to a and b. It's associative, which means a * (b * c) is identical to (a * b) * c for all a, b, and c in G 🎀 Repeated application of the group operation N-1 times to an element a is written as a^N, for any positive integer N. So a^2 = a * a, a^3 = a * a * a, and it keeps going like that 💖 Associativity is the reason a^n is unambiguous. No matter how you group the terms, you get the same answer ✨

Multiplicative notation is what we just used. There's also additive notation, where a * b is written as a + b and a^N is written as N * a 🦋 In multiplicative notation, a^N is called exponentiation, and the same thing in additive notation is called scalar multiplication. This document sticks with multiplicative notation everywhere for consistency 💜 Appendix E explains how the two notations line up.

Every group has a special element called the identity element, written as e. For each element a in G, e * a = a * e = a 🌈 By convention, a^0 is equal to the identity element for any a in G.

Every group element a has a unique inverse element b, where a * b = b * a = e 🔥 In multiplicative notation the inverse of a is written a^-1. (In additive notation, the inverse of a is written -a.) For any positive integer X, a^(-X) is defined to be (a^-1)^(X). With that convention, exponentiation behaves exactly the way you'd hope. For any integers X and Y:

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

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

In cryptographic applications, people usually work with finite groups, meaning groups with a finite number of elements. For those, the number of elements is also called the order of the group 👑 A group element a has finite order if a^X = e for some positive integer X, and the order of a is the smallest such X. If no such X exists, a has infinite order. All elements of a finite group have finite order, and the order of an element is always a divisor of the group order 🫶

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

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

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

the set H = { a, a^2, a^3, ... , a^R=e } forms a subgroup of G,
called the cyclic subgroup generated by a, and a is said to be a
generator of H.

Usually there are several group elements that generate H ✨ Any group element of the form a^M, with M relatively prime to R, also generates H. Note that a^M is equal to g^(M modulo R) for any non-negative integer M 🍓

Given the element a of order R, and an integer i between 1 and R-1, inclusive, you can compute a^i with the "square and multiply" method outlined in Section 2.1 of [M1983] (see also Knuth, Vol. 2, Section 4.6.3), or with other methods 💅

2.3. The Finite Field Fp

This section sets up the terminology and notation for finite fields with prime characteristic 🦋

When p is a prime number, the set Zp, together with the addition, subtraction, multiplication, and division operations, is a finite field with characteristic p 💜 Each nonzero element x in Zp has an inverse 1/x. There's a one-to-one correspondence between the integers from zero to p-1, inclusive, and the elements of the field 🌸 The field Zp is sometimes written as Fp or GF(p).

Equations involving field elements don't explicitly write the "mod p" operation, but it's understood to be there implicitly 🎀 For example, saying that x, y, and z are in Fp and

z = x + y

is the same as saying that x, y, and z are in the set { 0, 1, ..., p-1 } and

z = x + y mod p.

3. Elliptic Curve Groups

This note only covers elliptic curves over fields with characteristic greater than three 🧚 These are the curves used in Suite B [SuiteB]. For other fields, the definition of the elliptic curve group would be different 🌈

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

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

where x, y, a, and b are elements of the field Fp [M1985], and the discriminant is nonzero (as described in Section 3.3.1) ✨ A point on an elliptic curve is a pair (x,y) of values in Fp that satisfies the curve equation. Or it's a special point (@,@) that represents the identity element, which is called the "point at infinity" 💖 The order of an elliptic curve group is the number of distinct points.

Two elliptic curve points (x1,y1) and (x2,y2) are equal whenever x1=x2 and y1=y2, or when both points are the point at infinity 🦋 The inverse of the point (x1,y1) is the point (x1,-y1). The point at infinity is its own inverse 💅

The group operation for the elliptic curve group goes like this [BC1989] 🔥 For an arbitrary pair of points P and Q, specified by their coordinates (x1,y1) and (x2,y2) respectively, the group operation gives a third point P*Q with coordinates (x3,y3). Those coordinates are computed as follows:

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

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

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

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

In the equations above, a, x1, x2, x3, y1, y2, and y3 are elements of the field Fp. So computing x3 and y3 in practice has to reduce the right-hand side modulo p 🌸 Pseudocode for the group operation is in Appendix F.1 🎀

The representation of elliptic curve points as a pair of integers in Zp is known as the affine coordinate representation 💜 This representation is suitable as an external data representation for communicating or storing group elements, though the point at infinity must be treated as a special case 🫶

Some pairs of integers are not valid elliptic curve points. A valid pair satisfies the curve equation, while an invalid pair does not 🙈

3.1. Homogeneous Coordinates

Hold on, the heading below is part of this same section, so here it is properly 👇

3.1. Homogeneous Coordinates

There's an alternative way to implement the group operation, using homogeneous coordinates [K1987] (see also [KMOV1991]). This method is typically more efficient because it doesn't need a modular inversion operation 🚀

An elliptic curve point (x,y), other than the point at infinity (@,@), is equivalent to a point (X,Y,Z) in homogeneous coordinates whenever x=X/Z mod p and y=Y/Z mod p 🦋

Let P1=(X1,Y1,Z1) and P2=(X2,Y2,Z2) be points on an elliptic curve. Suppose that P1 and P2 are not equal to (@,@), P1 is not equal to P2, and P1 is not equal to P2^-1. Then the product P3=(X3,Y3,Z3) = P1 * P2 is given by

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

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

Z3 = v^3 * Z1 * Z2 mod p

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

When P1 and P2 are equal, then (X1/Z1, Y1/Z1) is equal to (X2/Z2, Y2/Z2). That's true if and only if u and v are both equal to zero 🌈

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

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

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

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

where w = 3 * X1^2 + a * Z1^2 mod p. In the equations above, a, u, v, w, X1, X2, X3, Y1, Y2, Y3, Z1, Z2, and Z3 are integers in the set Fp ✨ Pseudocode for the group operation in homogeneous coordinates is in Appendix F.2 🎀

When converting from affine coordinates to homogeneous coordinates, it's convenient to set Z to 1. When converting from homogeneous coordinates back to affine coordinates, you have to do a modular inverse to find 1/Z mod p 🫶

3.2. Other Coordinates

Some other coordinate systems have been described. Several are documented in [CC1986], including Jacobi coordinates 🌸

3.3. ECC Parameters

In cryptographic contexts, an elliptic curve parameter set consists of a cyclic subgroup of an elliptic curve, together with a preferred generator of that subgroup 💜 When you're working over a prime order finite field with characteristic greater than three, an elliptic curve group is completely specified by these parameters:

  • The prime number p that indicates the order of the field Fp.
  • The value a used in the curve equation.
  • The value b used in the curve equation.
  • The generator g of the subgroup.
  • The order n of the subgroup generated by g.

An example of an ECC parameter set is in Appendix D 🦋

Parameter generation is out of scope for this note 🙈

Each elliptic curve point is associated with a particular parameter set. The elliptic curve group operation is only defined between two points in the same group. It's an error to apply the group operation to two elements from different groups, or to apply it to a pair of coordinates that isn't a valid point. (A pair (x,y) of coordinates in Fp is a valid point only when it satisfies the curve equation.) See Section 10.3 for further information 🔥

3.3.1. Discriminant

For each elliptic curve group, the discriminant -16*(4*a^3 + 27*b^2) must be nonzero modulo p [S1986]. This requires that

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

3.3.2. Security

Security depends heavily on the choice of these parameters 🔐 This section gives normative guidance on acceptable choices. See also Section 10 for informative guidance 👑

The order of the group generated by g MUST be divisible by a large prime, in order to preclude easy solutions of the discrete logarithm problem [K1987] 💅

With some parameter choices, the discrete log problem is significantly easier to solve. This includes parameter sets in which b = 0 and p = 3 (mod 4), and parameter sets in which a = 0 and p = 2 (mod 3) [MOV1993]. These parameter choices are inferior for cryptographic purposes and SHOULD NOT be used. 💀

4. Elliptic Curve Diffie-Hellman (ECDH)

The Diffie-Hellman (DH) key exchange protocol [DH1976] lets two parties who are talking over an insecure channel agree on a secret key 🫶 It was originally defined in terms of operations in the multiplicative group of a field with a large prime characteristic. Massey [M1983] noticed that it can be generalized easily, so it's defined in terms of an arbitrary cyclic group 🦋 Miller [M1985] and Koblitz [K1987] analyzed the DH protocol over an elliptic curve group. This document describes DH following the former reference 💖

Let G be a group, let g be a generator for that group, and let t denote the order of G. The DH protocol runs like this 🌈 Party A chooses an exponent j between 1 and t-1, inclusive, uniformly at random, computes g^j, and sends that element to B. Party B chooses an exponent k between 1 and t-1, inclusive, uniformly at random, computes g^k, and sends that element to A. Each party can then compute g^(j*k): party A computes (g^k)^j, and party B computes (g^j)^k ✨

See Appendix B for how random integers are generated 🎀

4.1. Data Types

Okay so every run of ECDH is tied to one parameter set (bestie, check Section 3.3 🎀). The public keys g^j and g^k and the shared secret g^(j*k) all live in the cyclic subgroup linked to that set 🦋. An ECDH private key z is an integer in Zt, where t is the order of the subgroup 💅.

4.2. Compact Representation

So [M1985] (in the final paragraph) says the x-coordinate of g^(j*k) is a legit stand-in for the whole point whenever exponentiation is used as a one-way function ✨. In ECDH, once g^(j*k) is computed, you can just use that x-coordinate as the shared secret. We call this compact output 💖.

Following [M1985] again, when compact output is used in ECDH, you only need to send the x-coordinate of an elliptic curve point, not both coordinates like in the usual affine coordinate representation 🫶. We call this the compact representation. The math behind it is explained in Appendix C 🧚.

ECDH can be used with or without compact output. Both parties in a particular run of the ECDH protocol MUST use the same method 🙈. ECDH can be used with or without compact representation. If compact representation is used in a particular run of the ECDH protocol, then compact output MUST be used as well 🔥.

5. Elliptic Curve ElGamal Signatures ✨

5.1. Background

The ElGamal signature algorithm came out in 1984 [E1984a] [E1984b] [E1985] 🦋. It's based on the discrete logarithm problem, and it was first defined for the multiplicative group of the integers modulo a large prime number. It's pretty easy to extend it to other finite groups, like the multiplicative group of the finite field GF(2^w) [AMV1990] or an elliptic curve group [A1992] 💅.

An ElGamal signature is a pair of components. There are lots of possible generalizations of ElGamal signature methods, made by rearranging the equation for the second component. See [HMP1994], [HP1994], [NR1994], [A1992], and [AMV1990] 🌈. These generalizations don't depend on the mathematical group used, and they've been described for the multiplicative group modulo a prime number, the multiplicative group of GF(2^w), and elliptic curve groups [HMP1994] [NR1994] [AMV1990] [A1992] ✨.

The Digital Signature Algorithm (DSA) [FIPS186] is a big deal, and it's an important ElGamal signature variant 👑.

5.2. Hash Functions

ElGamal signatures must use a collision-resistant hash function. That's how they can sign messages of any length and avoid existential forgery attacks, so see Section 10.4 🔒. (This is true for all ElGamal variants [HMP1994].) We denote the hash function as h(). Its input is a bit string of any length, and its output is a non-negative integer 🌸.

Let H() be a hash function whose output is a fixed-length bit string. To use H in an ElGamal signature method, we define the mapping between that output and the non-negative integers. This is what makes h() from above real 💖. Given a bit string m, h(m) is computed like this:

  1. Evaluate H(m). The result is a fixed-length bit string.
  2. Convert that bit string to an integer i. The leftmost (initial) bit is the most significant bit of i, and the rightmost (final) bit is the least significant bit of i 🧠.

5.3. KT-IV Signatures

Koyama and Tsuruoka described a signature method based on Elliptic Curve ElGamal. In it, the first signature component is the x-coordinate of an elliptic curve point reduced modulo q [KT1994] 🎀. In this section, we go over that method, which we call KT-IV.

The algorithm uses an elliptic curve group, as described in Section 3.3, with prime field order p and curve equation parameters a and b. We denote the generator as alpha, and the order of the generator as q. We follow [FIPS186] when checking for exceptional cases 👀.

5.3.1. Keypair Generation

The private key z is an integer between 1 and q-1, inclusive, and it's generated uniformly at random. (See Appendix B about random integers 🎲.) The public key is the group element Y = alpha^z. Each public key is linked to a particular parameter set, as per Section 3.3 💅.

5.3.2. Signature Creation

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

  1. Choose an integer k uniformly at random from all the integers between 1 and q-1, inclusive. (See Appendix B about random integers.)
  2. Calculate R = (r_x, r_y) = alpha^k.
  3. Calculate s1 = r_x mod q.
  4. Check if h(m) + z * s1 = 0 mod q. If so, a new value of k MUST be generated and the signature MUST be recalculated. As an option, one MAY check if s1 = 0. If so, a new value of k SHOULD be generated and the signature SHOULD be recalculated. (It's extremely unlikely that s1 = 0 or h(m) + z * s1 = 0 mod q if signatures are generated properly 🙈.)
  5. Calculate s2 = k/(h(m) + z*s1) mod q.

The signature is the ordered pair (s1, s2). Both signature components are non-negative integers 💖.

5.3.3. Signature Verification

Given the message m, the generator g, the group order q, the public key Y, and the signature (s1, s2), verification goes like this:

  1. Check that 0 < s1 < q and 0 < s2 < q. If either condition is violated, the signature SHALL be rejected 🚫.
  2. Compute the non-negative integers u1 and u2, where:
u1 = h(m) * s2 mod q, and

u2 = s1 * s2 mod q.
  1. Compute the elliptic curve point R' = alpha^u1 * Y^u2.
  2. If the x-coordinate of R' mod q is equal to s1, then the signature and message pass the verification. Otherwise, they fail 🧚.

5.4. KT-I Signatures

Horster, Michels, and Petersen sorted out lots of different ElGamal signature methods, showed they're equivalent, and explained how to convert signatures of one type to another [HMP1994] 🌈. In their terminology, the signature method in Section 5.3 and [KT1994] is a Type IV method, which is why it's called KT-IV.

A Type I KT signature method has a second component that's computed the same way as in the Digital Signature Algorithm. In this section, we describe that method, which we call KT-I ✨.

5.4.1. Keypair Generation

Keypairs and keypair generation are exactly as in Section 5.3.1 💅.

5.4.2. Signature Creation

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

  1. Choose an integer k uniformly at random from all the integers between 1 and q-1, inclusive. (See Appendix B about random integers.)
  2. Calculate R = (r_x, r_y) = alpha^k.
  3. Calculate s1 = r_x mod q.
  4. Calculate s2 = (h(m) + z*s1)/k mod q.
  5. As an option, one MAY check if s1 = 0 or s2 = 0. If either s1 = 0 or s2 = 0, a new value of k SHOULD be generated and the signature SHOULD be recalculated. (It's extremely unlikely that s1 = 0 or s2 = 0 if signatures are generated properly 🙈.)

The signature is the ordered pair (s1, s2). Both signature components are non-negative integers 💖.

5.4.3. Signature Verification

Given the message m, the public key Y, and the signature (s1, s2), verification goes like this:

  1. Check that 0 < s1 < q and 0 < s2 < q. If either condition is violated, the signature SHALL be rejected 🚫.
  2. Compute s2_inv = 1/s2 mod q.
  3. Compute the non-negative integers u1 and u2, where:
u1 = h(m) * s2_inv mod q, and

u2 = s1 * s2_inv mod q.
  1. Compute the elliptic curve point R' = alpha^u1 * Y^u2.
  2. If the x-coordinate of R' mod q is equal to s1, then the signature and message pass the verification. Otherwise, they fail 🧚.

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

A KT-IV signature for a message m and a public key Y can easily be converted into a KT-I signature for the same message and public key. If (s1, s2) is a KT-IV signature for a message m, then (s1, 1/s2 mod q) is a KT-I signature for that same message [HMP1994] 🦋.

The conversion operation uses only public information. It can be performed by the creator of the pre-conversion KT-IV signature, the verifier of the post-conversion KT-I signature, or any other entity 👑.

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

5.6. Rationale

This subsection is not normative for this specification and is provided only as background information 📚.

[HMP1994] presents many generalizations of ElGamal signatures. Equation (5) of that reference shows the general signature equation:

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

where x_A is the private key, k is the secret value, and A, B, and C are determined by the Type of the equation, as shown in Table 1 of [HMP1994]. DSA [FIPS186] is an EG-I.1 signature method (as is KT-I), with A = m, B = -r, and C = s. (Here we use the notation of [HMP1994], where the first signature component is r and the second is s. In KT-I and KT-IV these components are called s1 and s2, respectively. The private key x_A corresponds to the private key z.) Its signature equation is:

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

The signature method of [KT1994] and Section 5.3 is an EG-IV.1 method, with A = m * s, B = -r * s, C = 1. Its signature equation is:

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

The functions f and g mentioned in Table 1 of [HMP1994] are just multiplication, as described under the heading "Fifth generalization" 🌸.

In the equations above, we rely on the implicit conversion of the message m from a bit string to an integer. No hash function is shown in these equations. But, as described in Section 10.4, a hash function should be applied to the message before signing to prevent existential forgery attacks 🔒.

Nyberg and Rueppel [NR1994] studied many different ElGamal signature methods and defined "strong equivalence" like this:

Two signature methods are called strongly equivalent if the signature of the first scheme can be transformed efficiently into signatures of the second scheme and vice versa, without knowledge of the private key.

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

A valid signature with s2=0 leaks the secret key, since in that case z = -h(m) / s1 mod q. We follow [FIPS186] in checking for this exceptional case and for the case that s1=0. The s2=0 check was suggested by Rivest [R1992] and is discussed in [BS1992] 🚨.

[KT1994] uses "a positive integer q' that does not exceed q" when computing the signature component s1 from the x-coordinate r_x of the elliptic curve point R = (r_x, r_y). The value q' is also used during signature validation, when comparing the x-coordinate of a computed elliptic curve point to the value of s1. In this note, we use the simplifying convention that q' = q 💜.

6. Converting between Integers and Octet Strings

A method for converting between integers and octet strings is specified in this section, following the established conventions of public key cryptography [R1993] 🧁. This method lets integers be represented as octet strings that are suitable for transmission or storage 📦. This method SHOULD be used when representing an elliptic curve point or an elliptic curve coordinate as they are defined in this note 🫶.

6.1. Octet-String-to-Integer Conversion

okay bestie, so we take an octet string S and turn it into an integer x 🔢✨ the rule is that the octets S1 through Sk get read from first to last, and the integer x has to satisfy this:

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

basically the first octet is the most significant one in the integer and the last octet is the least significant 💅 it's giving big-endian energy, no cap 🌸

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

6.2. Integer-to-Octet-String Conversion

now the reverse trip 🔄 the integer x gets converted into an octet string S of length k. the string S has to satisfy this:

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

where S1 through Sk are the octets of S from first to last 🧚

same vibe as before: the first octet of S carries the most significance in the integer, and the last octet has the least significance 💜 so the two conversions are literal mirror images of each other, iconic 👑

7. Interoperability ✨

okay so this part is where the algorithms in this note get along with other ECC specs 🫶 the algorithms can be used to interoperate with some other ECC specifications, and this section gives the details for each algorithm 💖

7.1. ECDH

Section 4 can be used with the Internet Key Exchange (IKE) versions one [RFC2409] or two [RFC5996] 🔐 these algorithms are compatible with the ECP groups defined by [RFC5903], [RFC5114], [RFC2409], and [RFC2412] 🦋

the group definition in this protocol uses an affine coordinate representation of the public key. [RFC5903] uses the compact output of Section 4.2, while [RFC4753] (which was obsoleted by RFC 5903) does not 🙈 and neither of those RFCs use compact representation, so the drama is real 😭

also, some groups say the curve parameter "a" is negative 🌈 these values are to be interpreted modulo the order of the field. for example, a parameter of a = -3 is equal to p - 3, where p is the order of the field 🧮 the test cases in Section 8 of [RFC5903] can be used to test an implementation, and those cases use the multiplicative notation, same as this note ✨

the KEi and KEr payloads are equal to g^j and g^k, respectively, with 64 bits of encoding data prepended to them 🍓

the algorithms in Section 4 can be used to interoperate with the IEEE [P1363] and ANSI [X9.62] standards for ECDH based on fields of characteristic greater than three 🎀 IEEE P1363 ECDH can be used in a way that will interoperate with this note, using these options and parameter choices from that spec:

  • prime curves with a cofactor of 1
  • the ECSVDP-DH (Elliptic Curve Secret Value Derivation Primitive, Diffie-Hellman version)
  • the Key Derivation Function (KDF) must be the "identity" function (equivalently, the KDF step should be omitted and the shared secret value should be output directly) 💅

7.2. KT-I and ECDSA

the Digital Signature Algorithm (DSA) is based on the discrete logarithm problem over the multiplicative subgroup of the finite field with large prime order [DSA1991] [FIPS186] 🧠 the Elliptic Curve Digital Signature Algorithm (ECDSA) [P1363] [X9.62] is an elliptic curve version of DSA, so it's basically DSA's glow-up ✨

KT-I is mathematically and functionally equivalent to ECDSA, and it can interoperate with the IEEE [P1363] and ANSI [X9.62] standards for Elliptic Curve DSA (ECDSA) based on fields of characteristic greater than three 🫶 KT-I signatures can be verified using the ECDSA verification algorithm, and ECDSA signatures can be verified using the KT-I verification algorithm. mutual respect 👑

8. Validating an Implementation 🔍

it is essential to validate the implementation of a cryptographic algorithm, periodt 💀 this section outlines tests that should be performed on the algorithms defined in this note 🧪

a known answer test, or KAT, uses a fixed set of inputs to test an algorithm. the output of the algorithm is compared with the expected output, which is also a fixed value 🍓 KATs for ECDH and KT-I are set out in the following subsections 🌸

a consistency test generates inputs for one algorithm being tested using a second algorithm that is also being tested, then checks the output of the first algorithm 🔁 a signature creation algorithm can be tested for consistency against a signature verification algorithm. implementations of KT-I should be tested this way, since their signature generation processes are non-deterministic and thus cannot be tested using a KAT 😭 signature verification algorithms, on the other hand, are deterministic and should be tested via a KAT. this combo of tests covers all of the operations, including keypair generation ✨ consistency testing should also be applied to ECDH 💖

8.1. ECDH

an ECDH implementation can be validated using the known answer test cases from [RFC5903] or [RFC5114] 🦋 the correspondence between the notation in RFC 5903 and the notation in this note is summarized in the table below. (refer to Sections 3.3 and 4; the generator g is expressed in affine coordinate representation as (gx, gy)) 📋

  +----------------------+---------------------------------------+
  | ECDH                 | RFC 5903                              |
  +----------------------+---------------------------------------+
  | order p of field Fp  | p                                     |
  | curve coefficient a  | -3                                    |
  | curve coefficient b  | b                                     |
  | generator g          | g=(gx, gy)                            |
  | private keys j and k | i and r                               |
  | public keys g^j, g^k | g^i = (gix, giy) and g^r = (grx, gry) |
  +----------------------+---------------------------------------+

the correspondence between the notation in RFC 5114 and the notation in this note is summarized in the next table 🌈

        +-----------------------+---------------------------+
        | ECDH                  | RFC 5114                  |
        +-----------------------+---------------------------+
        | order p of field Fp   | p                         |
        | curve coefficient a   | a                         |
        | curve coefficient b   | b                         |
        | generator g           | g=(gx, gy)                |
        | group order n         | n                         |
        | private keys j and k  | dA and dB                 |
        | public keys g^j, g^k  | g^(dA) = (x_qA, y_qA) and |
        |                       | g^(dB) = (x_qB, y_qB)     |
        | shared secret g^(j*k) | g^(dA*dB) = (x_Z, y_Z)    |
        +-----------------------+---------------------------+

8.2. KT-I

a KT-I implementation can be validated using the known answer test cases from [RFC4754] 🎀 the correspondence between the notation in that RFC and the notation in this note is summarized in this table 🧁

                +---------------------+------------------+
                | KT-I                | RFC 4754         |
                +---------------------+------------------+
                | order p of field Fp | p                |
                | curve coefficient a | -3               |
                | curve coefficient b | b                |
                | generator alpha     | g                |
                | group order q       | q                |
                | private key z       | w                |
                | public key Y        | g^w = (gwx,gwy)  |
                | random k            | ephem priv k     |
                | s1                  | r                |
                | s2                  | s                |
                | s2_inv              | sinv             |
                | u1                  | u = h*sinv mod q |
                | u2                  | v = r*sinv mod q |
                +---------------------+------------------+

9. Intellectual Property 💼

concerns about intellectual property have slowed the adoption of ECC 😤 the reason is that a bunch of optimizations and specialized algorithms have been patented in recent years, which is lowkey annoying 🙄

all of the normative references for ECDH (as defined in Section 4) were published during or before 1989, and those for KT-I were published during or before May 1994 📚 all of the normative text for these algorithms is based solely on their respective references 🫶

9.1. Disclaimer

This document is not intended as legal advice. Readers are advised to consult their own legal advisers if they would like a legal interpretation of their rights. ⚖️

the IETF policies and processes regarding intellectual property and patents are outlined in [RFC3979] and [RFC4879] and at https://datatracker.ietf.org/ipr/about/ 📜

10. Security Considerations 🚨

okay, this is the serious part, so buckle up 😭🔥 the security level of an elliptic curve cryptosystem is determined by the cryptanalytic algorithm that is the least expensive for an attacker to implement. there are several algorithms to consider 💀

the Pohlig-Hellman method is a divide-and-conquer technique [PH1978] 🧩 if the group order n can be factored as

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

then the discrete log problem over the group can be solved by independently solving a discrete log problem in groups of order q1, q2, ..., qz, and then combining the results using the Chinese remainder theorem. the overall computational cost is dominated by that of the discrete log problem in the subgroup with the largest order 📐

Shanks' algorithm [K1981v3] computes a discrete logarithm in a group of order n using O(sqrt(n)) operations and O(sqrt(n)) storage 🏃 the Pollard rho algorithm [P1978] computes a discrete logarithm in a group of order n using O(sqrt(n)) operations, with a negligible amount of storage, and it can be efficiently parallelized [VW1994] 🌀

the Pollard lambda algorithm [P1978] can solve the discrete logarithm problem using O(sqrt(w)) operations and O(log(w)) storage, when the exponent is known to lie in an interval of width w 🎯

the algorithms described above work in any group. there are specialized algorithms that specifically target elliptic curve groups 👀 there are no known subexponential algorithms against general elliptic curve groups, though there are methods that target certain special elliptic curve groups; see [MOV1993] and [FR1994] 🌸

10.1. Subgroups

a group consisting of a nonempty set of elements S with associated group operation * is a subgroup of the group with the set of elements G, if the latter group uses the same group operation and S is a subset of G 🧁 for each elliptic curve equation, there is an elliptic curve group whose group order is equal to the order of the elliptic curve. that is, there is a group that contains every point on the curve 💜

the order m of the elliptic curve is divisible by the order n of the group associated with the generator. that is, for each elliptic curve group, m = n * c for some number c 🧮 the number c is called the "cofactor" [P1363]. each ECC parameter set as in Section 3.3 is associated with a particular cofactor ✨

it is possible and desirable to use a cofactor equal to 1 💖

10.2. Diffie-Hellman 💖

okay bestie, so the key exchange from Section 4 does NOT protect you from active attacks 😭 Party A has to use some method to make sure that (g^k) actually came from the intended communicant B and not some sneaky attacker, and Party B has to do the exact same thing with (g^j). 🕵️‍♀️

Authenticating the shared secret g^(j*k) is not enough, ngl. That leaves the protocol open to attacks that mess with the public keys. Instead, the public keys g^x and g^y that get swapped should be directly authenticated. This is the strategy used by protocols that build on Diffie-Hellman and that use end-entity authentication to protect against active attacks, like OAKLEY [RFC2412] and the Internet Key Exchange [RFC2409] [RFC4306] [RFC5996]. Iconic behaviour 👑

When the cofactor of a group is not equal to 1, there are a bunch of attacks that can hit ECDH. Go check out [VW1996], [AV1996], and [LL1997] if you want the receipts 🧾

10.3. Group Representation and Security 🦋

The elliptic curve group operation does not explicitly include the parameter b from the curve equation. This opens the door for a malicious attacker to learn info about an ECDH private key by submitting a bogus public key [BMM2000]. The attacker can craft an elliptic curve group G' with the same parameters as a group G that's being used in an ECDH protocol, except that b is different. Then they submit a point on G' into a run of the ECDH protocol that is using group G, and they gain information from the fact that the group operations using the private key of the device under attack are effectively happening in G' instead of G. Not me being impressed by how sneaky this is 🙈

This attack can gain useful information about an ECDH private key that's tied to a static public key, meaning a public key that gets used in more than one run of the protocol. However, it does not gain any useful information against ephemeral keys. ✨

This sort of attack is thwarted if an ECDH implementation does not assume that each pair of coordinates in Zp is actually a point on the appropriate elliptic curve. Main character energy for implementers 💅

These considerations also apply when ECDH is used with compact representation (see Appendix C). 🌸

10.4. Signatures 🖊️

Elliptic curve parameters should only be used if they come from a trusted source. Otherwise, some attacks are possible [AV1996] [V1996]. Don't skip this one, bestie 🚨

If no hash function is used in an ElGamal signature system, then the system is vulnerable to existential forgeries. That's when an attacker who does not know a private key can generate valid signatures for the associated public key, but cannot generate a signature for a message of its own choosing. (See [E1985] for instance.) Using a collision-resistant hash function gets rid of this vulnerability. It's giving security 🔐

In principle, any collision-resistant hash function is suitable for use in KT signatures. To keep things interoperable, these hashes are recognized as suitable for use as the function H defined in Section 5.2:

SHA-256, which has a 256-bit output.

SHA-384, which has a 384-bit output.

SHA-512, which has a 512-bit output.

All of these hash functions are defined in [FIPS180-2]. 🧚

The number of bits in the output of the hash used in KT signatures should be equal or close to the number of bits needed to represent the group order. Matching sizes, a whole vibe 🎀

11. Acknowledgements ✨

The author wants to say thank you to the originators of elliptic curve cryptography, whose work made this note possible, and to all of the reviewers, who gave valuable constructive feedback. 🫶 Special thanks go to Howard Pinder, Andrey Jivsov, Alfred Hoenes (who contributed the algorithms in Appendix F), Dan Harkins, and Tina Tsou. Love them all 💜

12. References 📚

12.1. Normative References

[AMV1990]    Agnew, G., Mullin, R., and S. Vanstone, "Improved
             Digital Signature Scheme based on Discrete
             Exponentiation", Electronics Letters Vol. 26, No. 14,
             July, 1990.

[BC1989]     Bender, A. and G. Castagnoli, "On the Implementation of
             Elliptic Curve Cryptosystems", Advances in Cryptology -
             CRYPTO '89 Proceedings, Springer Lecture Notes in
             Computer Science (LNCS), volume 435, 1989.

[CC1986]     Chudnovsky, D. and G. Chudnovsky, "Sequences of numbers
             generated by addition in formal groups and new primality
             and factorization tests", Advances in Applied
             Mathematics, Volume 7, Issue 4, December 1986.

[D1966]      Deskins, W., "Abstract Algebra", MacMillan Company New
             York, 1966.

[DH1976]     Diffie, W. and M. Hellman, "New Directions in
             Cryptography", IEEE Transactions in Information
             Theory IT-22, pp. 644-654, 1976.

[FR1994]     Frey, G. and H. Ruck, "A remark concerning
             m-divisibility and the discrete logarithm in the divisor
             class group of curves.", Mathematics of Computation Vol.
             62, No. 206, pp. 865-874, 1994.

[HMP1994]    Horster, P., Michels, M., and H. Petersen, "Meta-ElGamal
             signature schemes", University of Technology Chemnitz-
             Zwickau Department of Computer Science, Technical
             Report TR-94-5, May 1994.

[K1981v2]    Knuth, D., "The Art of Computer Programming, Vol. 2:
             Seminumerical Algorithms", Addison Wesley , 1981.

[K1987]      Koblitz, N., "Elliptic Curve Cryptosystems", Mathematics
             of Computation, Vol. 48, 1987, pp. 203-209, 1987.

[KT1994]     Koyama, K. and Y. Tsuruoka, "Digital signature system
             based on elliptic curve and signer device and verifier
             device for said system", Japanese Unexamined Patent
             Application Publication H6-43809, February 18, 1994.

[M1983]      Massey, J., "Logarithms in finite cyclic groups -
             cryptographic issues", Proceedings of the 4th Symposium
             on Information Theory, 1983.

[M1985]      Miller, V., "Use of elliptic curves in cryptography",
             Advances in Cryptology - CRYPTO '85
             Proceedings, Springer Lecture Notes in Computer Science
             (LNCS), volume 218, 1985.

[MOV1993]    Menezes, A., Vanstone, S., and T. Okamoto, "Reducing
             Elliptic Curve Logarithms to Logarithms in a Finite
             Field", IEEE Transactions on Information Theory Vol. 39,
             No. 5, pp. 1639-1646, September, 1993.

[R1993]      RSA Laboratories, "PKCS#1: RSA Encryption Standard",
             Technical Note version 1.5, 1993.

[S1986]      Silverman, J., "The Arithmetic of Elliptic Curves",
             Springer-Verlag, New York, 1986.

That's the whole reference list for this part 🌈

12.2. Informative References 📚✨

Okay so these are the informative refs, the extra reading that backs up the whole vibe 🧚 Every single one is kept exactly as written, bestie.

[A1992] Anderson, J., "Response to the proposed DSS", Communications of the ACM, v. 35, n. 7, p. 50-52, July 1992.

[AV1996] Anderson, R. and S. Vaudenay, "Minding Your P's and Q's", Advances in Cryptology - ASIACRYPT '96 Proceedings, Springer Lecture Notes in Computer Science (LNCS), volume 1163, 1996.

[BMM2000] Biehl, I., Meyer, B., and V. Muller, "Differential fault analysis on elliptic curve cryptosystems", Advances in Cryptology - CRYPTO 2000 Proceedings, Springer Lecture Notes in Computer Science (LNCS), volume 1880, 2000.

[BS1992] Branstad, D. and M. Smid, "Response to Comments on the NIST Proposed Digital Signature Standard", Advances in Cryptology - CRYPTO '92 Proceedings, Springer Lecture Notes in Computer Science (LNCS), volume 740, August 1992.

[DSA1991] U.S. National Institute of Standards and Technology, "DIGITAL SIGNATURE STANDARD", Federal Register, Vol. 56, August 1991.

[E1984a] ElGamal, T., "Cryptography and logarithms over finite fields", Stanford University, UMI Order No. DA 8420519, 1984.

[E1984b] ElGamal, T., "Cryptography and logarithms over finite fields", Advances in Cryptology - CRYPTO '84 Proceedings, Springer Lecture Notes in Computer Science (LNCS), volume 196, 1984.

[E1985] ElGamal, T., "A public key cryptosystem and a signature scheme based on discrete logarithms", IEEE Transactions on Information Theory, Vol. 30, No. 4, pp. 469-472, 1985.

[FIPS180-2] U.S. National Institute of Standards and Technology, "SECURE HASH STANDARD", Federal Information Processing Standard (FIPS) 180-2, August 2002.

[FIPS186] U.S. National Institute of Standards and Technology, "DIGITAL SIGNATURE STANDARD", Federal Information Processing Standard FIPS-186, May 1994.

[HP1994] Horster, P. and H. Petersen, "Verallgemeinerte ElGamal-Signaturen", Proceedings der Fachtagung SIS '94, Verlag der Fachvereine, Zurich, 1994.

[K1981v3] Knuth, D., "The Art of Computer Programming, Vol. 3: Sorting and Searching", Addison Wesley, 1981.

[KMOV1991] Koyama, K., Maurer, U., Vanstone, S., and T. Okamoto, "New Public-Key Schemes Based on Elliptic Curves over the Ring Zn", Advances in Cryptology - CRYPTO '91 Proceedings, Springer Lecture Notes in Computer Science (LNCS), volume 576, 1991.

[L1969] Lehmer, D., "Computer technology applied to the theory of numbers", M.A.A. Studies in Mathematics, 180-2, 1969.

[LL1997] Lim, C. and P. Lee, "A Key Recovery Attack on Discrete Log-based Schemes Using a Prime Order Subgroup", Advances in Cryptology - CRYPTO '97 Proceedings, Springer Lecture Notes in Computer Science (LNCS), volume 1294, 1997.

[NR1994] Nyberg, K. and R. Rueppel, "Message Recovery for Signature Schemes Based on the Discrete Logarithm Problem", Advances in Cryptology - EUROCRYPT '94 Proceedings, Springer Lecture Notes in Computer Science (LNCS), volume 950, May 1994.

[P1363] "Standard Specifications for Public Key Cryptography", Institute of Electric and Electronic Engineers (IEEE), P1363, 2000.

[P1978] Pollard, J., "Monte Carlo methods for index computation mod p", Mathematics of Computation, Vol. 32, 1978.

[PH1978] Pohlig, S. and M. Hellman, "An Improved Algorithm for Computing Logarithms over GF(p) and its Cryptographic Significance", IEEE Transactions on Information Theory, Vol. 24, pp. 106-110, 1978.

[R1988] Rose, H., "A Course in Number Theory", Oxford University Press, 1988.

[R1992] Rivest, R., "Response to the proposed DSS", Communications of the ACM, v. 35, n. 7, p. 41-47, July 1992.

[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997.

[RFC2409] Harkins, D. and D. Carrel, "The Internet Key Exchange (IKE)", RFC 2409, November 1998.

[RFC2412] Orman, H., "The OAKLEY Key Determination Protocol", RFC 2412, November 1998.

[RFC3979] Bradner, S., "Intellectual Property Rights in IETF Technology", BCP 79, RFC 3979, March 2005.

[RFC4086] Eastlake, D., Schiller, J., and S. Crocker, "Randomness Requirements for Security", BCP 106, RFC 4086, June 2005.

[RFC4306] Kaufman, C., "Internet Key Exchange (IKEv2) Protocol", RFC 4306, December 2005.

[RFC4753] Fu, D. and J. Solinas, "ECP Groups For IKE and IKEv2", RFC 4753, January 2007.

[RFC4754] Fu, D. and J. Solinas, "IKE and IKEv2 Authentication Using the Elliptic Curve Digital Signature Algorithm (ECDSA)", RFC 4754, January 2007.

[RFC4879] Narten, T., "Clarification of the Third Party Disclosure Procedure in RFC 3979", BCP 79, RFC 4879, April 2007.

[RFC5114] Lepinski, M. and S. Kent, "Additional Diffie-Hellman Groups for Use with IETF Standards", RFC 5114, January 2008.

[RFC5903] Fu, D. and J. Solinas, "Elliptic Curve Groups modulo a Prime (ECP Groups) for IKE and IKEv2", RFC 5903, June 2010.

[RFC5996] Kaufman, C., Hoffman, P., Nir, Y., and P. Eronen, "Internet Key Exchange Protocol Version 2 (IKEv2)", RFC 5996, September 2010.

[SuiteB] U. S. National Security Agency (NSA), "NSA Suite B Cryptography", http://www.nsa.gov/ia/programs/suiteb_cryptography/index.shtml.

[V1996] Vaudenay, S., "Hidden Collisions on DSS", Advances in Cryptology - CRYPTO '96 Proceedings, Springer Lecture Notes in Computer Science (LNCS), volume 1109, 1996.

[VW1994] van Oorschot, P. and M. Wiener, "Parallel Collision Search with Application to Hash Functions and Discrete Logarithms", Proceedings of the 2nd ACM Conference on Computer and communications security, pp. 210-218, 1994.

[VW1996] van Oorschot, P. and M. Wiener, "On Diffie-Hellman key agreement with short exponents", Advances in Cryptology - EUROCRYPT '96 Proceedings, Springer Lecture Notes in Computer Science (LNCS), volume 1070, 1996.

[X9.62] "Public Key Cryptography for the Financial Services Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA)", American National Standards Institute (ANSI) X9.62.

Appendix A. Key Words 🎀

Okay so these are the key words, quoted straight from [RFC2119] because they're used all over Internet standards 💅 They got reproduced in this note so we don't need a normative reference from after 1994, which is very much a main character move 🦋

  1. MUST - This word, or the terms "REQUIRED" or "SHALL", means that the definition is an absolute requirement of the specification.
  2. MUST NOT - This phrase, or the phrase "SHALL NOT", means that the definition is an absolute prohibition of the specification.
  3. SHOULD - This word, or the adjective "RECOMMENDED", means that there may exist valid reasons in particular circumstances to ignore a particular item, but the full implications must be understood and carefully weighed before choosing a different course.
  4. SHOULD NOT - This phrase, or the phrase "NOT RECOMMENDED", means that there may exist valid reasons in particular circumstances when the particular behavior is acceptable or even useful, but the full implications should be understood and the case carefully weighed before implementing any behavior described with this label.
  5. MAY - This word, or the adjective "OPTIONAL", means that an item is truly optional. One vendor may choose to include the item because a particular marketplace requires it or because the vendor feels that it enhances the product while another vendor may omit the same item. An implementation which does not include a particular option MUST be prepared to interoperate with another implementation which does include the option, though perhaps with reduced functionality. In the same vein an implementation which does include a particular option MUST be prepared to interoperate with another implementation which does not include the option (except, of course, for the feature the option provides.)

Appendix B. Random Integer Generation 🧚

Generating a random integer is honestly easy, no cap ✨ You just pick an integer uniformly at random between zero and (2^t)-1, inclusive, for some positive integer t. Make a random bit string with exactly t bits, then turn that bit string into a non-negative integer by treating the bits as the coefficients in a base-2 expansion of an integer. Iconic 💖

Sometimes you need an integer r that's random and has some property P, like sitting inside a certain interval. The simple way to do this is the rejection method, and it goes like this 🌸

  1. Generate a candidate number c uniformly at random from a set that includes all numbers that satisfy property P (plus some other numbers, preferably not too many).
  2. If c satisfies property P, then return c. Otherwise, return to Step 1.

For example, to generate a number between 1 and n-1, inclusive, you repeatedly generate integers between zero and (2^t)-1, inclusive, and stop at the first integer that falls within that interval. So cute 🍓

Recommendations on how to generate random bit strings are provided in [RFC4086]. Go check that one out, it's giving essential reading 🫶

Appendix C. Why Compact Representation Works ✨

okay so this one is the "why does this even work?" appendix 🧠 In the affine representation, the x-coordinate of the point P^i does not depend on the y-coordinate of the point P, for any non-negative exponent i and any point P. Bestie, this is lowkey wild. If you only have the x-coordinate of a point P, you can't pin down the y-coordinate exactly, but the y value still has to solve the curve equation:

y^2 = x^3 + a*x + b (mod p).

There are at most two distinct solutions, y = w and y = -w mod p, so the point P has to be either Q=(x,w) or Q^-1=(x,-w). That means P^n is equal to either Q^n or (Q^-1)^n = (Q^n)^-1. Both of those have the same x-coordinate 💅 So the x-coordinate of P^i can be computed from the x-coordinate of P by picking one of the possible y values for P, computing the ith power of P, and then just ignoring the y-coordinate of that result. It's giving math magic ✨

In general, you can compute a square root modulo p using Shanks' method [K1981v2], and there are simple methods for some values of p. When p = 3 (mod 4), the square roots of z mod p are w and -w mod p, where

w = z ^ ((p+1)/4) (mod p);

this observation is due to Lehmer [L1969]. When p has this property, y can be computed from the curve equation, and either y = w or y = -w mod p, where

w = (x^3 + a*x + b)^((p+1)/4) (mod p).

Now the catch 🙈 Square roots modulo p only exist for a quadratic residue modulo p [R1988]. If z is not a quadratic residue, there is no number w such that w^2 = z (mod p). A simple way to check that z is a quadratic residue after computing w is to verify that w * w = z (mod p). If that relation doesn't hold, then the value x is not a valid x-coordinate for a valid elliptic curve point. This is an important consideration when ECDH is used with compact output; see Section 10.3. Don't skip this part, fr fr 😭

The primes used in the P-256, P-384, and P-521 curves described in [RFC5903] all have the property that p = 3 (mod 4). Iconic 👑

Appendix D. Example ECC Parameter Set 🎀

okay, for concreteness, here's an elliptic curve defined by Solinas and Fu in [RFC5903] and referred to as P-256, which is believed to provide a 128-bit security level 🔐 We use the notation of Section 3.3, and express the generator in the affine coordinate representation g=(gx,gy), where the values gx and gy are in Fp.

p: FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF

a: - 3

b: 5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B

n: FFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551

gx: 6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296

gy: 4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5

Note that p can also be expressed as

p = 2^(256)-2^(224)+2^(192)+2^(96)-1.

Appendix E. Additive and Multiplicative Notation 🦋

the early elliptic curve papers used multiplicative notation, but most modern publications use additive notation 📚 This section has a table mapping between those two conventions. In this section, a and b are elements of an elliptic curve group, and N is an integer.

+-------------------------+-----------------------+
| Multiplicative Notation | Additive Notation     |
+-------------------------+-----------------------+
| multiplication          | addition              |
| a * b                   | a + b                 |
| squaring                | doubling              |
| a * a = a^2             | a + a = 2a            |
| exponentiation          | scalar multiplication |
| a^N = a * a * ... * a   | Na = a + a + ... + a  |
| inverse                 | inverse               |
| a^-1                    | -a                    |
+-------------------------+-----------------------+

Appendix F. Algorithms 🧚

this section is the pseudocode for the elliptic curve group operation. Anything that follows the symbol // is a comment, not an instruction, so don't panic when you see it 💜

F.1. Affine Coordinates

to an arbitrary pair of elliptic curve points P and Q, specified by their affine coordinates P=(x1,y1) and Q=(x2,y2), the group operation gives you a third point R = P*Q with the coordinates (x3,y3). Here's how those get computed:

  if P is (@,@),
     R = Q
  else if Q is (@,@),
     R = P
  else if P is not equal to Q and x1 is equal to x2,
     R = (@,@)
  else if P is not equal to Q and x1 is not equal to x2,
     x3 = ((y2-y1)/(x2-x1))^2 - x1 - x2 mod p and
     y3 = (x1-x3)*(y2-y1)/(x2-x1) - y1 mod p
  else if P is equal to Q and y1 is equal to 0,
     R = (@,@)
  else    // P is equal to Q and y1 is not equal to 0
     x3 = ((3*x1^2 + a)/(2*y1))^2 - 2*x1 mod p and
     y3 = (x1-x3)*(3*x1^2 + a)/(2*y1) - y mod p.

From the first and second case, it follows that the point at infinity is the neutral element of this operation, which is its own inverse 🌸

From the curve equation, it follows that for a given curve point P = (x,y) distinct from the point at infinity, (x,-y) is also a curve point. From the third and the fifth case, it follows that this is the inverse of P, P^-1.

Note: The fifth and sixth case are known as "point squaring". 🫶

F.2. Homogeneous Coordinates

an elliptic curve point (x,y) (other than the point at infinity (@,@)) is equivalent to a point (X,Y,Z) in homogeneous coordinates, with X, Y, and Z in Fp and not all three being zero at once, whenever x=X/Z and y=Y/Z. "Homogenous coordinates" means that two triples (X,Y,Z) and (X',Y',Z') are regarded as "equal" (i.e., representing the same point) if there is some nonzero s in Fp such that X'=s*X, Y'=s*Y, and Z'=s*Z. The point at infinity (@,@) is regarded as equivalent to the homogenous coordinates (0,1,0), i.e., it can be represented by any triple (0,Y,0) with nonzero Y in Fp.

Let P1=(X1,Y1,Z1) and P2=(X2,Y2,Z2) be points on the elliptic curve, and let u = Y2 * Z1 - Y1 * Z2 and v = X2 * Z1 - X1 * Z2.

We observe that the points P1 and P2 are equal if and only if u and v are both equal to zero. Otherwise, if either P1 or P2 is equal to the point at infinity, v is zero and u is nonzero (but the converse implication does not hold). 👀

Then, the product P3=(X3,Y3,Z3) = P1 * P2 is given by:

  if P1 is the point at infinity,
     P3 = P2
  else if P2 is the point at infinity,
     P3 = P1
  else if u is not equal to 0 but v is equal to 0,
     P3 = (0,1,0)
  else if both u and v are not equal to 0,
     X3 = v * (Z2 * (Z1 * u^2 - 2 * X1 * v^2) - v^3)
     Y3 = Z2 * (3 * X1 * u * v^2 - Y1 * v^3 - Z1 * u^3) + u * v^3
     Z3 = v^3 * Z1 * Z2
  else    // P2 equals P1, P3 = P1 * P1
      w = 3 * X1^2 + a * Z1^2
     X3 = 2 * Y1 * Z1 * (w^2 - 8 * X1 * Y1^2 * Z1)
     Y3 = 4 * Y1^2 * Z1 * (3 * w * X1 - 2 * Y1^2 * Z1) - w^3
     Z3 = 8 * (Y1 * Z1)^3

So it turns out the point at infinity is the identity element, and for P1=(X,Y,Z) not equal to this point at infinity, P2=(X,-Y,Z) represents P1^-1. Periodt 💅✨

Authors' Addresses 💖

David A. McGrew
Cisco Systems
510 McCarthy Blvd.
Milpitas, CA  95035
USA

Phone: (408) 525 8651
EMail: mcgrew@cisco.com
URI:   http://www.mindspring.com/~dmcgrew/dam.htm
Kevin M. Igoe
National Security Agency
Commercial Solutions Center
United States of America

EMail: kmigoe@nsa.gov
Margaret Salter
National Security Agency
9800 Savage Rd.
Fort Meade, MD  20755-6709
USA

EMail: msalter@restarea.ncsc.mil
📦 where this page comes from