# What Are Elliptic Curves?

## Elliptic Curves Are Not Ellipses

**Elliptic curves are not ellipses.**
An ellipse is a closed curve.
A circle is a special case of an ellipse.
Ellipses are pretty simple.

**An elliptic curve,** on the other hand,
is a more complex smoothly curving shape.
Potentially *much* more complex.

You can do operations of addition, negation, and multiplication
on points on an elliptic curve.
Those operations have exactly the same
properties as they do with integers.
But they work *very* differently.

Calculating powers, or chained multiplications,
is easy and fast.
But reversing that, calculating a
**discrete logarithm,**
is impractically difficult.
There's your **trapdoor.**

The big two things to see here are the graphical illustration
of addition on an elliptic curve, and how to calculate
a set of points on a curve.

Let's see how those work.

## Just A Little Math

For me the first big epiphany was seeing the graphical version of addition on an elliptic curve and how much it differed from what I had naïvely expected. The second was figuring out how to do the modulo arithmetic to generate a set of curve points.

But before those big steps,
we need to look at the **elliptic curve.**
It is defined as the set of points (x,y) satisfying
something called a Weierstrass equation:
$$ y^2 + axy + by = x^3 + cx^2 + dx + e $$

However, we're looking to do cryptography, not to explore abstract mathematics.

**The elliptic curves used in cryptography
are simplified by setting some of the
constants to zero or one:**
$$ y^2 + xy = x^3 + ax^2 + b $$

**or even simpler,** the frequently used:
$$ y^2 = x^3 + ax + b $$

We are free to choose the constants,
\(a\) and \(b\) in the two simplified equations
above, so long as the *discriminant* \( \Delta \)
is not zero:
$$ \Delta = -16(4a^3 + 27b^2) \neq 0 $$

Below are some example curves for various integer values
of \(a\) and \(b\).
Notice the shape where they're both zero,
when the determinant would also be zero.
It has a *cusp,* where the curve goes into a corner
and reverses direction.
Other combinations of \(a\) and \(b\)
yielding a determinant of zero generate a curve
that crosses over themself.
**To be a real elliptic curve, the discriminant
must be non-zero.**
No cusps, no crossings.
A curve might be in one or two parts,
if its discriminant is negative or positive, respectively.
We see two-part curves here for \( a = 2 \)
and \( b = \{-1, 0, 1\} \),
and for \( a = 1 \) and \( b = 0 \).

The constants \( a \) and \( b \) could be non-integer
real numbers like \(1.234\).
They could even be
*irrational* numbers like
\( \sqrt{2} \)
or *transcendental* numbers like
π, *e,* or *ϕ,*
numbers with an infinite number of digits.

But look at the above examples — they all use
integers for \( a \) and \( b \).
**Why make things harder than they have to be?**

Besides, where we're headed there is nothing but integers.

## A Little More Math (Elementary School Level)

There are a few basic concepts of arithmetic that you should have learned in your first year or two of school. They can be dressed up with fancy names, but the concepts or rules are very simple.

Let's say that all we have is **addition**
and **negation.**
Here are the rules with formal names, and some with
simpler explanations.
I'm using a fancy script 𝒪 to represent zero,
as you will see that in more advanced discussion
of elliptic-curve cryptography.

**Addition — adding zero does nothing:**
$$ P + 𝒪 = P $$
$$ 𝒪 + P = P $$

**Inverse or Negation:**
$$ P + (-P ) = 𝒪 $$
That leads to the invention or discovery of
**subtraction:**
$$ P + ( -P ) = P - P = 𝒪 $$

**Commutative — order doesn't matter:**
$$ P + Q = Q + P $$

**Associative — grouping doesn't matter:**
$$ (P + Q) + R = P + (Q + R) $$

What you learned as a young child is true for integers. $$ 7 + 𝒪 = 7 $$ $$ 7 - 7 = 𝒪 $$ $$ 2 + 3 = 3 + 2 $$ $$ (2 + 3) + 4 = 2 + (3 + 4) $$ And:

**Multiplication can be built from addition:**
$$ 2 \cdot P = P + P $$
$$ 3 \cdot P = P + P + P $$
$$ Q \cdot P = P + P + ... + P $$
The last one is \( Q \) copies of \( P \) added together.

## The Same Rules Apply On Curves

We can say that if ** E**
is the set of points on some elliptic curve,
then we can do arithmetic on those points.
And, the above rules apply.

What we're about to see is that we do arithmetic on those
curve points in a way that I did *not* expect.
Each point has some (*x,y*) coordinates, and
I expected arithmetic on those points to be like
vector addition, or dot products, or cross products.
**Not at all!**
But the important thing is that
the same rules and relationships apply.

Amazon

ASIN: B000000OXE

## Seeing This In Pictures

