Diffie-Hellman: Sharing Secrets with Modular Math

This article explains how the Diffie-Hellman key exchange revolutionized cryptography by allowing two parties to establish a shared secret over an insecure communication channel. It covers the historical problem of key distribution, the mechanics of modular arithmetic, the step-by-step mathematical process of the exchange, and how the discrete logarithm problem prevents eavesdroppers from intercepting the secret key.

The Key Distribution Problem

Before 1976, secure communication required both the sender and the receiver to possess the exact same secret key to encrypt and decrypt messages. This created a fundamental paradox: to send a secret key securely, you already needed a secure channel. Organizations had to rely on physical couriers to transport keys, which was slow, expensive, and vulnerable to interception. Whitfield Diffie and Martin Hellman solved this by finding a way to generate a shared secret using public information, eliminating the need to ever transmit the key itself.

The Power of Modular Arithmetic

The Diffie-Hellman exchange relies on a branch of mathematics called modular arithmetic, often referred to as "clock math." In modular arithmetic, numbers wrap around upon reaching a certain fixed value, called the modulus.

To find the result of X mod Y, you divide X by Y and keep only the remainder. For example, 14 mod 12 is 2, just as 14:00 on a 12-hour clock is 2:00.

Diffie and Hellman combined modular arithmetic with exponentiation to create a "one-way function"—a mathematical operation that is easy to perform in one direction, but extremely difficult to reverse.

While it is easy to calculate g^a mod p (where g is a base number, a is an exponent, and p is the modulus), it is computationally infeasible to figure out what a is if you are only given the final remainder, g, and a sufficiently large p. This roadblock is known as the Discrete Logarithm Problem, and it is the foundation of the algorithm's security.

How the Exchange Works

To see how two people—traditionally named Alice and Bob—use this math to create a shared secret over a tapped wire, follow these steps:

1. Agree on Public Numbers

Alice and Bob publicly agree on two numbers that anyone, including an eavesdropper, can see:

  • p: A very large prime number (the modulus).
  • g: A small prime number, called the generator (the base).

(For simplicity, we will use small numbers: let p = 23 and g = 5).

2. Choose Private Secrets

Alice and Bob each pick a secret number that they never share with anyone.

  • Alice picks the secret integer a = 4.
  • Bob picks the secret integer b = 3.

3. Calculate and Exchange Public Results

Both parties now use their private numbers, along with the public numbers, in the modular equation.

  • Alice calculates A = g^a mod p.
    • A = 5^4 mod 23
    • A = 625 mod 23
    • A = 4 (since 625 divided by 23 is 27, with a remainder of 4).
  • Bob calculates B = g^b mod p.
    • B = 5^3 mod 23
    • B = 125 mod 23
    • B = 10 (since 125 divided by 23 is 5, with a remainder of 10).

Alice sends her result (4) to Bob. Bob sends his result (10) to Alice. An eavesdropper intercepts both the 4 and the 10, alongside the original p (23) and g (5).

4. Generate the Shared Secret

Alice and Bob now take the number they received from the other person and raise it to the power of their own original secret number, applying the modulus one last time.

  • Alice calculates Secret = B^a mod p.
    • Secret = 10^4 mod 23
    • Secret = 10,000 mod 23
    • Secret = 18
  • Bob calculates Secret = A^b mod p.
    • Secret = 4^3 mod 23
    • Secret = 64 mod 23
    • Secret = 18

Both Alice and Bob have arrived at the exact same number: 18. They can now use this number as their encryption key for future communications.

Why the Math Works and Stays Secure

The reason Alice and Bob arrive at the same number is due to the rules of exponents. Even with the modulus applied at every step, the underlying math ensures that: (g^a)^b mod p is always equal to (g^b)^a mod p, which simplifies to g^(ab) mod p.

Meanwhile, the eavesdropper is stuck. They have the numbers p = 23, g = 5, A = 4, and B = 10. However, they cannot calculate g^(ab) mod p without knowing either a or b. Simply multiplying A and B together gives g^a * g^b = g^(a+b), which is useless.

To find a or b, the eavesdropper must reverse the modular exponentiation. With a small prime like 23, a computer could guess the answer instantly. However, in modern cryptography, the prime number p is typically 600 digits long (2048 bits) or more. With numbers of that magnitude, reversing the modular math to find the secret exponents would take the world's fastest supercomputers thousands of years, ensuring the shared secret remains completely secure.