ECC

This page is outdated and will be reorganized and moved to https://www.ellipticcurve.info.

Equation of an elliptic curve

An elliptic curve is the set of solutions to a general equation in the third degree in two variables.

General form

$gz^{3}+hz^{2}w+jzw^{2}+kw^{3}$ $+\,mz^{2}+pzw+qw^{2}$ $+\,rz+sw+t=0.$

Weierstraß normal form

The general equation for an elliptic curve has ten coefficients. A linear transformation is employed to simplify it to a form easier to work with.

${\begin{bmatrix}x\\y\end{bmatrix}}={\begin{bmatrix}\alpha &\beta \\\gamma &\delta \end{bmatrix}}{\begin{bmatrix}z\\w\end{bmatrix}}+{\begin{bmatrix}\zeta \\\eta \end{bmatrix}}.$

When the coefficients of the general equation are worked out in the transformed coördinates $(x,y)$ in terms of the original coördinates $(z,w)$, this transformation can be solved for its Greek-lettered coefficients, and the general equation may be expressed much more simply in Weierstraß normal form with four coefficients, only two of which are free.

$y^{2}=x^{3}+ax+b.$

Elliptic curves over algebraic fields

The elliptic curve itself, defined by an algebraic equation, consists of the set of solutions to its equation over some algebraic field, which may or may not be explicitly specified in any particular context.

It is generally easiest to visualize the elliptic curve or draw a graph of it over the field $\mathbb {R}$ of real numbers. If complex (real+imaginary) solutions to its equation are of interest, then the field is $\mathbb {C}$; if rational points on the elliptic curve are of interest, then the field is $\mathbb {Q}$.

For cryptographic applications, it is usually the case that the elliptic curve is defined over an arbitrary "finite field" which is neither a subfield nor an extension of the real numbers.

Point group operation

The set of ordered pairs $(x,y)$ that solve the equation of an elliptic curve in Weierstraß normal form $y^{2}=x^{3}+ax+b,$ together with an additional point ${\mathcal {O}}$ "at infinity," form an additive abelian group under a specific operation "$\oplus$."

Identity and inverse

${\mathcal {O}}$ is the group identity element; for all points $(x,y)$ on the elliptic curve, $(x,y)\oplus {\mathcal {O}}=(x,y).$ The group inverse of a point is formed by reflecting it across the x-axis: $\ominus (x,y)=(x,-y)$ and $(x,y)\oplus [\ominus (x,y)]={\mathcal {O}}.$

General calculation

The intuitive idea is to consider the elliptic curve equation over the real numbers. If a straight line intersects the elliptic curve at two points, then their group sum is defined as the group inverse of the third point at which the line intersects the elliptic curve, so that

$(x_{1},y_{1})\oplus (x_{2},y_{2})\oplus (x_{3},y_{3})={\mathcal {O}}.$

The mechanics of this operation are labor-intensive but fairly straightforward to derive from scratch. Substitute the equation for the line through $(x_{1},y_{1})$ and $(x_{2},y_{3})$ into the equation for the elliptic curve $y^{2}=x^{3}+ax+b,$ solve for x, and factor out the first two solutions $x_{1}$ and $x_{2}$ to find $x_{3}.$

If $\lambda =(y_{2}-y_{1})/(x_{2}-x_{1})$ is the slope, then we can substitute $y=\lambda (x-x_{1})+y_{1}$ and factor out $(x-x_{1})(x-x_{2})$ to solve for x to find the third point $x=x_{3},$ where ${\big [}\lambda (x-x_{1})+y_{1}{\big ]}^{2}=x^{3}+ax+b.$

$x^{3}-{\big [}\lambda (x-x_{1})+y_{1}{\big ]}^{2}+ax+b$ $=\,(x-x_{1})(x-x_{2})(x-x_{3}).$

$x^{3}-\lambda ^{2}(x-x_{1})^{2}-2\lambda y_{1}(x-x_{1})$ $-\,y_{1}^{2}+ax+b$ $=\,(x-x_{1})(x-x_{2})(x-x_{3}).$

$x^{3}-\lambda ^{2}(x-x_{1})^{2}+(a-2\lambda y_{1})(x-x_{1})$ $-\,y_{1}^{2}+ax_{1}+b$ $=\,(x-x_{1})(x-x_{2})(x-x_{3}).$

Complete the cube and factor x – x₁

Substitute $x^{3}=(x-x_{1})^{3}+3x_{1}(x-x_{1})^{2}+3x_{1}^{2}(x-x_{1})+x_{1}^{3}.$

$(x-x_{1})^{3}+(3x_{1}-\lambda ^{2})(x-x_{1})^{2}+(3x_{1}^{2}+a-2\lambda y_{1})(x-x_{1})$ $-\,y_{1}^{2}+ax_{1}+b+x_{1}^{3}$ $=\,(x-x_{1})(x-x_{2})(x-x_{3}).$

$(x-x_{1})^{2}+(3x_{1}-\lambda ^{2})(x-x_{1})+(3x_{1}^{2}+a-2\lambda y_{1})$ $+\,{\frac {-y_{1}^{2}+ax_{1}+b+x_{1}^{3}}{x-x_{1}}}$ $=\,(x-x_{2})(x-x_{3}).$

Complete the square and factor x – x₂

Substitute $x^{2}=(x-x_{2})^{2}+2x_{2}(x-x_{2})+x_{2}^{2}.$

1. Solve the remaining linear identity for the last factor $x-x_{3}=0.$
2. Substitute $x_{3}$ into the equation for the line to find $y_{3}=\lambda (x_{3}-x_{1})+y_{1}.$
3. The reflection of $(x_{3},y_{3})$ across the x-axis is the result of the group operation: $(x_{1},y_{1})\oplus (x_{2},y_{2})=(x_{3},-y_{3}).$

Point doubling

Finding the group sum of a point with itself is a special case because it involves finding a line tangent to the elliptic curve at the point to be "doubled" rather than passing through two distinct points. Differentiate the Weierstraß equation $y^{2}=x^{3}+ax+b$ with respect to x (basic calculus) to find the slope of the line tangent to the elliptic curve at $(x_{1},y_{1}).$

${\frac {d}{dx}}y^{2}={\frac {d}{dx}}{\big (}x^{3}+ax+b{\big )}$

$2y{\frac {dy}{dx}}=3x^{2}+a$

${\frac {dy}{dx}}={\frac {3x^{2}+a}{2y}}$

Proceed as above with $x_{2}=x_{1},\,$ $y_{2}=y_{1},$ and $\lambda ={\frac {3x_{1}^{2}+a}{2y_{1}}}.$