The Beauty and Power of Elliptic Curve Cryptography

The Beauty and Power of Elliptic Curve Cryptography

Here is the Spotify podcast:

and Apple:

I have a secret. And you have a secret. And together we can merge our secret into another secret. What I am outlining here is the beauty of the Elliptic Curve Diffie Hellman (ECDH) method, and it is protecting your rights to privacy in the access that you have to this podcast. And what about trust? Well, there’s a chance that the Web site that you are receiving this from is using the ECDSA (Elliptic Curve Digital Signature Algorithm). So, in this podcast, I’m going to outline something that is pure mathematical beauty: the Elliptic Curve.

The Diffie-Hellman key exchange method

But, before we begin, let’s look at a bit of history. In 1976, possibly it is Whitfield Diffie and Martin Hellman published their classic paper entitled: “New Directions in Cryptography”. With this, Alice generates secret a, and Bob generates b. They agree to a base generator for their logarithms of g, and also a prime number of p.

Alice passes A=g^a (mod p), and Bob passes B=g^b (mod p). Alice takes Bob’s value and raises it to the power of a to get a shared secret of:

K = g^{ab} (mod p)

The hard problem is:

Given g, and g^x, it is difficult to find x.

The method is known as Diffie-Hellman key exchange.

Elliptic Curves

Now, let’s look at elliptic curves and elliptic curve cryptography (ECC). Around 1985, Neal I. Koblitz and Victor Miller independently invented ECC. Their idea came from preliminary work conducted by H.W Lenstra Jr on using elliptic curves to crack the RSA method. His paper was entitled, “Factoring Integers using Elliptic Curves”.

Although they created ideas between 1985 and 1987, the main methods of ECC did not take off until 2005.

Overall, there are three main curves used. These are:

• Edwards curve: x²+y² = 1+d.x²y2 — named after Harold Edwards. Ed25519.
• Montgomory curves: By²=x³+Ax²+x (mod p) — named after Peter Montgomary.
• Weierstrass (wire strass): y²=x³+bx+c (mod p) — as used with Bitcoin.

So, let’s look at a Weierstrass Curve. For Bitcoin we have:

y² = x³ + 7 (mod p)

So if we have p=17.

The first point is at (1, 12) but there’s also a point at (1, 5).

This is because 12² (mod 17) is equal to 8, and 5² (mod 17) is equal to 8 is also equal to 1. So for every value x value, there are two valid y values. One is even and the other is odd. Unfortunately, not every x coordinate value gives a point, such as where x is equal to 4. This leads us to the order of the curve, and which is the maximum number of points we can use. This will be less than p — but hopefully quite close to it.

So how does it actually work for our key exchange? Will with elliptic curves we define a base point of G. This is an (x,y) point, and is well-known to everyone. We start off this the secret again, and where Alice generates a, and Bob generates b. Typically these are 256 bits long. Alice then computes her public key point on the curve by multiplying a by G — which is basically G+G+G … G … a times. This gives a.G. This has an (x, y) value — and will thus have 512 bits for the x and the y coordinate value. Bob does the same with his secret and computes his public key point. They exchange their public key points. Alice then multiplies Bob’s public key point to give a.b.G, and Bob multiples Alice’s point with b, to also get a.b.G. This will be their shared secret, and even though Eve listened to the conversation she should not be able to recover the shared secret.

Thus, Bob and Alice agree on a, b, p and G, and which will define the curve they are using. This defines their curve. Overall, we typically start at the 256-bit curves, such as secp256k1 and secp256r1 — and where secp256r1 is also known as the NIST-defined P256 curve. For more security, we can have the NIST-defined P521 curve, and which uses a 521-bit prime number. The more bits that the prime number has, the more secure it will be. Generally, we have 128-bit equivalent security for the secp256 curves.

Curve 25519

There’s another curve which is becoming increasingly popular, and it’s called Curve 25519 — and named after the prime number: 2²⁵⁵-19. This gives 128-bit security, and was created by Daniel J. Bernstein. It has the advantage of only requiring an x coordinate value for the public key, and this has a smaller key.

Point addition and point doubling

The thing that makes ECC so efficient, is that it only needs two operations — a point addition such as P+Q, and a point double 2.P. With this, we can use the Montgomery multiplication method to produce the point multiplication, and where we only need the point addition or point doubling. Another advantage is that it can compute this in a fixed time period, and which is equal to the number of bits used. Some methods in cryptography can be weak in terms of leaking information in the time it takes to complete an operation. Unfortunately, the Montgomery method can be prone to this as the point addition and point doubling will be different in their effect on the processor. This variation could be leaked through electrical noise or radio emissions. This is known as a side channel, and designers often have to try and obfuscate the operation of the point multiplication.

Digital Signatures

And, so, what’s the other application of ECC. Well, it is in digital signing. With this, we create a private key as before. For example, Alice creates a scalar value of a. She then creates her public key as a.G, and where G is the base point on the curve. For digital signing, we need to prove the integrity of a message, and also verify the sender. For this Alice create a hash of the message, and signs this with his private key. He sends the signature with the message, and Alice checks the signature with Bob public key. In order to create the signature Bob needs to generate a random nonce value for the signature. This should be deleted after use, as it is possible to crack the signature if someone discovers the nonce used, and also if it is reused at a future time.

The main signature method is called ECDSA (Elliptic Curve Digital Signature Algorithm), and it produces two values: r and s. It was defined, in 1999, by Don Johnson Alfred Menezes (1999) in a classic paper on “The Elliptic Curve Digital Signature Algorithm (ECDSA)”.

It is based on the Digital Signature Algorithm (DSA) and which used discrete logarithms. These methods are defined as defined in Federal Information Processing Standard (as FIPS 186) for digital signatures. It was outlined by NIST in 1991, and proposed within the Digital Signature Standard (DSS). This was then standardized with FIPS 186 in 1994, and FIPS 186–4 in 2013. Within FIPS 186–5, it is defined that DSA should not be used for the generation of signatures, but can be used for signature verification. Although DSA has a patent (Patent 5,231,668 by David W. Kravitz, who had previously worked for the NSA), NIST published the standard as a royalty-free method.

A key element for trust is for Bob to get his public key to Alice in a trusted way. This is achieved with the PKI (Public Key Infrastructure). With this, Trent — a trusted entity — checks and encapsulates Bob’s public key and signs this with its private key. This encapsultation is known as a digital certificate. When Alice receives this digital certificate, she will check the signature of the certificate with Trent’s public key, and if it checks out, she can trust Bob’s public key.

Bitcoin and Ethereum

In 2008, Satoshi Nakamoto selected the secp256k1 curve for Bitcoin. With this, a user creates a 256-bit private key, and then converts this into a Base58 format. This is known as a Wif (Wallet Import Format) and which is then protected with a password. The public key is created by creating an ECDSA signature of the private key, and then hashing twice to produce the public Bitcoin ID. The wonderful thing about this, is that Bob can sign a transaction with his private, and everyone can prove that it was Bob who signed the transaction, using his public ID. Ethereum also adopted ECC with secp256k1.

Quantum computers

ECC methods are now used extensively for key exchange and increasing in creating digital signatures. Unfortunately, using Shor’s algorithm, it is possible to break elliptic curve methods. And, so, we are searching for replaces to the main public key methods — including RSA and ECC. The most widely proposed method is lattice-based. But it will take a while to remove ECC, especially as it is used to generate the symmetric key used for the HTTPs connection. What is likely is that we will use a hybrid approach, and where the public key passed for the key exchange will include both the ECC public key and a lattice-based public key. We can then migrate over time from the ECC method to the lattice-based one.