Basics of ECC handling

The ECC, as any asymmetric cryptography system, deals with private keys and public keys. Private keys are generally used to create signatures, and are kept, as the name suggest, private. That’s because possession of a private key allows creating a signature that can be verified with a public key. If the public key is associated with an identity (like a person or an institution), possession of the private key will allow to impersonate that identity.

The public keys on the other hand are widely distributed, and they don’t have to be kept private. The primary purpose of them, is to allow checking if a given signature was made with the associated private key.

Number representations

On a more low level, the private key is a single number, usually the size of the curve size: a NIST P-256 private key will have a size of 256 bits, though as it needs to be selected randomly, it may be a slightly smaller number (255-bit, 248-bit, etc.). Public points are a pair of numbers. That pair specifies a point on an elliptic curve (a pair of integers that satisfy the curve equation). Those two numbers are similarly close in size to the curve size, so both the x and y coordinate of a NIST P-256 curve will also be around 256 bit in size.

Note

To be more precise, the size of the private key is related to the curve order, i.e. the number of points on a curve. The coordinates of the curve depend on the field of the curve, which usually means the size of the prime used for operations on points. While the order and the prime size are related and fairly close in size, it’s possible to have a curve where either of them is larger by a bit (i.e. it’s possible to have a curve that uses a 256 bit prime that has a 257 bit order).

Since normally computers work with much smaller numbers, like 32 bit or 64 bit, we need to use special approaches to represent numbers that are hundreds of bits large.

First is to decide if the numbers should be stored in a big endian format, or in little endian format. In big endian, the most significant bits are stored first, so a number like $2^{16}$ is saved as a three bytes: byte with value 1 and two bytes with value 0. In little endian format the least significant bits are stored first, so the number like $2^{16}$ would be stored as three bytes: first two bytes with value 0, than a byte with value 1.

For ECDSA big endian encoding is usually used, for EdDSA little endian encoding is usually used.

Secondly, we need to decide if the numbers need to be stored as fixed length strings (zero padded if necessary), or if they should be stored with minimal number of bytes necessary. That depends on the format and place it’s used, some require strict sizes (so even if the number encoded is 1, but the curve used is 128 bit large, that number 1 still needs to be encoded with 16 bytes, with fifteen most significant bytes equal zero).

Public key encoding

Generally, public keys (i.e. points) are expressed as fixed size byte strings.

While public keys can be saved as two integers, one to represent the x coordinate and one to represent y coordinate, that actually provides a lot of redundancy. Because of the specifics of elliptic curves, for every valid x value there are only two valid y values. Moreover, if you have an x value, you can compute those two possible y values (if they exist). As such, it’s possible to save just the x coordinate and the sign of the y coordinate (as the two possible values are negatives of each-other: $y_1 == -y_2$ ).

That gives us few options to represent the public point, the most common are:

As a concatenation of two fixed-length big-endian integers, so called raw encoding.
As a concatenation of two fixed-length big-endian integers prefixed with the type of the encoding, so called uncompressed point representation (the type is represented by a 0x04 byte).
As a fixed-length big-endian integer representing the x coordinate prefixed with the byte representing the combined type of the encoding and the sign of the y coordinate, so called compressed point representation (the type is then represented by a 0x02 or a 0x03 byte).

Interoperable file formats

Now, while we can save the byte strings as-is and “remember” which curve was used to generate those private and public keys, interoperability usually requires to also save information about the curve together with the corresponding key. Here too there are many ways to do it: save the parameters of the used curve explicitly, use the name of the well-known curve as a string, use a numerical identifier of the well-known curve, etc.

For public keys the most interoperable format is the one described in RFC5912 (look for SubjectPublicKeyInfo structure). For private keys, the RFC5915 format (also known as the ssleay format) and the PKCS#8 format (described in RFC5958) are the most popular.

All three formats effectively support two ways of providing the information about the curve used: by specifying the curve parameters explicitly or by specifying the curve using ASN.1 OBJECT IDENTIFIER (OID), which is called named_curve. ASN.1 OIDs are a hierarchical system of representing types of objects, for example, NIST P-256 curve is identified by the 1.2.840.10045.3.1.7 OID (in dotted-decimal formatting of the OID, also known by the prime256v1 OID node name or short name). Those OIDs uniquely, identify a particular curve, but the receiver needs to know which numerical OID maps to which curve parameters. Thus the prospect of using the explicit encoding, where all the needed parameters are provided is tempting, the downside is that curve parameters may specify a weak curve, which is easy to attack and break (that is to deduce the private key from the public key). To verify curve parameters is complex and computationally expensive, thus generally protocols use few specific curves and require all implementations to carry the parameters of them. As such, use of named_curve parameters is generally recommended.

All of the mentioned formats specify a binary encoding, called DER. That encoding uses bytes with all possible numerical values, which means it’s not possible to embed it directly in text files. For uses where it’s useful to limit bytes to printable characters, so that the keys can be embedded in text files or text-only protocols (like email), the PEM formatting of the DER-encoded data can be used. The PEM formatting is just a base64 encoding with appropriate header and footer.

Signature formats

Finally, ECDSA signatures at the lowest level are a pair of numbers, usually called r and s. While they are the x coordinates of special points on the curve, they are saved modulo order of the curve, not modulo prime of the curve (as a coordinate needs to be).

That again means we have multiple ways of encoding those two numbers. The two most popular formats are to save them as a concatenation of big-endian integers of fixed size (determined by the curve order) or as a DER structure with two INTEGERS. The first of those is called the :term:raw encoding inside the Python ecdsa library.

As ASN.1 signature format requires the encoding of INTEGERS, and DER INTEGERs must use the fewest possible number of bytes, a numerically small value of r or s will require fewer bytes to represent in the DER structure. Thus, DER encoding isn’t fixed size for a given curve, but has a maximum possible size.

Note

As DER INTEGER uses so-called two’s complement representation of numbers, the most significant bit of the most significant byte represents the sign of the number. If that bit is set, then the number is considered to be negative. Thus, to represent a number like 255, which in binary representation is 0b11111111 (i.e. a byte with all bits set high), the DER encoding of it will require two bytes, one zero byte to make sure the sign bit is 0, and a byte with value 255 to encode the numerical value of the integer.