Elliptic Curve Cryptography

Summary

This documentary gives a brief introduction into elliptic curve cryptography

Elliptic Curve Cryptography

Elliptic curve cryptography is a part of asymmetric cryptography, it is based on the mathematical hard problem to find a solution for the elliptic curve discrete logarithm. The calculations are performed on the algebraic structure of elliptic curves over finite fields, which means we compute points on a elliptic curve over finite field by applying the group operations double and add. The scalar multiplication of a point on an elliptic curve over a finite field is equivalent to the exponentation of a number in a prime field, therefore the inversion is also called discrete logarithm.

First proposed application of elliptic curves in cryptography was random number generations, now ECC is widely used for key establishment and digital signature schemes.

Simple Weierstrass Elliptic Curve Presentation

• Simple Weierstrass form curve equation:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y^2 = x^3 + ax + b} The elliptic curve are all points in the x,y coordinates which fulfill the cubic curve equation, whereas a and b are called the characteristic of the curve. The curve needs to be smooth, which means that it will not contain any singularities such as a cusp or a self intersection,

This can be also described by the term: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 4a^3 + 27b^2 \neq 0}

Another characteristic we need to introduce is the point at infinity denoted by Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{O} } (also known as ideal point), which can be thought as identity element infinitly raised on the y axis. Therefore our points on the elliptic curve over R² all fulfill this equation Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{(x,y) \in R^2 | y^2=x^3+ax+b, 4a^3+27b^2 \neq 0\} \cup \{\mathcal{O}\}} and can be presented by:

A point consists of 2 values P(x,y).

Group operations on elliptic curves

According to the group law all points support following operations:

• Point Addition: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P+Q=R}
• Case: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Q=P} -> Point Doubling : Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2P=R}
• Case: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Q=-P} -> Inversion of a Point: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P + (-P)=\mathcal{O} }

TODO:Need to install link target extension: https://www.mediawiki.org/wiki/Extension:LinkTarget Test: https://cdn.rawgit.com/andreacorbellini/ecc/920b29a/interactive/reals-add.html

Point Addition

Given the elliptic curve Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle E:y^2=x^3+ax+b} and the points Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P=(x_1,y_1)} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Q=(x_2,y_2)} , we can caculate the coordinates of the point Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle R=P+Q=(x_3,y_3)} as follows.

Geometric derivation of the point addition by the Tangent Chord Law

1. Calculation of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y_3}

• We know the equation from the line

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y=kx+d \qquad \text{concising of} \qquad k=\frac{\Delta y}{\Delta x}}

• Therfore

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k=\frac{y_2-y_1}{x_2-x_1}} and we can find the intersection with the y-axis and achieve d Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d=y_1-kx_1=\frac{y_1\cdot x_2-y_1 \cdot x_1-y_2 \cdot x_1 +y_1 \cdot x_1}{x_2-x_1}=\frac{y_1 \cdot x_2-y_2 \cdot x_1}{x_2-x_1}} .

• Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y_3} we can find by insertion in the line equation:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y_3=(-1)\bigg( \frac{y_2-y_1}{x_2-x_1}\cdot x_3 + y_1 - \frac{y_2-y_1}{x_2-x_1}\cdot x_1 \bigg)=\bigg(\frac{y_2-y_1}{x_2-x_1}\bigg)(x_1-x_3)-y_1}

2. Calculation of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_3}

• Now we insert the values of the line equation into the elliptic curve equation:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{aligned} (k \cdot x+d)^2 &=x^3+a \cdot x+b\\ k^2x^2+2k \cdot x\cdot d+d^2&=x^3+a \cdot x +b\\ x^3-x^2k^2+x(a-2k \cdot d)+b-d^2 &=0 \end{aligned}}

• The cross points can be searched by

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{aligned} (x-x_1)\cdot(x-x_2)\cdot(x-x_3)&=0\\ (x^2-x \cdot x_2 - x \cdot x_1 +x_1 \cdot x_2) \cdot(x-x_3)&=0\\ x^3-x^2 \cdot x_2-x^2 \cdot x_1 + x \cdot x_1 x_2 - x^2 \cdot x_3 + x \cdot x_2 x_3 + x \cdot x_1x_3-x_1x_2x_3 &=0\\ x^3 - x^2 (x_1+x_2+x_3) + x(x_1x_2+x_2x_3+x_1x_3)+x_1x_2x_3 &=0 \end{aligned}}

• Now we can conclude from the second term

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{aligned} x^3-x^2 \underline {k^2}+x(a-2k \cdot d)+b-d^2 &=0\\ x^3 - x^2 \underline {(x_1+x_2+x_3)} + x(x_1x_2+x_2x_3+x_1x_3)+x_1x_2x_3 &=0\\ k^2 &=x_1+x_2+x_3 \end{aligned}}

• and achieve a solution for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_3} by:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_3=k^2-x_1-x_2 =\bigg(\frac{y_2-y_1}{x_2-x_1}\bigg)^2-x_1-x_2}

This is also called the calculations in affine coordinates and the computational costs are 1 x inversion, 2 x multiplications and 1 x quadration.

The Point Addition over an elliptic curve (e.g. a finite field

Algebraic group of points

The points further comply associative and commutative algebraic group laws and the handling of the neutral element:

• Closure: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P+Q=R \quad \forall \quad P,Q,R \in E}
• Associative law: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P+\mathcal{O}=\mathcal{O}+P \quad \forall \quad P \in E}
• Identity element and inverse that: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P+(-P) = \mathcal{O} \quad \forall \quad P \in E}
• Cummutative law: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P+(Q+R)=(P+Q)+R \quad \forall \quad P,Q,R \in E}

The inverse point of a point P(x,y) is therefore P(x,-y).

Scalar Multiplication

Is main used operation in cryptography, it adds n times the point P of the elliptic curve over a prime field.

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle nP= \underbrace{P+P+P+P+...+P}_\text{n times}}

Curve25519

Curve25519 is a highly optimized curve proposed by Daniel J. Bernstein (djb) in 2005. The curve equation is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y^2=x^3+486662x^2+x} over a prime field Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^{255}-19}