Difference between revisions of "Elliptic Curve Cryptography"

Revision as of 12:41, 30 March 2020

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:

$y^{2}=x^{3}+ax+b$ The elliptic curve are all points in the $x,y$ coordinates $P(x,y)$ 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}\}} . A valid curve over rational numbers is shown in the next image.

In cryptography elliptic curves over finite fields are used. The number of rational 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 \#E} of an elliptic curve over a finite 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 K} e.g. the 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 GF(p)} can be computed with the Schoof-Elkies-Alkin algorithm, which is implemented in the PARI/GP library. The Hasse theorem gives an estimation of the number of points in the intervall:

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+1-2\sqrt{p} \leq \#E \leq p+1+2\sqrt{p}}

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

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 calculate 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(x_3,y_3)} by adding this two 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 R=P+Q} as follows.^[1]

Geometric derivation of the Point Addition by the Tangent Chord Law

In the geometric derivation a line is drawn through 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} 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} , the result point R is the symmtric inversion on the 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} axis of the point at the 3rd intersection on the elliptic curve. 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{concizing of} \qquad k=\frac{\Delta y}{\Delta x}}

Therefore

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}

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=\bigg(\frac{y_2-y_1}{x_2-x_1}\bigg)^2- x_1 -x_2 \ \text{ and } \ y_3=\bigg(\frac{y_2-y_1}{x_2-x_1}\bigg)(x_1-x_3)-y_1.}

This operation is also called the Point Addition in affine coordinates and the computational costs are 1 x inversion, 2 x multiplications and 1 x squaring. Interactive tool to visualize point addition online at https://cdn.rawgit.com/andreacorbellini/ecc/920b29a/interactive/reals-add.html.

Point Doubling

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 special 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 P=Q} with 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 P=(x_1,y_1)} . The result 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(x_3,y_3)} is achieved by doubling 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=2P} as follows.^[1]

Geometric derivation of the Point Doubling by the Tangent Chord Law

For the doubling a tangent is drawn at 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} . At the intersection with the elliptic curve again the inversion on the 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} is taken to achieve the result 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} .

1. The tangent in 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} has the equation 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=kx+d} . The slope of the tangent 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} is calculated by the differential function 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 E} 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 \delta x} 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 \delta y} .

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{E \delta x}{E \delta y}=\frac{(y^2=x^3+ax+b) \delta x}{(y^2=x^3+ax+b) \delta y}=\frac{3x_1^2+a}{2y_1}}

and then the intersection of the tangent with the y-axis is calculated by inserting the point coordinates 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)} in the equation of the tangent 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} .

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-k \cdot x_1=y_1-\frac{3x_1^2+a}{2y_1}\cdot x_1}

2. The y-coordinate of the point of the second intersection with 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 y_3} can be calculated by inserting the point coordinates in the equation of the tangent and multiply 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 (-1)} to get the inverse point on the y axis.

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)(kx_3+d)= (-1)\bigg(\frac{3x_1^2+a}{2y_1} \cdot x_3 + y_1-\frac{3x_1^2+a}{2y_1}\cdot x_1 \bigg)=\bigg(\frac{3 x_1^2+a}{2 y_1}\bigg)(x_1-x_3)-y_1 }

3. 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} is achieved by inserting

Example of elliptic point operations over an elliptic curve over a finite field

Given a curve E 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+3x+5 \text{ over } \mathbb{Z}_{17}} we examine the basic operations on the elliptic curve:

Validation of the elliptic curve: This is done to determine if the elliptic curve is smooth by calculating the discriminant.

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 \Delta = -16(4a^3+27b^2)= -12528 \equiv 1 (\mod 17)} therefore 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 \Delta \neq 0 } holds and this curve can be used for EC operations.

Examining the number of points: Choosing one random point of the curve P(6,1) as generator G all points on the curve can be calculated with the equations given above over a the prime field 17. This means first the point gets doubled and a modulo 17 operation is applied. Then continuously all other points are calculated by adding the point P to the result each time applying the modulo 17 .

