The Diffie-Hellman Key Exchange is one of the first widely used algorithms to exchange keys publicly. That raises two questions: What is a key exchange? and Why would you do that publicly?.

Let's start with the first one. Some information, e.g. private messages or corporate secrets, are not meant to be accessible by everyone. To ensure that only certain people (or machines) can read this kind of information, one can use various cryptographic systems. These systems allow two or more parties to share information if and only if everyone has a key to encode and/or decode the data. Of course it wouldn't be practical for one person to encode a message with a key which is completely independent from the receiver's key. Therefore, some information needs to be known to all parties involved. We call the procedure of sharing this specific information a key exchange.

Why would you do that publicly? First of all, there are key exchanges which work only privately. The problem here is that you need to find a secure way to exchange the keys. If a person, who's not supposed to get certain data, were to get access to the secretly exchanged key, they could read all of the encoded infomation. Having said that, if the keys are exchanged publicly, there is no harm in giving the keys to people who are not involved.

Now, we have a cryptographic system which exchanges keys publicly, meaning that anyone has access to the public keys. How can we ensure that secret information can only be decoded by certain people? The Diffie-Hellman Key exchange provides one possible solution to this problem.

The Algorithm

Two people, Alice and Bob, want to exchange cryptographic keys. They agree on a prime number $p$ and a common public key $g^1$, both publicly known. Alice creates a secret key $a$ and Bob a secret key $b$. Each key is exclusively known to its creator. Alice can now calculate a public key $Q_A$:

Simultaneously, Bob calculates his public key $Q_B$:

Both of these keys, $Q_A$ and $Q_B$, are common knowledge. With it, Alice and Bob can calculate their common secret key $s$:

This common secret key $s$ can then be used in other cryptographic systems, e.g. to encode secret messages or information.

How Secure is the Algorithm?

If the secret keys $a$ and $b$ are kept secret, nobody can easily calculate $Q_A$ or $Q_B$. A thrid party would need to know the discret logarithm $x$ of $Q_A$ to base $g$, which means they would need to know a $x$ with $g^x = Q_A$ (equally for $Q_B$). If such an $x$ could be found, the secret key would not longer be secret:

The Diffie-Hellman Algorithm is built on the problem of finding such an $x$. Logarithms in e.g. the natural numbers ($\N$) or the real numbers ($\R$) are easy to calucate. Every calculator could find the solution to $g^x=Q_A$ by simply typing in $x=log_g(Q_A)$. The difference to the Diffie-Hellman Algorithm is that we are working with modulo $p$. To date, there is no fast algorithm which can calculate a discrete logarithm modulo a prime number $p$. That leaves a third party only with testing different values for $x$ to find $g^x=Q_A$. For small prime numbers $p$ it can be done in a short amount of time and the algorithm wouldn't be secure. Therefore, security experts suggest long prime numbers with at least 2048 bits. The testing of different values for $x$ to solve our logarithm problem would take too long and would be too expensive for attackers to perform.

Examples

To make the alorithm a little easier to understand, we will have a look at the following two examples.

The Diffie Hellman Key Exchange with Colors

In the grapic below you can see how the keys interact with each other and how they are calculated. Certainly, mixing different colors can not provide any information about the security but you can follow the way the algorithm works.

Table of Known and Unknown Variables

In following examlpe shows an overview over a key exchange between Alice and Bob and a third party (Charlie) who's not part of the exchange. Alice and Bob agree on the prime number $p=79$, the common public key $g=6$ and after some calculation receive the common secret key $s=62$.$^2$

What Alice knows:

• Prime number $p=79$
• Common public key $g=6$
• Alice' secret key $a=4$
• Bob's secret key $b$ is unknown
• Alice' public key $Q_A=6^4 mod\: 79= 32\: mod\: 79$
• Bob's public key $Q_B=58\: mod\: 79$
• Common seceret key $s=58^4\: mod\: 79 = 62\: mod\: 79$

What Bob knows:

• Prime number $p=79$
• Common public key $g=6$
• Alice' secret key $a$ is unknown
• Bob's secret key $b=3$
• Alice' public key $Q_A=32\: mod\: 79$
• Bob's public key $Q_B=6^3 mod\: 79=58\: mod\: 79$
• Common seceret key $s=32^3\: mod\: 79=62 \:mod\: 79$

What Charlie knows:

• Prime number $p=79$
• Common public key $g=6$
• Alice' secret key $a$ is unknown
• Bob's secret key $b$ is unknown
• Alice' public key $Q_A=32\: mod\: 79$
• Bob's public key $Q_B=58\: mod\: 79$
• Common seceret key $s$ is unknown

The Diffie-Hellman Key exchange is a powerful tool in cryptographic systems. It forms the base of various encryptions like the ElGamal encryption and can even be modified to be used with ellipitic curves (ECDH).

$^1$ To be mathematically correct: $g$ needs to be a primitive root modulo $p$, but for this article it is enough to assume that $1\leq g<p$ and $g$ is a natural number ($g\in\N$).

$^2$ Note that the prime number $p=79$ is far to small to guarantee any kind of security. It is only used for demonstration purposes.