Asymmetric Cryptography – Elliptic Curve Cryptography

In the previous parts of this blog series I introduced the general principle of asymmetric cryptography and explained how one can use the Diffie-Hellman Key Exchange to establish a shared secret among multiple parties over an unsecure channel. In this blog I will introduce you to Elliptic Curve Cryptography (ECC), which allows using shorter keys than, for example, the DH key exchange or the RSA cryptosystem.

Elliptic Curves

An elliptic curve is a collection of points space that satisfy the equation y² = x³ + ax² + bx + c^1,2. For most practical uses a depressed cubic curve is sufficient, which means that a = 0 and therefore y² = x³ + ax + b (using reassigned coefficients). If we choose a = -1 and b = 1, the curve will look like this:

Fig. 1: y² = x³ – x + 1

Preparation

To use the elliptic curves for asymmetric cryptography in a way similar to the DH key exchange, we will need to define an Abelian group that is based on the curve. To do this as a first step there needs to be a group operation *. For elliptic curves this operation is called addition and behaves as follows:

1. To add two distinct points P₁ = (x₁,y₂) and P₂ = (x₂,y₂), connect the points in a straight line and draw that line further until it intersects the curve again in a point P₃. Mirror this point on the x-axis and you get the result of P₁+P₂. Thus R = (x_r,y_r) = (δ – x₁ – x₂, δ(x₁ – x_r) – y₁) while δ = (y₂ – y₁)/(x₂ – x₁).
   

   Fig. 2: Adding two distinct points

2. To add a point to itself one cannot connect the two addends. Instead you just use the tangent on the curve in that point and thus get to P₃. The rest works the same as in 1, therefore R = (x_r,y_r) = (δ – x₁ – x₂, δ(x₁ – x_r) – y₁) while δ = (3x₁² + b)/2y₁.
   

   Fig. 3: Adding point to self

3. Connecting two points where x₁ = x₂ will only intersect the curve a third time at infinity. Therefore we introduce the point (∞,∞) and add it to the group as the identity element.
   

   Fig. 4: Adding two points vertically

It is easy to see, that this leads to the satisfaction of four out of five requirements of an Abelian group³.

For the same reason as in the “normal” Diffie-Hellman algorithm, we do not want to have an infinite amount of points so that we take all the points on the curve modulo a certain number. Geometrically this is quite counter-intuitive but algebraically it works well. Say we take the curve from figure 1 and use modulo 7, which will lead to the following points:

• x=0; y²=1 → y=1 or y=6
• x=1; y²=1 → y=1 or y=6
• x=2; y²=0 → y=0
• x=3; y²=4 → y=2 or y=5
• x=4; y²=5 → no integer square root
• x=5; y²=2 → no integer square root
• x=6; y²=1 → y=1 or y=6
• x=∞; → y=∞

Fig. 1: y² = x³ – x + 1 (mod 7)

This Abelian group over a discrete elliptic curve can be used for cryptography similarly to the previous blog post, which will be explained in the following section.

Elliptic Curve Diffie-Hellman (ECDH)

Like exponentiation on integers, multiplication⁴ on elliptic curves is a one-way function and therefore can be used for the Diffie-Hellman key exchange in a similar way. Alice and Bob agree on a discrete elliptic curve and a specific generator point, i.e. the following parameters:

• p: the prime number that is the order of the group.
• a & b: the coefficients for the elliptic curve.
• x_g & y_g: the coordinates of the generator point G
• q: the order of the sub-group generated by G
• h: the cofactor of the curve, which is the ratio between the number of points on the curve and the number of points generated by G

First of all they both secretly create their private keys α and β, which are both integers while 0 < α,β < p holds. They then create their public keys A = αG and B = βG and share them with their counterparts. All parties can now calculate the shared secret S = αB = αβG = βαG = βA and use it for symmetric encryption.

Encryption/Decprytion

Gaining authenticity is quite similar to ECDH and works as follows. Say Alice wants to send an encrypted message to Bob using his public key B. What she must do first is to create a random number r (0 < r < q). She then generates a point R on the curve by multiplying r with the generator point G (R = rG). Additionally she creates the (symmetric) encryption key S which is Bob’s public key B multiplied with her random number r (S = rB) and uses this to encrypt the message. She then sends R along with the ciphertext to Bob.

Upon reception of the point-ciphertext pair, Bob multiplies R with his private key β, which leads to βR = βrG = rβG = rB = S to restore the shared secret which he uses to decrypt Alices’ message.

Digital Signatures

To sign her message Alice will first create a random number k (0 < k < q). Similarly to encryption she generates a point R using that number (R = kG) and uses its x-coordinate as r (mod q). Note that r must not be zero. She now computes s as in s = (h + αr)/k mod q, h being the hashed message to be signed, and sends the pair (r,s) along with the message to Bob.

To verify Alice’s signature he calculates a point P as follows: P = (h/s)G + (r/s)A mod q. He then compares x_p (i.e. the x-coordinate of point P) and r. If they are equal, the signature is valid⁵.

A note on the random number k

It is very important that Alice chooses a different k for each signature she creates. Refraining from doing so will lead to a situation where a third-party can easily recover Alice’s private key α. This can be seen as follows: Using k for two different signatures will lead to r₁ = kG = r₂ and therefore s₁ = (h₁ + αr)/k mod q and s₂ = (h₂ + αr)/k mod q which is a system of two linear equations with two unknowns (k and α), which is trivial to solve.

Footnotes

1. Elliptic curves do not represent ellipses! The name stems from the calculation of arc lengths of ellipses.
2. Additionally the curve must be non-singular, meaning the discriminant must not be zero.
3. Except for associativity which can be proven as shown here.
4. As in simple arithmetics, multiplication of a point on an elliptic curve with a scalar n is the same as adding that point n times to itself.
5. The proof of this is left as an exercise for the reader.