# Elliptic Curve Crypto

A brief review of concepts leading to ECC:

Algebraic Group: A set G with a single binary operator (+) that maps any 2 elements of G to another element of G.  If the + operator is commutative, G is called an Abelian group or a Commutative group.

Algebraic Ring: A set R with a two binary operators (+) and (*) that map any 2 elements of G to another element of R. Every Ring is an Abelian group with respect to (+). If it is Abelian with respect to (*) then it is called a Commutative Ring.

Algebraic Field: A set F with a two binary operators (+) and (*) that map any 2 elements of F to another element of F; where (+) and (*) are both commutative; and where each element of F has an inverse with respect to (*), which is also in F.

Polynomial: A construct consisting of repeated applications of (+) and (*) on elements of a Field (which by definition of a Field returns another element of the Field )

Closed Field: If the roots of every polynomial belong to the Field, it is a Closed Field. The set of Complex numbers form a Closed Field, the set of Integers do not.

Algebraic Finite Field: A Field with finite number of elements. It is not a Closed Field, but satisfies other properties of a Field. The number of elements of the Finite Field is called its order. An example is the modulus field, obtained by modulo division by a prime number P. Note that exponentiation on a finite field generates a distribution of all the numbers in the sequence less than the order – for large values of an exponent it produces an highly irregular distribution. This makes the inverse operation of discrete logarithm a hard problem.

Galois Field: Same as above, a finite Field.

Elliptic-Curve: Arises in calculation of arclength of an ellipse and naturally has a group property, where two elements on the curve map to a third element also on the curve. See here. The EC has an interesting property that allows definition of another set of maps from any two points on the field to a third: EC-additon and EC-scalar-multiplication. This is the group operation on Elliptic curves, a reasonable explanation of why it exists is here. These two operations are defined in more detail- http://www.coindesk.com/math-behind-bitcoin/ . Lets observe that they are distinct from, but dependent on the underlying field properties.

Elliptic-Curve over a Field: The set of points (tuples) belonging to a field F that satisfy an elliptic curve equation (y*y = x*x*x+a*x+b) with the (+) and (*) defined according to the field.  The name elliptic curve arises because this equation comes up when calculating the arclength of the ellipse.

Elliptic-Curve over a Finite Field: Tuples drawn from a Finite Field F, that satisfy the elliptic curve equation (y^2 = x^3+ax+b).

Elliptic-Curve Crypto: Built on the hardness of solving the discrete logarithm problem: Given an elliptic curve E defined over a finite field Fq of order(=size) n, a point P ∈ E(Fq ), and a point Q ∈ E(Fq ), find the integer k ∈ [0,n −1] such that Q = k P. The integer k is called the discrete logarithm of Q to the base P, denoted by k = logP Q. This is asking for an inverse operation

In the Bitcoin implementation, the finite field is a prime modulus field Zp and the EC equation is y^2 = x^3+7.  The “curve” on the finite field is highly discontinuous and an example is shown here.

The cryptol verification software has been used to find bugs in the implementation of a Elliptic Curve Crypto implementations. Implementation errors can dramatically impact security properties of crypto that appears mathematically solid.