# An introduction to elliptic curve cryptography

October 12, 2012

Editor's note: See the original article on PurpleAlientPlanet.

Some of my research is focused on the implementation issues of elliptic curve cryptography on embedded systems. Since I often have to explain what elliptic curve cryptography exactly is, I decided to write this little introduction on the matter. Maybe this will get the attention of some of my students and can perhaps get them more interested in the mathematical branch of finite fields in algebra.

Introduction
Elliptic curve cryptography (ECC) is a public key cryptography method, which evolved form Diffie Hellman. To understanding how ECC works, lets start by understanding how Diffie Hellman works.

The Diffie Hellman key exchange protocol, and the Digital Signature Algorithm (DSA) which is based on it, is an asymmetric cryptographic systems in general use today. It was discovered by Whitfield Diffie and Martin Hellman in 1976, and uses a problem known as the Discrete Logarithm Problem (DLP) as its asymmetric operation. The DLP concerns finding a logarithm of a number within a finite field arithmetic system.

Prime fields are fields whose sets are prime. In other words, they have a prime number of members. Prime fields turn out to be of great use in asymmetric cryptography since exponentiation over a prime field is relatively easy, while its inverse, computing the logarithm, is difficult. The "Diffie-Hellman Method for Key Agreement" allows two hosts to create and share a secret key. This is done by the following method:

1. First the hosts must get the "Diffie-Hellman parameters": a prime number (larger than 2) and "base", , an integer that is smaller than . They can be hard coded or fetched from a server, depending on the implementation.

2. The hosts each generate a secret private number called , which is less than .

3. Next, the hosts generate the public keys, . They are created with the function:

4. The two host then exchange the public keys () and these exchanged numbers are then converted into a secret key, as follows:

The secret key can at this point be used as the key for a standard encryption method, used to transfer the information between the hosts. Mathematically, the two hosts have generated the same value for the secret key since:

Using the values in the equation above, finding the discrete logarithm problem is finding when only , and are known. As an example, take the situation in which someone has multiplied by itself times, and reduced the result into the field (by performing the modulo operation) as often as needed to keep the result smaller than . In this case, when knowing , and , the problem is trying to find what what value of was used. This turns out to be extraordinarily difficult to do for  large enough values of , where is prime. It is in fact so much more difficult to do than just finding from , and that, even using the world's fastest supercomputer, it would be unfeasible to attempt within a reasonable amount of time.

Mathematically, a proof to this effect is neither known nor thought to be forthcoming. Before wide-scale implementation, it is thus of the utmost importance that an extensive investigation of the true complexity of the problem is done in order to obtain the highest degree of confidence in the security of discrete logarithm based cryptographic systems. Such an investigation is in progress by various researchers around the world.

Elliptic curves
Since the discovery of RSA (and El-Gamal) their ability to withstand attacks has meant that these two cryptographic systems have become widespread in use. They are being used every day both for authentication purposes as well as encryption/decryption. Both systems cover the current security standards--so why invent a new system? Even though ECC is relatively new, the use of elliptic curves as a base for a cryptographic system was independently proposed by By Victor Miller and Neil Koblitz. What makes it stand apart from RSA and El-Gamal is its ability to be more efficient that those two. The reason why this is important are the developments in information technology--most importantly hand held, mobile devices, sensor networks, etc. Somehow, there must be a way to secure communications generated by these devices, however their computing power and memory are not nearly as abundant as on their desktop and laptop counterparts. A contemporary desktop or laptop system has no problems working with 2048 bit keys and higher, but these small embedded devices do since we do not want to spend a lot of their resources and bandwidth securing traffic.

The operations on which RSA are founded are modular exponentiation in integer rings. The security of RSA depends on the difficulty of factoring large integers which can be done in sub-exponential times. For the ECDLP however, only exponential algorithms are known which means we can use shorter keys for security levels where RSA and El-Gamal would need much bigger keys. For example, a 160 bit ECC key and a 1024 bit RSA key offer a similar level of security. To reach the same level of security than a 15360 bit RSA key, one only needs 512 bit ECC key.

