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.

Advertisements

2 thoughts on “Elliptic Curve Crypto

    1. Modulo math is just like Clock math – as the clock hour wraps around from 12 to 1, the number wraps around the modulus number Zp, typically chosen a prime. Interesting to visualize a clock with 13 hours instead of 12 – the remainder does not reveal (leak) the factors of the original number with modulus chosen as prime. Hamilton pure time was all about division and that too by tuples. One can think of a finite group consisting of tuples, Zp X Zq, and use it for crypto.

      Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s