Basic explanation of Elliptic Curve Cryptography?

Question

I have been studying Elliptic Curve Cryptography as part of a course based on the book Cryptography and Network Security. The text for provides an excellent theoretical definition of the algorithm but I'm having a hard time understanding all of the theory involved in ECC.

I'm looking for an explanation suitable for someone who has studied at undergraduate level in computer science. Can anyone explain how elliptic curve cryptography works in a simple, straightforward manner?

Answer 1

There are some widely used cryptographic algorithms which need a finite, cyclic group (a finite set of element with a composition law which fulfils a few characteristics), e.g. DSA or Diffie-Hellman. The group must have the following characteristics:

• Group elements must be representable with relatively little memory.
• The group size must be known and be a prime number (or a multiple of a known prime number) of appropriate size (at least 160 bits for the traditional security level of "80-bit security").
• The group law must be easy to compute.
• It shall be hard (i.e. computationally infeasible, up to at least the targeted security level) to solve discrete logarithm in the group.

DSA, DH, ElGamal... were primarily defined in the group of non-zero integers modulo a big prime p, with modular multiplication as group law. The characteristics we look for are reached as long as p is large enough, e.g. at least 1024 bits (that's the minimal size for discrete logarithm to be hard in such a group).

Elliptic curve are another kind of group, appropriate for group-based cryptographic algorithm. An elliptic curve is defined with:

• A finite field, usually consisting in integers modulo some prime p (there are also other fields which can be used).
• A curve equation, usually $y^2 = x^3 + ax +b$, where $a$ and $b$ are constant values from the finite field.

The curve is the set of pairs of values $(x, y)$ which match the equation, along with a conventional extra element called "the point at infinity". Since elliptic curves initially come from a graphical representations (when the field consists in the real numbers $\mathbb{R}$), the curve elements are called "points" and the two values $x$ and $y$ are their "coordinates".

Then we define a group law, called point addition and denoted with a "$+$" sign. The definition looks quite artifical, with all the business about tracing a line and computing the intersection of that line with the curve; but the bottom-line is that it has the characteristics required for a group law, and it is easily computable (there are several methods; as a rough approximation, it costs about 10 multiplications in the base field). The curve order (the number of points on the curve) is close to $p$ (the size of the finite field): the curve order is equal to $p+1-t$ for some integer $t$ such that $|t| \leq 2\sqrt{p}$.

Compared to the traditional multiplicative group modulo a big prime, elliptic curve variants of cryptographic algorithms have the following practical features:

• They are small and fast. There is no known efficient discrete-logarithm solving algorithm for elliptic curves, beyond the generic algorithms which work on every group. So we get appropriate security as soon as $p$ is close to 160 bits. Computing the group law costs ten field operations, but on a field which is 6 times smaller; since multiplications in a finite field have quadratic cost, we end up with an appreciable speedup.
• Creating a new curve is uneasy. Generating a new big prime is a matter of a fraction of a second with a basic PC, but making a new curve is much more expensive (the hard part is figuring out the curve order). Since there is no security issue in using the same group for several distinct key pairs, it is customary, with elliptic curves, to rely on a handful of standard curves which have been created such that their order is appropriate (a big prime value or a multiple of a big enough prime value); see FIPS 186-3. The implementations are thus specialized and optimized for these particular curves, which again considerably speeds things up.
• Elliptic curves can be used to factor integers. Lenstra's elliptic curve factorization method can find some factors in big integers with a devious use of elliptic curves. This is not the best known factorization algorithm, except when it comes to finding medium-sized factors in a big non-prime integer.
• Some elliptic curves allow for pairings. A pairing is a bilinear operation which can link elements from two groups into elements of a third group. A pairing for cryptography requires all three groups to be "appropriate" (in particular with a hard-to-solve discrete logarithm). Pairings are an active research subject because they can be used to implement protocols with three participants (e.g. in electronic cash systems, with the buyer, the vendor and the bank, all mathematically involved in the system). The only known practical pairings for cryptography use some special elliptic curves.

Elliptic curves are usually said to be the next generation of cryptographic algorithms, in order to replace RSA. Performance of EC computations is the main interest of these algorithms, especially on small embedded systems such as smartcards (in particular Koblitz curves over binary fields); the biggest remaining issue is that public-key operations with group-based algorithms are a bit slow (RSA signature verification or asymmetric encryption, as opposed to signature generation and asymmetric decryption, respectively, is extremely fast, whereas analogous operations in the group-based algorithms are just fast). Also, involved mathematics are a bit harder than with RSA, and there have been patents, so implementers are a bit wary. Yet elliptic curves become more and more common.

Answer 2

Once upon a time, in a land far, far away, there lived two men by the name of Neal Koblitz and Victor S. Miller. They didn't know each other, however, in 1985 they both suggested using elliptical curves over finite fields for encrypting/decrypting data.

Seriously, though, the following explanation requires that you have a basic understanding of finite fields. Most of it is taken from the Wiki links suggested by D.W.

Elliptic curve cryptography (ECC) is an approach to public-key cryptography based on the algebraic structure of elliptic curves over finite fields.

Public-key cryptography is based on the intractability of certain mathematical problems. Early public-key systems, such as the RSA algorithm, are secure assuming that it is difficult to factor a large integer composed of two or more large prime factors.

For elliptic-curve-based protocols, it is assumed that finding the discrete logarithm of a random elliptic curve element with respect to a publicly-known base point is infeasible. The size of the elliptic curve determines the difficulty of the problem. It is believed that the same level of security afforded by an RSA-based system with a large modulus can be achieved with a much smaller elliptic curve group. Using a small group reduces storage and transmission requirements.

For current cryptographic purposes, an elliptic curve is a plane curve which consists of the points satisfying the equation

$y^2 = x^3 + ax + b$,

along with a distinguished point at infinity. (The coordinates here are to be chosen from a fixed finite field of characteristic not equal to 2 or 3, or the curve equation will be somewhat more complicated.) This set together with the group operation of the elliptic group theory form an Abelian group, with the point at infinity as identity element. The structure of the group is inherited from the divisor group of the underlying algebraic variety.

How it works depends on the cryptographic scheme you apply it to. As an example, it can be applied it to the Diffie-Hellman key exchange, which is commonly known as the Elliptic Curve Diffie-Hellman (ECDH) key agreement protocol.

Suppose Alice wants to establish a shared key with Bob, but the only channel available for them may be eavesdropped by a third party. Initially, the domain parameters (that is, $(p,a,b,G,n,h)$ in the prime case or $(m,f(x),a,b,G,n,h)$ in the binary case) must be agreed upon. Also, each party must have a key pair suitable for elliptic curve cryptography, consisting of a private key d (a randomly selected integer in the interval $[1,n − 1]$) and a public key $Q$ (where $Q = dG$). Let Alice's key pair be $(d_A,Q_A)$ and Bob's key pair be $(d_B,Q_B)$. Each party must have the other party's public key (an exchange must occur).

Alice computes $(x_k,y_k) = d_AQ_B$. Bob computes $k = d_BQ_A$. The shared key is $x_k$ (the $x$ coordinate of the point).

The number calculated by both parties is equal, because $d_AQ_B = d_Ad_BG = d_Bd_AG = d_BQ_A$.

The protocol is secure because nothing is disclosed (except for the public keys, which are not secret), and no party can derive the private key of the other unless it can solve the Elliptic Curve Discrete Logarithm Problem.

Answer 3

I recommend that you start by reading the description of elliptic curve cryptography in Wikipedia, and then let us know what you'd like to know: What didn't you understand? What didn't it cover that you'd like to know about?

The one-sentence version is that elliptic curve cryptography is a form of public-key cryptography that is more efficient than most of its competitors (e.g., RSA).

For every public-key cryptosystem you already know of, there are alternatives based upon elliptic curve cryptography (ECC). The ECC schemes are probably faster. Consequently, ECC is particularly appropriate for embedded devices and other systems where performance is at a premium. On the other hand, ECC is newer than some other well-known alternatives, and there is a bit of a patent minefield surrounding some kinds of elliptic-curve cryptography, so ECC hasn't seen as much deployment as classic RSA/DSA/El Gamal -- but ECC is used in the wild in some systems.

Answer 4

I wanted to add a couple of very handy references.

Firstly, there is the self-acclaimed elliptic curve crypto blog (not mine, no self plugging today). But the exact page that I linked you to happens to have a large list of references to learn about crypto and, in particular, elliptic curve cryptography (including the book written by my current graduate advisor, which I haven't actually read).

But one of them, which has a few good quick overview parts is Smart's Cryptography, available free here (and legal, by the way - distributed by the author himself).