INNOVATE

A Gentle Introduction to Elliptic Curve Cryptography

And the math that makes it possible

If you have ever read any article about elliptic curves, you already know that an elliptic curve is defined by the equation y² = x³ + a ⋅ x + b and has a strange looking graph like this one:

Figure 1: Curve y² = x³ — 7x + 10 plotted for all numbers by desmos.com.

However, what is the meaning of this? How do we use this strangely shaped line for cryptography? And why would we want to deal with elliptic curves in the first place?

Let’s take a step back for a second. Why do we need cryptography to begin with? In most daily cases, we need it for only three things:

1. to encrypt stuff (and then decrypt it)
2. to exchange keys (so we can communicate and exchange data securely)
3. to sign things (to prove ownership)

Of course, this doesn’t include an e-voting case, which needs cryptography for more specific operations: proving something about the secret without revealing the secret (zero-knowledge proofs), performing mathematics over encrypted data (e.g., homomorphic tally), etc.

So, how do cryptography goals relate to elliptic curves? The answer is speed. We use cryptography daily without even realizing it: connecting to websites, opening our cloud, logging into an app, etc. We don’t notice cryptography running in the background because it’s running fast. If we had to wait a few minutes every time we wanted to send a message, we would be aware and incredibly irritated at how slow everything is.

To see why elliptic curves help speed of cryptographic processes, recall that cryptography loves dealing with huge numbers, which is difficult even for modern computers. Generally, the bigger the number — the slower doing mathematics with it will be. However, if we check the guidelines, we’ll see that to achieve 128-bit level of security, we need 3072-bit numbers when working with integers but only 256-bit numbers for elliptic curve points. A 12-fold difference! That is why elliptic curves are so fast — they don’t need to deal with such enormous integers as cryptography based on discrete logarithms or module factoring.

However, the cost to pay for using such lightweights is the complexity of the operations. With integers, the mathematics we do is modular (we divide and keep the remainder of the division), which is relatively easy to understand. On the other hand, elliptic curves require artificial formulas — specifically designed operations to obtain a cyclic group of curve points suitable for cryptography. Those formulas are not as intuitively understandable as modular math. Nevertheless, if we focus on graphical representations of those operations, we can understand the logic of elliptic curve math.

The first operation we need is negation. We all know that 2 — 2 = 0, so -2 is the inverse of 2. In modular math, it’s a bit more complex. We claim number a is an inverse of b if a ⋅ b = 1 mod p. For example, for p = 11, the inverse of 2 would be 6 because 2 ⋅ 6 mod 11 = 12 mod 11 = 1. However, what would be the inverse of a point Q = (x, y) on a curve? There is no natural definition, but since we must define it, we say it is a “mirror point” or reflection -Q = (x, -y) (see Figure 2).

Figure 2: Point Q inverse by plotted desmos.com.

What about points addition? This is where things get crazy. To add points P and Q, we draw a line (the green line in Figure 3) between P and Q and find where it intersects with the curve (the blue line in Figure 3). Then, we need to find an inverse of the intersection point, which gives us the P + Q point. If it seems unnecessarily convoluted, remember that the formula is artificial. The mathematics were designed to ensure the sum of two points will stay on the curve and P + Q + (-Q) = P. Check, it will be true!

Figure 3: Point Q and R addition plotted by desmos.com.

However, what if we would like to add Q + Q? There is only one point, but our formula for point addition says we need two. Luckily, there is a different formula for the Q + Q operation called point doubling. To double the point, we need to draw a tangent — a straight line that “just touches” the curve at point Q. Then we find where the tangent intersects with the curve and inverse that point to get 2Q.

Figure 4: Point doubling plotted by desmos.com.

Is that it? Not yet! There are a couple of exceptional cases (see Figure 5) when the tangent is a vertical line and when we try to add Q and -Q. Strictly speaking, there is no intersection with a curve in these cases, so our formulas do not work … unless we imagine an intersection.

This imaginary point is called a point at infinity Θ, and we must always add it to our curve, so the math works smoothly. We also say that Θ + Θ = Θ, Q + Θ = Q and Q + (-Q) = Θ.

Figure 5: Tangent doesn’t interest with the curve plotted by desmos.com.

What about point multiplication? Well, such an operation is not defined. We are only allowed to do point addition, negation, and doubling. However, we can extend formulas to compute xP for any x (e.g., 5P = 2 ⋅ (2 ⋅ P) + P). The beauty is that, by only looking at the result, it is hard to say what x was used (if we use sufficiently large numbers and a secure curve), which is enough to build cryptography!

Of course, our phones and computers do not draw graphs and find intersections — that would be too slow. Also, computers love integers, so we use elliptic curves over finite fields instead of dealing with all numbers. In other words, we always do mathematics modulo some prime p.

By definition, the elliptic curve over a finite field with a prime p > 3 is the set of all points with integer coordinates (x, y) which fulfill the equation y² ≡ x³ + a · x + b mod p together with an imaginary point of infinity Θ, where a, b are such integers that 4 · a³ + 27 · b² ≠ 0 mod p. The extra condition is needed to ensure the curve is non-singular — without self-twists or cusps (see Figure 6) because our math would not work with them.

Figure 6: Curve with a cusp and curve with a self-twist plotted by desmos.com.

To perform point addition and doubling, there are formulas:

As you can see, all cases involving the point at infinity must be handled with care. Moreover, this point does not always have a numerical representation, so some curves should be more careful with arithmetic than others. But we’ll talk about that in the next ECC article.

If you’ve read this far, you’re probably wondering why all our graphs were plotted for all numbers when elliptic curve cryptography always does operations modular prime p. The answer is for the simplicity of the explanation. Figure 7 shows the curve y² = x³ — 7x + 10 plotted for all numbers and curve points over a finite field with the prime p = 11. The result is quite different, right? However, as crazy as it sounds, all points still belong to the curve.

Figure 7: Curve y² = x³ — 7x + 10 plotted for all numbers and curve points over finite field for p = 11.

Recall that in the modular mathematics x + np mod p = x for any n. So, many different numbers would become x after the mod operation.

Similar logic holds for curves: a curve y² = f(x) in finite fields would be equivalent to f(x) + p, f(x) + 2p, etc. So, if we plot y² = mod(f(x), 11) for all numbers, the elliptic curve points we use for cryptography should end up on one of the resulting lines (see Figure 8).

Figure 8: Graph for y² = mod(x³ — 7 ⋅ x + 10, 11) + 11n plotted by desmos.com for n = [0,..9].

There are many more things to say about elliptic curves: optimizations for faster arithmetic, security, what is a safe curve to use, mapping messages to points, etc. Hopefully, we’ll touch on some of these topics next time!

This article was written by Tamara Finogina (PhD), Cryptography Researcher at Scytl.