Elliptic Curve Cryptography Explained, Hacker News

Recently, I am learning how Elliptic Curve Cryptography works. I searched around the internet, found so many articles and videos explaining it. Most of them are covering only a portion of it, some of them skip many critical steps how you get from here to there. In the end, I didn’t find an article that really explains it from end-to-end in an institutive way. With that in mind, I would like to write a post explaining Elliptic Curve Cryptography, cover from the basics to key exchange, encryption, and decryption.

To plot the curve for writing this article, and also get a sense of how things work, I wrote a Jupyter Notebook for curve plotting and calculations in Python. The plotting library ismatplotlib. And if you want to play around an elliptic curve and feel how it works yourself, lucky you! I made the source code open-sourcedhere on GitHub,one for real numbersandone for finite field:

You can find most of the article diagrams in the notebook.

Please note that this article isnot meant for explaining how to implement Elliptic Curve Cryptography securely, the example we use here is just for making teaching you and myself easier. We also don’t want to dig too deep into the mathematical rabbit hole, I only want to focus on getting the sense of how it works essentially. So we will strip out many math details and only provide a reference read for it.

Now, shall we begin?

Let’s play a game

An elliptic curve is a curve defined by

For example, let and, then when you plot the curve, it looks like this:

Now, let’s play a game. Pick two different random points with different x value on the curve, connect these two points with a straight line, let’s say and. Then you will notice the line touches the curve at a third point. Once we find that third point and flip its y value to the other side of x axis, let’s call it.

The point is the sum of and. You can think of this process is some kind of space travel. Imagine there are enemies following your spacecraft. To lose your enemy, you are taking a straight shortcut off the route to another point on the route, bounce to the other side of the route sharply once you hit the third point.

Well, the enemies still follow, let’s do the trick again. This time we start from last point to another point.

As you can see, we can keep repeating the same trick by adding a new point to bounce to a new sum, as long as the new line is not vertical.

Over time, you realize that it’s tedious to find a new point to jump to. To make the trick more institutive and easier to repeat, let’s now take the shortcut along the tangent line of our current position, and it will look like this:

Consider the previous two points style jumping trick, as if you see point and point are infinitely close to each other at, it’s actually the same trick. So we can apply the previous rule, call the result sum of and, which is, i.e. .

Likewise, we can repeat the same step more to lose our enemies, this time, we start from back to the original point:

For the result, we call it or. Obviously, we can keep doing this many times to reach. Now, here comes the question, given the coordinate of a point, can you find out what is the value? In other words, how many times we’ve jumped from to, like the following diagram:

I can tell you the answer of the point on the diagram above is. It’s really easy for me to tell because I pick the number. It would be very hard for you to find out, as there’s no known easy and efficient way to figure out the value.

That’s it, you’ve just learned the basis of Elliptic Curve Cryptography! The curve and original point is a shared value everybody knows and agreed to use, the final point is yourpublic key, safe to share to anyone. How many steps you jump, the value is yourprivate key. As we said, people who know just and, it will be very hard for them to find out what’s your private key as this is known to be a hard problem to solve.

  

Not so fast!

I heard you yelled at me.

  

To get the point NP, doesn’t that mean you need to do it N times. If you can do it in a reasonable amount of time, can’t I just do the same, move forward one by one until I meet the same point NP to find out exactly how many steps it takes?

That’s a great question, I actually got the same one after reading many articles online, but found a few of them explain that clearly. So, next, let’s talk about how to really make your enemies lose track of you in the space.

Move forward in warp speed

The trick we did to jump around curve for cutting loose enemies, it’s not wise to do it slowly, as it’s easily traceable. Your enemies can simply do the same until they figure out how many times it takes to get there. To really make you untraceable, you need to move forward in warp speed.

The thing is, for the sum operation, or the trick we did on the elliptic curve got an interesting characteristic. The points on the curve and the sum operation followgroup law. The idea is, you can apply some kind of operation on the elements in a group, let’s call it “add” here, they will still stay in the group. And the operation comes with specific properties. One of the specific property associativity is like this:

is the same as