Let's select one curve out of the above collection, the one where \( a = -1 \) and \( b = 2 \). $$ y^2 = x^3 - x + 2 $$

Let's select two points on that curve,
*P* and *Q.*
Each would be defined in terms of *x* and *y*
coordinates satisfying the curve's equation.
$$ P = ( x_P, y_P ) $$
$$ Q = ( x_Q, y_Q ) $$
We don't want to bother with solving cubic equations here,
it's enough to know that we *could* if we had to.

Good news — we won't have to!

Here's where it starts to get a little weird.

To **negate** a point, you replace its
*y* coordinate with its negation.
You reflect the point's position
across the *x* axis.
$$ P = ( x_P, y_P ) $$
$$ -P = ( x_P, -y_P ) $$
$$ Q = ( x_Q, y_Q ) $$
$$ -Q = ( x_Q, -y_Q ) $$

Most of the time,
**a line through two points on an elliptic curve
also intersects the curve at a third point.**

*Most* of the time.
There are two exceptions.
One is a vertical line, which continues up and
down to infinity with no third intersection.

Notice: *"to infinity
with no
third intersection."*

The formal terminology is: *"An elliptic curve is
the set of points satisfying*
$$ y^2 = x^3 + ax + b $$
*plus
a point* 𝒪 *at infinity."*

So, "point 𝒪" means there's no such point, even infinitely far up and down the vertical line. OK.

Here's where it gets more weird, or at least more unexpected, at least for me.

We want to do arithmetic using points on the curve. We want to calculate: $$ P + Q = R $$

We can do this graphically. Draw a line through \( P \) and \( Q \). As long as \( Q \neq -P \) the line will also intersect the curve at a third point. That third point is \( -R \).

Negate that point \( -R \) and there's your answer, \( R \).

Amazon

ASIN: 0486682528

Amazon

ASIN: 0387978259

So if we add \( P \) and \( -P \), meaning if we subtract, we get $$ P + ( -P ) = P - P = 𝒪 $$ That is, a vertical line with "intersection at infinity", actually no intersection at all, so zero.

One last piece we need is **doubling,**
or multiplying by 2.

As \( P \) and \( Q \) come closer to each other, the point \( Q \) approaches becoming equal to \( P \). The line passing through \( P \) and \( Q \) approaches simply being the tangent to the curve at \( P \). When \( Q \) actually is \( P \), then the line is the tanget to the curve at \( P \) and it intersects the curve at \( -R \). Here's the other exception to the rule that every line through two points intersects the elliptic curve at a third point. We can graphically calculate: $$ P + P = 2 \cdot P = R $$

## The Algebra — Feel Free To Skip

The good news is that the algebra for calculating the coordinates of the answer has already been worked out for us.

The *even better news* is that we won't need
to get into those details!
If you want, feel free to
jump ahead
to the last page.

But to be complete, here is how to calculate the coordinates.
No need to draw lines and measure intersections.
Just plug the coordinates of *P* and *Q*
into some fairly simple equations.

**If the curve is:**
$$ y^2 = x^3 + ax + b $$
then to calculate \( R \) in:
$$ P + Q = R $$
where \( P \neq Q \) and:
$$ P = ( x_P, y_P ) $$
$$ Q = ( x_Q, y_Q ) $$
$$ R = ( x_R, y_R ) $$
you do it this way:
$$ \lambda = \frac{ y_Q - y_P }{ x_Q - x_P } $$
$$ x_R = \lambda^2 - x_P - x_Q $$
$$ y_R = \lambda( x_P - x_R ) - y_P $$

To calculate \( R \) in: $$ P + P = 2 \cdot P = R $$ you do it this way: $$ \lambda = \frac{ 3 {x_P}^2 + a }{ 2 y_P } $$ $$ x_R = \lambda^2 - 2 x_P $$ $$ y_R = \lambda( x_P - x_R ) - y_P $$

**If, on the other hand, the curve is:**
$$ y^2 + xy = x^3 + ax^2 + b $$
then to calculate \( R \) in:
$$ P + Q = R $$
where \( P \neq Q \),
you do it this way:
$$ \lambda = \frac{ y_Q + y_P }{x_Q + x_P} $$
$$ x_R = \lambda^2 + \lambda + x_P + x_Q + a $$
$$ y_R = \lambda( x_P + x_R ) + x_R + y_P $$

To calculate \( R \) in: $$ P + P = 2 \cdot P = R $$ you do it this way: $$ \lambda = x_P + \frac{ y_P }{ x_P } $$ $$ x_R = \lambda^2 + \lambda + a $$ $$ y_R = {x_P}^2 + \lambda x_R + x_R $$

That's it for the algebra formulas! On to the last page:

This is where overly formal treatments would tell you that

forms anEAbelian group,and a finite set of points on the curve is aGalois field.Even though both statements are true, they aren't helpful here.