An introduction to elliptic curve cryptography

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 $ p $ (larger than 2) and “base”, $ g $ , an integer that is smaller than $ p $ . They can be hard coded or fetched from a server, depending on the implementation.

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

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

$y = g^x bmod{p}$

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

$z = y^x bmod{p}$

The secret key $ z $ 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 $ z $ since:

$z = (g^x bmod{p})^{xprime} bmod{p} = (g^{xprime} bmod{p})^x bmod{p}$

Using the values in the equation above, finding the discrete logarithm problem is finding $ x $ when only $ y $ , $ g $ and $ p $ are known. As an example, take the situation in which someone has multiplied $ g $ by itself $ x $ times, and reduced the result into the field (by performing the modulo operation) as often as needed to keep the result smaller than $ p $ . In this case, when knowing $ y $ , $ g $ and $ p $ , the problem is trying to find what what value of $ x $ was used. This turns out to be extraordinarily difficult to do for large enough values of $ p $ , where $ p $ is prime. It is in fact so much more difficult to do than just finding $ y $ from $ g $ , $ x $ and $ p $ 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 $ P $ and $ Q $ be two points on an elliptic curve such that , where $ k $ is a scalar. Given $ P $ and $ Q $ , it is computationally unfeasible to obtain $ k $ , if $ k $ is sufficiently large. Hence, $ k $ is the discrete logarithm of $ Q $ to $ P $ . We can see that the main operation involved in ECC is point multiplication, namely, multiplication of a scalar $ k $ with any point $ P $ on the curve to obtain another point $ Q $ 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 $ P $ and $ Q $ , one must guess at least the square root of the number of points on average to find $ k $ . So if the field size is $ 2^n $ , one must guess $2^{(n/2)}$ points. With a 80 bit symmetric key, it takes $2^{79}$ guesses to crack it on average. The table below gives a comparison of equivalent key sizes.

Each curve has a specially designated point $ G $ 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 $ k $ which serves as the private key, and computes $ kG $ which serves as the corresponding public key. For cryptographic application the order of $ G $ , that is the smallest non-negative number $ n $ such that , with $ O $ the point at infinity, must be prime.

Point multiplication
In point multiplication a point $ P $ on the elliptic curve is multiplied with a scalar $ k $ using elliptic curve equation to obtain another point $ Q $ 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 $ P $ and $ Q $ to obtain another point $ R $ written as . Point doubling is defined as adding a point $ P $ to itself to obtain another point $ Q $ so that .

Point multiplication is hence achieved as follows: let $ P $ be a point on an elliptic curve. Let $ k $ be a scalar that is multiplied with the point $ P $ to obtain another point $ Q $ 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
Point addition is the addition of two points $ P $ and $ Q $ on an elliptic curve to obtain another point $ R $ 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 $ P $ and $ Q $ so that and .

Let where . Then

, thus $ s $ is the slope of the line through $ P $ and $ Q $ .

If i.e. then where $ O $ 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 $ P $ on the elliptic curve to itself to obtain another point $ Q $ on the same elliptic curve. To double a point $ P $ to get $ Q $ , i.e. to find , consider a point $ P $ on an elliptic curve as shown in the figure below. If the $ y $ coordinate of the point $ P $ is not zero then the tangent line at $ P $ will intersect the elliptic curve at exactly one more point $ -Q $ . The reflection of the point $ -Q $ with respect to $ x $ -axis gives the point $ Q $ , which is the result of doubling the point $ P $ .

Analytically, we can again write this as follows.

Consider a point $ P $ such that , where .

Let where . Then

x_Q = s^2 2x_P

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

If y_P = 0 then , where $ O $ 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 $ F_p $ be a prime finite field so that $ p $ is an odd prime number, and let satisfy $4a^3 + 27b^2 pmod{p} neq 0$ . Then an elliptic curve over $ F_p $ defined by the parameters consists of the set of solutions or points for to the equation: