Understanding the basics of Elliptic-curve cryptography

Part 1) The theory and math — visually

Published in

Cabal-Labs

6 min readNov 15, 2022

Elliptic curve cryptography visualization, in space (Mid journey)

If you want to understand elliptic-curve cryptography but don’t want to get bogged down in the math, this blog post is for you. We’ll give you a basic overview of the math behind elliptic-curve cryptography, and then in part 2, we will apply what we learned to implement it in C++.

A brief overview

Before the 1970s, the only way to encrypt a message was to use a symmetric cipher, which requires both parties to have a shared secret. This was fine at the beginning of the 20th century, but the second World War and the rise of the internet made it necessary to develop a cryptographic protocol where two parties could communicate securely without any previous communication.

This kind of cryptography is known as asymmetric, or public-key cryptography. In simple terms, public-key cryptography is a system that uses two related keys — a public key and a private key — to encrypt and decrypt data. The public key can be shared with anyone, while the private key must be kept secret.

How does it work theoretically?

Here's a good video describing how it works that summarizes it very well in a visual way. If you would rather have text and visualizations, scroll below the video.

What is an elliptic curve?

Elliptic curves are a class of curves that satisfy certain mathematical criteria. Specifically, a planar curve is elliptic if it is smooth and takes the commonly used “Weierstrass form” of

y²=x³+Ax+B, where 4A³+27B² ≠0

Visualization of an elliptic curve

https://www.allaboutcircuits.com/technical-articles/elliptic-curve-cryptography-in-embedded-systems

On the left, in transparent red, is the 3-dimensional contour plot of y²=x³–3x+z. The orange plane that intersects the 3D contour plot is shown on the right. The curve is “elliptic” everywhere except at the saddle point, where the curve transitions from a closed curve to an open curve.

How this can be used to build encryption?

Elliptic curves have this property where adding two points on an elliptic curve creates a third point that lies on the curve. This third point is found by reflecting the point across the horizontal axis. It is defined as:

P ⊕ Q = R, where P + Q + R = 0

Note: The character ⊕ is used as a mathematical point addition operator, not the binary XOR operator.

Visualization of P ⊕ Q = R

As you can see for any point P and point Q there is a corresponding -R that intersects when forming a straight line through the curve. When this -R is reflected across the x-axis, we find point R.

How do we use this property to build a lock?

We can understand this visually by comparing it to a padlock.

https://blog.cloudflare.com/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/

The basic principle behind a padlock is that it uses a key to move the pins in the locking mechanism into the correct position in order to open the lock. The pins in the locking mechanism are usually spring-loaded so that they are always in the locked position unless the key is inserted and turned. When the key is inserted, it pushes the pins up to the shear line, which is the line at which the pins line up in the correct position to open the lock.

The way we can turn P ⊕ Q = R into a lock is by doing the same operations a specific number of times, n. That operation ends up acting just like the pins in a padlock.

When we reflect point -R over the X-axis and add it back to point P we always get a new point on the elliptic curve. We can keep doing this many times. Visually, we can understand this like a password like an android phone.

When we do this n times to arrive at a final point, finding out n when you only know the final point and the first point is hard. It would be like being told the starting point and ending point of the android password and being told to crack the code via random guesses. For an attacker, it's like doing a maze the size of Earth where the walls are all mirrors. Never knowing which turns to make and being unable to remember where they came from.

Easy to do, hard to undo. This is the goal of a trap door function. A function in which that is easy to compute in one direction, but difficult to compute in the opposite direction without special information.

This is how your crypto wallet keys work. The public key is the starting point on the curve and your private key is the number of times you do the operation P ⊕ Q = R. This allows you to sign transactions and prove that you are you with the private key.

How do we exchange these keys to do meaningful things?

Alice and Bob first agree to use the same curve and a few other parameters, and then they pick a random point G on the curve.

Both Alice and Bob choose secret numbers, or private keys, (α, β). Alice multiplies the point G by itself α times, and Bob multiplies the point G by itself β times.

Each arrives at new points A=αG and B=βG where they then exchange the points with one another. Starting at the new points, Alice and Bob again multiply their new point by their own secret number.

Bob and Alice multiply their secret number by the point they receive to generate the secret S. This works because:

Shared Secret = S =α(βG)=β(αG)

Visualization of getting a shared secret

This creates a way for two people to share a secret without anyone else being able to figure it out. The two people combine their messages with a shared secret, which makes it hard for someone who shouldn’t know the secret to figure it out. In part 2 we will use this understanding to implement it in C++.

Let's Implement it in C++

Now that we have an understanding of the theory and math, lets create an Elliptic point class in part 2 and then use that elliptic point class in part 3 to create a Elliptic Curve Digital Signature Algorithm.

Elliptic Curve Cryptography in C++

Part 2) Building an ECC class in code

blog.caballabs.com

Cabal Labs

Cabal Labs is on a mission to enhance human freedoms and rights through technological innovation. We have grown a network of companies that serve under our banner. These developers and researchers have made it their life’s goal to break the status quo and deliver revolutionary solutions to age-old problems.

We would love to hear from you: caballabs@gmail.com

References

This was article was made possible by these articles.