# Davide De Rosa

## Elliptic-curve keys

part of a series: < prev | next >

See on Github

In the previous post I gave you an overview of public-key cryptography and its relation with the blockchain. You’re about to familiarize with real crypto functions to generate Bitcoin keypairs.

In the hope of making the topic as clear as possible, the article might seem a little verbose. By the way, your patience will be rewarded as the course will be downhill from here.

### An overview of Bitcoin keys

Some facts about Bitcoin EC cryptography:

• Private keys are 32 bytes long.
• Public keys are 64 bytes (uncompressed form) or 32 bytes (compressed form) long plus a 1-byte prefix.
• The elliptic curve C is the secp256k1 curve.
• EC crypto is based on modular arithmetic.

In this overwhelming context, our only input is the private key. The public key is uniquely derived from the private key, be it uncompressed or compressed. First, we’ll use OpenSSL to generate a sample keypair from the command line. Next, we’ll do the same via C code.

TO MAC USERS: I strongly encourage you to test this code on a homebrew release of OpenSSL. OS X 10.10 ships with the long gone 0.9.8 version and some commands may not work as expected!

For your information, Bitcoin Core developers are slowly moving away from OpenSSL towards their own implementation of secp256k1 crypto.

#### Private key

A private key is a 32-byte number chosen at random, and you know that 32 bytes make for a very big number, as big as $2^{256}$. Such a number is therefore ridiculously hard to guess, assuming it’s generated with a very high degree of randomness.

Getting a new, random key is straightforward:

$openssl ecparam -name secp256k1 -genkey -out ec-priv.pem  The output file ec-priv.pem includes the curve name (secp256k1) and the private key, both encoded base64 with other additional stuff. The file can be quickly decoded to text so that you can see the raw hexes: $ openssl ec -in ec-priv.pem -text -noout


Here’s what my keypair looks like (your output will differ):

read EC key
Private-Key: (256 bit)
priv:
16:26:07:83:e4:0b:16:73:16:73:62:2a:c8:a5:b0:
45:fc:3e:a4:af:70:f7:27:f3:f9:e9:2b:dd:3a:1d:
dc:42
pub:
04:82:00:6e:93:98:a6:98:6e:da:61:fe:91:67:4c:
3a:10:8c:39:94:75:bf:1e:73:8f:19:df:c2:db:11:
db:1d:28:13:0c:6b:3b:28:ae:f9:a9:c7:e7:14:3d:
ac:6c:f1:2c:09:b8:44:4d:b6:16:79:ab:b1:d8:6f:
85:c0:38:a5:8c
ASN1 OID: secp256k1


where the private key is better displayed as:

16 26 07 83 e4 0b 16 73
16 73 62 2a c8 a5 b0 45
fc 3e a4 af 70 f7 27 f3
f9 e9 2b dd 3a 1d dc 42


The key reflects our identity, so we want to keep it secret and safe. I mean, had this not been a sample private key, I wouldn’t share it with anybody. We’ll sign our messages with it so that the world can trust we actually wrote them. If someone steals our private key, he’ll be able to fake our identity. In Bitcoin, he’ll be able to take our money. Watch out!

#### Public key

By default, a public key is made of two 32-byte numbers, the so-called uncompressed form. The numbers represent the $(x, y)$ coordinates of a point on the secp256k1 elliptic curve, which has the following formula:

The point location is determined by the private key, while it’s unfeasible to infer the private key from the point coordinates. After all, this is what makes EC cryptography secure. Due to its dependent nature, $y$ can be implied from $x$ and the curve formula. In fact, the compressed form saves space by omitting the $y$ value.

From the private key, it’s possible to take out the public part and store it to an external file I called ec-pub.pem:

$openssl ec -in ec-priv.pem -pubout -out ec-pub.pem  If we now decode the public key: $ openssl ec -in ec-pub.pem -pubin -text -noout


the text description will obviously not include the private key:

read EC key
Private-Key: (256 bit)
pub:
04:82:00:6e:93:98:a6:98:6e:da:61:fe:91:67:4c:
3a:10:8c:39:94:75:bf:1e:73:8f:19:df:c2:db:11:
db:1d:28:13:0c:6b:3b:28:ae:f9:a9:c7:e7:14:3d:
ac:6c:f1:2c:09:b8:44:4d:b6:16:79:ab:b1:d8:6f:
85:c0:38:a5:8c
ASN1 OID: secp256k1


