Intro to Series
Elliptic curves are very simple. The Elliptic Curves Digital Signature Algorithm (ECDSA) is the crucial element of most blockchains like Bitcoin, Ethereum, etc. It is essentially a couple of simple formulas working on top of the properties of elliptic curves.
Yet it isn’t easy to find a good explanation on the internet and build all the pieces together. But here it is! In this short series of articles, we will.
The series requires knowing no more than middle-school math.
Only the last part of the series is intended for programmers.
There we will implement ECDSA using zero dependencies, and it will take only 100 lines of code.
In parts 1, 2, and 3, we will discover all the concepts and formulas needed to completely understand and implement the algorithm — one by one. At the end of this series, we will have a fully functioning demo implemented from scratch, using only the concepts and formulas discovered here. We will be able to extract the public key from the private key, sign a message, and verify that the signature is correct.
The series consists of four parts; each part uses the concepts discovered in the previous parts:
- The Magic of Elliptic Curves [you’re here]
- The Magic of Elliptic Curves Combined with Finite Fields
- Using The Magic of Elliptic Curves to Sign and Verify Messages
- ECDSA Implementation in Python Using Zero Dependencies
Let’s start here!
We’re all probably familiar with all those graphs on coordinate grids, where the y variable somehow depends on x. For example, y = x, y = x^2, and so on. Most probably we all have some experience with it. Let’s look at them:
The equation for an elliptic curve is not much different! It has the form of y^2 = x^3 + a*x + b. What’s a and b? Just some arbitrary constants. Let’s see how it looks with a = 0, b = 7, just like in the Bitcoin curve:
It has the following 3 super important properties, upon which everything works:
This is where it may get hard to follow and understand why. You may even think this is something incoherent and irrelevant. But please trust me. These properties will lead us to a very amazing result! But now let’s pretend that we’re just having fun without a purpose.
- The elliptic curve is symmetric along the x-axis. It means that for any point on the curve A, we can get its mirror point, called -A, by simply mirroring its y coordinate:
- If we draw a line through any of two points not lying on a vertical line, it will intersect the curve at exactly one more point! Let’s draw a line through the A and B points, and call the third point —C. Then let’s reflect it to get point C:
Another example:
This C point is called the sum of A and B. So A + B = C.
- If we draw a tangent line through any point A lying on a curve, it will intersect the curve at exactly one point. We will call this point -2A. We already know how to get 2A:
The easiest way to think about a tangent line is to imagine that it intersects A point twice. As if it intersects the curve not at two points, but at three: A, A, -2A.
That’s it! We defined three mathematical operations on the elliptic curve: multiplying the point by -1, adding two points together, and doubling the point.
And here is where the algebra of elliptic curves starts working.
Now we have the following picture with points A, 2A, and -2A:
Let’s draw a line through A and 2A. The third point that we’ll get is -3A. Then just reflect it to get 3A:
You probably don’t yet understand why we’re doing all of it. Just look at one more step.
What if we try drawing a line between 3A and -2A?
Do you see the magic? By drawing a line between 3A and -2A we’re getting the -A point, which is the reflection of our original A point along the x-axis!
What we just defined in the three points above, is the algebra of elliptic curves.
Just try to understand the power of those three operations: essentially now we can perform operations on the points lying on a curve as if they’re not points, but just numbers!
What we can do with points on a curve:
- Addition of two points (A + B)
- Subtraction of two points A - B = (A + (-B))
- Doubling of the point (multiplication by two) 2*A
- Multiplying by any integer (by combining the previous operations together, we can get any integer * Point)
What we can’t do:
- Multiplication of two points
- Division of a point over another point
- Division of a point over a scalar value
For example, to get 10A:
2*A = 2A
2*2A = 4A
2*4A = 8A
8A + 2A = 10A
It’s also good to notice that the calculation may be performed in a logarithmic amount of operations. So the approximate amount of operations needed for calculating n * Point is O(log2(n))!
Eventually, we can multiply a point by any integer, but there is no way to get the integer back! This is the gist of it! And this is what makes the elliptic curves very good for cryptography. This algebra works for infinitely large numbers.
The only drawback, for now, is the need to draw it. But of course, there are mathematical formulas for reflecting a point, for addition, and for doubling a point:
Multiplying the point by -1.
If we have a point A(x, y), we can easily get -A by multiplying its y coordinate by -1. -A(x, -y).
Example:
-1 * A(2, 2) → -A(2, -2)
-1 * A(1, -1) → -A(1, 1)
-1 * A(5, 8) → -A(5, -8)
-1 * A(5, -8) → -A(5, 8)Adding two points together.
We can add two points together, but with one condition: they should not lie on a vertical line (their x coordinates should not be equal). This is the formula for adding A and B (A + B = C):
- Adding a point to itself (multiplying a point by 2). This is a very similar operation to the addition of two points, but slightly different:
That’s it! Time to practice!
Let’s try adding A and B here (let’s use approximation to 3 points after a comma):
According to the formula defined above for adding two points,
Now let’s find our point C graphically:
It works! Yes, with a small proximity issue, because of rounding. But it works!
For better understanding, I recommend you try to perform all those operations on your own.
This was all we need to know about elliptic curves and the operations on them that we need to be able to perform!
Everything is fine, but we need a couple more properties for building a cryptography system.
Next part: The Magic of Elliptic Curves Combined with Finite Fields
Feel free to contact me and ask questions:
exemak@gmail.com
t.me/exemak
Mikhail Karavaev
Top comments (1)
"Eventually, we can multiply a point by any integer, but there is no way to get the integer back! This is the gist of it!"
As of now there is no working method to get the integer (private key) from point (public key) back. But the reverse way (halve and subtract) is known for a long time since we use binary representation for double and add algorithm. It requires one to know whether point is even or odd.
Here is a simple example:
Q = public key
k = private key
G = generator point (in secp256k1 curve that Bitcoin uses any point can be a generator but we get a predefined one )
Q=k*G
Q=20*G=20G
k = 20 10100(binary representation):
0 1+1=2 (G+G=2G)
1 2+2+1=5 (2G+2G+1G=5G)
0 5+5=10 (5G+5G=10G)
0 10+10=20 (10G+10G=20G)
the other way round:
Q=k*G (we have just Q and G)
Q=20*G
20 divide by 2 = 10 0
10 divide by 2 = 5 0
5 subtract 1 then divide by 2 = 2 1
2 divide by 2 = 1 0
if we are back at 1G then 1 plus bits(0010) reversed = 10100 = 20