Understanding EC Diffie-Hellman
If you’ve worked with web servers, the chances are that you’ve come across the Elliptic-curve Diffie–Hellman (ECDH) or Elliptic-curve Diffie–Hellman Ephemeral (ECDHE) cipher suites. You might have wondered what these suites implement and how they work. That is what we will discuss today.
To understand ECDH, we first have to dive into the standard Diffie-Hellman key exchange protocol. It was one of the first public-key protocols to be designed, back in 1976, and is still widely used today. It was named after Whitfield Diffie and Martin Hellman — both outstanding cryptographers that left their mark on the community, they were both part of the three-person team that invented public-key cryptography.
Traditionally, when one implemented encryption (symmetrical encryption), you would need to exchange a secret via a secure channel (could be of any form of transmission) — between two parties. The inherent flaw with this methodology is that a party can intercept the secret if they are privy to the communication channel. This secret can then be used to decrypt the encrypted data between the two parties, rendering it useless.
Cryptographic Keys
In cryptography, a key is a string of characters used within an encryption algorithm for altering data so that it appears random. Like a physical key, it locks (encrypts) data so that only someone with the right key can unlock (decrypt) it. It is important to note that every time you use the same key on the same data the result will be the same.
A key usually conforms to a certain size in bits. The use with symmetric encryption such as AES 256 the key sizes vary from 128 to 256 bits. In DH the key size is recommended to be upwards of 2000 bits where the same level of security can be achieved in ECDH with 250 bits. One can have a look at the Keylength website to get a better understanding of which key size is relevant to their implementation.
Diffie-Hellman
Diffie-Hellman allows the two parties, mentioned above, to exchange their secret without the need for a secure channel to transfer the secret. In fact, this can be used across any unsecured channel. The secret generated by the exchange can then be used to encrypt subsequent communications utilizing symmetrical encryption with the generated secret.
As mentioned in my previous article, I brushed across the basics of this, but we will go into more detail here. An analogy illustrates the concept of public key exchange by using colours instead of very large numbers which are actually used during the process.
Suppose a third party were to inspect the exchange on the unsecured communication. They would only see the common colour (yellow in this case) and the first set of mixed colours (light orange and light blue). It would be extremely difficult for the third part to compute the final colour. Instead of colours, extremely large numbers are used; this determination is computationally expensive. It is infeasible to try and calculate the final colour, even for modern-day supercomputers.
Breakdown
1 - I generate a prime number (called p) and a number (called g) which is coprime to p-1. I then tell you both those numbers.2 - You pick a secret (called a). You then compute (gᵃ modulo p)(called A) and send that back to me.3 - I do the same and pick a secret (called b). (gᵇ modulo p) (called B) and send that to you.4 - Use the number I sent you to do the same operation. (Bᵃ modulo p)5 - I do the same operation with A (Aᵇ modulo p)The numbers we get at 4 and 5 are the same.
So that we have the same numbers at step 4 and 5, we can then use that value as our secret for symmetrical encryption. The math above really comes down to properties of modulo exponents.
Elliptic-curve Diffie–Hellman
So now that we know how normal Diffie-Hellman key exchange works we can get into Elliptic-curve Diffie–Hellman. The concept is more or less the same. The same process takes place, but also, it uses algebraic curves to generate keys to be used by the parties. Also, both parties need to agree on an elliptic curve beforehand. Using elliptic curves is also much faster than using the large numbers required in normal DH. Elliptic curve discrete logarithm problem is also harder to solve than the normal discrete logarithm problem. Which means we can get away with smaller keys than we do with DH.
What is an elliptic curve?
In mathematics, an elliptic curve is a smooth, projective, algebraic curve of genus one, on which there is a specified point O. Every elliptic curve over a field of characteristic different from 2 and 3 can be described as a plane algebraic curve is given by an equation of the form: y² = x³ + ax + b [Wikipedia]
Here is what a real elliptic curve looks like:
How does ECDH work?
So you first decided on which elliptic curve the two parties will be using. Once that has been decided, the domain parameters will have been selected. Some curves are safer than others. The elliptic curve link I added at the beginning of this paragraph shows which curves are safe to use. This is the same as picking good prime numbers in normal Diffie-Hellman.
The following are the domain parameters specified:
E — the elliptic curve itself
G — a point on E that is set as the base point
Breakdown:
1 - I generate a random integer a as my private key
2 - I generate my public key A by computing aG
3 - You generate a random integer b as your private key
4 - You generate your public key B by computing bG
5 - We exchange public keys
6 - I calculate K as aB
7 - You calculate K as bASo that we have the same numbers at step 6 and 7, we can then use that value as our secret for symmetrical encryption. This elliptic curve key exchange is hard to break because someone would need to crack the Discrete Logarithm problem.
So why elliptic curves?
As one can see, the difference between ECDH and DH isn’t too different, and not too complicated to implement. One should remember that for large amounts of computation that take place (such as a website with a lot of traffic) the time saved on using elliptic curves instead of large prime numbers will add up. One might not see a difference on a small website but the more traffic, the more apparent the performance increase.