Operations on elliptic curves
The security of ECC depends on the difficulty of the Elliptic Curve Discrete Logarithm Problem. This problem is defined as follows: let and be two points on an elliptic curve such that , where is a scalar. Given and , it is computationally unfeasible to obtain , if is sufficiently large. Hence, is the discrete logarithm of to . We can see that the main operation involved in ECC is point multiplication, namely, multiplication of a scalar with any point on the curve to obtain another point on the curve.

This is also the reason a ECC key of 160 bits provides the equivalent protection of a symmetric key of 80 bits, namely because of the methods used to crack . If one knows and , one must guess at least the square root of the number of points on average to find . So if the field size is , one must guess points. With a 80 bit symmetric key, it takes guesses to crack it on average. The table below gives a comparison of equivalent key sizes.

Each curve has a specially designated point called the base point chosen such that a large fraction of the elliptic curve points are multiples of it. To generate a key pair, one selects a random integer which serves as the private key, and computes which serves as the corresponding public key. For cryptographic application the order of , that is the smallest non-negative number such that , with the point at infinity, must be prime.

Point multiplication
In point multiplication a point on the elliptic curve is multiplied with a scalar using elliptic curve equation to obtain another point on the same elliptic curve, giving . Point multiplication can be achieved by two basic elliptic curve operations, namely point addition and point doubling. Point addition is defined as adding two points and to obtain another point written as . Point doubling is defined as adding a point to itself to obtain another point so that .

Point multiplication is hence achieved as follows: let be a point on an elliptic curve. Let be a scalar that is multiplied with the point to obtain another point on the curve so that . If then .

Thus point multiplication uses point addition and point doubling repeatedly to find the result. The above method is called the 'double and add' method for point multiplication. There are other, more efficient methods for point multiplication.

Point addition is the addition of two points and on an elliptic curve to obtain another point on the same elliptic curve. This is demonstrated geometrically in the figure below for the condition that Q \neq -P .

Analytically, we can perform a point addition as follows.

Consider two distinct points and so that and .

Let where . Then

, thus is the slope of the line through and .

If i.e. then where is the point at infinity.
If then then point doubling equations are used.

Also note that the addition is commutative, thus .

Point doubling
Point doubling is the addition of a point on the elliptic curve to itself to obtain another point on the same elliptic curve. To double a point to get , i.e. to find , consider a point on an elliptic curve as shown in the figure below. If the coordinate of the point is not zero then the tangent line at will intersect the elliptic curve at exactly one more point . The reflection of the point with respect to -axis gives the point , which is the result of doubling the point .

Analytically, we can again write this as follows.

Consider a point such that , where .

Let where . Then

x_Q = s^2 2x_P

, where is the tangent at point and is one of the parameters chosen with the elliptic curve.

If y_P = 0 then , where is the point at infinity.

Finite fields
The elliptic curve operations defined in the previous section are on real numbers. Operations over the real numbers are slow and inaccurate due to rounding errors. Cryptographic operations have to be fast and accurate. To make operations on elliptic curve accurate and more efficient, the elliptic curve cryptography is defined over finite fields, also called Galois fields in honor of the founder of finite field theory, Évariste Galois. For example:

• Prime field
• Binary field

The field is chosen with finitely large number of points suited for cryptographic operations. Even though the curve would no longer a gently flowing graph, as shown in the figure below, the algebraic equations for point addition and doubling still apply.

Operations over Prime Field

Let be a prime finite field so that is an odd prime number, and let satisfy . Then an elliptic curve over defined by the parameters consists of the set of solutions or points for to the equation:

Together with the extra point at infinity. The equation is called the defining equation of . For a given point , is called the x-coordinate of , and is called the y-coordinate of .
The prime number is chosen such that there is a finitely large number of points on the elliptic curve to make the cryptosystem secure, usually between 112 and 521 bits.

