Learning Cryptography, Part 3: Elliptic Curves

Introduction

Elliptic Curve Cryptography (ECC) was introduced in 1985 and has been one of the biggest advances in the field since then. It took 25 years of trial and testing before it was used in production by OpenSSL. Delays like this aren’t uncommon since the bridge between theoretical and practical cryptography can only be proven through the test of time.

ECC’s biggest downside lies in the inherent fact that it’s complex. Its upside lies in the fact that its 256-bit key is stronger and more efficient than RSA’s 4096-bit key. Rather than relying on large numbers alone, elliptic curves obtain their security by combining points on mathematical curves.

So what are elliptic curves?

We define elliptic curves as a group of x and y coordinates represented on a graph via an equation such as y^2=x^3–7x+10 represented below. Wherever there exists a valid x-value which corresponds to a y-value, we call that a pair on the curve that satisfies the equation. Example points for our example equation are represented below.

The curve y²=x³–7x+10.

Real-world elliptic curves aren’t too different from this, although this is just used as an example.

You can try calculating a point yourself by plugging in the numbers:

• y^2=x^3–7x+10
• y^2=(2)3–7(2)+10
• y^2=8–14+10
• y^2=4
• y=2

The point (2, 2) exists on the graph above and is considered a valid pair. An example of an invalid pair would be where the x-value is less than ~ -3.1, since no y-value can be determined when substituted into the equation.

Elliptic Curve Integers

Our elliptic curve depicted above can be represented as a group of integers represented by each y-value modulo a prime number.

Below is the group of integers represented by the equation y^2=x^3–7x+10 mod 19.

We can derive these points ourselves as well. Let’s take the point where x = 5.

• y^2 mod 19=x^3–7x+10 mod 19
• y^2 mod 19=(5)^3–7(5)+10 mod 19
• y^2 mod 19=125–35+10 mod 19
• y^2 mod 19=100 mod 19
• y^2 mod 19=5
• y=9 or 10 (y=9*9=81 mod 19 = 5 or 10*10 =100 mod 19 = 5)

Instead of using modulo 19, what if we used 97? Suddenly we get 82 points instead of 24.

To make this even more obvious, if we used modulo 127 then we’d get 133 points.

Point Addition

Adding points on an elliptic curve are relatively easy to understand. All we do is draw a line between the two points on our graph, find the third point of intersection on the curve and reflect it on the. I’ve illustrated how it works visually below.

To recap our geometrical method of doing point addition:

1. Choose your point P;
2. Choose your point Q you want to add P to;
3. Find the third point of intersection;
4. Reflect the third point of intersection along the y-axis to get your final result.

As easy and straight forward as this method is, it won’t always work and isn’t how computers do point addition. Instead:

1. We need to find the gradient of the two points in the form of y=mx+c;
2. Find the point of intersection between the two curves where (mx+c)2=x3–7x+10;
3. Depending on our range of solutions we need to do point addition or double the point itself (which we’ll cover soon).

Adding a Point to its Negative

Each point P on an elliptic curve has an inverse defined as “the point at infinity”. Finding the point at infinity is as simple as finding the point of intersection along the y-axis with the mirror image. The point itself is virtual and doesn’t intersect the curve. It’s best described as a virtual point that describes what 0 is to integers.

Adding a Point to Itself (Doubling a Point)

You may be a bit overwhelmed with the number of concepts presented but if there’s anything you need to pay attention to, it’s this part. If we want to add a point P to itself, we call the operation doubling. It works a little something like this:

1. Draw a tangent to the curve at point P;
2. Find the first point of intersection with the elliptic curve;
3. Reflect the intersection point along the y-axis;
4. You now have your point defined as 2P = P + P.

Multiplying Two Points

Just like regular multiplication, point multiplication relies on multiple point addition operations. If you need to multiply P, k times then you just execute a series of addition operations. For example:

• 2P=P+P
• 3P=P+P+P
• 4P=P+P+P+P
• and so on…

Point addition in this manner would take a long time especially if we’re dealing with much larger numbers. So how can we speed this process up? Well, there’s a little trick we can utilize called the “Fast Exponentiation Algorithm”. Here’s how we could use it to find out what 32P is:

• 2P=P+P
• 4P=2P+2P
• 8P=4P+4P
• 16P=8P+8P
• 32P=16P+16P

As you can see this took us just 6 steps rather than 32 steps. Thinking about the costs of computation and optimizing it takes us to the branch of complexity theory which we’ll touch later on.

Closing

This is by far one of the more complicated articles in this series. Our goal was to introduce you to the basics of elliptic curves, how they’re formed and the types of operations we can do on them. Upcoming parts will talk about how we utilize the properties of elliptic curves for the public key and private key cryptography in today’s world.

About Loopring

Loopring is a decentralized exchange protocol utilizing zkSNARKs to bring highly scalable, non-custodial trading to the masses. You can sign up for their bi-weekly update, and learn more at:

⭑ Twitter: twitter.com/loopringorg
⭑ Reddit: reddit.com/r/loopringorg
⭑ Telegram: t.me/loopring_en & t.me/loopringfans (Chinese)
⭑ Discord: discord.gg/KkYccYp
⭑ GitHub: https://github.com/Loopring
⭑ Kakao: open.kakao.com/o/gJbSZdF (Korean)