Diffie-Hellman Key Exchange

Cryptography · Axiom Academy

LESSON Diffie-Hellman Key Exchange The first practical public key exchange protocol Before the key exchange begins, Alice and Bob agree on two public parameters: p - A large prime number (publicly known) g - A generator (primitive root modulo p, publicly known) These parameters can be transmitted openly - Eve can see them too. The security doesn't depend on keeping p and g secret. A generator g modulo p is a number whose powers produce all integers from 1 to p-1. For example, if p=7, then g=3 is a generator because 3¹, 3², 3³, 3⁴, 3⁵, 3⁶ mod 7 = 3, 2, 6, 4, 5, 1 . 2. Generating Private and Public Keys Alice picks a secret random number a (her private key) Alice computes A = g a mod p (her public key) Bob picks a secret random number b (his private key) Bob computes B = g b mod p (his public key) Alice and Bob now exchange their public keys A and B over the insecure channel. Eve, who is eavesdropping, can see: Alice's public key A = g a mod p Bob's public key B = g b mod p However, Eve does not know the private keys a or b. This is crucial for security. 4. Computing the Shared Secret Alice computes s = B a mod p = (g b ) a mod p = g ab mod p Bob computes s = A b mod p = (g a ) b mod p = g ab mod p Both arrive at the same shared secret s = g ab mod p ! 5. Why Eve Cannot Compute the Secret Eve can intercept all public information: A = g a mod p (Alice's public key) B = g b mod p (Bob's public key) To compute the shared secret s = g ab mod p, Eve would need to know either a or b.

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