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:

• 0g = infinity
• 1g = g
• 2g = g + g
• 3g = g + g + g (or 2g + g)
• and so on.

Remember g, 2g and 3g are all points on the curve, and + in this context means point addition as defined above. If you keep going in this way you will eventually come to some number (lets call it n), such that ng = infinity. If you are lucky then you may have chosen a curve and a g, such that continually adding g to itself will eventually visit all of the possible points on the curve - but often this is not the case. The number n is called the order of g. For various complicated mathematical reasons it also turns out that the total number of points that exist on the curve is divisble by n. Dividing the total number of points by n gives you another number known as the cofactor.

The security of Elliptic Curve Cryptography comes from the fact that given some point on the curve kg, (where k is a number and g is the known generator point), it is difficult to work out what the value of k is. This is known as the discrete logarithm problem. In the Elliptic Curve Cryptography algorithms ECDH and ECDSA, the point kg would be a public key, and the number k would be the private key.

Types of Field

In principle there are many different types of field that could be used for the values x and y of a point (x, y). In practice however there are two primary ones used, and these are the two that are supported by the OpenSSL EC library.

The simplest is typically referred to as the field F_p where p is a prime number. In cryptographic applications p must be a very large prime number. The elements of the set are simply the numbers 0 through to p-1, and addition and multiplication over the field have the normal meaning for modular (or clock) arithmetic. So, if p=7 then the elements of the set are {0, 1, 2, 3, 4, 5, 6} and:

0 + 1 = 1

2 + 3 = 5

3 + 3 = 6

4 + 3 = 0

5 + 4 = 2

and so on.

The next common type of field is referred to as the field F_2^m

DESCRIPTION OF F2M FIELDS HERE.

Defining Curves

The parameters necessary for performing cryptographic operations for ECDH and ECDSA are simply the parameters required to set up the curve. Namely: the type of field (e.g. F_p or F_2^m), the value p or m for the field, the values a and b from the curve equation, the generator point (g), the order and the cofactor.

Fortunately unless you are defining a new curve (not recommended unless you know what you are doing), or you are using an unusual curve that OpenSSL does not have support for, you can usually utilise one of the named curves that are built-in to OpenSSL. These are a set of well known and widely used curves. The complete collection of curve parameters can be set in one go simply by selecting the appropriate named curve.

 #include <openssl/obj_mac.h>
 #include <openssl/ec.h>
 ...

 	EC_GROUP *curve;
 
	if(NULL == (curve = EC_GROUP_new_by_curve_name(NID_secp224r1)))
		handleErrors();

If a custom curve needs to be created, then it can be done as follows. This example code creates the same curve as the code above, but creates it "manually":

EC_GROUP *create_curve(void)
{
	BN_CTX *ctx;
	EC_GROUP *curve;
	BIGNUM *a, *b, *p, *order, *x, *y;
	EC_POINT *generator;

	/* Binary data for the curve parameters */
	unsigned char a_bin[28] =
		{0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
		0xFF,0xFF,0xFF,0xFF,0xFF,0xFE,0xFF,0xFF,0xFF,0xFF,
		0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFE};
	unsigned char b_bin[28] =
		{0xB4,0x05,0x0A,0x85,0x0C,0x04,0xB3,0xAB,0xF5,0x41,
		0x32,0x56,0x50,0x44,0xB0,0xB7,0xD7,0xBF,0xD8,0xBA,
		0x27,0x0B,0x39,0x43,0x23,0x55,0xFF,0xB4};
	unsigned char p_bin[28] =
		{0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
		0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0x00,0x00,0x00,0x00,
		0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x01};
	unsigned char order_bin[28] =
		{0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
		0xFF,0xFF,0xFF,0xFF,0x16,0xA2,0xE0,0xB8,0xF0,0x3E,
		0x13,0xDD,0x29,0x45,0x5C,0x5C,0x2A,0x3D };
	unsigned char x_bin[28] =
		{0xB7,0x0E,0x0C,0xBD,0x6B,0xB4,0xBF,0x7F,0x32,0x13,
		0x90,0xB9,0x4A,0x03,0xC1,0xD3,0x56,0xC2,0x11,0x22,
		0x34,0x32,0x80,0xD6,0x11,0x5C,0x1D,0x21};
	unsigned char y_bin[28] =
		{0xbd,0x37,0x63,0x88,0xb5,0xf7,0x23,0xfb,0x4c,0x22,
		0xdf,0xe6,0xcd,0x43,0x75,0xa0,0x5a,0x07,0x47,0x64,
		0x44,0xd5,0x81,0x99,0x85,0x00,0x7e,0x34};

	/* Set up the BN_CTX */
	if(NULL == (ctx = BN_CTX_new())) handleErrors();

	/* Create the BIGNUMs for the various parameters */
	if(NULL == (a = BN_new())) handleErrors();
	if(NULL == (b = BN_new())) handleErrors();
	if(NULL == (p = BN_new())) handleErrors();
	if(NULL == (order = BN_new())) handleErrors();
	if(NULL == (x = BN_new())) handleErrors();
	if(NULL == (y = BN_new())) handleErrors();

	/* Set the values for the various parameters */
	if(NULL == (a = BN_bin2bn(a_bin, 28, NULL))) handleErrors();
	if(NULL == (b = BN_bin2bn(b_bin, 28, NULL))) handleErrors();
	if(NULL == (p = BN_bin2bn(p_bin, 28, NULL))) handleErrors();
	if(NULL == (order = BN_bin2bn(order_bin, 28, NULL))) handleErrors();
	if(NULL == (x = BN_bin2bn(x_bin, 28, NULL))) handleErrors();
	if(NULL == (y = BN_bin2bn(y_bin, 28, NULL))) handleErrors();

	/* Create the curve */
	if(NULL == (curve = EC_GROUP_new_curve_GFp(p, a, b, ctx))) handleErrors();

	/* Create the generator */
	if(NULL == (generator = EC_POINT_new(curve))) handleErrors();
	if(1 != EC_POINT_set_affine_coordinates_GFp(curve, generator, x, y, ctx))
		handleErrors();

	/* Set the generator and the order */
	if(1 != EC_GROUP_set_generator(curve, generator, order, NULL))
		handleErrors();

	EC_POINT_free(generator);
	BN_free(y);
	BN_free(x);
	BN_free(order);
	BN_free(p);
	BN_free(b);
	BN_free(a);
	BN_CTX_free(ctx);

	return curve;
}