Elliptic Curve Cryptography:

A beginner’s introduction.

Elliptic Curve Cryptography (ECC) is a type of public key cryptography that uses elliptic curves over finite fields to derive keys. It’s the magic that powers website encryption, cryptocurrencies, iMessage, credit cards and many other secure data transfer systems. This article is for anyone looking for a high level overview of ECC without any prior knowledge. Let’s get into it.

Before we actually get into ECC, let’s break down a few terms.

1. Cryptography: Cryptography is the science of securely transmitting information in the presence of third parties. Take the internet, for example; every message, photo or piece of information you send over the internet is transmitted through the air, and anyone can listen in. Without cryptography, it’d be unwise to send anything remotely confidential.
2. Key: A key is a piece of information that is necessary to access some other information. It’s usually a string of characters that’s used to encode and decode messages in cryptography
3. Public Key (Asymmetric) Cryptography: Asymmetric cryptography is a class of cryptography that uses mathematically linked keypairs for encryption/decryption. The foundation of asymmetric encryption is that any information encrypted with one key can only be decrypted with the other key. So if you encrypt information with my public keys, only I, with my private keys, can ever decrypt it. This concept will become relevant later.

With the unfamiliar terms out of the way, let’s start with what an elliptic curve is.

What is an Elliptic Curve

An elliptic curve is a mathematical function defined by the equation:

Where a and b are any real variables with the condition that:

Here are a few pictures of elliptic curves:

All elliptic curves share two properties:

1. They’re all symmetric about the x-axis and,
2. A straight line through any two points on the curve will only touch one other point on the curve.

These two properties of elliptic curves are crucial to understanding ECC.

Operations on Elliptic Curves

In normal algebra, you can perform addition, subtraction, multiplication and division. In elliptic curves, there are only two operations that you can perform on points that lie on an elliptic curve:

1. Adding a point to itself.

Take a point P on an elliptic curve. To get 2P (in elliptic curve terms), we draw a tangent at point P, and wherever this tangent touches the curve is -2P. Since elliptic curves are symmetric about the x-axis, we flip the value of -2P and get 2P. In this example, R = 2P.

2. Adding two points together.

Let’s say there are two points on an elliptic curve, P and Q, and we want a point R where P+Q=R. According to the second property of elliptic curves, if we draw a line through P and Q, it will touch the curve at exactly one point. As you might have guessed, this point is -R. If we flip this point, we get R. Here, R = P + Q.

It’s important to note that elliptic curve operations are commutative. That’s to say it doesn’t matter if you add P to Q or Q to P, the answer will always be R.

The One-Wayness of Elliptic Curves

Let’s say I give you two points on an elliptic curve. And I tell you, one of them is an elliptic curve multiple (ecMUL) of the other; it is mathematically impossible to derive what the multiple is.

That’s to say if A = a.G, it’s impossible to extricate G knowing only a and A.

The only known way to find A is by brute force, i.e., to add G to itself for every possible value of a (1, 2, 3, 4, 5, 6, 7, 8,…, ∞) until you hit A.

Thanks to the power of computers, for a small elliptic curve, you should be able to find a after several hours of brute forcing. But for a large enough curve, the sun will literally explode and destroy the earth before you try all possible solutions.

The other important property of a and A is that because they’re mathematically linked. An encoding algorithm can be designed in such a way that anything encoded with a can only be decoded with A and vice-versa. This property, in conjunction with the one-way property of elliptic curves is what makes them perfect for public-key cryptography.

A Practical Example of ECC: The Diffie-Hellman Key Exchange Algorithm

The problem statement of the DHKE is a way to arrive on a shared secret over an insecure network.

This shared secret is usually used as the key for symmetric cryptography but further discussion of that is outside the scope of this article. Just imagine it as two people communicating over an insecure network who want to agree on a number that only the two of them know.

Say we have two people, Alice and Bob, who want to perform a DHKE. Here’s how they can achieve it with elliptic curves and ECC:

Alice and Bob start by agreeing on and publicly disclosing:

1. the parameters of their elliptic curve,
2. a random point on the curve called the generator point G.

Next, they also each select random numbers, a for Alice and b for Bob. These numbers are their private keys and they don’t disclose them.

Next, each of them, performs an elliptic curve multiple of their private keys by the generator point to create public keys A and B.

They send these public keys to each other over the insecure network.

So far, all the following information is public:

1. the elliptic curve chosen by Alice and Bob
2. the generator point G.
3. the public keys A and B.

But only Bob and Alice know their private keys.

With this information, Alice and Bob can independently create a shared secret key that no one else can derive. Here’s how:

Since elliptic curve multiplications are commutative, If Alice and Bob multiply the other person’s public keys by their own private keys, they get the same answer.

For Bob:

For Alice:

Anyone listening over the insecure network has the elliptic curve, A, B, and G. But all of this information is insufficient to derive the shared secret.

The above is a basic example of how ECC can be used to secure information in the wild.

Another use for Elliptic Curves is the Elliptic Curve Digital Signature Algorithm (ECDSA), but that’s a topic for another day.

Conclusion

This article has explored how ECC works at a high level. In a bid for simplicity, I’ve left out some details, like the fact that the elliptic curves used in ECC are defined over finite fields as opposed to the set of real numbers. But a lot of that information is largely unnecessary to grok the concept. And I hope you’ve come away from this with a high level but complete understanding of how elliptic curves and ECC work.

That’s all for this article, have a good one.