Elliptic Curve Cryptography for Noobs (Part 1)
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. It is kind of important to understand, that instead of doing the following calculation:
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 3X:
On the curve, we can observe the following result:
What we’ve just seen here by calculating 3X from adding X to itself is what we call a Point multiplication. We’ve added X to X to X which is equal to 3*X. If we keep doing the same process, we will find out that we are jumping around on the curve seemingly at random.
ECC Keys
This apparent randomness is what makes Elliptic Curves so attractive for cryptography.
The multiplication of a point, or in other words, adding a point to itself multiple times, is the operation that is used for deriving keys in ECC.
Adding the the point X a secret amount of times (a) to itself (in practice a number about 256 bit long), we end up on a random coordinate on the curve. There exist algorithms to calculate this point efficiently, if a is known. But if a is not known, it is nearly impossible.
This makes a an ideal private key and the point it produced, let’s call it A its corresponding public key.
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.