(6,1)	(4,8)	(15,5)	(9,9)	(11,14)	(2,6)	(1,14)	(12,1)
(16,16)	(10,10)	(5,14)	(5,3)	(10,7)	(16,1)	(12,16)	(1,3)
(2,11)	(11,3)	(9,8)	(15,12)	(4,9)	(6,16)	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}}

All by point P(6,1) generated 23 points satisfy the equation of the elliptic curve. Notice that each x value has two y values.

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(6,1)+J(10,10) = ?}

The points P(6,1) and J(10,10) are added with calculations in the finite field using the modular operation each time. 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} m &= \bigg(\frac{y_2-y_1}{x_2-x_1}\bigg) \mod 17 =(10-1) \cdot (10-6)^{-1} \mod 17 \\ &= 9 \cdot 4^{-1} \mod 17 = 9 \cdot 13 \mod 17 \\ &= 117 \mod 17 = 15 \\ \end{aligned} }

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=m^2- x_1 -x_2 \mod 17= 15^2-6-10 \mod 17=4-6-10 \mod 17= -12 \mod 17= 5}

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=m(x_1-x_3)-y_1= 15 (6-5)-1 \mod 17=14}

Solution: 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(6,1)+J(10,10) = R(5,14)} The addition of point P and J to get the result point R is visualized in the next figure.

Algebraic group properties of the 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}}

Double and Add algorithm

Calculation in projective coordinates

Side Channel Attacks

Montgomery ladder

Standardization of elliptic curves

The domain parameters for ECC schemes are described in the form 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(q,a,b,G,n,h)} .

Parameter description
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}	defines the field size, either a prime 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} or 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^{m}} where m is prime
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 a}	first parameter of the 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 b}	second parameter of the 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 G}	generating point consisting of both point coordinates 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_G,y_G)}
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 n}	order 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 G }
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 h}	cofactor which is equal to the order of the curve divided 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 n}

The generation of safe elliptic curves is an effort, hence it is recommended to use standardized known curves. First curves have been standardized in the ANSI X9.62 standard by the American National Standards Institute(ANSI) in 1999 ^[2], these have been extended or replaced by ANSI X9.63 in 2001^[3] and ANSI FRP256V1 in 2011. The National Institute of Standard and Technology (NIST) defined their own curves in the NIST FIPS 186-2 in 2000^[4]. In the same year the Certicom published the widely-used Certicom SEC2 curves ^[5] which have been continously updated in version 2 ^[6]. In 2005 NIST published the NSA Suite B^[7] and the Federal Office for Information Security in Germany proposed their own randomly generated curves in the same year^[8].

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}

Edward curves

Applications of Elliptic Curve Cryptography

Example: Elliptic Curve Diffie Hellman Key Exchange (ECDH)

Is a key establishment protocol that allows two parties which know the common domain parameter of a 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(p,a,b,G,n,h) } to calculate a common shared secret over an insecure channel. Assuming Alice and Bob like to establish a common shard secret for communication, both need to generate a keypair. A keypair consists of a private/secret key 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_i} and a public key 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_i} . For the private key 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_i} a integer less than 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 n} is randomly selected, then both need to calculate their public key with 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_i=d_i \cdot G} , so that Alice has a pair 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 (d_A,Q_A)} . She sends her public key 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_A} to Bob and he sends back his public key 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_B} . Now both are able to calculate the shared secret, Alice computes 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_{AB}=Q_B\cdot d_A} and Bob 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_{BA}=Q_A \cdot d_B} . This works because 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_{AB}=Q_B \cdot d_A=(d_B \cdot G) \cdot d_A=(d_A \cdot G) \cdot d_B=K_{BA}} .

Online resources

References

