Elliptic Curve Cryptography

From OpenSSLWiki
Revision as of 12:32, 9 August 2013 by Dsamarin (talk | contribs) (Finite fields need an order of some prime power. The set of integers from 1 to 100 has 100 elements which is not a prime power. The set of integers from 0 to 100 has 101 elements which is prime)
Jump to navigationJump to search

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).

Note: This page provides an overview of what ECC is. It also describes the low-level API for working with Elliptic Curves. If all you need is support for normal ECDSA and ECDH operations then you should normally use the high level EVP API. Refer to EVP for a description of the EVP API. Refer to EVP Signing and Verifying for how to perform digital signature operations (including using ECDSA), and EVP Key Derivation for how to derive shared secrets using DH and ECDH.

Why use Elliptic Curves?

The primary advantage of using Elliptic Curve based cryptography is reduced key size and hence speed. Elliptic curve based algorithms use significantly smaller key sizes than their non elliptic curve equivalents. The difference in equivalent key sizes increases dramatically as the key sizes increase. The approximate equivalence in security strength for symmetric algorithms compared to standard asymmetric algorithms and elliptic curve algorithms is shown in the table below.

Symmetric Key Length Standard asymmetric Key Length Elliptic Curve Key Length
80 1024 160
112 2048 224
128 3072 256
192 7680 384
256 15360 512

As can be seen, to get equivalent strength to a 256 bit symmetric key, a standard asymmetric algorithm would have to use an enormous key of 15360 bits. Keys of this size are typically not practical due to the amount of processing power that would be required, and therefore the speed of the operations. However, with elliptic curve algorithms, the equivalent key length is 512 bits, which is entirely practical.

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 0 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.

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 set of points on a curve (plus the special point, infinity) 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. The set of points generated by repeatedly adding g to itself, along with the Point Addition operation together form a mathematical structure known as a group.

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 as defined above, 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 prime field Fp 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 binary field F2m. Elements of a binary field are typically represents as polynomials and not as numbers. So for example an element could be:

x4+x2+1

This can then be expressed as a binary number ({1 0 1 0 1} in this case), where each term represents one bit in the binary representation. Addition of such polynomials is done as normal but with the result of each term reduced modulo 2. So for example:

(x2 + 1) + (x2 + x) = 2x2 + x + 1

Each term is then reduced modulo 2 to give an answer 0x2 + x +1 = x + 1

In binary representation this sum could be expressed as follows:

{1 0 1} + {1 1 0} = {0 1 1}

Note then that addition is just a simple XOR operation.

Multiplication in the binary field is done respective to an irreducible polynomial. Multiplication of polynomials is done in the normal way and the result is then divided by the irreducible polynomial. The remainder is the result of the multiplication. See http://en.wikipedia.org/wiki/Finite_field_arithmetic, for a discussion of binary field arithmetic.

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. prime (Fp) or binary (F2m), the value p for a prime field, the irreducible polynomial for a binary 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 using EC_GROUP_new_by_curve_name. 

 #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". In this example a prime field is being used, and the prime number is provided in the variable p. If a binary field was being created instead then a bit string representing the irreducible polynomial would have been provided in the p variable. For further information on the low level EC functions being used refer to the EC manual pages: 

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();

	/* 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;
}

Working with Keys

Keys for ECDH and ECDSA are represented using an EC_KEY structure in the low level EC API. If you are using the preferred high-level EVP API then this EC_KEY structure will be wrapped in an EVP_PKEY object.

Creating a new EC_KEY is a process of creating a curve as described above, creating a new EC_KEY object, and then setting the key to use the curve using the EC_KEY_set_group function. Alternatively, the creation of the curve and the key can be done in one step as shown below using EC_KEY_new_by_curve_name: 

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

 	EC_KEY *key;
 
	if(NULL == (key = EC_KEY_new_by_curve_name(NID_secp224r1)))
		handleErrors();

At this point the EC_KEY object has been set up and associated with the curve - but it is empty. There is no key data in it. In order to generate new keys for use with the EVP interface see EVP Key and Parameter Generation. To generate them using the low level API this can be done as follows: 

	if(1 != EC_KEY_generate_key(key)) handleErrors();

Note that this operation generates a public and private key pair. Alternatively you may already know either the private key, the public key, or both. Setting the private key and/or public key is done as follows: 

	BIGNUM *prv;
	EC_POINT *pub;

	/* Set up private key in prv */
	/* Set up public key in pub */

	if(1 != EC_KEY_set_private_key(key, prv)) handleErrors();
	if(1 != EC_KEY_set_public_key(key, pub)) handleErrors();

If you set the private key then you must also set the public key. There have been occasional questions on the openssl-users email list from people who only have the private key but do not know the public key. Fortunately calculating the public key is simply a matter of multiplying the private key by the generator for the curve using EC_POINT_mul: 

	if (1 != EC_POINT_mul(curve, pub, prv, NULL, NULL, ctx))
		handleErrors();

Finally, it is possible to convert a low-level EC_KEY object into an EVP_PKEY object using the EVP_PKEY_set1_EC_KEY function described in the manual here: Manual:EVP_PKEY_set1_RSA(3)

Retrieved from "https://wiki.openssl.org/index.php?title=Elliptic_Curve_Cryptography&oldid=1198"