In this blog post I would like to introduce readers into Elliptic Curve
Cryptography and use this knowledge to construct an Ethereum address.
Part 1: Elliptic Curves
An Elliptic Curve is a curve define by the equation
\[y^2 = x^3 + ax +b,\]
The curve has a number of nice properties, and one of them is that if take two
points on the curve and draw a line through them, the line will intersect the
curve at exactly one point. You can play around with this property using the
Bokeh application below:
CODE
This property allows us to map 2 points on a curve to a 3 point, an operation
that we will refer to as an addition (with respect to the curve). The reason we
call this an addition, because it shares certain similarities with an
arithmetic addition. However, we refine our addition to result in the reflected
point, see illustration below:
We can verify algebraically that \(y_R^2 = x_R^3 + ax_R + b\), meaning
\(R\) is on our curve. Finally, for our addition to be valid, we need to
define a point that would serve the role of \(0\). So, by definition,
\(P + O = P\), and \(-P + P = O\). My vague intuition is that I can think
of \(O\) as the entire x-axis.
Part 2: Mathematical Fields
If we pick a prime number \(p\), we can define multiplication, addition,
subtraction and division module \(p\):
Mathematically, this means that we have a field, \(\mathbb{F}_p\). Real
numbers form a field too, so you probably have a good intuition for how fields
work.
Here are arithmetic tables for \(\mathbb{F}_{7}\), skipping subtraction as I don’t have space:
*
1
2
3
4
5
6
1
1
2
3
4
5
6
2
2
4
6
1
3
5
3
3
6
2
5
1
4
4
4
1
5
2
6
3
5
5
3
1
6
4
2
6
6
5
4
3
2
1
/
1
2
3
4
5
6
1
1
2
3
4
5
6
2
4
1
5
2
6
3
3
5
3
1
6
4
2
4
2
4
6
1
3
5
5
3
6
2
5
1
4
6
6
5
4
3
2
1
+
1
2
3
4
5
6
1
2
3
4
5
6
0
2
3
4
5
6
0
1
3
4
5
6
0
1
2
4
5
6
0
1
2
3
5
6
0
1
2
3
4
6
0
1
2
3
4
5
Plot twist: we are now going to deal with an elliptic curve defined over
\(\mathbb{F}_p\). Turns out the equations for addition with respect to a curve,
\eqref{eqn:point_r}, are still well-defined: they only use simple arithmetic
operations (*, /, +, -) anyway. Unfortunately, we no longer have the geometric
intuition, as our curve plotted will now look like just a bunch of points.
Part 3: Toy Elliptic Curve over \(\mathbb{F}_{37}\)
I wrote some auxiliary code that implements fields and elliptic curves, attached in
appendix. For now, let’s use play with it to get used to the elliptic curves
over prime fields:
I started with a point \((0, 4)\), module 37, and kept adding it until I reached
\(O\). I have to reach \(O\), because the number of points on the curve is
finite, so they have to start repeating:
\[nP = mP \implies (n-m)P = 0,\]
for some \(n \neq m\). Are there any more points on the curve? Let’s find out:
Yes, there’s at least one more point: \((1, 18)\). Any more?
Looks like \((1, 18)\) generates all points on our curve. How many points do
we have? 49:
In mathematics , we say that the order of point2 is 49, whilst the
order of point1 is 7, where order is the number of times we add until we
reach zero. point2 in this toy example plays the same role that number
\(1\) plays in integers: by adding \(1\) repeatedly we an generate all
positive integers. Same holds for point2: by adding it repeatedly we generate
all points on the curve. OK, hopefully you get a better feel for this object.
Let’s proceed.
Part 4: Ethereum Address
I went on vanity-eth.tk and generated a public and a
private key:
We have already covered all the material needed to replicate such
computation. Both Ethereum and Bitcoin use an elliptic curve \(y^2 = x^3 + 7\)
over \(\mathbb{F}_p\), where
\(p = 2^{256} - 2^{32} - 2^{9} - 2^{8} - 2^{7} - 2^{6} - 2^{4} - 1\), a very large prime.
It turns out whilst calculating \(n * P = Q\), i.e. summing \(P\) with
itself \(n\)-times, is computationally easy, finding \(n\), given \(P\)
and \(Q\) is computationally hard. So the private key is \(n\), whilst the
public key is \(n * P\), for some specified \(P\). Below is the code that
defines the curve and the specified point, taken from the secp256k1 specs:
Finally, we can generate the public point using multiplication:
That’s almost our public key, but not quite. We now encode (x, y) coordinates
of our public point in hex, to get something like
Finally, we compute Keccak-256 hash function on the public point, and take
last 40 characters:
Voilà!
Credits
Thanks to bellbind github account for his toy implementations and Timur
Badretdinov for his blog post.