The number of points on is denoted by . Hasse's Theorem on elliptic curves states that:

It is then possible to define an addition rule to add points on . The addition rule is specified as follows:

Rule to add the point at infinity to itself:

Rule to add the point at infinity to any other point:

Rule to add two points with the same x-coordinates when the points are either distinct or have y-coordinate 0:

This also means that the negative of the point is

Rule to add two points with different x-coordinates: Let and (x_2, y_2) \in E(F_p) be two points such that . Then , where:

Rule to add a point to itself (double a point): Let be a point with . Then , where:

The set of points on forms a group under this addition rule. Furthermore the group is Abelian, meaning that for all points . Notice that the addition rule can always be computed efficiently using simple field arithmetic.

What about scalar multiplication of elliptic curve points? These can be computed efficiently using the addition rule together with the double-and-add algorithm or one of its variants.

Operations on Binary Field

Let be a characteristic 2 finite field, and let satisfy in . Then a (non-supersingular) elliptic curve over defined by the parameters consists of the set of solutions or points for to the equation:

Where together with an extra point at infinity, with the only elliptic curves over of interest being non-supersingular elliptic curves. Here the elements of the finite field are integers of length at most bits. These numbers can be considered as a binary polynomial of degree . In this binary polynomial the coefficients can only be 0 or 1. All the operation such as addition, subtraction, division, multiplication involves polynomials of degree or less.

The number of points on is denoted by . The Hasse Theorem states that:

It is again possible to define an addition rule to add points on as it was done for . The addition rule is specified as follows:

Rule to add the point at infinity to itself:

Rule to add the point at infinity to any other point:

Rule to add two points with the same x-coordinates when the points are either distinct or have x-coordinate 0:

This also means that the negative of the point is

Rule to add two points with different x-coordinates: Let and (x_2, y_2) \in E(F_{2^m}) be two points such that . Then , where:

Rule to add a point to itself (double a point): Let be a point with . Then , where:

The set of points on forms an Abelian group under this addition rule. Notice that the addition rule can always be computed efficiently using simple field arithmetic. As before, scalar multiplication is the process of adding to itself times. The result of this scalar multiplication is denoted and can be computed efficiently using the addition rule together with the double-and-add algorithm or one of its variants.

Besides the curve parameters and , there are other parameters that must be agreed upon by both parties involved. These are called the domain parameters. The domain parameters for both prime fields and binary fields are described below.

Domain parameters for

The domain parameters for elliptic curves over are , , , , and . Here is the prime number defined for the finite field while and are the parameters defining the curve . is the generator point , a point on the elliptic curve chosen for cryptographic operations and is the order of the elliptic curve. The scalar for point multiplication is chosen as a number between 0 and . is the cofactor where .

Domain Parameters for

The domain parameters for elliptic curve over are , , , , , and . is an integer defined for the finite field . The elements of the finite field are integers of length at most bits. is the irreducible polynomial, known as the reduction polynomial, of degree used for elliptic curve operations while and are the parameters defining the curve . is again the generator point and a point on the elliptic curve chosen for cryptographic operations while is the order of the elliptic curve. The scalar for point multiplication is chosen as a number between 0 and . is the cofactor where

Choosing the field
Should we choose a curve over the prime field or the binary field ? This decision has to be made based on the way the system is going to be implemented. While curves over the prime field can be more efficient to implement in software, there are optimisations possible that puts the efficiency of curves over a binary field on par with those over a prime field.

During his professional career, Johan Dams has been involved in many projects around the world in the fields of embedded systems, software engineering and systems and security among others. He is a published researcher working in the fields of cryptography and robotics and has over ten years of experience running software teams. He is a lecturer at the Vaasa University of Applied Sciences in Finland and has been invited to give guest lectures at Universities all over the world on topics such as robotics, cryptography, machine vision and learning, software development, software team management and embedded systems and its applications.

• 10.28.2013

• 10.28.2013

• 10.12.2012