Intro

As long as there have been humans, there have been secrets. And as long as there have been secrets, there have been methods to conceal those secrets. Just looking through history gives us a glance into the rich history of trying to conceal information from prying eyes: the Caesar-Cipher, the Pigpen Cipher, Enigma.

But what exactly is cryptography? The prefix 'crypt' comes from the Greek word 'kryptos', which means 'hidden,' and the suffix means writing, or 'hidden writing.' Cryptography is the art of hiding messages in plain sight.

As technology has become more sophisticated, so has our cryptography. Today, we use math to make it statistically infeasible for prying eyes to decipher our messages. This math is what prevents your card from being stolen when you shop online, your identity safe while doing taxes, and keeps messages between you and loved ones private.

In our technologically driven world, almost all of our communication happens over the internet. The internet, by design, is a public place. Between any two devices, there may be any number of devices that relay (and can potentially steal) this communication. How can two devices with no direct communication possibly hope to keep anything safe?

History and Background

In 1976, Whitfield Diffie and Martin Hellman proposed a solution to this problem in what is known today as a Diffie-Hellman Key Exchange (DHKE).

The goal of this key exchange is simple: create a shared secret between two parties. This shared secret can then be used to encrypt messages, all over public channels. But how does one prevent a third party from replicating the steps to derive this shared secret? The answer is one-way functions, which form the backbone of this exchange.

One-way functions are operations that are easy to do but hard to undo. Let's use paints as an example. If you have two paints, it is trivial to mix them into a new color. However, if you gave a friend the mixed paint and asked them to figure out which two colors went in, they have no better option than to guess-and-check combinations of colors until they find a match.

This is the principle that Diffie and Hellman built their key exchange on. If we stick with the paint example, we can see how this exchange works. Let's say we have two people, Alice and Bob, who want to agree on a single paint color, but no eavesdroppers should be able to determine what color they agree on. Alice and Bob can accomplish by doing the following:

Alice and Bob agree on a public color anybody can see.
Alice and Bob each randomly choose a private color they keep secret.
Alice mixes her private color with the public color and sends the result to Bob.
Bob mixes his private color with the public color and sends the result to Alice.
Alice mixes the color she receives from Bob with her private color, arriving at the secret color.
Bob mixes the color he receives from Alice with his private color, arriving at the same secret color as Alice.

Visual of this exchange

Alice and Bob now have a secret color between them, and anybody who has been watching this exchange cannot determine any of the secret colors efficiently.

Using this principle, the DHKE can be used to create a shared secret between two parties as long as there is an underlying one-way function.

Much of our modern cryptography is based on this exchange. In 1977, Ron Rivest, Adi Shamir and Leonard Adleman built the RSA encryption scheme using the factorization of prime numbers as their underlying one-way function. This was the golden standard and is still used prevalently today, but the size of the numbers used has grown to stay ahead of advancements in computational power. Over time, these larger numbers have made the scheme less efficient.

Because of this, an alternative one-way function started to gain precedence: elliptic curves. Using elliptic curves as the basis for a one way-function was proposed by both Neal Koblitz and Victor Miller in 1985, and is the recommended method today. Elliptic curves can provide the same level of security using much smaller numbers.

Let's explore how these elliptic curves are used in cryptography, and the math that allows them to stay secure.

Explanation of Mathematics

An elliptic curve is a graph that follows the general equation: $$ y^2 = x^3 + ax + b $$ Below is an applet that lets you play with the $a$ and $b$ parameters yourself to see how they influence an elliptical curve:

Original Elliptic Applet

In our case, $a$ and $b$ can be any integer numbers as long as $4a^3+27b^2 \neq 0$. (This sounds intimidating, but it just makes sure our graph is sufficiently 'curvy' so the elliptic math works nicely.) In addition, we need to define a point at infinity to be a part of the curve. In elliptic curves, this is generally denoted as 0. This provides us with a finalized description of a valid curve: $$ \{(x, y) \in {\mathbb{R}}^2 | y^2=x^3+ax+b, 4a^3+27b^2 \neq 0\} \cup \{0\} $$
Now here's where things get really interesting. We're going to define a group over this definition. The rules of this group are as follows:

The elements of this group are the points of the curve.
The identity element (the element that remains unchanged by multiplication) is defined as the point $0$ (the infinity we discussed above).
The inverse of an element is the element symmetric through the x-axis.
Addition is defined as follows: given three non-zero points $P$, $Q$, and $R$, if a straight line can be drawn through these points, their sum is $P+Q+R=0$.
These points can be aligned without respect to order, so the addition operation is commutative.

That was a lot to process, let's just summarize the most important details:

Any operation preformed on a point will yield another point on the curve (with the exception of the 0 point).
Multiplication is defined as follows: $kP = \sum_{n=1}^{k} P$; (i.e. $4P = P+P+P+P$).
$P+P$ is equivalent to adding $P$ with a point infinitely close to itself, meaning $P+P$ is the tangent line of the elliptic curve at point $P$.

So what does addition actually look like in this group? Let's say we have points $P$ and $Q$ and we want to solve for $R$. Starting with our definition of addition, this would give us the following equation: $$ P + Q + R = 0\\ P + Q = -R $$
What this equation is effectively telling us is, ”given two points on the curve, draw a straight line between them. At the point where this line intersects the curve for the third time, take the reflection over the x-axis of this point to get the sum of the two original points.”