The mathematic proof behind this concept is actually not easy, you can read it (hereorhereif you are interested. While it’s hard to prove, but it’s easy to see it yourself if you plot the curve and lines. Let’s see an example. As you see we have a point above, according to the associativity property, we should be able to do first then, and it should arrive at the same final position. Now here’s.

Next, let’s do.

Look at the final position, it’s exactly the same as. Don’t believe me? Here’s the value printed out from the program I wrote:

ab_c=ab   c a_bc=a   bc (ab_c, a_bc)  (9531851331698311, 1. 733918191357413),  Point (0. 9531851331698316, 1. 7339181913574133))

As you can see,ab_cand (a_bc) are mostly identical. The difference is due to floating-point calculation roundoff error. This is actually abigproblem, we will talk about this later.

Similarly, for the single-point situation, the group law allows us to sum up to the same position by a different order. Here’s the critical one, remember how we get to via? Now I want to show you that

is the same as

At first, let’s see doing the calculation in a silly way, just keep adding. Here’s the final step:

Then, let’s try to add the point to itself, which is exactly the cutting tangent line trick we did before:

See? Both ways lead to the same result. This is it, since we can double a point easily, and the order of adding it doesn’t matter. We can “cheat” by keep doubling a point and pick the power of the point we need to composite the desired value quickly without adding it up one by one.

Let’s try to add up to a slightly bigger number, say, let’s first break it down to binary so that we can get its power of two composition. Its binary representation is

in other words, summing up all the power of two values ​​would be

and i.e

So the operation we need would be

Add P and double P  
• Add 2P and double 2P

  

• Double 4P

  

• Double 8P

  

• Double (P)   
• Add 32 P and double (P)   
• Add 64 P and double (P)   
• Add 128 P and double (P)

That’s only 8 steps, compares to 227 steps, it’s way faster . This method is calleddouble and add. It allows us to get to the desired multiple times of point jumping on an elliptic curve pretty fast. The number in this example is small, given that we can approach the number we want with, even the number is as big as the number of atoms in the universe, say, which is around, this method can still finish calculating it in 275 double-and-add steps.

Now we know how to jump forward on the elliptic curve in warp speed, with that, we can jump forward bazillion times easily. While it’s easy for us, this is extremely difficult for the attacker to find out exactly how many times we jump, namely, find out what’s the value from and point given if is big enough. This is called Elliptic Curve Discrete Logarithm Problem, you can search it if you want to learn more about this topic.

Let’s meet at a secret coordinate

We have been talking about how to jump around a silly elliptic curve in light speed, but what about encryption? Hang on, we are about to introduce it. And before that, let’s introduce key exchange first.

Think about this, Alice and Bob are traveling in the space, they are about to exchange the location of rebellion’s new HQ. Suddenly, they realized there are drones from the empire are tailing them and intercepting the communication between their spacecraft. To exchange information securely, they agree to meet at a secret coordinate where only both of them could know. But how can they exchange this secret coordinate if the enemy is eavesdropping? Now, Elliptic Curve Cryptography is here to rescue. Here’s what Alice and Bob are going to do:

Alice:

  

Hey Bob, let’s use P as the starting point, here’s my public key NP

Bob:

  

P as the starting point sounds good to me, and my public key is MP

Here, as how we defined it, is the point of after times of sum operation. And likewise, is point of after times of sum operation.

Next, Alice takes Bob’s, start adding this point to itself times:

Bob will instead take Alice’s public key and add this point to itself times:

Well, both and are very big, as we don’t want the enemy to find it out easily. Obviously, they are really adding one-by-one, they are cheating by using the double-and-add trick we just introduced. Eventually, they will meet at a secret coordination only they could know

Think about this, for Alice, each jump is times worth of point, and she does it for times. And for Bob, each jump is times worth of point, and he does it for time. Let’s say Alice is jumping 4 lightyears a time, and she jumps 3 times. And Bob is jumping 3 lightyears a time, and he jumps 4 times, or they are all going to end up at:

For eavesdroppers, they need to find out or to be able to get the same coordinate. One step off and the final point will be completely off. But as we mentioned previously, there’s no easy way to do that given the number is big enough, so that we can be sure only Alice and Bob could know this secret coordinate. This key exchange protocol is calledElliptic Curve Diffie – Hellman.

Encryption

Now let’s talk about encryption. For Alice, to send information securely to Bob, they need to perform Elliptic Curve Diffie – Hellman key exchange first as we just mentioned above:

