Basics of Encryption: The Diffie-Hellman Key Exchange Explained

In Encryption, The Diffie-Hellman(DH) Key Exchange is a method for two parties who have never met before to establish a shared secret key that only the two of them know, without compromising their individual security.

DH was one of the first algorithms to be able to achieve this and is subsequently considered one of the most important achievements in modern cryptography.

For your purposes, learning how DH works is a great introduction to modern cryptography concepts. Let’s dive right in!

A Bit of Vocab

Cryptographic Keys: A Cryptographic key is a long string of numbers or letters that can be used to uniquely encrypt or decrypt a piece of information.

Key Exchange: For two parties to securely transfer information, they need to agree on a cryptographic key. The Key exchange method is the way in which they establish a shared key to use for encryption. Historically, this was done with a physical courier who would travel between the parties and give them each the key to use.

Asymmetric Cryptography: The use of a physical courier(Known as symmetric cryptography) obviously doesn’t scale to the digital age. Asymmetric cryptography is a method of two people exchanging a key without ever meeting physically by using both a public and private key. The shared cryptographic key is then created by mixing the public and private keys in a way that doesn’t expose the individual parties’ private keys.

Modulus The Modulus function is at the heart of the DH key exchange. In most languages it is represented by the ‘%’ key and it returns the remainder of a division. Ig 5 % 3 is 2.

How DH Works

DH utilizes the following mathematical fact:

Don’t worry if this seems overwhelming right now, because we’ll unpack it in full and even implement it in Python.

Let’s say Annie and Billy want to establish a shared cryptographic key using DH. First, the following variables will be established:

• Annie’s Private Key(Billy doesn’t know it). This will an integer that we will refer to it as a
• Billy’s Private Key(Annie doesn’t know it). This will also be an integer. We will refer to is as b
• A public key that can be seen by anyone(Including Billy, Annie, and anyone malicious). This will be two different integers, a base g and a modulus p.
  

To shared cryptographic key will be given by

So how can Annie and Billy get this value without revealing their private keys(a and b)?

Consider the values:

It turns out that when p is made sufficiently large(as in the hundreds of digits), it is nearly impossible to recover a from A, and b from B. There is no clean algorithm to recover the secret keys from these values, so if a hacker had access to A or B, they would have to manually check millions of possibilities.

The difficulty of recovering the private keys from these values allows Annie and Billy to be able to send these values through public, insecure channels without worrying about exposing their private keys.

The next thing to notice is, from the formula at the beginning of this section, we have the equality:

The DH exchange works by Annie and Billy sending each other A and B respectively over the insecure channel. And then using their private keys in conjunction with A or B, to compute the same cryptographic key without ever exposing their private keys.

With the DH key exchange, the only pieces of information that are exposed to the public, and therefore susceptible to interception by malicious actors, are A, B, p, and g. None of which are sufficient to recover Annie or Billy’s private keys. More importantly, this is not enough information to recover the Cryptographic key, therefore allowing Annie and Bob to send encrypted messages to each other safely.

Code Implementation

Here’s an example of what this might look like in Python

With sample output

What’s Next

There you go! We’ve just learned how to implement a Diffie Hellman Key Exchange! I’d recommend picking some small numbers for p, g, a, and b and working out some examples by hand, in order to convince yourself that you always end up with the same key.

Now DH is just the tip of the iceberg for modern encryption. The next topic I would recommend learning is RSA, which is much more widely used nowadays compared to DH.

Hope you enjoyed!