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
🔽
Let’s say we are working in
This last sum is zero because it is larger than
We can also say that two integers are congruent modulo p, written
This means that we can convert between
Let’s see an example
🔽
Let’s say we are working in
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
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
An abelian group is defined by a set
Closure: If
Commutativity: For all
Associativity: For all
Identity Element: There exists an element
Inverse Element: For every
An Elliptic Curve is a smooth, algebraic curve given by an equation of the form
The equations we’ll be looking at are in Weierstrass form:
There is an alternative form of elliptic curves called Montgomery curves that are of the form:
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
so
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,
To draw a line between these two points, we calculate the slope between them:
So the equation of the line becomes
We can plug this equation back into the curve equation, eventually giving us an solution for the components of the intersection point:
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:
The other two formulae are the same.
If we wanted to continue do a big point multiplication, like
Instead, we use a method called Double and Add to quickly calculate the value.
Let’s say we want to do some computation like
In order to compute
So we can begin with
We double it to get
We then double twice more to get
If I gave you some point
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
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
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.