The Bluffers Guide to secp256k1 … When Satoshi Said Goodbye To PKI

If it wasn’t for Satoshi Nakamoto, you probably would never have heard of the secp256k1 Elliptic Curve Cryptography (ECC) method. But…

The Bluffers Guide to secp256k1 … When Satoshi Said Goodbye To PKI

If it wasn’t for Satoshi Nakamoto, you probably would never have heard of the secp256k1 Elliptic Curve Cryptography (ECC) method. But, Satoshi used it to take a private key and then produce a public identifier.

At the core of the adoption of Bitcoin is the usage of the ECDSA (Elliptic Curve Digital Signature Algorithm), and where it was possible to verify a transaction from the public Bitcoin identifier. The standard for secp256k1 is published [here]:

This is a Weierstrass form of elliptic curve, and uses:

y²=x³+7 (mod p)

It has a base point of g=(0x79be667ef9dcb … 959f2815b16f81798, 0x483ada77 … 8ffb10d4b8) and a prime number of ²²⁵⁶−²³²−²⁹−²⁸−²⁷−²⁶−²⁴−1. The order of the curve is n=0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141.

Overall we have a private key of a and then produce a public key of aG. We do this though point addition. For secp256k1, we have a 256-bit private key value, and a 512-bit public key value (and which is a point on the elliptic curve).

Why secp and not NIST?

Who knows why Satoshi chose the secp256k1 curve over the NIST defined curve of secp256k1. Many have questioned the close relationship between NIST and the NSA, and the possiblity of inserting a backdoor in the curve. And, so, perhaps Satoshi went for secp256k1 for this reason.

Points on secp256k1

The points on an elliptic curve curve do not always give a valid x-co-ordinate. Also there are two points for every valid x-co-ordinate value:

Elliptic Curve points for common curves in an x-range. Elliptic Curve points. This example uses Curve 25519, secp256k1, P256 and P512 to show the range of points for a given x-coordinate range.
First 20 Elliptic Curve points in Finite Field for common curves. Elliptic Curve points. Locating the first 20 points in an elliptic curve in a finite field for curves including Curve25519 (Tor), secp256k1 (Bitcoin) and NIST P-256.

Montgomery Ladder with secp256k1

The thing that makes elliptic curve cryptography fast, is the ability to multiply a point (G) by a scalar value (normally, the private key) to give a.G. This is fast due to the Montgomery ladder:

Montgomery Ladder in calculating kG in a fixed time. Ladder. Calculates kG for secp256k1.

Charting

An elliptic curve is beautiful in its analogue from, but points when discrete:

Draw y²=x³+7(mod p) [here].

Point multiplication

At the core of elliptic curve cryptography, we perform point multiplication:

Real ECC curves for (1G, 2G and nG). Elliptic Curve real. Curve 25519, secp256k, and so on.
Inverse of private key for secp256k1 with Python. Inverse of private key secp256k1. In this example Alice sends aG and Bob sends back abG. Alice then calculates a−1(mod n) and can then determine a^{−1}abG=bG. The secp256k1 curve is in the Weierstrass curve form (y²=x³+ax+b).

Key generation

Basically elliptic curve cryptography focuses on the digital signing process, and where we generate a private key (sk) and a public key (pk). There are defined as a key pair:

Elliptic Curve (OpenSSL Key Generator). Elliptic Curve (Keys). Elliptic Curv is a public key method. This page outline the generation of ECC key, including secp128r1.
Elliptic Curve (Keys). Elliptic Curve (Keys). Elliptic Curv is a public key method. This page outline the generation of ECC keys in Bitcoin.

ECDH with secp256k1

Along with digital signatures, elliptic curve methods are used in key exchange:

Elliptic Curve Diffie-Hellman (ECDH) with secp256k1. ECDH. Elliptic Curve Diffie Hellman is used to create a shared key.
Elliptic Curve Diffie-Hellman (ECDH) with different curves. ECDH. Elliptic Curve Diffie Hellman is used to create a shared key using different curves, including secp256k1, p192 and p224.
secp256k1 ECDH with Python. secp256k1 ECDH. Elliptic Curve Diffie Hellman using secp256k1 with Python. The secp256k1 curve is in the Weierstrass curve form (y²=x³+ax+b).
Authenticated secp256k1 ECDH with Python. Authenticated secp256k1 ECDH. Elliptic Curve Diffie Hellman using secp256k1 with Python, and where we use a long-term key for Bob and Alice to create a shared session key. The secp256k1 curve is in the Weierstrass curve form (y²=x³+ax+b).

ECDSA

A core part of the trust on the Bitcoin and Ethereum is the usage of the ECDSA signature:

Elliptic Curve Digital Signature Algorithm (ECDSA). ECDSA. Elliptic Curve Digital Signature Algorithm (ECDSA) is used to sign data.
Elliptic Curve Digital Signature Algorithm (ECDSA) with core operations. ECDSA. Elliptic Curve Digital Signature Algorithm (ECDSA) is used to sign data with core operations.

But it needs to be treating with caution:

Crack ECDSA from leak of nonce (SECP256k1). ECDSA with nonce. This outlines ECDSA how the private key can be recovered with a leak of the nonce value for SECP256k1.
Crack ECDSA with weak nonces. ECDSA with weak nonces. This outlines ECDSA how the private key can be recovered with weak nonce values.
Blinded ECDSA. Blinded ECDSA. With a blinded signature, Bob can sign for a message, without knowning what the message is. In this case Alice will create a blinded ECDSA signature, and where Bob can then sign it, and then Alice can unblind it. The method is based on one produced by Oleg Andreev for blinding signatures in Bitcoin.
ECDSA: Fault Attack. ECDSA: Fault Attack. In the fault attack in ECDSA we only require two signatures. One is produced without a fault (r,s) , and the other has a fault (rf,sf)

What’s the size of the public key?

As the public key is a point, in its purest form we have a 512 bit public key, and which is made up of 256 bits for the x-coordinate and 256 bits for the y-coordinate. But, we can also compress this, as we can easily derive the y-coordinate from the x-coordinate. In the end, there are only two possible y-coordinates, so all we have to do, is record whether it is odd or even and compress the point with just an identifier and the x-coodinate:

02, 03 or 04? So What Are Compressed and Uncompressed Public Keys? https://asecuritysite.com/ecc/js_ethereum2

Conclusions

With ECDH in key exchange, and ECDSA in digital signatures, the secp256k1 curve has been proven to be winner in replacing the Diffie-Hellman method in key exchange and RSA signatures.