The Diffie-Hellman Key Exchange

The Diffie-Hellman Key Exchange

29 June 2021

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 pp and a common public key g1g^1, both publicly known. Alice creates a secret key aa and Bob a secret key bb. Each key is exclusively known to its creator. Alice can now calculate a public key QAQ_A:

QA=gamodp.Q_A = g^a mod\: p.

Simultaneously, Bob calculates his public key QBQ_B:

QB=gbmodp.Q_B = g^b mod\: p.

Both of these keys, QAQ_A and QBQ_B, are common knowledge. With it, Alice and Bob can calculate their common secret key ss:

s=(QB)amodp=gabmodp=(QA)bmodps = (Q_B)^a\: mod\: p = g^{ab}\: mod\: p = (Q_A)^b\: mod\:p

This common secret key ss 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 aa and bb are kept secret, nobody can easily calculate QAQ_A or QBQ_B. A thrid party would need to know the discret logarithm xx of QAQ_A to base gg, which means they would need to know a xx with gx=QAg^x = Q_A (equally for QBQ_B). If such an xx could be found, the secret key would not longer be secret:

s=(QA)b=(gx)b=(QB)x.s = (Q_A)^b = (g^x)^b = (Q_B)^x.

The Diffie-Hellman Algorithm is built on the problem of finding such an xx. Logarithms in e.g. the natural numbers (N\N) or the real numbers (R\R) are easy to calucate. Every calculator could find the solution to gx=QAg^x=Q_A by simply typing in x=logg(QA)x=log_g(Q_A). The difference to the Diffie-Hellman Algorithm is that we are working with modulo pp. To date, there is no fast algorithm which can calculate a discrete logarithm modulo a prime number pp. That leaves a third party only with testing different values for xx to find gx=QAg^x=Q_A. For small prime numbers pp 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 xx to solve our logarithm problem would take too long and would be too expensive for attackers to perform.


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.

Diffie-Hellman Paint Example

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=79p=79, the common public key g=6g=6 and after some calculation receive the common secret key s=62s=62.2^2

What Alice knows:

  • Prime number p=79p=79
  • Common public key g=6g=6
  • Alice' secret key a=4a=4
  • Bob's secret key bb is unknown
  • Alice' public key QA=64mod79=32mod79Q_A=6^4 mod\: 79= 32\: mod\: 79
  • Bob's public key QB=58mod79Q_B=58\: mod\: 79
  • Common seceret key s=584mod79=62mod79s=58^4\: mod\: 79 = 62\: mod\: 79

What Bob knows:

  • Prime number p=79p=79
  • Common public key g=6g=6
  • Alice' secret key aa is unknown
  • Bob's secret key b=3b=3
  • Alice' public key QA=32mod79Q_A=32\: mod\: 79
  • Bob's public key QB=63mod79=58mod79Q_B=6^3 mod\: 79=58\: mod\: 79
  • Common seceret key s=323mod79=62mod79s=32^3\: mod\: 79=62 \:mod\: 79

What Charlie knows:

  • Prime number p=79p=79
  • Common public key g=6g=6
  • Alice' secret key aa is unknown
  • Bob's secret key bb is unknown
  • Alice' public key QA=32mod79Q_A=32\: mod\: 79
  • Bob's public key QB=58mod79Q_B=58\: mod\: 79
  • Common seceret key ss 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^1 To be mathematically correct: gg needs to be a primitive root modulo pp, but for this article it is enough to assume that 1g<p1\leq g<p and gg is a natural number (gNg\in\N).

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