Theory of Elliptic Curves

Once again, this is just another of my notes aggregated from various sources. This is a very dumbed down version for just my understanding and it’s my advice to follow the resources attached as they are more thorough and detailed explained by experts on the topic. I’m just a novice who is interested in learning cryptography.

Walking side by side with death

The devil mocks their every step

The snow drives back the foot that’s slow

The dogs of doom are howling more

Now, for the song. This time we’ll listen No Quarter by Led Zeppelin. No description for this. I guess they don’t need one :)

Discrete Logarithm Problem

Discrete logarithm Problem (DLP) for a group $G$ and an element $g\in G$ is,

Given an element $h$ in the subgroup generated by $g$, find an integer $m$ satisfying $h=g^m$.

This can be computed using $m={\log }_g(h)$. DLP for some groups is said to be very easy and for some difficult which allowed cryptographers to experiment with it and invent some amazing primitives in cryptography.

DLP is easy for:

• $\frac{\mathbb{Z}}{m\mathbb{Z}}$ under addition
• ${\mathbb{R}}^{\star }$ or ${\mathbb{C}}^{\ast }$ under multiplication

And for some groups, it is difficult but not computably infeasible:

• ${\mathbb{F}}_p^{\ast }$ under multiplication: said to be sub-exponential

Elliptic Curves

This is a curve defined in plane ${\mathbb{R}}^2$.

$$\begin{array}{rcl}\{(x,y)\in \bar{K}& |& y^2+a_{1}xy+a_{3}y=x^3+a_2{x}^2+a_{4}x+a_6,\}\cup \left\{0\right\}\end{array}$$

• Above equation is called the general Weierstrass equation. $0$ is the point at infinity.
• $\bar{K}$ is the algebraic closure of field $K$.
• Can be defined on any fields, such as ${\mathbb{F}}_p,\mathbb{Q},\mathbb{R}$.
• EC defined on ${\mathbb{F}}_p$ are finite groups.
• ECDLP is discrete logarithm problem for the EC defined on finite field which has exponential time complexity to solve.
• Best known algorithm for an EC defined over ${\mathbb{F}}_p$ takes $O(\sqrt{p})$.

We make simplification of the general equation with the case when field characteristic is not 2 or 3. Define curve $E/K$ read as curve $E$ over field $K$. This gives rise to short Weierstrass equation form of the EC.

$$\begin{array}{r}E:y^2=x^3+ax+b\end{array}$$

Coordinate System

Affine Coordinates

Traditional representation of the coordinates, i.e. just an $(x,y)$ where $x$ and $y$ satisfy curve equation. Normally this representation is used for storing and transmitting points.

Standard Projective Coordinates

Point in standard projective coordinates $(X,Y,Z)$ represents $(\frac{X}{Z},\frac{Y}{Z})$ in Affine coordinate system. Also called homogeneous projective coordinates as the curve equation takes on the homogeneous form $Y^{2}Z=X^3+4Z^3$.

Points become straight line through the origin in $(X,Y,Z)$ space, with the affine point being the intersection of the line with the plane $Z=1$. Equivalence relation from plane to projective space can be defined as:

$$\sim :(a:b:c)\sim (a^{\prime }:b^{\prime }:c^{\prime })⟺\exists \lambda (a,b,c)=(\lambda a^{\prime },\lambda b^{\prime },\lambda c^{\prime })$$

Jacobian Coordinates

Jacobian Point $(X,Y,Z)$ → $\frac{X}{Z^2},\frac{Y}{Z^3}$. Curve equation becomes $Y^2=X^3+4Z^6$.

Group Law of Elliptic Curves

• Elements of the group are points on elliptic curve.
• identity element is the point at infinity $O$
• inverse of point $P$ is symmetric about $x$-axis
• addition rule: given three aligned, non-zero points $P,Q,R$ on EC, $P+Q+R=0$

Elliptic Curves in ${\mathbb{F}}_p$

$$\begin{array}{rcl}\{(x,y)\in ({\mathbb{F}}_p{)}^2& |& y^2\equiv x^3+ax+b(\mathrm{mod}p),\\ & & 4a^3+27b^2\not\equiv 0(\mathrm{mod}p)\}\cup \left\{0\right\}\end{array}$$

Every EC has an order $N$ which represents the number of points on the curve. This can be explained using group theory. Let’s say we have a group, and the order of group denotes the number of points on the group. Now, if we take a point on the curve, then it tends to repeat itself in a cycle after some points. An amazing animated tutorial for elliptic curve in $F_p$ can be found here.

For Example: Let’s take a curve $y^2\equiv x^3+2x+3(\mathrm{mod}p)$ and the point $P=(3,6)$. The multiples of P are just 5 distinct point on the curve $(0,P,2P,3P,4P)$ and they are just repeating themselves.

This makes set of the multiples of $P$ a cyclic subgroup of the group formed by the elliptic curve. The point $P$ is called the generator or base point of the cyclic subgroup. Finding order of the subgroup is done by finding smallest $n$ such that $nP=0$.

Normally, curves are defined for large prime fields, where short equation covers all possible isomorphism classes of elliptic curves. ¹

There are other ways to express an elliptic curve:

• Montgomery equation $B{y}^2=x^3+A{x}^2+x$, where $B(A^2-4)\ne 0$ in ${\mathbb{F}}_p$. substituting $x=Bu-A/3$ and $y=bv$ gives short weierstrass equation.
• Edwards equation $x^2+y^2=1+d{x}^2{y}^2$, substituting $u=\frac{1+y}{1-y}$ and $v=\frac{1+y}{(1-y)x}$ produces montgomery equation.

What is the difference between these curve equations? And how does one is beneficial over other?

Concisely answered here and here. Expanding on this, montgomery ladder is faster than standard Weierstrass point multiplication methods as montgomery ladder is constant-time. There is very concise explanation about Curve25519 by Martin Klepmann.

Montgomery curve

$$\begin{array}{rl}{M}_{A,B}:B{y}^2& =x^3+A{x}^2+x,B(A^2)-4\ne 0\end{array}$$

Why montgomery form is better for multiplication?

Edwards curve

TODO

Twisted Edwards curve

$$\begin{array}{c}E(\mathbb{F}):\{a{x}^2+y^2=1+d{x}^2{y}^2\}\end{array}$$

There is a 1:1 correspondence between TEd curves and Mont curves. In a more cryptographic glossary, every Twisted Edwards curve is birationally equivalent to Montgomery curve². To convert a curve from Twisted Edwards form to montgomery form:

$$\frac{4}{a-d}{y}^2=x^3+\frac{2(a+d)}{a-d}{x}^2+x$$

We can also convert a montgomery curve to Twisted Edwards curves using following equation:

$$\frac{A+2}{B}{x}^2+y^2=1+\frac{A-2}{B}{x}^2{y}^2$$

Resources

• ethereumbook’s elliptic curve section
• An Introduction to Elliptic Curves
• Exploring Elliptic Curve Pairings
• BLS12-381 for the rest of us
• Pairings over BLS12-381
• EC domain parameters
• choosing safe curves for elliptic-curve cryptography
• The animated elliptic curves
• Elliptic Curve Cryptography: a gentle introduction
• An introduction to elliptic curves

Footnotes

1. Pairings For Beginners Page 14 ↩

2. Birationally equivalent just means that a map exists between two objects and is invertible. ↩