Elliptic Curve Cryptography

The OpenSSL EC library provides support for Elliptic Curve Cryptography (ECC). It is the basis for the OpenSSL implementation of the Elliptic Curve Digital Signature Algorithm (ECDSA) and Elliptic Curve Diffie-Hellman (ECDH).

What is an Elliptic Curve?

First of all some terminology. We need to define what is meant by a field. In essence a field is a set of elements with operations defined for the elements of that set that equate to something like addition, substraction, multiplication and division. The elements could be numbers, or they could be something else entirely. In order to be a field the following conditions also have to be met:

• Both addition and multiplicaiton are closed over the set, so for example if a and b are in the set then so are a + b and a * b
• Addition and multiplication must be associative: so a + (b + c) = (a + b) + c and similarly for multiplication
• Addition and multiplication must be commutative: so a + b = b + a and similarly for multiplication
• Both addition and multiplication must have identity elements. So, for example 0 and 1 where: a + 0 = a, and a * 1 = a
• There must be additive and multiplicative inverses for all elements in the set. So, for example, for every element a in the set there is also a -a so that a + (-a) = 0 (where 0 is the identity element for addition). Similarly for multiplication.
• Multiplication distributes over addition. So if a, b and c are in the set then a * (b + c) = (a * b) + (a * c)

A finite field is simply a field where the set has a finite number of elements. So, for example, the set of all integers could not be used as the basis for a finite field because there are an infinite number of them. However the set of integers from 1 to 100 could form the basis of a finite field.

So now we can define what an Elliptic Curve is. In general an Elliptic Curve is one of the form: y² = x³ + ax + b, where x, y, a, b and c are elements of some Field

In Elliptic Curve Cryptography we further restrict this such that x, y, a, b and c are elements of a finite field.

Contrary to its name Elliptic Curves do not form an ellipse!

Ok, so far so good - but now it gets a bit more complicated! As well as the points on our curve we add an additional "special" point known as infinity. Using this set of points (i.e. all the points on the curve and infinity), we can define some operations on this set, which we call Point Addition and Point Multiplication. This actually gives us a new mathematical structure called a group.

Points on a curve are given in terms of their x and y co-ordinates, (x, y). Point Addition is essentially an operation which takes any two given points on a curve and yields a third point which is also on the curve. The maths behind this gets a bit complicated but think of it in these terms. Plot two points on an elliptic curve. Now draw a straight line which goes through both points. That line will intersect the curve at some third point. That third point is the result of the addition operation. Point Doubling is similar and can be thought of as adding a point to itself. Imagine a point on the curve and draw a straight line which is a tangent to the curve at that point. The result of the Point Doubling operation is where that tangent line intersects the curve at some other point.

Point multiplication is the operation of taking a point on the curve and "multiplying" it by some number. In practice this is achieved through repeated addition and doubling operations.

So with our group of points on a curve we can start doing some useful. First of all we pick a point on the curve called the generator (we'll call it g).

Now, we will define:

• g⁰ = infinity
• g¹ = g
• g² = g + g
• g³ = g + g + g
• and so on.

Remember g, g² and g³ are all points on the curve, and + in this context means point addition.

The security of Elliptic Curve Cryptography comes from the fact that given some point on the curve g^x, and knowing g, it is difficult to work out what the value of x is. This is known as the discrete logarithm problem.