# Elliptic curve cryptography

Public key cryptography systems are usually based on the assumption that a particular mathematical operation is easy to do, but difficult to undo unless you know some particular secret. This particular secret that serves as the secret key. A recent development in this field is the so-called elliptic curve cryptography.

Elliptic curve cryptography works with points on a curve. The security of this type of public key cryptography depends on the elliptic curve discrete logarithm problem.

## Introduction

Elliptic curve cryptography was invented by Neil Koblitz in 1987 and by Victor Miller in 1986. The principles of elliptic curve cryptography can be used to adapt many cryptographic algorithms, such as Diffie-Hellman or ElGamal. Although no general patent on elliptic curve cryptography appears to exist, there are several patents that may be relevant depending on the implementation (US 5,159,632, US 5,271,061, US 5,463,690 and US 6,141,420).

The main advantage of elliptic curve cryptography is that the keys can be much smaller. Recommended key sizes are in the order of 160 bits rather than 1024 bits for RSA.

## Elliptic curves

An elliptic curve is a set of points (x, y), for which it is true that

^{2}= x

^{3}+ ax + b

given certain chosen numbers a and b. Typically the numbers are
integers (whole numbers), although in principle the system also works
with real (fractional) numbers. Despite what the name
suggests, the curves do not have an elliptic shape. For example, a = -4 and
b = 0.67 gives the elliptic curve with equation
y^{2} = x^{3} - 4x + 0.67.
This curve is illustrated in the following figure.

If x^{3} + ax + b contains no repeated factors,
or equivalently if 4a^{3} +
27b^{2} is not 0, then the elliptic curve can be used to form a
group. A group is simply a set of points on the curve. Because it is a group,
it is possible to "add up" points which gives another point on the
curve. On the graph, two points are added up by drawing a line through
both and taking as the outcome where the line intersects the curve.

For cryptographic purposes, an elliptic curve must have only points with all coordinates whole numbers (integers) in the group.

The trick with elliptic curve cryptography is that if you have a point F on the curve, all multiples of this point are also on the curve.

## Generating an elliptic curve public key

Alice and Bob agree on an elliptic curve and pick a certain point F
on this curve. They can do this with Eve listening in. Alice next
picks a random number A_{S} (which does not have
to be a point on on the curve) and
computes A_{P} = A_{S}*F. The
point A_{P} is on the curve, because it is a
multiple of F. This is easy to compute.

Alice's public key is A_{P} and her secret
key is A_{S}. Bob does the same thing and ends
up with B_{P} and B_{S}.

## Encrypting and decrypting messages

Alice and Bob can now secretly agree on a key with which they can encrypt messages using secret key cryptography. The key simply is the product of Alice's public key and Bob's secret key (which is the same as the product of Alice's secret key and Bob's public key). It will be clear that Alice and Bob can compute this product after they have exchanged their public keys, but Eve cannot since she has none of the secret keys.

## Cracking the elliptic curve key

If Eve wanted to crack the key, she would have to reconstruct
one of the secret keys. This means having to compute
A_{S} given A_{P} and F
(because A_{P} = A_{S} * F).
And that is very difficult.

The number of discrete points on the curve (points with both X and
Y coordinates being integers) is called the order of the curve. If
the order of the point F is a prime number of n bits, then computing
A_{S} from A_{S}*F and F
takes roughly 2^{n/2} operations.
If F is, say, 160 bits long, then Eve needs about
2^{80} operations. If
she can do a billion operations per second, this takes about 38
million years.

This problem is commonly referred to as the elliptic curve discrete logarithm problem.