Elliptic Curve Cryptography for Noobs (Part 1)
Written by a Noob
Eliptic Curve Cryptography has seen a rise in popularity in recent years due to it’s advantages over other cryptographic key derivation schemes like RSA. When it comes to memory and computation, ECC can provide the same security as RSA at a fraction of the footprint.
But for someone new, it can be a little bit difficult to “get the foot in the door“ when it comes to understanding how ECC works, even if it’s only superficially.
What is it Elliptic Curve Cryptography (ECC)?
Elliptic Curve Cryptography is a subfield of Cryptography which relies on the mathematical and numerical properties of Elliptic Curves… (Duh)
But what does that mean? What makes Elliptic curves interesting for Cryptography?
To understand that, we should first ask ourselves what we are looking for in Cryptography, or more specifically, in Encryption.
Encryption: The basics.
Encryption has one simple goal. Ensuring that a message (Plaintext) can be turned into giberish (Cyphertext) using an encryption machine or algorythm (Cypher) and a secret (Key). Everyone that does not have the Key to decrypt the Cyphertext back into the Plaintext, is left guessing.
Now, we have defined the basic parts needed for Encryption and Decryption:
Plaintext: A message that is readable AND understandable by humans or machines
Cyphertext: A message that is not understandable by humans or machines without the key for decryption
Cypher: An algorythm or machine that can turn a Plaintext into a Cyphertext and vice-versa
Key: A secret that is needed by the Cypher for encryption and decryption
Encryption: The Key
“A good cipher is hard/impossible to crack even if you get its source code”
The Key is key, so to speak.
The assumption is, that as long as the Key is secret, no one without the Key can decrypt the Cyphertext or learn anything about the Plaintext, even if they have access to the Cyphers source code.
That is great, but what exactly makes up a Key? And when is a Key considered secure?
A Key with a 128 bits Security is considered un-crackable. That, doesn’t mean that the Keys length is 128 bits, no. If we recall the graph from above, we see that an RSA Key has to be more than 3000 bits long to provide 128 bits of security. If the key is too short, or not random enough, it can be bruteforced. If that is the case, then even the best Cypher won’t protect us.
But how can we use a Key to send someone an encrypted message we have never met? We would have to send them the Key for decryption somehow? But how can we do that without compromising the Key?
Today, there are two main ways of exchanging Keys over insecure channels.
Diffie-Hellman Key Exchange (Shared-Secret)
Asymetric Encryption (Public Key Cryptography)
Even though they are very different in how they work, both of those methods rely on the same mathematical basic principle:
One-way-functions
A one-way-function is a function that computes an output from an input easily, but computing the output back to the input is hard, or nearly impossible.
Some examples of functions like this are:
Prime number factorization: Prime number factorization is the underlying security for RSA. Multiplying two prime numbers is very easy. But finding two prime numbers that make up a given number is hard. Looking at the problems below, which one is harder? b) of course. We have to essentially brute force the result by trying all prime numbers. a) we can just calculate with one operation.
\(a)\ 7919 * 11657 = x\)\(b)\ p*q = 215640989\)Elliptic Curve DLP: The Elliptic Curve DLP is another one-way-function. With Elliptic curves it is possible to do both Asymmetric Encryption (Public Key Cryptography) as well as Diffie-Hellman Key Exchange (Shared-Secret).
Elliptic Curves: The Basics
Elliptic Curves are graphs of a function where:
This equation is not really important for understanding how Elliptic Curves work on a high level. I find it better to visualize what such a curve might look like when drawn on a Cartesian plane:
This is the curve secp256k1 which uses the equation:
There are many criteria for a curve to be considered secure, but in this article I won’t go into detail about this. Check out this answer on stackexchange for an overview of security criteria for Elliptic Curves.
Elliptic Curve arithmetic
Elliptic Curve arithmetic is the basis of ECC. What we mean by Elliptic Curve arithmetic is basically calculations on the location of points on the curve.
If we have two points on the curve, for example if point A and point B are known, we can ADD them together to calculate C.
We use the normal math notation for addition, but when we are talking about adding points together on an Elliptic Curve it means something a little different:
Since we know A and B we can draw a line through both of them. The line will intersect at a third point. This point is going to be called C'. Now all that is left to is to flip point C' alongside the x-axis to get point C.
That is how we can do point addition on Elliptic Curves!
We can also add a point to itself. For example, let’s add point X to itself.
In order to do that, we just need to take the tangent of point X instead of drawing a line through two points, and then flip that point again alongside the x-axis:
From here we can take it further: let’s calculate point 3X.
Since we’ve already calculated 2X we can use that to calculate the next point.
If we want to calculate 4X, we have to add point 2X to itself again. Meaning we are taking the tangent of 2X to find the next intersection on the curve, which is going to be 4X:
Doubling and adding
If you have paid attention, you might have noticed something:
We have used the same amount of operations to calculate 4X as we have to calculate 3X. This is what is known as the “double and add” method. It allows us to take shortcuts when deriving a point on the curve.
The naive approach would be to do:
X plus X plus X plus X , resulting in 3 addition operations.
But with double and adding, we did
X plus X = 2X
and then
2X plus 2X = 4X
Resulting in only 2 operations.
At the scale of small numbers like this, the gains are not really noticeable. But if we imagine the operations it would take to derive a point that is representing a key, which in case of `secp256k1` is a number of 256 bit, the naive approach doesn’t cut it.
256 bit numbers are 78 digits long. I don’t even know what you would call such a number, and all computers in the world could not run that many cycles.
Let’s take a look at how you would calculate 10X. To make it easier on ourselves, we can note the number 10 in it’s binary format: 1010
Having the binary representation makes it super easy to apply the double and add algorithm to the number:
For the first bit we have a 1. The leftmost bit of any binary number should always be 1, so in that case that is our starting point:
X
The second bit, is a zero. encountering a zero, means we double and move on to the next bit:
X+X=2X
Now we encounter a 1 again. This means we should double again, and then add X
2X+2X=4X
4X+X=5X
And finally, we have another 0. So we multiply and finish with:
5X+5X=10X
Keys
As you see, this is fairly simple. So if you have a 256 bit private key, all you would do is write it down as a binary number, and then follow the double and add algorithm to calculate your public key. You would need to do a maximum of 512 calculations, instead of 10^78 :)
Reversing this process, is nearly impossible (we could call it cryptographically unfeasible), as there is no known way to efficiently derive the factor (or multiplier) from the resulting point.
Thanks for reading, that’s it for part one.
In part two, we put the theory into practice, and see what kind of cryptographic schemes we can implement using ECC.