Elliptic Curves

Definition 1

The set of all lines in three-dimensional space that pass through the origin is called the projective plane. Any line that passes through the origin and does not lie in the $XOY$ plane (i.e., $z\ne 0$) can be associated with a point $(x,y,1)$. For a vector $l$ with coordinates $(X,Y,Z)$ where $Z\ne 0$, the corresponding point has coordinates:

$$\left(\frac{X}{Z},\frac{Y}{Z},1\right)$$

Thus, the projective plane can be thought of as the 2D plane $(x,y,1)$ along with a set of points at infinity formed by vectors lying in the $XOY$ plane.

Definition 2

A set of points $C$ on the projective plane $P$ of the form:

$$C=\{(x,y,z)\in P\mid f(x,y,z)=0\}$$

is called an algebraic curve. If the polynomial $f$ has degree $\mathrm{deg}f=m$, then $C$ is called a curve of degree $m$.

Bézout’s Theorem

Let $C_1$ and $C_2$ be two algebraic curves of degrees $n$ and $m$, respectively. If they have a finite number of intersection points and are defined over an algebraically closed field, then they intersect at exactly $m\cdot n$ points.

Definition 3

An elliptic curve is a cubic curve in the projective plane over an algebraically closed field $K$, given by a degree-3 equation with coefficients from $K$, along with a designated point at infinity.

The general form of the elliptic curve in affine coordinates is:

$$E:y^2+a_{1}xy+a_{3}y=x^3+a_2{x}^2+a_{4}x+a_6$$

If the curve is defined over a field of characteristic $\ne 2$, we can simplify the equation by a change of variable:

$$y\to y-\frac{a_{1}x+a_3}{2}$$

resulting in:

$$E:y^2=x^3+A{x}^2+Bx+C$$

For fields with characteristic $\ne 2$ and $\ne 3$, further substitution:

$$x\to x-\frac{A}{3}$$

gives the canonical form:

$$E:y^2=x^3+ax+b$$

Group Structure

An elliptic curve can be equipped with the structure of an abelian group. If $P$ and $Q$ are two points on the curve, Bézout’s theorem ensures that the line through them intersects the curve at a third point $R$.

Formulas for computing coordinates of resulting points are derived from solving the canonical cubic equation. These formulas can be found on Wikipedia. Using these formulas along with Bézout’s theorem, one can prove that this operation defines a valid abelian group.

Hasse’s Theorem

There is no general formula for the number of points on an elliptic curve group. However, Hasse’s theorem provides an estimate. For an elliptic curve over a finite field $F_q$ (where $q=p^n$ and $p$ is prime), the number of points $N$ satisfies:

$$|N-q-1|\le 2\sqrt{q}$$

In cryptography, one selects curves whose group order is the product of large primes. If the primes are too small, the curve is considered cryptographically weak. After selecting such a curve, the largest subgroup (with maximal prime order) is typically used.

Security Considerations

For cryptographic use, it is essential that the elliptic curve has no singular points. This can be ensured by checking that the discriminant is nonzero:

$$\Delta =-16(4a^3+27b^2)\ne 0$$

Otherwise:

1. If all three roots of $x$ are zero, the equation becomes $E:y^2=x^3$. Mapping each pair $(x,y)\in E$ to $\frac{x}{y}$ gives an isomorphism with the additive group, making the discrete logarithm trivial.
2. If the curve has a double root, it takes the form $E:y^2=x^2(x+a)$ with $a\ne 0$. Then, mapping $(x,y)\in E$ to $\frac{y+\alpha x}{y-\alpha x}$ (where ${\alpha }^2=a$) gives an isomorphism to a multiplicative group, in which solving the discrete log is also easy for typical key sizes.