Diffie-Hellman key exchange

Let’s say you want to encrypt some data and send it to your friend using some symmetric encryption algorithm like AES, but to decrypt the ciphertext, your friend will need to know the secret key you used during encryption, this problem called the “key distribution problem”, and, hopefully, two solutions come to mind:

Option 1: you meet your friend in person (won’t work in long distances)
Option 2: use the power of math and follow the DHKE protocol

Today we will be talking about the second option, which is more practical and secure.

How does Diffie-Hellman key exchange work?

The Diffie-Hellman key exchange is a mathematical model that enables two parties to establish a secret key without exposing it to the public. The concept relies on the use of modular arithmetic and large primes, which makes brute-force attacks time-consuming.

Step 0: Public Constants

First, we need public constants that anyone can see and use.

g - very small number, called “generator”, usually 2 or 5
p - huge prime number, called “prime”, often 2048+ bits long

These values are so common that systems like TLS, SSH, and VPN use standardized defaults, instead of generating prime constants every time.

For example, many tools use the following values as it specified in the RFC 3526 standard specification

g = 2
p = FFFFFFFF FFFFFFFF C90FDAA2 2168C234 C4C6628B 80DC1CD1
    29024E08 8A67CC74 020BBEA6 3B139B22 514A0879 8E3404DD
    EF9519B3 CD3A431B 302B0A6D F25F1437 4FE1356D 6D51C245
    E485B576 625E7EC6 F44C42E9 A637ED6B 0BFF5CB6 F406B7ED
    EE386BFB 5A899FA5 AE9F2411 7C4B1FE6 49286651 ECE45B3D
    C2007CB8 A163BF05 98DA4836 1C55D39A 69163FA8 FD24CF5F
    83655D23 DCA3AD96 1C62F356 208552BB 9ED52907 7096966D
    670C354E 4ABC9804 F1746C08 CA237327 FFFFFFFF FFFFFFFF

Step 1: I Generate My Secret

I generate a random number “a” and compute my special key.

A = g^a mod p

Step 2: My Friend Does the Same

My friend generates his number “b” and computes his special key.

B = g^b mod p

Step 3: We Exchange Our Keys and Compute Secret

Now we exchange our public values:

I send A to my friend.
My friend sends B to me.
Now, we can both independently compute the same secret S.

# My calculation
S = B^a mod p

# My friend's calculation
S = A^b mod p

In both calculations we get the same result without exposing it to public. I can now use “S” to encrypt data using AES-256 and my friend will not have any problem with decrypting it.

Security Considerations

The most significant weakness of DHKE is its susceptibility to man-in-the-middle attacks, where an attacker can intercept and modify communications between parties.

A weak random number generation in key selection or insufficiently large primes can make the discrete logarithm problem easier to solve.

And when it comes to quantum computing, Shor’s algorithm could efficiently break traditional DHKE by solving the underlying math problems exponential faster than classical computers.

Elliptic Curve Variant

An alternative elliptic curve cryptography variant is known as ECDHKE. This method offers an equivalent level of security to the classical DHKE while using smaller key sizes. The math involves performing operations on points of an elliptic curve within a finite field, as opposed to employing modular exponentiation. It’s most often used due to its efficiency.

Thank you for reading this article. When I first learned about Diffie-Hellman key exchange, I was very impressed by the elegance of this mathematical technique.

Go back