Diffie-Hellman Key Exchange

Number Theory · Axiom Academy

LESSON Diffie-Hellman Key Exchange Establishing a shared secret over an insecure channel using modular exponentiation First, Alice and Bob agree on two public parameters that everyone can see: p : A large prime number (the modulus) g : A generator (a primitive root modulo p) These values are not secret. An eavesdropper named Eve can see both p and g. In this example, we'll use small numbers for illustration: p = 23 and g = 5. Next, Alice and Bob each secretly choose their own private key: Alice chooses a secret number a (let's say a = 6) Bob chooses a secret number b (let's say b = 15) These private keys are never shared or transmitted. They remain completely secret to their respective owners. Alice and Bob each compute a public value using their private key and send it to the other party: Alice computes: A = g a mod p = 5 6 mod 23 = 8 Bob computes: B = g b mod p = 5 15 mod 23 = 19 Alice sends A = 8 to Bob, and Bob sends B = 19 to Alice. Eve can intercept these values, but that doesn't help her! 4. Computing the Shared Secret Now comes the magic! Alice and Bob can each compute the same shared secret: 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 arrive at the same value: s = 2 . This is their shared secret key! The mathematical reason both parties compute the same value is simple: Alice computes: B a mod p = (g b ) a mod p = g ab mod p Bob computes: A b mod p = (g a ) b mod p = g ab mod p

This is the written version of the interactive lesson above. See the full Number Theory course.