Elliptic Curve Cryptography

Cryptography has been used for many centuries now. One of the most well-known and a rather old cryptographic cipher is the Caesar cipher.

There are two main different types of encryption - symmetric encryption, which uses one key to both encrypt and decrypt (e.g. AES), and asymmetric encryption, which uses two different keys (e.g. RSA). These are often called a public and private key, where the private key is not to be disclosed. RSA uses integer factorization cryptography based on algebraic number theory, while elliptic curve cryptography (ECC) uses integer factorization cryptography based on elliptic curves. In this post, we will delve deeper into ECC and discuss an application of it, Elliptic-Curve Diffie-Hellman (ECDH).

Preliminaries

Elliptic Curve Cryptography is a choice for public-key-cryptography, based on elliptic curves over finite fields.

What are elliptic curves?

Let K be a field with characteristic not equal to 2 or 3. Let a, b ∈ K with 4a3 + 27b2 ≠ 0. Then the elliptic curve over K is represented by the Weierstrass equation:

We are interested in the case K = Fp where p is prime. The set of points of such an elliptic curve over K is the collection of ordered pairs (x,y) with coordinates in K and x, y satisfying the equation (1) plus an additional point called the point at infinity or zero point.

Lets have look at an example of a random elliptic curve in the following Figure.

An elliptic curve E has the crucial property that we can define as the addition of two points on the elliptic curve so that we obtain a third point also being on the curve. This happens in the following way: Let P and Q be Points on E. To add these two points together, we pass a line through them. Through reflection of the intersection of the line with E, we get a third point R = (P+Q). The idea behind the described group operation is that the three points P, Q, -R lie on a common line with the same slope and the points, which are the reflection of each other over the z-axis are considered to add up to be zero (see the previous Figure). EC addition is described very nicely in the original Lenstra paper "Factoring integers with elliptic curves". A very nice tool to experiment with the mathematical properties of elliptic curves can also be found here. With the addition of two points we can define the multiplication kP with k a positive integer and P a point obtained through add P k times to itself, as example 2P = P + P.

Note that there are a multitude of curves available, and picking one can make a difference. Some of the published curves include Curve25519, Curve448, P-256, P-384, and P-521, with P-256 being the most popular one, followed by Curve25519 (which promises to be faster than P-256). There is also the major difference that Curve25519 (and its selection of parameters) is documented openly, while P-256, which is published by NIST, is not. This is likely one of the reasons that SSH has adopted Curve25519 as its curve.

But how does Elliptic Curve Cryptography work exactly?

Using the operations defined in the previous paragraph, a key exchange method based on Elliptic Curves can be devised. Specifically, we will take a look at Elliptic-Curve Diffie-Hellman (ECDH) next. Note that, similarly to standard Diffie-Hellman, while ECDH protects against passive attacks such as eavesdropping, it does not protect against active ones such as a Man-in-the-Middle attack. To devise a secure key exchange, additional measures such as authentication are required. Now, the following steps are needed to securely exchange a key between two parties Alice and Bob (with Cathy being an adversary that eavesdrops) without having a pre-shared key:

1. Alice, Bob and Cathy agree on a public elliptic curve and a public fixed curve point G.

2. Alice picks a private random integer α. From now on, α is her private key.

3. Now Alice computes her public key. That is the curve point A = αG. She publishes her public key.

4. Bob picks a private random integer β. β is his private key.

5. Now Bob computes his public key. His public key is the curve point B = βG. He also publishes his public key.

6. Cathy does the same way.

7. Now we suppose Alice wants to send Bob a message.

   1. Alice can simply compute P = αB = α(βG) and uses P as the private key for the conversation.

   2. Bob can simply compute P =βA = β(αG) and uses P as the private key for the conversation.

   3. You see αB = α(βG) = β(αG) = βA, so just Alice and Bob know the private key P for their conversation.

8. Suppose Cathy wants to read the conversation between Alice and Bob.
   She knows the elliptic curve, the point G, the order of G and the public keys A and B from Alice and Bob. What she does not know are the private keys - she would have to compute the private key P to do so.

The Figure below illustrates the steps above and serves as a graphical aid.

The security of this method (against passive attacks) is believed to be adequate for current computers (Haakegard et al.), however, it is also believed that Quantum Computing could render ECC insecure (Roetteler et al.).

Advantages of ECC

For one, key bit length plays an important role - the key lengths of ECC keys are much smaller than the ones of RSA, given the same security level is required. ECC also arguably offers a largely better performance, with ECC-512 (comparable to RSA-15360) being up to 400 times as fast as RSA for both encryption and decryption, as per Lauter.

In summary, ECC is a very interesting method - as a matter of fact, Github uses ECC keys in their documentation examples (e.g. when generating SSH keys) due to its performance.

*Figures are not representative of a product, and were made by the author.

References:
Lenstra, "Factoring integers with elliptic curves"
Lauter, "The advantages of elliptic curve cryptography for wireless security"
"Faktorisierung großer Zahlen"
Haakegard et al., "The Elliptic Curve Diffie-Hellman (ECDH)"
Roetteler et al., "Quantum resource estimates for computing elliptic curve discrete logarithms"