Difference between revisions of "Elliptic Curve Cryptography"
(Add references section; Remove Todo (cite extension)) |
(Fix <math> elements; remove TOD (install math extension)) |
||
Line 17: | Line 17: | ||
* Simple Weierstrass form curve equation: | * Simple Weierstrass form curve equation: | ||
<math>y^2 = x^3 + ax + b</math> | |||
<math> | |||
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 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, | The curve needs to be smooth, which means that it will not contain any singularities such as a cusp or a self intersection, | ||
Line 29: | Line 28: | ||
Another characteristic we need to introduce is the point at infinity denoted by 0 (also known as ideal point), which can be thought as identity element infinitly raised on the y axis. | Another characteristic we need to introduce is the point at infinity denoted by 0 (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 | Therefore our points on the elliptic curve over R² all fulfill this equation | ||
<math>\{(x,y) | <math>\{(x,y) \in R^2 | y^2=x^3+ax+b, 4a^3+27b^2 \neq 0\} \cup \{0\}</math> | ||
and can be presented by: | and can be presented by: | ||
Line 40: | Line 39: | ||
According to the group law all points support following operations: | According to the group law all points support following operations: | ||
* Point addition: <math> P+Q=R</math> | * Point addition: <math> P+Q=R</math> | ||
* Point doubling: <math> P=Q - 2P=R< | * Point doubling: <math>P=Q - 2P=R</math> | ||
TODO:Need to install link target extension: https://www.mediawiki.org/wiki/Extension:LinkTarget | TODO:Need to install link target extension: https://www.mediawiki.org/wiki/Extension:LinkTarget | ||
Line 90: | Line 89: | ||
=== Algebraic group of points === | === Algebraic group of points === | ||
The points further comply associative and commutative algebraic group laws and the handling of the neutral element: | The points further comply associative and commutative algebraic group laws and the handling of the neutral element: | ||
** closure: <math>P+Q=R \forall P,Q,R \in E< | ** closure: <math>P+Q=R \forall P,Q,R \in E</math>b | ||
** associative: <math>P+0=0+P \forall P \in E< | ** associative: <math>P+0=0+P \forall P \in E</math> | ||
** identity element and inverse that: <math>P+(-P) = 0 \forall P \in E< | ** identity element and inverse that: <math>P+(-P) = 0 \forall P \in E</math> | ||
** cummutative: <math>P+(Q+R)=(P+Q)+R \forall P,Q,R \in E< | ** cummutative: <math>P+(Q+R)=(P+Q)+R \forall P,Q,R \in E</math> | ||
The inverse point of a point P(x,y) is therfore P(x,-y). | The inverse point of a point P(x,y) is therfore P(x,-y). | ||
Line 112: | Line 111: | ||
Curve25519 is a highly optimized curve proposed by Daniel J. Bernstein (djb) in 2005. | Curve25519 is a highly optimized curve proposed by Daniel J. Bernstein (djb) in 2005. | ||
The curve equation is | The curve equation is | ||
<math>y^2=x^3+486662x^2+x< | <math>y^2=x^3+486662x^2+x</math> over a prime field <math>2^{255}-19</math> | ||
=== Edward curves=== | === Edward curves=== | ||
== Applications Example Elliptic curve Diffie Hellman key exchange == | == Applications Example Elliptic curve Diffie Hellman key exchange == |
Revision as of 14:23, 21 February 2019
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:
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:
Another characteristic we need to introduce is the point at infinity denoted by 0 (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 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:
- Point doubling:
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
Given the elliptic curve and the points and , we can caculate the coordinates of the point as follows. 1. Calculation of
- We know the equation from the line
- Therfore
and we can find the intersection with the y-axis and achieve d .
- we can find by insertion in the line equation:
2. Calculation of
- Now we insert the values of the line equation into the elliptic curve equation:
- The cross points can be searched by
- Now we can conclude from the second term
- and achieve a solution for by:
Algebraic group of points
The points further comply associative and commutative algebraic group laws and the handling of the neutral element:
- closure: b
- associative:
- identity element and inverse that:
- cummutative:
The inverse point of a point P(x,y) is therfore P(x,-y).
Scalar Multiplication
Double and Add algorithm
Calculation in projective coordinates
Side Channel Attacks
Montgomery ladder
Standardization of elliptic curves
Curve25519
Curve25519 is a highly optimized curve proposed by Daniel J. Bernstein (djb) in 2005. The curve equation is over a prime field
Edward curves
Applications Example Elliptic curve Diffie Hellman key exchange
References
- ↑ Hankerson, D., A. Menezes and S. Vanstome: Guide to Elliptic Curve Cryptographie. Springer Verlag New York, Inc., 1. Auflage, 2004.