An Introduction to Elliptic Curve Cryptography: With Math!

BY

Modern cryptography is a very murky subject for many people, so today I will try to explain to you one of the more complex subjects, Elliptic Curves. Many of you may have heard their name before, but likely don’t know much about them beyond that. To begin, I will describe what an elliptic curve is.

An elliptic curve is an equation in the form $latex Y^2=X^3+AX+B$ where $latex 4A^4+27B^2\ \neq\ 0$.
If you refer to figure 1, you can see a handy graph of what one elliptic curve looks like.

Example graph of an Elliptic Curve.

Now, elliptic curves are useful for crypto because they have some useful properties. They have an identity element ($latex P \oplus 0 = P$), the have an inverse ($latex P \oplus P’ = 0$), they are associative ($latex P \oplus Q = Q \oplus P$), and they are commutative ($latex P \oplus (Q \oplus R) = (P \oplus Q) \oplus R$). This means they form an Abelian group. Which means that they behave “nicely” for how we want to use them.

In the prior section, I listed some equations that likely looked kinda familiar, but also weird because of the $latex \oplus$ symbol. This symbol is similar to + that you know, but is the analogue for adding two points on an elliptic curve. To add two points on an elliptic curve, you draw a line between them, then find the 3rd point on that line that intersects the curve. Then you mirror that point across the x-axis and that point on the curve is the result of that addition. If that description didn’t make the most sense, refer to figure 2 to see a graphic depiction.

Animated example of Elliptic Curve addition.

However, there are some corner cases we also need to address. What if the line between the two points doesn’t intersect the curve again? Then we say that the third point is 0, which can be thought of as a point at infinity (figure 3).

Animated example of Elliptic Curve addition using point at infinity.

Lastly, what if we add the same point to itself. This can be done by using the line tangent to the point, and then finding the 3rd point the same way as before (figure 4).

Animated example of Elliptic Curve addition using point at infinity.

Now that we understand what an elliptic curve is, we must address the motivation for using an elliptic curve for crypto. In traditional public key crypto, the name of the problem that makes them hard to crack is called the Discrete Log Problem. There is an analogous problem on an elliptic curve named the Elliptic Curve Discrete Log Problem. Now even though they are related problems, the time complexity of solving the DLP is less than the time complexity of solving the ECDLP. $latex O( p^{\epsilon}\textrm{ for every }\epsilon > 0)$ vs $latex O(\sqrt{P}\textrm{ on }F_p)$ respectively. Thus, elliptic curve crypto is much harder to brute force a solution.

Lastly, I will provide an example of how elliptic curves can be used for crypto. I will begin with describing the traditional Diffie-Hellman key exchange involving two people, Alice and Bob.

To do D-H key exchange, Alice and Bob both public agree upon two numbers g and p that they will share. Then, Alice generates A based on her secret number $latex \alpha$ and Bob generates B based on his secret number $latex \beta$ using the equations $latex A \equiv g^{\alpha} (mod\ p)$ and $latex B \equiv g^{\beta} (mod\ p)$ respectively. They then publicly exchange A and B. Alice then computes $latex B^{\alpha} (mod\ p)$ and Bob computes $latex A^{\beta} (mod\ p)$. However, these can be rewritten as $latex (g^{\beta})^{\alpha} (mod\ p)$ and $latex (g^{\alpha})^{\beta} (mod\ p)$ which are the same (because these operations are commutative). Thus, they have a shared number, but an outsider must solve the DLP for either A or B using g and m to recover $latex \alpha$ or $latex \beta$ which can then be used to find this secret shared number. This is visually demonstrated in figure 5

Animated example of Elliptic Curve addition using point at infinity.

Now, we can write the elliptic curve analog by replacing the operations $latex a^b (mod\ p)$ with $latex nP (mod\ p)$.

Thus, D-H key exchange using elliptic curves looks as follows. Alice and Bob agree upon a public point P on shared publicly known curve C. Then Alice generates $latex Q_a$ based on her secret number $latex n_a$ and Bob generates $latex Q_b$ based on his secret number $latex n_b$ using the equations $latex Q_a = n_aP$ (on C) and $latex Q_b = n_bP$ (on C). They then publicly exchange $latex Q_a$ and $latex Q_b$. Alice then computes $latex n_aQ_b$ (on C) and Bob computes $latex n_bQ_a$ (on C). These can be rewritten as $latex n_a(n_bP)$ and $latex n_b(n_aP)$ (both on c). Again, these are the same it is commutative. Again, they have a shared number (technically a point, but it can be converted to a number), but an outsider must solve the ECDLP for either $latex Q_a$ or $latex Q_b$ using P and the curve C in order to recover $latex n_a$ or $latex n_b$ which can then be used to find the shared secret. You can also refer to figure 6.

Animated example of Elliptic Curve addition using point at infinity.

Now that you’ve got a basic understanding of elliptic curves, it is important to remember, “with great power comes great responsibility.” It is almost never correct to write your own crypto algorithms. You should usually defer to using public and well known implementations. It is very common create bugs in your code that weaken your implementation while still allowing it to “work”.

Leave a Reply

Your email address will not be published. Required fields are marked

Your comment

Your name, please

Your email, please

POSTED

September 25, 2015

SHARE POST

LOCATED IN

(147)
(37)

TAGS

(2)
(1)
(1)
(4)
(3)

CATEGORIES

HAVE A QUESTION ABOUT OUR SERVICES?

Ready to start on a project?

WANT TO SEE OUR WORK?

Visit our case studies page or request specific project examples.