Diffie-Hellman Key Exchange Protocol: Theory and Python Implementation

Overview

The Diffie-Hellman key exchange, published in 1976 by Whitfield Diffie and Martin Hellman, was the first concrete implementation of the concept of public-key cryptography. Using this protocol, parties can securely establish a shared secret key through a public communication channel susceptible to eavesdropping, without needing to share any secret information in advance.

This protocol is important for ensuring Forward Secrecy. Forward secrecy is the property that ensures past communications cannot be decrypted even if the secret key is compromised in the future. In DH key exchange, a new shared key is generated for each session, achieving this property.

Algorithm Principles

The Diffie-Hellman key exchange bases its security on the difficulty of the discrete logarithm problem.

1. Agreement on Public Parameters: Alice and Bob, who wish to communicate, first agree on two public parameters:

   • A large prime number $p$
   • A primitive root (or generator) $g$ modulo $p$

2. Secret Key Generation:

   • Alice randomly chooses a secret integer $a$.
   • Bob randomly chooses a secret integer $b$. These $a$ and $b$ become Alice’s and Bob’s secret keys, respectively.

3. Public Key Computation and Exchange:

   • Alice computes her public key $A = g^a \pmod{p}$ and sends it to Bob.
   • Bob computes his public key $B = g^b \pmod{p}$ and sends it to Alice. Since $A$ and $B$ travel through the public communication channel, an eavesdropper can also learn them.

4. Shared Key Computation:

   • Alice uses Bob’s public key $B$ and her own secret key $a$ to compute the shared key $S_A = B^a \pmod{p}$.
   • Bob uses Alice’s public key $A$ and his own secret key $b$ to compute the shared key $S_B = A^b \pmod{p}$.

Here, $S_A = (g^b)^a \pmod{p} = g^{ba} \pmod{p}$ and $S_B = (g^a)^b \pmod{p} = g^{ab} \pmod{p}$, so $S_A = S_B$, meaning Alice and Bob can share the same secret shared key.

Discrete Logarithm Problem

Even if an eavesdropper knows the public values $g, p, A, B$, computing the secret keys $a$ or $b$ is extremely difficult.

In the equation $A = g^a \pmod{p}$, the problem of finding $a$ when $A, g, p$ are known is called the discrete logarithm problem. With a large prime $p$, this problem is considered extremely difficult to solve in practical time with current computing power. This difficulty serves as the basis for the security of the Diffie-Hellman key exchange.

Simple Python Implementation

The following Python code concisely demonstrates the principles of the Diffie-Hellman key exchange. In actual cryptographic communications, much larger prime numbers and secure random number generators should be used.

import random

# 1. Agreement on public parameters
# In practice, much larger primes and primitive roots are used
p = 23  # Large prime (example: 23)
g = 5   # Primitive root modulo p (example: 5)

print(f"Public parameters: p = {p}, g = {g}\n")

# 2. Secret key generation
# Alice and Bob each randomly choose a secret integer
# In practice, choose randomly from a range smaller than p-1
alice_private_key = random.randint(1, p - 1)
bob_private_key = random.randint(1, p - 1)

print(f"Alice's secret key (a): {alice_private_key}")
print(f"Bob's secret key (b): {bob_private_key}\n")

# 3. Public key computation and exchange
# Alice's public key A = g^a mod p
alice_public_key = pow(g, alice_private_key, p) # pow(base, exp, mod) computes (base**exp) % mod
# Bob's public key B = g^b mod p
bob_public_key = pow(g, bob_private_key, p)

print(f"Alice's public key (A): {alice_public_key}")
print(f"Bob's public key (B): {bob_public_key}\n")

# 4. Shared key computation
# Shared key computed by Alice: S_A = B^a mod p
shared_secret_alice = pow(bob_public_key, alice_private_key, p)
# Shared key computed by Bob: S_B = A^b mod p
shared_secret_bob = pow(alice_public_key, bob_private_key, p)

print(f"Shared key computed by Alice: {shared_secret_alice}")
print(f"Shared key computed by Bob: {shared_secret_bob}\n")

# Verify that the shared keys match
if shared_secret_alice == shared_secret_bob:
    print(f"Shared keys match: {shared_secret_alice}")
else:
    print("Shared keys do not match.")