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.
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 . 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!
By default, a public key is made of two 32-byte numbers, the so-called uncompressed form. The numbers represent the 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, can be implied from and the curve formula. In fact, the compressed form saves space by omitting the 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
A more readable version:
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
- The 32-byte coordinate.
- The 32-byte coordinate.
It’s easy to convert an uncompressed public key to the compressed form, we just omit the and change the prefix according to its value. The first byte becomes
02 for even values of and
03 for odd values. My ends with
8c, so the new prefix is
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
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
- The 32-byte 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:
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_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
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 on the curve (the generator,
group in the code) and multiply it by the scalar private key , a virtually irreversible operation in modular arithmetic. The resulting 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.
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:
- Initializes an
- Puts the private key back into
- Puts the derived public key into
pubin 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
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!