Please note here, Alice needs to be able to verify that the public key really belongs to Bob. Otherwise, an imposter could provide their own public key to Alice, and claim to be Bob. Alice will then exchange a shared secret key with the attacker. The attacker can then performman-in-middle attack. To address the problem, there’s another concept calledPublic key infrastructure, as it’s off-topic, you can search it if you’re interested.

As today we want to only focus on Elliptic Curve Cryptography, let’s assume Alice already knew and have good faith that it’s from Bob, and Bob also knew Alice’s public key. Now, after the key exchange, they end up getting the same shared secret coordinate, we can take the x value as the key. Once we have a shared secret, it’s now easy. We can then use any secure symmetric encryption method to encrypt our secret data with the shared key. Let’s say we useAES 256here, for example. The receiver Bob can decrypt the encrypted message with the same shared secret key.

Great, now even with drones from empire eavesdropping all the communications, Alice can still share the location of rebellion’s new HQ securely to Bob. Likewise, Bob can use the same shared secret key to encrypt a secure message and send it back to Alice.

When Alice and Bob know each other, we know we can use Elliptic Curve Cryptography to send a message securely. However, what if there’s a case we want to send a message to someone securely, but they don’t know and probably don’t care who you are? Easy, in our example, we assume Bob already knew Alice’s public key, say if only Alice knows Bob’s public key, she can take her own private key, generate the same shared secret key, encrypt the data and send her public key in plain text along with the encrypted data. Once Bob received the message, he can use the and his private key to create the same secret key and decrypt the encrypted data. Just, however, Bob won’t be able to know the message is from whom, as the attached public key could belong to anyone. Alice can also choose to create a temporary new pair of key for the same operation if Bob doesn’t care who the sender is.

The problem of floating-point

So far, we have been talking about Elliptic Curve Cryptography with real number calculations. The reason we use real numbers here is that it’s easier to explain and understand. In the real world, this actually isn’t how we do cryptography. Using real number bring many problems, one big problem we have shown previously is that there will be calculation errors. Another problem is, for some extreme cases, the number could be extremely huge, and floating-point may not be able to hold it.

What should we use instead you may ask, the answer is to perform it onfinite field, or more accurately, on a finite field of integers modulo p, where p is a prime number. Again, we don’t want to dig the rabbit hole too deep, so if you are interested, you can readElliptic Curve Cryptography: finite fields and discrete logarithms, or watchthis series of video from Trusticaandtheir corresponding articles.

To explain elliptic curve on finite field of integers modulo p in math:

And let’s pick and let and, then visualize it:

This doesn’t look like too much of a “curve”, but it’s indeed what an elliptic curve looks like on a finite field. Basically, will be equal to only on specific integer points. Take point as the example, for:

and for:

As the both sides have the same remainder divided by, so that’s indeed a point on the curve.

While it doesn’t look like a curve, but it does follow the same group law like the one on real numbers. Let’s see an example, set point and, and calculate with the same sum operation:

Yep, also, a bit special about this curve on a finite field, when a line hits the boundaries, it can actually warp around to the other end, as the modular operation is circling around. The line will hit the third point somewhere, just like the curve on the real number does.

Given our example, is the point we hit. And we flip value to be and mod by will get you. So the sum of and is.

To make it easier to understand, personally I really like the presentation of it in 3D space as a donut shape, like the one fromTrustica video series about ECC:

But given that I am writing an article, it’s easier to present it in a simple 2D image.

Now, let’s add a new point to:

Next, let’s see if associativity of group law still holds with finite field, this time we add first:

Then, let’s add to:

Yep, they both end up at the same point:

a_b=a   b b_c=b   c (a_b   c), (a   b_c)  Point (p=19, x=14, y=16), Point (p=19, x=14, y=16))

Now you may ask, what about adding a point to itself? Yes, a point adding itself holds the same rule, using the tangent line on the finite field to connect the third. As we’ve already shown how this works with real numbers, we don’t want to repeat ourselves here, or, actually, that’s because I am lazy 😅.

In the end, as the finite field only operates on integers, we won’t lose any precision. It’s more suitable for cryptography purposes.

Finally

That’s it, now you know how Elliptic Curve Cryptography works. It took me an unexpected level of effort to write this post. If you like my writing, the best way to support me is to follow me onTwitter,dev.toor (Mediumfor new posts, share this article, or buymy book. Feedbacks are welcome. Finally, hopefully, it is as I promised this is institutive, and you found it helpful. ***