ECDSA Primer

Summary

In the context of cryptography, the elliptic-curve digital signing algorithm (ECDSA) is the message signing algorithm chosen for CV deployment. This algorithm uses elliptic curve cryptography to generate a unique number, called a signature, that is appended to messages. ECDSA uses points along a curve to represent keys that are used for signing and verification purposes.

This document consists of a set of definitions for reference, as well as the basic procedure and pseudocode for creating and verifying a signature.

Definitions

Elliptic curve

A special curve function that follows the formula y³ = x² + ax + b. The values of a and b are either chosen (as in secp256k1) or are randomly generated (as in secp256r1) ^{Note - not sure if this is correct?}. Note that an elliptic curve in crypto is defined as both the function that maps the curve as well as the set of all valid numbers [1,n-1], the field, that fit a set of security requirements for the curve.

Generator Point (G)

Sometimes called "point at infinity", this number is the chosen starting point from which the r and s values of the signature are created. If the curve is a defined curve, such as in secp256k1, this number is always the same number. The private key of ECDSA is the result of multiplying the generator point by a random number d_a: Q_a = d_a x G. Note that this is elliptic curve multiplication.

Public/Private Key

In the context of ECDSA, the private key is a cryptographically secure randomly generated integer in the range of [1,N-1], where N is the field of the function (see Field Size (N) below). The public key is a point that is obtained by doing elliptic curve multiplication of the generator point by the private key. Note - the security of ECDSA rests entirely on the difficulty of reversing this multiplication operation.

Elliptic Curve Multiplication

TODO

Elliptic Curve Addition

TODO

secp256r1

The standard ECDSA implementation chosen for CV deployments. This defines a proven prime from which all public/private keys are predictably derived. Uses a random curve.

secp256k1

The standard ECDSA implementation chosen by BitCoin. More documentation is present on this standard, so examples are taken from this. Uses the Koblitz curve y³ = x² + 7, designed for speed, slightly less secure than secp256r1.

Message

The data we want to sign, in the context of the ODE this is an ASN.1-encoded IEEE1609.2 package that, if decoded, contains the public key used to sign the message and a sha256 digest of the message.

Digest

This is a sha256 hash of the message, this is what is actually signed by the ECDSA routine. By definition of a hashing function, a message digest is always a fixed length.

Signature

A difficult-to-reproduce message appended to a message, secure enough to be considered non-reputable. An ECDSA signature is a concatenation of two numbers, r and s:

r = x₁ mod n

s = k^-1 (z + rd_a) mod n

Where n is the largest number in the field of the chosen function, k is the CSRNG number, and d_a is the private key integer.

Proven Prime (P)

This is a large prime number chosen by a given standard. In secp256k1 corresponding to the value 2²⁵⁶ - 2³² - 2⁹ - 2⁸ - 2⁷ - 2⁴ - 1. Equivalent to 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f or approximately 1.158 x 10⁷⁷. All valid points on the secp256k1 curve are less than this number, because to generate a point the X and Y values are the result of a modulo function by this number. In the case of secp256r1, this number is created through a guess-and-check process and _then included for reference for verifying public key^{Not sure if this is true?}.

Field Size (N)

This represents how many valid points are possible in a given curve and proven prime. In the context of CV, this number is 0xFFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551. A special property of ECDSA math is that these numbers are unique to a specific curve.

Ephemeral point

TODO. Possibly another name for the generator point?

References

Standards Definition Document: http://www.secg.org/SEC2-Ver-1.0.pdf