Here's an applet that allows you to see this in action. Try changing the coordinates of Points $P$ and $Q$ and see how Point $R$ reacts.

In this graph, we have points $P$, and $Q$. To add these two points together, we first draw a straight line between them and extend the line in both directions. Point $R$ will be defined as wherever this line intersects the curve for a third time. Then, by our third rule of the group, $-R$ will be point $R$ reflected over the x-axis. This gives us our final point, as we can see in the applet.

As neat as that is, how do we use this to create a one way function? Here's where the math gets really cool. Remember when we said that multiplying a point P by a positive integer k is like adding the P to itself k times? Let's see what this process actually looks like. Let's say we want to multiply P by 5. How does that look? $$ P + P + P + P + P = 5P\\ 2P + P + P + P = 5P\\ 3P + P + P = 5P\\ 4P + P = 5P\\ 5P = 5P $$ In this example, as we continue adding $P$, the resulting point will continue moving around the graph in an unpredictable fashion. And here is where we find our one-way function. In the applet below, try incrementing the value of $n$ one at a time. This has the same effect as adding another $P$ to the point $Q$.

Multiplication within this group is a one-way function. How? Let's say instead of $5P$, I wanted to calculate $117P$. You might think I have to sit and add $P$ to itself $117$ times, which would take quite a while. But remember, I can add two points together to get the sum of those points. We can take advantage of this to quickly calculate the quotient: $$ P + P = 2P\\ 2P + 2P = 4P\\ 4P + 4P = 8P\\ 8P + 8P = 16P\\ 16P + 16P = 32P\\ 32P + 32P = 64P\\ 64P + 32P + 16P + 4P + P = 117P $$ As you can see, instead of $116$ addition operations, we only needed $10$. But now what happens if I give you the starting point $P$ and the final point $117P$ and asked you to tell me how many times I added $P$ to itself? Because the point moves around unpredictably, the only way to find what I multiplied $P$ by would be to start at $1$ and continue incrementing until you found a matching point. This sounds eerily similar to our original paint conundrum!

In fact, we can now repeat our original DHKE with an elliptic curve!

Alice and Bob agree on an elliptic curve and a starting point (parameters $a$, $b$, and a starting point $P$) that anybody can see.
Alice and Bob each randomly choose an integer they keep secret.
Alice multiplies the starting point by her secret integer and sends the result to Bob.
Bob multiplies the starting point by his secret integer sends the result to Alice.
Alice multiplies the point she received from Bob with her secret integer, arriving at the secret point.
Bob multiplies the point he received from Alice with his secret integer, arriving at the same secret point as Alice.

Alice and Bob now have a shared secret between them that can be used to encrypt messages between the two!

Significance and Applications

It's hard to overstate how many practical applications this math has in the real world. This is math that you use every day, and most don't even realize it. It quite literally is a fundamental backbone of the internet, and by extension, our modern world.

You might be wondering now secure this algorithm is. In real cryptography, the numbers used are 256 bits long. This gives them an effective range between $0$ and $2^{255}$. To put this into perspective, this number is on the scale of atoms in the observable universe. In other words, an attacker hoping to brute-force one of the secret integers is at equivalent odds of trying to choose a single atom from all the matter in the observable universe. Of course, there are some ways to limit the scope of your search, but the number of combinations is so insurmountable. Let's say you had access to all the computational power currently being used in the Bitcoin network. This network can preform around $1.6 * 10^{20}$ operations per second. This sounds like a it should be able to break a key in no time. However, in actuality, it will take this network $1.2×10^{49}$ years to brute-force this key.

In addition to providing security over insecure channels, this same one-way property can be spun to a whole suite of cryptographic functions, such as message verification (making sure a message hasn't been tampered with after it's been sent), and random number generation (though this one has been met with controversy), among others.

In conclusion, by taking advantage of the quirky, and somewhat strange, properties of elliptic curves, we can continue to secure our privacy in this digital age.

Resources

Atom, A. C. (2015, May 17). Elliptic curve cryptography: A gentle introduction. https://andrea.corbellini.name/2015/05/17/elliptic-curve-cryptography-a-gentleintroduction/

Robert Pierce. (2014b). Elliptic Curve Diffie Hellman. YouTube. Retrieved October 30, 2023, from https://www.youtube.com/watch?v=F3zzNa42-tQ.

McFadden, C. (2023, June 22). 11 cryptographic methods that marked history: From the Caesar Cipher to Enigma code and beyond. 11 Amazing Cryptographic Methods That Made History. https://interestingengineering.com/innovation/11-cryptographic-methods-thatmarked-history-from-the-caesar-cipher-to-enigma-code-and-beyond

Sullivan, N. (2013, October 10). A (relatively easy to understand) primer on elliptic curve cryptography. The Cloudflare Blog. https://blog.cloudflare.com/a-relatively-easy-tounderstand-primer-on-elliptic-curve-cryptography/

Wikimedia Foundation. (2023a, June 14). Elliptic-curve Diffie-Hellman. Wikipedia. https://en.wikipedia.org/wiki/Elliptic-curve_Diffie%E2%80%93Hellman