From Coils to Curves - A Primer on Elliptic Curve Cryptography

It is well known that prime numbers are important for cryptography, although it has not always been true. The advent of primes came with several groundbreaking papers almost 50 years ago. Pioneers in introducing asymmetric cryptography, Whit Diffie, Martin Hellman, Ron Rivest, Adi Shamir and Leonard Adleman, used results from number theory to build key agreement, encryption, and signatures. Prime numbers hold a very special position in number theory, and this carried over to cryptography.

Cryptographic protocols are typically working modulo some prime p. This can be likened to turning the number line into a coil, such that 0, p, 2p, etc. all join at the same place. From then on, whenever we add or multiply the number such that we go beyond p, we can simply remove as many multiples of p as necessary until we come between 0 and p again.

Now, imagine that we used a composite number instead, for example 12. Then 0 and 12 are "the same" in this situation, but that also means that 3 multiplied by 4 is ... 0! One of the intuitions when working with normal numbers is that if ab = 0, then either a or b would have to be 0. Hence, when using composite numbers, there is simply stuff that no longer works the way we’re used to. Fortunately, this is not the case when using the primes — for instance 7 — as our so-called modulus.

Let’s make a rule, and let’s call it m. We take the coil we just made from the number line, and since we can always reduce numbers to below p, we label our points on this circle from 0 to p-1. Given two points a and b on the circle, we decided that the output of the rule m(a, b) should be the point which is represented by the product ab, possibly after reducing modulo p. It may look like a very natural rule, but it is nonetheless a rule we just agreed on. If you play around with this rule a bit, you will notice some properties:

• If a = 1, then m(a, b) = b (and the other way around).
• For any a, b not equal to 0, m(a, b) is never zero. So, if we removed 0 from the circle entirely, no harm would happen — the rule would still be well-defined.
• For any nonzero a, there is always some b such that m(a, b) = 1.

These nice properties — together with a property called associativity — are the properties we need to be able to do cryptographic computations.

Now focus on a particular number on the circle, and let’s call it g. If we take m(g, g), or — to return to the more usual notation — g², we will reach a new point on the circle. We can continue this process and compute g³, g⁴, etc. At some point, we will reach 1.

All the points we have visited in this process are members of the set of numbers generated by g, and if the number of points on the coil is a large prime, then we have a very good candidate for doing cryptography, for example Diffie-Hellman key exchange. Let h be some number in this set generated by g. That means that h = gᵉ for some exponent e. If it is easy to find this e from g and h, we would have trouble. Fortunately, it turns out that if we use large enough primes, then this e appears to be very difficult to find.

Coiling up the number line is not the only way of finding suitable primitives for cryptography. Let’s make a new rule. Instead of using a circle like we did in the previous section, we consider the following equation:

y² = x³ + ax + b, where a and b are fixed constants.

If we graph this in our usual coordinate system, it may look like this curve:

We will now make a rule on how to combine two distinct points P and Q on this curve. The agreed upon notation is to call this rule addition, but we will have to define what we mean by that. Programming languages often include this mental concept as operation overloading. Draw the straight line between P and Q. It will intersect at a third point, say, R. This could have been a nice candidate for P + Q, but since we are making the rules, let’s make this a bit more interesting. Draw a vertical line through R. It will intersect the curve on the opposite side of the x-axis, and we define this point as P + Q. Just as before, this is a rule we’re deciding here and now. However, this also turns out to be a very useful rule, with the same properties as before:

• Instead of having the point 1 on the circle, we imagine a point infinitely far up. (Remember what you see when looking at railway tracks: parallel lines actually meet beyond the horizon, at infinity.) So, now the line intersecting R and P + Q is indeed also intersecting a third point: the point at infinity. This can be made precise, but requires maths from algebraic geometry, which is far beyond the scope of this blog post. This point at infinity has all the same properties as 1 had above.
• For any point S on the curve, there is always a point T such that we get a line intersecting S, T and the point at infinity. This means that for any point S, we can find a point we can call -S.

You can test this rule interactively in a simple GeoGebra demonstration.

In this case we assumed that P and Q were distinct. If P = Q, then we simply use the tangent to the curve at point P instead, and proceed as before.

In particular, take a point G, and compute 2G = G + G, 3G, 4G, etc, that is, we add G to itself many times. Eventually, we reach the point at infinity, and then back to G, see illustration below. We have now spent about 1000 words of this blog post getting here, just to do the same as we did above (where some fixed number g was multiplied by itself over and over again until we reached 1 modulo p), and what was the point? Above, we said that computing exponents are secure if the primes were large enough. It turns out that "large enough" is currently about 3072 bits, or a number with approximately 925 digits. That is somewhat strenuous even for a computer, but the elliptic curve version only requires us to work on numbers of size 256 bits, or 77 digits, which is far more efficient.

The Diffie-Hellman key-exchange protocol is widely used today, and its instantiation using elliptic curves is ranked as the best choice in modern cryptographic protocols like TLS and SSH. The protocol is fairly simple. The public information is an elliptic curve E and a generator G for the points on this curve. One party, Alice, samples a random integer a and computes a point A = aG. Another party, Bob, samples a random integer b and computes B = bG. Then they exchange the values A and B, and compute the shared key K = bA = aB = abG. As long as both a and b stay secret, even when an attacker knows G, A and B, then the key is secure.

Reference: https://asecuritysite.com/encryption/go_x3dh. Used with permission.

To achieve long-term security, to protect previous messages in the case where someone’s secret keys are leaked after the fact, Alice and Bob can do an ephemeral key-exchange every time they communicate. If a and A is Alice’s long term key pair where A is public to everyone, and similar for Bob, they can run the following protocol to agree upon a one-time session-key. Alice samples a random integer c and computes C = cG, and Bob samples a random integer d and computes D = dG. Then they exchange C and D, and compute the shared key as (ab + cd )G.

The interested reader can check out this simple example written in Go. Are you able to extend the basic protocol to the ephemeral key-exchange on behalf of Alice and Bob?

We finally point out that this protocol is vulnerable to a man-in-the-middle attack, and we need to also send signatures computed on the messages to ensure that the communication is authentic. Are you able to attack the protocol as described above, when signatures are not used? If you found these problems interesting, we encourage you to check out similar challenges at cryptohack.org.

Not all elliptic curves are suitable for cryptography. There could also be power in choosing a curve and the distinguished base point(s). Hence, implementations tend to choose among a small number of well-known curves. The US National Institute of Standards and Technology maintains a list of recommended curves; P-256 is perhaps the most popular among these.

Among others, there is also the SafeCurves collection proposed by Dan Bernstein and Tanja Lange. In particular, their Curve25519 has proven to be a popular choice.

Elliptic curve libraries will typically have tailored support for certain curves.