Elliptic Curve Cryptography: An Introduction

The mathematical properties and concepts of elliptic curves are used in asymmetric key exchange cryptography schemes. Common applications include:

• Key agreement for encryption
• Digital signature verification
• Generating pseudo-random numbers for cryptosystems

In this article, we’ll take a deep dive into elliptic curve cryptography. We aim to take a digestible, slightly less academic look that still thoroughly explains this technical topic. For something a little lighter, explore our introduction to cryptography.

What is elliptic curve cryptography?

Elliptic curve cryptography was introduced in 1985 by two scientists, N. Koblitz and V. Miller. They proposed the idea of using points defined by elliptic curves instead of the finite prime fields such that the Discrete Logarithm problem assumption holds, as commonly used in the standard Diffie-Hellman key exchange protocol.

This assumption serves as the fundamental security principle for asymmetric key exchange cryptography methods. The elliptic curve cryptography takes it one step ahead by providing an efficient mathematical approach to compute the necessary cryptographic operations.

Yes, these topics get quite technical — but the underlying mathematical concepts are rather straightforward. This simplicity is precisely what makes elliptic curve-based cryptosystems so efficient for use in securing modern devices that:

• Run on low power
• Have limited memory cycles and processing capacity to spare

Let’s explore how elliptic curve cryptography helps achieve this goal using simple explanations of these underlying concepts.

Reviewing Diffie-Hellman

Let’s first review the generalized Diffie-Hellman key exchange protocol:

1. Alice and Bob agree on public parameters (generator, G, which is a multiplicative group of a finite prime field for a natural Number, N; a direct sum operation, ⊕; and prime modulus, P).
2. Alice chooses secretly and randomly, her private key number, α, where 0<α<N. Alice computes the element g^α of G and sends this number to Bob. 
3. Bob chooses secretly and randomly, his private key number, β, where 0<β<N. Bob computes the element g^β of G and sends this number to Alice.
4. Alice is now able to compute (g^β)^α of G.
5. Bob is now able to compute (g^α)^β of G.

Both Alice and Bob now possess the same group elements such that  (g^β)^α =(g^α)^β of G and so, g^βα=g^αβ of G. Now, an adversary Eve may be intercepting the communications channel. Note that the values α and β are kept private by Alice and Bob. And since G is a large prime order group, there exists no efficient algorithm to compute g^αβ from g, g^α, g^β, which are shared over the public channel.

The computational Diffie Hellman assumption holds: it is hard to compute g^αβ correctly by multiplying g^α, g^β, since mathematically, g^α x g^β= g^(α+β). No efficient algorithm exists to solve this Diffie-Hellman problem.

Concepts that support elliptic curves

Now let’s look at the mathematical concepts behind elliptic curves and how these underlying concepts are exploited to develop a secure implementation of the Diffie Hellman key exchange protocol.

In the steps below, we define the Elliptic Curve Diffie-Hellman key exchange protocol:

1. The group points G can be defined as an elliptic curve over the finite field. The elliptic curve has the equation y² = x³ + ax + b; parameters a and b are agreed as the public parameters. This curve function may generate points G = (X_g,Y_g).
2. Alice chooses a secret and random number key α, and performs a scalar multiplication with the generated points (α*G = A), and sends the resulting points A =  (X_A, Y_A) to Bob.
3. Bob chooses a secret and random number key β, and performs a scalar multiplication with the generated points (β*G = B), and sends the resulting points B =  (X_B, Y_B) to Bob.
4. Alice is now able to compute P = β*a*G.
5. Bob is now able to compute P = a*β*G.

Now, both Alice and Bob possess the same group elements generated using the points (P = βaG = aβG) on the elliptic curve over the finite field. It is not possible for Eve intercepting the communications as a Man-in-the-Middle adversary to compute P using only G, A = α*G and B = β*G. This is because the Diffie-Hellman assumption as discussed earlier, holds. Note that other variations of elliptic curve cryptography exist (other than using the D-H key exchange scheme).

But why use elliptic curves for the generator function G, when any finite cyclic field generator can do the job well enough? Consider the mathematical properties of elliptic curves, and the mathematical functions required to implement the D-H key exchange protocol. The group operations on the elliptic curve can be performed as follows:

• Addition: For any points P and Q on the elliptic curve (generalized), the direct sum operation lies on the reflection of the third intersecting point, R. This is shown in the diagram below:

(Image source @VitalikButerin)

•  Scalar Multiplication: This is computed simply as a repeated addition of the same points. For example, to compute Q = k*P, use the repeated addition Q = P+P+...+P, k-times.

This scalar multiplication is a one-way function, which means that it is possible to find the output of a function given any integer input, but very hard to find the inverse function value that is generated from any random integer. In simple terms, it is easy to find the image from an original input, but hard to invert the image reflection such that it produces the original image.

The elliptic curve is defined as the field of integers modulo prime P. Considering any points P and Q on this curve, Q being some multiple of P, it is find to hard exactly the chosen integer value k such that Q = k*P. This assumption refers to the Elliptic Curve Discrete Logarithm problem and is the fundamental principle behind the Elliptic Curve implementation of the Diffie Hellman key exchange protocol.

Benefits of the elliptic curve

But why use the Elliptic Curve implementation instead of a standard finite cyclic group field for the generator function? You can notice how computing the direct sum and scalar multiplication between two points in the field of the elliptic curve does not have an algebraic structure, and yet, any set of (different) points from this field can be chose such that the Discrete Log security assumption of the D-H algorithm also holds.

This means that in order to achieve the same levels of security, the Elliptic Curve Diffie Hellman cryptography requires much shorter key length. This results in fewer memory cycles and CPU resources consumed to implement the elliptic curve based cryptography key exchange protocol.

For example, a symmetric encryption of 56 bits key size may require 512 bits for the RSA and standard Diffie Hellman implementation (modulus size for bits) and 112 bits for the elliptic curve cryptography. Now for stronger security, the symmetric encryption security worth 256 bits requires 15360 bits key size implementation using the RSA and standard D-H algorithm, but only 512 bits using the elliptic curve DH implementation.

This makes elliptic curve cryptography particularly suitable for efficient cryptographic implementations in mobile devices.