04

82 00 6e 93 98 a6 98 6e
da 61 fe 91 67 4c 3a 10
8c 39 94 75 bf 1e 73 8f
19 df c2 db 11 db 1d 28

13 0c 6b 3b 28 ae f9 a9
c7 e7 14 3d ac 6c f1 2c
09 b8 44 4d b6 16 79 ab
b1 d8 6f 85 c0 38 a5 8c


The uncompressed conversion form takes 65 bytes:

• The constant 04 prefix.
• The 32-byte $x$ coordinate.
• The 32-byte $y$ coordinate.

It’s easy to convert an uncompressed public key to the compressed form, we just omit the $y$ and change the prefix according to its value. The first byte becomes 02 for even values of $y$ and 03 for odd values. My $y$ ends with 8c, so the new prefix is 02:

02

82 00 6e 93 98 a6 98 6e
da 61 fe 91 67 4c 3a 10
8c 39 94 75 bf 1e 73 8f
19 df c2 db 11 db 1d 28


The same is accomplished with:

\$ openssl ec -in ec-pub.pem -pubin -text -noout -conv_form compressed


that yields:

read EC key
Private-Key: (256 bit)
pub:
02:82:00:6e:93:98:a6:98:6e:da:61:fe:91:67:4c:
3a:10:8c:39:94:75:bf:1e:73:8f:19:df:c2:db:11:
db:1d:28
ASN1 OID: secp256k1


In conclusion, the compressed conversion form takes 33 bytes:

• The constant 02 or 03 prefix.
• The 32-byte $x$ coordinate.

### Generating a keypair from code

The keypair generation task is cumbersome, yet not difficult with the aid of the OpenSSL library. I wrote a helper function in ec.h declared as follows:

Let’s analyze part of its code together. Several OpenSSL data structures are involved:

• BN_CTX, BIGNUM
• EC_KEY
• EC_GROUP, EC_POINT

The first two structs belong to the arbitrary-precision arithmetic area of OpenSSL, because we need to deal with very big numbers. All the other types relate to EC crypto. EC_KEY can be a full keypair (private + public) or just a public key, whereas EC_GROUP and EC_POINT help us calculate the public key from a private key.

Most importantly, we create an EC_KEY structure to hold the keypair:

Loading the private key is easy, but requires an intermediate step. Before feeding the input priv_bytes to the keypair, we need to translate it to a BIGNUM, here named priv:

For complex big numbers operations, OpenSSL needs a context, that’s why a BN_CTX is also created. The public key derivation needs a deeper understanding of EC math, which is not the aim of this series. Basically, we locate a fixed point $G$ on the curve (the generator, group in the code) and multiply it by the scalar private key $n$, a virtually irreversible operation in modular arithmetic. The resulting $P = n * G$ is a second point, the public key pub. Eventually, the public key is loaded into the keypair:

WARNING: the code is simplified and doesn’t check for library errors.

### Example

It’s finally time to test our keypair in ex-ec-keypair.c. We expect the code to output the same results we got from openssl on the command line, given that priv_bytes holds our sample private key:

The test proceeds this way:

1. Initializes an EC_KEY keypair with priv_bytes.
2. Puts the private key back into priv through a BIGNUM.
3. Puts the derived public key into pub in all conversion forms.

The third step is the most complicated. The conversion form is set first, which in turn affects the length of the public key (33 or 65). The actual length is obtained with a NULL-argument call to i2o_ECPublicKey, so that pub is allocated enough bytes to hold the output. i2o_ECPublicKey finally converts the public key from the internal representation to octects, hence the i2o prefix (octet = byte). The encoded bytes are written to pub through pub_copy.

Try running the program and compare it with the output of the openssl command line tool.

### Get the code!

Full source on GitHub.

### Next block in chain?

You learned how to generate a new EC keypair. With some custom code, you also learned how to create a keypair from raw bytes.

In the next article you’ll use EC keypairs to produce and verify digital signatures. Please share this post if you enjoyed it and use the form below for questions and comments!