Diffie-Hellman Key Exchange

The Diffie-Hellman (DH) key exchange is a cryptographic protocol that allows two parties to securely establish a shared secret over an insecure channel – without ever transmitting the secret itself.

It was introduced in 1976 by Whitfield Diffie and Martin Hellman – marking the birth of modern public-key cryptography.

The Need for Cryptographic Keys

Whenever we send data over the internet, it passes through many network devices – routers, switches, servers – owned by different parties. Anyone controlling these devices could potentially intercept or even modify our data.

To protect against this, we use cryptographic algorithms. These algorithms are designed to:

• Prevent unauthorized parties from reading our messages (confidentiality)
• Prevent tampering or undetected modifications (integrity)

However, most cryptographic systems require both communicating parties to share a secret piece of information known as a cryptographic key (or simply, a key).

This key is essential:

• It is used during encryption to transform plaintext into ciphertext.
• It is used during decryption to convert ciphertext back into readable plaintext.

If the key is incorrect, the decrypted message will not make sense.

A Simple Example: Caesar's Cipher

One of the earliest known encryption methods is Caesar's cipher, believed to have been used by the Roman general Julius Caesar to communicate with his army.

Although very simple by modern standards, it helps us understand the basic idea of encryption.

How Caesar's Cipher Works

The cipher arranges the 26 letters of the English alphabet in a circular structure:

A B C D E F G H I J ... U V W X Y Z

After Z, the cycle wraps back to A, forming a loop.

Encryption works by shifting each letter in the message:

• Forward (to the right) by n positions for encryption
• Backward (to the left) by n positions for decryption

The value n is the key. Both parties must already know the key n.

The major problem is obvious:

How do we securely share the key (8) in the first place?

If someone intercepts the key during transmission, they can decrypt every message.

This problem is called the key distribution problem – and it remained unsolved for centuries.

Example: Encrypting a Message

Let's encrypt the message:

Plaintext: MEET ME AT LUNCHTIME
Key (n): 8

Each letter is shifted 8 positions forward:

Final result:

Plaintext  : MEET ME AT LUNCHTIME
Ciphertext : UMMB UM IB TCVKPBQUM

Decryption

To decrypt the message, we reverse the shift:

t = (c − n) mod 26

Using the same key (n = 8), we shift each character 8 positions backward to recover the original message.

The Mathematical View

We can represent each letter with numbers:

A = 0, B = 1, C = 2, ..., Z = 25

Encryption becomes a simple modular arithmetic formula:

c = (t + n) mod 26

Where:

• t = plaintext letter (as a number)
• n = key
• c = ciphertext letter

The modulo 26 operation ensures that once we pass Z, we wrap back to A – just like a clock wraps around after 12. The only difference is that instead of 12 positions (like hours on a clock), we have 26 positions (letters of the alphabet).

Why Caesar's Cipher is Insecure

Caesar's cipher is extremely easy to break.

Since there are only 26 possible keys, an attacker can simply try all possible shifts – this is know as the brute-force attack.

Modern cryptographic algorithms use:

• Much larger key sizes
• Complex mathematical structures
• Computationally hard problems

We use Caesar's cipher here only to understand the big picture:

• Encryption transforms readable data into unreadable form.
• Decryption reverses the process using a shared key.
• Security depends heavily on how hard it is to guess or compute that key.

The Core Weakness of Classical Ciphers

With symmetric encryption systems like Caesar's cipher:

• The same key is used for encryption and decryption.
• Both parties must already share that key.
• The key must be transmitted securely somehow.

But if we already have a secure channel to share the key…

Why do we even need encryption?

This circular dependency was a fundamental limitation of early cryptography.

The Breakthrough: Diffie-Hellman (1976)

In 1976, Whitfield Diffie and Martin Hellman introduced a revolutionary idea:

Two parties can agree on shared secret without ever sending the secret itself.

This was the birth of public-key cryptography.

Instead of sending the key directly:

• Each party generates a private secret
• They exchange derived pubic values
• Using mathematics, both compute the same shared key
• An eavesdropper cannot compute the key

This solves the key distribution problem.

The Core Problem It Solves

Imagine:

• You (Alice) want to talk securely with Bob.
• An attacker (Eve) can see all network traffic.
• You will never met Bob before.
• No shared secret exists.

How can you create a secret key over an open network?

Diffie-Hellman solves exactly this.

Diffie-Hellman doesn't replace Caesar's idea – it replaces the insecure way of sharing the key.

Mathematical Foundation

DH relies on:

Modular Arithmetic

Working in a finite group:

a mod p

Primitive Roots

A number g is a generator (primitive root) modulo prime p.

Discrete Logarithm Problem (DLP)

Given:

g^a mod p

It is computationally hard to find a.

This “hardness” is the security backbone.

Step-by-Step Working

Let's walk through the full protocol.

Step 1: Public Parameters (Shared openly)

Both parties agree on:

• A large prime number p
• A generator g

These are public.

Example (small numbers for understanding):

p = 23
g = 5

Step 2: Private Keys (Secret)

Alice picks:

a = 6

Bob picks:

b = 15

These are NEVER shared.

Step 3: Public Keys

Alice computes:

A = g^a mod p
  = 5^6 mod 23
  = 8

Bob computes:

B = g^b mod p
  = 5^15 mod 23
  = 19

They exchange:

• Alice sends 8
• Bob sends 19

Step 4: Shared Secret Computation

Alice computes:

S = B^a mod p
  = 19^6 mod 23 = 2

Bob computes:

S = A^b mod p
  = 8^15 mod 23 = 2

Both now share secret = 2

Why It's Secure

An attacker sees:

• p
• g
• A = g^a
• B = g^b

To compute the secret:

They must find a or b.

That means solving:

a = log(g) A mod p

This is the Discrete Logarithm Problem

For large 2048-bit primes, this is computationally infeasible.

Simple Analogy

Think of it like this:

• Caesar's cipher:

  “Here's the key. Keep it secret.”

• Diffie-Hellman:

  “Let's mathematically create the same key without ever sending it.”

References

• medium