↑ ^1.0 ^1.1 Hankerson, D., A. Menezes and S. Vanstome: Guide to Elliptic Curve Cryptographie. Springer Verlag New York, Inc., 1. Auflage, 2004.
↑ Accredited Standards Committee X9. "American National Standard X9.62-1999, Public key cryptography for the financial services industry: the elliptic curve digital signature algorithm (ECDSA)." 1999.
↑ Accredited Standards Committee X9. "American National Standard X9.63-2001, Public key cryptography for the financial services industry: key agreement and key transport using elliptic curve cryptography." 1999.
↑ National Institute for Standards and Technology. "Digital signature standard." Federal Information Processing Standards Publication 186-2. 2000. [1]
↑ Certicom Research. "SEC 2: Recommended Elliptic Curve Domain Parameters, Version 1.0." September 20, 2000. Local copy of http://www.secg.org/SEC2-Ver-1.0.pdf, which keeps moving
↑ Certicom Research. "SEC 2: Recommended Elliptic Curve Domain Parameters, Version 2.0." January 27, 2010. Local copy of [2], which keeps moving.
↑ Committee on National Security Systems. "National information assurance policy on the use of public standards for the secure sharing of information among national security systems." 1 October 2012.
↑ ECC Brainpool. "ECC Brainpool standard curves and curve generation." October 2005. https://tools.ietf.org/html/rfc5639

[HMV-1] 1.0 ^1.1 Hankerson, D., A. Menezes and S. Vanstome: Guide to Elliptic Curve Cryptographie. Springer Verlag New York, Inc., 1. Auflage, 2004.

[ANSI-X9.62-2] Accredited Standards Committee X9. "American National Standard X9.62-1999, Public key cryptography for the financial services industry: the elliptic curve digital signature algorithm (ECDSA)." 1999.

[ANSI-X9.63-3] Accredited Standards Committee X9. "American National Standard X9.63-2001, Public key cryptography for the financial services industry: key agreement and key transport using elliptic curve cryptography." 1999.

[NIST_186-2-4] National Institute for Standards and Technology. "Digital signature standard." Federal Information Processing Standards Publication 186-2. 2000. [1]

[SEC2-v1-5] Certicom Research. "SEC 2: Recommended Elliptic Curve Domain Parameters, Version 1.0." September 20, 2000. Local copy of http://www.secg.org/SEC2-Ver-1.0.pdf, which keeps moving

[SEC2-v2-6] Certicom Research. "SEC 2: Recommended Elliptic Curve Domain Parameters, Version 2.0." January 27, 2010. Local copy of [2], which keeps moving.

[NIST_Suite_B-7] Committee on National Security Systems. "National information assurance policy on the use of public standards for the secure sharing of information among national security systems." 1 October 2012.

[Brainpool-8] ECC Brainpool. "ECC Brainpool standard curves and curve generation." October 2005. https://tools.ietf.org/html/rfc5639

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

@@ Line 112: / Line 112: @@
 . The y-coordinate of the point of the second intersection with the elliptic curve <math>y_3</math> can be calculated by inserting the point coordinates in the equation of the tangent and multiply by <math>(-1)</math> to get the inverse point on the y axis.
-<math>y_3=(-1)kx_3+d= (-1)\bigg(\frac{3x_1^2+a}{2y_1} \cdot x_3 + y_1-\frac{3x_1^2+a}{2y_1}\cdot x_1 \bigg)=\bigg(\frac{3  x_1^2+a}{2  y_1}\bigg)(x_1-x_3)-y_1 </math>
+<math>y_3=(-1)(kx_3+d)= (-1)\bigg(\frac{3x_1^2+a}{2y_1} \cdot x_3 + y_1-\frac{3x_1^2+a}{2y_1}\cdot x_1 \bigg)=\bigg(\frac{3  x_1^2+a}{2  y_1}\bigg)(x_1-x_3)-y_1 </math>
+. <math>y_3</math> is achieved by inserting
 </div>
 </div>

Difference between revisions of "Elliptic Curve Cryptography"

Revision as of 12:41, 30 March 2020

Contents

Summary

Elliptic Curve Cryptography