Elliptic_Curve

Table of Contents

Assumed Knowledge
What is an Elliptic Curve
Addition Geometrically
Multiplication
Types
Elliptic Curve Cryptography Background

This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.

Assumed Knowledge

Modular Arithmetic

What is an Elliptic Curve

An elliptic curve is simply a curve over 2 dimensions that has equation y² = x³ + ax + b. What makes this worth studying is all of it's special properties as I will describe below

Addition Geometrically

To add the Points P and Q take the line between them and then extend it until it hits the curve again and call that point R, take the reflection of the point R in the x axis and then this point is P + Q.

There are however 3 different cases of the above statement that we need to think about as illustrated above

This is where everything works perfectly as Q and P are different points and the line going through them hits the curve at exactly 1 other point so P + Q is just the reflection of that point
This is where P = Q and so we take the line through these 2 points to be the tangent to the curve at P; however this line will still hit the curve at exactly 1 point and so 2P is just the reflection of that point
This is where Q is directly under P (in this case we say Q = -P). This line will never hit to the curve again however for convenience sake we say that the curve includes a special point 𝓞 (called point at infinity or Poif) and so Q + P = 𝓞
3 now makes us consider what would happen if Q was this special point 𝓞; luckily we take the line between P and 𝓞 to be the line directly downwards so in image 3 this would mean it'd hit the curve again at Q making that R and so P + 𝓞 = P

𝓞 is called the unit of addition (as P + 𝓞 = P) but in some formulations of the Elliptic curve

Why is P + Q not just R

A lot of what makes Elliptic curves interesting and useful is the interesting way in which you can do multiplication by a number on them; and specifically the reason they are good for cryptography is that this multiplication is difficult to predict.

Now say P + Q = R as described above. Then P + P = R where R is where the tangent to the line at hits the curve again; R = 2P. R + P would therefore be 𝓞 as the line through P and R doesn't hit the curve at any other points (as the tangent to the curve at P goes through P and R and those are the only points it hits the curve). So for any point 3P = 𝓞 and so 4P = P (by 4 above). However this makes multiplication rather less exciting as nP is either P, 2P or 𝓞 which takes away the difficulty of the problem that we rely upon when we're doing cryptography over elliptic curves.

All of these problems are solved by making P + Q = -R, and so that's what we do

abbreviation(with HTML of abbr label)

That is, the abbreviation of a longer word or phrase, provided that recognition is turned on HTML Label is turned on by default

Multiplication

Now we aren't very interested in multiplication by other points on the elliptic curve - we are more interested in np where n is a integer.

We can define multiplication as below

0P = 𝓞
(n+1)P = P + nP

The smallest positive n such that nP = 𝓞 is called the order of P.

Types

Name	Formula	The unit	Addition Formula	Doubling Formula
Short Weierstrass	$y^2=x^3+ax+b$	Poif	$g=\frac{y_2-y_1}{x_2-x_1}$ $x_3=g^2-x_1-x_2$ $y_3=(2x_1+x_2)g-g^3-y_1$	$g=\frac{3x_1^2+a}{2y_1}$ $x_3=g^2-2x_1$ $y_3=3x_1g-g^3-y_1$
Montgomery	$by^2=x^3+ax^2+x$	Poif	$g=\frac{y_2-y_1}{x_2-x_1}$ $x_3=bg^2-a-x_1-x_2$ $y_3=(2x_1+x_2+a)g-bg^3-y_1$	$g=\frac{3x_1^2+2ax_1+1}{2by_1}$ $x_3=bg^2-a-2x_1$ $y_3=(3x_1+a)g-bg^3-y_1$
Edwards	$x^2+y^2=c^2(1+dx^2y^2)$	(0, 1)	$x_3=\frac{x_1y_2+y_1x_2}{c(1+dx_1x_2y_1y_2)}$ $y_3=\frac{y_1y_2-x_1x_2}{c(1-dx_1x_2y_1y_2)}$	$x_3=\frac{2x_1y_1}{c(1+dx_1^2y_1^2)}$ $y_3=\frac{y_1^2-x_1^2}{c(1-dx_1^2y_1^2)}$

Assumed Knowledge

What is an Elliptic Curve

Addition Geometrically

Multiplication

Types

Elliptic Curve Cryptography Background