Jack Greenberg, Oscar De La Garza, Nabih Estefan
Use your left and right arrows to nagivate!
Press the ? key to see the shortcuts.
Go back up or use the right arrow to continue.
Use the <esc> key to Zoom out and see all the slides.
If we say we have a set of integers modulo p called $\mathbb{Z}_p$, this means that $\mathbb{Z}_p = \{0, 1, …, p-1\}$. If a computation on any two elements in this set were to land outside of this range under normal circumstances, it would instead wrap back around to the other end.
đź”˝
Let’s say we are working in $\text{mod } 7$. Then we have the following:
$$1 + 1 \equiv 2$$ $$2 + 1 \equiv 3$$ $$3 + 1 \equiv 4$$ $$4 + 1 \equiv 5$$ $$5 + 1 \equiv 6$$ $$6 + 1 \equiv 0$$
This last sum is zero because it is larger than $p - 1$, so it wraps around to the beginning.
We can also say that two integers are congruent modulo p, written $a \equiv b \pmod p$, if and only if there exists a $k$ such that $a - b = kp$.
This means that we can convert between $a$ and $b$ by adding or subtracting $p$ repeatedly.
This also means that we can bring both $a$ and $b$ into the range of $\mathbb{Z}_p$ by adding or subtracting multiples of $p$, which we call reduction modulo p.
Let’s see an example
đź”˝
Let’s say we are working in $\text{mod } 7$. Then we have the following:
9 - 2 = k(7) 7 = 7
9 mod 7 = 2 mod 7
We can see that 9 seems to be out of the range of $\mathbb{Z}_p$, but by using $mod p$ we make sure its still in range.
One reason why modular arithmetic is used so often in computing is that it allows us to represent values in a finite number of bits, even if the number we are representing wouldn’t fit. This is because we decrease the number to fit in $\text{mod } p$, and if we set $p$ to a set number of bits, any $\text{mod }p$ calculation will be less than that number of bits.
An abelian group is defined by a set $E$ together with a an operation $\bullet$. This operation combines two elements $a,b \in E$. Abelian groups follow five other axioms…
Closure: If $a, b \in E$ then $a \bullet b \in E$.
Commutativity: For all $a, b \in E$, $a \bullet b = b \bullet a$.
Associativity: For all $a, b, c \in E$, $(a \bullet b) \bullet c = a \bullet (b \bullet c)$.
Identity Element: There exists an element $I$ in $E$ such that $a \in E$, $a \bullet I = a$. This is called the identity or nautral element.
Inverse Element: For every $a \in E$ there exists an element $b$ such that $a \bullet b = I$, where $I$ is the identity element. This also means that we call $b$ the inverse of $a$, also written $b = a^{-1}$.
An Elliptic Curve is a smooth, algebraic curve given by an equation of the form
$$y^2 = x^3 + Ax + B$$
The equations we’ll be looking at are in Weierstrass form:
$$y^2 = x^3 + Ax + B$$
There is an alternative form of elliptic curves called Montgomery curves that are of the form:
$$y^2 = x^3 + Ax^2 + x$$
One of the major uses of Elliptic Curves is Cryptography. In the next slides you will see why its used in cryptography and some examples of real world curves and their specific uses.
Bitcoin uses a curve called secp256k1. The equation looks like
$$y^2 = x^3 + 7$$
so $A = 0$ and $B = 7$.
Many major messaging services including Whatsapp and Signal use a curve called X25519. The equation of the curve is too big to show here.
An Elliptic Curve creates a group of points, and as explained in Abelian Groups, this means that there is an operation using points P and Q to get point R. Since this other point is still on the curve, the process can be repeated multiple times. The way this is done in an Elliptic Curve is the following:
When adding two points together, we draw a straight line between the two points, find the third point at which they intersect, and then reflect that across the horizontal axis…
If you want to know how this process looks mathematically, go down đź”˝
If not you can continue right ▶️
When adding two points, $P = (x_P, y_P)$ and $Q = (x_Q, y_Q)$, we write their sum as $P + Q = R = (x_R, y_R)$.
To draw a line between these two points, we calculate the slope between them:
$$\lambda = \frac{y_Q - y_P}{x_Q - x_P}$$
So the equation of the line becomes
$$y = \lambda(x-x_P) + y_P$$
We can plug this equation back into the curve equation, eventually giving us an solution for the components of the intersection point:
$$x_R = \lambda^2 - x_P - x_Q$$
$$y_R = \lambda(x_P - x_R) - y_P$$
This Desmos graph lets you play around with addition of points on an elliptic curve.
Now that we’ve seen addition, the next step is multiplication.
This doesn’t mean multiplying two points together—rather, we mean scalar multiplication, meaning adding a point to itself multiple times.
If you want to know how this process looks mathematically, go down đź”˝
If not you can continue right ▶️
The method for determining the location of the doubled point is similar to the method of adding, but the main difference is that since we can no longer calculate the “slope” between two points, we instead calculate the derivative at that point:
$$\lambda = \frac{dy}{dx}\Bigr\rvert_{P} = \frac{3x_P^2 + A}{2y_P}$$
The other two formulae are the same.
If we wanted to continue do a big point multiplication, like $48798273P$, the method of adding P to itself over and over can get very slow.
Instead, we use a method called Double and Add to quickly calculate the value.
Let’s say we want to do some computation like $dP$, where $d$ is some integer. We can begin by writing out the binary expansion of $d$. Let’s take an easy example, like $d=43$:
$$43 = 2^{5} + 2^{3} + 2^{1} + 2^{0}$$
In order to compute $dP = 43p$, we can rewrite our expression as:
$$43P = (2^{5} + 2^{3} + 2^{1} + 2^{0})P = 2^5P + 2^3P + 2^1P + 2^0P$$
So we can begin with $2^0P = P$.
We double it to get $2P$, and we add it to $P$.
We then double twice more to get $8P$, and add it again, and again with $32P$, and after we add it to our sum, we are left with $43P$.
If I gave you some point $X$, which I computed secretly by doing $dP$, and $P$, could you tell me what $d$ is?
This problem is known as the discrete logarithm problem, and it is the crux of the secureness of elliptic curve cryptography.
Think back to the graph when we explained Point Multiplication. If I gave you 3P, and called the point X. Would you be able to tell me that d = 3?
The reason ECC is secure is that there are no known methods for efficiently solving $X = dP$ for $d$.
The curves you’ve seen so are are defined over the plane of real numbers. So there are an infinite number of points that lie on the curve.
In ECC, we define curves over a finite field, or Galois field. The field is most commonly defined over the integers $\mod p$, where $p$ is a prime number. We generally write it as $(\mathbb{Z}_P, +\cdot)$.
Relies on a couple of steps with secret and public values:
Lets say Alice and Bob want to exchange information by encrypting it using the D-H key exchange method:
We are going visualize these as colors in a paint can to see how they each use they keys, but take into account these are integers in real life, and they are normally extremely big.
Lets say we have a third person Carlos, that doesn’t know any private keys, only the public ones. This means they know the base and mod g & p, and both public keys A & B. This means that Carlos doesnt know any of a, b or K. If Carlos were able to get any of these 3 secret keys, then they would be able to calculate K the shared private key with which the message are encrypted.
These private keys can technically be calculated if g & p are not chosen properly. Normally, p is a prime number of a large magnitude with g being a coprime to p-1. The final key is also normally 256 bits long.
These characteristics make it practically impossible for a third person to calculate K after its been established, making it extremely safe.
You may be asking now that we have gone through all of this, how exactly do all these components relate and work together?
We know that from D-H Key Exchange both parties can get a private key, known only to the people communicating. We call this key “K”.
We also saw how, if we have a starting point P in a curve, we can, through point operation, to another point in the same curve.
“K” is actually the parameter that tells us how many times to do the defined dot operation on the elliptic curve.
Since we get a new point, and getting “K” is close to impossible, being able to obtain the final key of the ECC with D-H Key Exchange is also practically impossible.
Thank you so much for taking a look through this site, we hope you learned a lot.
We had a great time learning about this topic, and we’re excited to share our learning with the rest of the world.
This site was created by Jack Greenberg, Oscar De La Garza, and Nabih Estefan.
The project was a final for MTH3110 (Discrete Math) taught by Dr. Sarah Spence Adams.
The site is built using Hugo, and specifically the reveal-hugo theme that uses Reveal.js.
The site is hosted using Github Pages . The repository can be found here.
The animations were created using Manim, the mathematics animation library by 3Blue1Brown.
Other animations were created using Keynote with the Magic Move transition
This site is released under the GNU GPLv3 license.
These are some sources we found helpful along the way. Credit where credit is due.