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