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 23A = 625 mod 23A = 4(since 625 divided by 23 is 27, with a remainder of 4).
- Bob calculates
B = g^b mod p.B = 5^3 mod 23B = 125 mod 23B = 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 23Secret = 10,000 mod 23Secret = 18
- Bob calculates
Secret = A^b mod p.Secret = 4^3 mod 23Secret = 64 mod 23Secret = 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.