Securing Ethereum With Elliptic Curves

To begin, every account has a unique private key which is used to sign each transaction. In self-custodial wallets, this private key is stored locally and never exposed. Then, in a non-reversible operation, the private key is used to generate a public key.¹ This public key is then turned into a hash, which is what we know as an Ethereum address.²

When a transaction is signed and sent from the original account, the receiving party then uses the public key to confirm that the transaction was truly sent by the original account. Easy enough –but how exactly is a public key derived from a private key?

Ethereum, like bitcoin, uses secp256k1 – an elliptic curve primitive – for the encryption used in this process. Secp256k1 commonly uses the following variables:

• $(x, y)$ – public key
• $(r, s)$ – signature
• $msgHash$ – message hash
• $d$ – private key

The cryptographic function Secp256k1 provides:

• Signing a message (generating an $r$ and $s$ value based on the $msgHash$ and $d$)
• Verifying a signature (given $x$, $y$, $r$, $s$ and $msgHash$ verifying that the signature is legitimate)
• Generating public key (given $d$, generate $x$ and $y$)
• Compute shared secret (won’t be covered)

So how is secp256k1 secure? It comes down to elliptic curve cryptography. The secp256k1 uses curve $y^2 = x^3 + 7$. We won’t go into the arithmetic that is used to sign and verify a message using this curve, but we’ll cover the public key generation. Private key in secp256k1 is denoted as d, while the public key is denoted as $(x, y)$. To generate a public key, you calculate the following:

$(x, y) = Gd$

Where:

$(x, y)$ -– public key

$G$ -– initial point

$d$ -– private key

$G$ consists of 2 numbers that make up a point. For secp256k1 the following two coordinates are used:

(55066263022277343669578718895168534326250603453777594175500187360389116729240, 32670510020758816978083085130507043184471273380659243275938904335757337482424)

To simplify the implementation, crypto libraries usually only focus on the $x$ coordinate of a point, since $y$ coordinate can be trivially derived. So the formula can be re-written as follows:

$x = G_x * d$

Where $G_x$ = 55066263022277343669578718895168534326250603453777594175500187360389116729240

And that’s all it takes to generate a private key, one multiplication! You might think, if it’s just multiplication, why can’t we divide back to get $d$?

$d = x / Gx$

The problem is, we’re not operating in integer space, but rather in a finite field of order p where p is a prime number. Moreover, we’re operating inside of an Elliptic Curve defined over the finite field. All modular arithmetic operations are done on the Elliptic Curve points. Thus, making the division not an easily solved problem using the usual division techniques, but rather a problem of the field of index calculus. AKA, The discrete logarithm problem.

Written as $Z_p$, it’s any integer modulo $p$. I.e. if $p$ is 5, it’s $\{ 0, 1, 2, 3, 4 \}$, if $p$ is $7$, it’s $\{ 0, 1, 2, 3, 4, 5, 6 \}$. Field simply means a set of integers. Order just means the size of the field.

Let’s look at linear curves. Let’s define a linear curve of order $p$ where $p$ is $13$ (a prime number).

Relatively simple curve! Let’s try to make a function which maps private key to public key: Wow! There’s some semi-random relationship there. Just by looking at the public key, you won’t easily figure out the private key. But, it’s still reversible. Let’s increase order $p$ and initial point $G$. The pattern is even more pronounced here. Linear Curve cryptography is a no-go -– too easy to derive public key from private key. Now, let’s introduce the Elliptic Curve over finite field $p$ where $p$ is $257$ (a prime number): This point cloud looks pretty random! Thing is, when computing a public key from a private key, this is the point cloud we’re using as the space. What would a private → public key graph look like? Let’s select the starting point $(G_x)$ to be $17$ As you can see, it’s another random-looking graph. There’s no obvious relationship, and the only way to go back from public to private is to solve the discrete logarithm problem. Obviously, the real secp256k1 curve uses 55066263022277343669578718895168534326250603453777594175500187360389116729240 as $G_x$, and 115792089237316195423570985008687907853269984665640564039457584007908834671663 $(2^256 - 2^32 - 977)$ as $p$, so this graph will look indistinguishable from white noise, and completely impossible to compute exhaustively (like desmos does for for small integers).

