Part 1: What Are Elliptic Curves ?

As stated in its name, elliptic curve cryptography (ECC) is based on a particular kind of curve called an elliptic curve. The aim of this first post on ECC is to explain what elliptic curves are.

Definition of elliptic curves

An elliptic curve is an abstract mathematical object generally defined as "a smooth, projective, algebraic curve of genus one, with a specified point (O)." This definition may seem complex, so let's break down the key terms:

• Smooth: A smooth curve is a curve that is free of singularities, such as cusps or self-intersections.

• Projective: A projective space is a fundamental geometric concept that generalizes the idea of euclidean space by adding "points at infinity," allowing for a unified treatment of lines, intersections, and perspectives.

• Algebraic: The curve consists of points that satisfy a polynomial equation.

• Genus : The genus of a curve is a topological invariant that, in intuitive terms, counts the number of "holes" in the curve.

• Specified point (O): This is the invariant point, the point at infinity of the curve where every lines intersect.

Illustration of the Point at Infinity: A Railway Analogy

This definition alone doesn’t provide a clear picture of what an elliptic curve looks like. In practice, elliptic curves are usually introduced via their algebraic equation, along with the criteria mentioned above.

Note: Elliptic curves should not be confused with ellipses, which are a different type of curve known as conics.

Smooth curves (curves without singularities) in the cartesian plan with they algebraic equation.

Familly of elliptic curves

Elliptic curves can be defined by specific algebraic equations. There are several well-known families of elliptic curves, each with particular properties and applications. Let’s take a look at some of the most commonly used ones.

Weirstrass curves

$$y^{2} + a_{1}xy + a_{3}y = x^{3} + a_{2}x^{2} + a_{4}x + a_{6} \quad \text{(Weierstrass form)}$$

$$y^{2} = x^{3} + ax + b \quad \text{(Weierstrass reduced form)}$$

where $a_i$ belongs to a field and the discriminant $\Delta$ (given by $4a^3 + 27b^2$ in the reduced form) is nonzero in $F_p$., defining an elliptic curve over $F_p$. Every elliptic curve over $F_p$. can be converted to a short Weierstrass equation if $p$. is larger than 3.

Weierstrass curve representation. The surrounding curves are not elliptic as they have a singularity point (cusp and a double point), i.e., Δ = 0.

Montgomery curves

$$By^2 = x^3 + Ax^2 + x \quad \text{(Montgomery form)}$$

where $B(A^2 - 4)$ is nonzero in $F_p$, defining an elliptic curve over $F_p$. Substituting $x = Bu - \frac{A}{3}$ and $y = Bv$ produces the short Weierstrass equation:

$$v^2 = u^3 + au + b$$

where

$$a = \frac{3 - A^2}{3B^2}, \quad b = \frac{2A^3 - 9A}{27B^3}.$$

Montgomery curves were introduced by Montgomery in 1987.

Montgomery curve representation. The surrounding curves does not respect one of the Montgomery criteria $B(A^2 - 4)$ ≠ 0.

Edwards curves

$$y^{2} + x^{2} = 1 + dx^{2}y^{2} \quad \text{(Edwards form)}$$

where $d(1 - d)$ is nonzero in $F_p$, defining an elliptic curve over $F_p$. Substituting $x = \frac{u}{v}$ and $y = \frac{u-1}{u+1}$ produces the Montgomery equation:

$$Bv^2 = u^3 + Au^2 + u$$

where

$$A = \frac{2(1+d)}{1-d}, \quad B = \frac{4}{1-d}.$$

Edwards curves were introduced by Edwards in 2007 in the case that $d$ is a fourth power. SafeCurves requires Edwards curves to be complete, i.e., for $d$ to not be a square; complete Edwards curves were introduced by Bernstein and Lange in 2007.

Edwards curve representation. The surrounding curves does not respesct an Edwards criteria d(1-d)≠ 0.

Takeaways

This article laid one of the mathematical foundations of elliptic curve cryptography: the elliptic curve itself. If you had to explain what an elliptic curve is, here are two ways to do it:

1. (Mathematician) Formal definition: Give the rigorous mathematical definition (which, while accurate, is hard to remember and not very intuitive).

2. (Engineer) Practical approach:

   • Show how these curves look graphically.

   • Describe the algebraic equations that define them.

   • Clarify that they are not ellipses and belong to a different mathematical family.

In Part 2 of this ECC series, we’ll explore finite fields and how elliptic curves are defined over them.