Given that the order of the finite field p is $2^256 - 2^32 - 977$, to do a brute force attack on a public key, you need to iterate over $2^256 - 2^32 - 977$ private keys. Let’s assume an attacker has a CPU with 256 cores, each core running at 10GHz, and computing a public key takes one CPU cycle (conservative). In that case:

Number of public keys per second: $256 × 10 × 10^9 = 2560000000000$ ops

Seconds to compute the whole finite field: $4.52312848583266 × 10^64$ seconds

Years to compute the whole finite field: $1.43332235820261 × 10^57$ years

Years to compute 50% of the finite field: $7.1666117910131 × 10^56$ years

In comparison, the age of the universe is merely $1.4 × 10^10$ years.

As you can see, brute force attacks on private keys are impractical.

For further reading, there are many other types of attacks that can be mounted on Elliptic Curves. They are

• Quantum Computing - one of the more promising attack vectors.
• Pollard's rho algorithm for logarithms - improvement over brute force
• Baby Step-Giant Step DLP algorithm
• Lifting Integer field of order p into Rational number field of order p (index calculus)
• See https://eprint.iacr.org/2015/1022.pdf for more

Other attacks also exist, such as side-channel attacks (measuring computer signals during execution of cryptographic functions) and exploits of implementation bugs -– such as insecure nonce generated for signature verification.

On a final note, some accounts take their security one step further. There are thousands of accounts on Ethereum for which we know the public key and the associated wallet address. There are also, however, a certain number of accounts on Ethereum where we only know the wallet address – the public key is unknown because they’ve never signed a transaction. This can happen when an account has just been initiated. There might have been incoming transactions sent to the address, but no signed transactions were published from that address.

This stops the moment an account signs their first transaction, though. The public key is disclosed as part of a signature to verify that the transaction was indeed performed by an account holder associated with that wallet address. This is where the “private key → public key → wallet address” chain becomes more transparent. Users are no longer limited to knowing the wallet address, they now know the wallet address and the public key.

Some wallets have never signed a transaction like this, though. Let’s have a look at few of the largest ethereum thereum wallet addresses for examples:

Among the ones which are Externally Owned Accounts (not a contract address), let’s take the following ones:

• 0xda9dfa130df4de4673b89022ee50ff26f6ea73cf
• 0xbe0eb53f46cd790cd13851d5eff43d12404d33e8
• 0x73bceb1cd57c711feac4224d062b0f6ff338501e
• 0x9bf4001d307dfd62b26a2f1307ee0c0307632d59

First three all have signed transactions:

While the fourth one doesn’t!

So the three largest Ethereum wallets are okay with relying on the cryptographic security of the secp256k1, while the fourth largest is more conservative and hasn’t actually published their public key. In this case, they are not only relying on the irreversible nature of Elliptic Curve, but also on the irreversible nature of the “public key → wallet address” function, which is a hash.

In general, Elliptic Curve cryptography is pretty secure. Naïve attacks are futile, and the DLP over large prime numbers is still difficult to solve. Quantum computing is the most promising attack vector so far, and in the age of large scale adversaries it is not out of question that someone builds a quantum computer large enough to solve DLP for Elliptic Curves.

It is unknown when this will happen, but the common estimates are on the order of a few decades. Once quantum computing is powerful enough to solve secp256k1, Ethereum will have to switch to a quantum resistant algorithm. A few of such systems are currently in development, which rely on $P \neq NP$, but don’t use DLP for its security properties. Lattice based systems and Hash-based systems are currently showing promise.

But for now, we’ll be using secp256k1 to secure all of our Externally Owned Accounts on Ethereum. After all, the three largest accounts on the network, worth a combined 6m ETH ($12b) trust it!

¹ Reversing this operation is only possible by doing an exhaustive search on every possible private key or by solving the discrete logarithm problem aka DLP, but we won’t go into that.

² We won’t go into details on how wallet addresses are generated, but in broad terms, it’s another irreversible function based on the keccak hash function.