What Diffie-Hellman has to do with primitive roots Image: Dan Spisak (CC BY-SA 2.0)

What Diffie-Hellman has to do with primitive roots

In November 1976 Whitfield Diffie and Martin Hellman published a paper called New Directions in Cryptography, and the direction was this: two parties can agree on a shared secret by exchanging messages that an eavesdropper sees in full. Until then, every cipher needed a key delivered in advance by a trusted courier. After it, the key could be made on the spot, which is what happens every time a browser connects to a website over HTTPS. The mathematics is the theory of primitive roots, which Gauss set out in the Disquisitiones in 1801 for other reasons entirely.

Powers modulo a prime

Take the prime 23 and the number 5. The powers of 5 modulo 23 are 5, 2, 10, 4, 20, 8, 17, 16, 11, 9, 22, 18, 21, 13, 19, 3, 15, 6, 7, 12, 14, 1, and then they repeat. Every non-zero residue modulo 23 appears exactly once among the first 22 powers; 5 is a primitive root modulo 23. For a prime p, a primitive root g is a number whose powers g, g², ..., g^(p-1) run through all the non-zero residues, and Unit 9 of the masterclass proves that every prime has one, in fact φ(p - 1) of them.

Given g and an exponent k, computing g^k mod p is fast: repeated squaring needs about 2 log₂ k multiplications. Given g and a residue h, finding the exponent k with g^k ≡ h is called the discrete logarithm problem, and for a large prime no fast method is known. For p = 23 one reads the exponent off the list above: the discrete logarithm of 8 to the base 5 is 6. For a 600-digit prime, the list has 600 digits' worth of entries and the best known algorithms take, in a precise sense, a time that grows faster than any power of the number of digits.

The exchange

Alice and Bob agree in public on p = 23 and g = 5. Alice chooses a secret a = 6, computes A = 5^6 mod 23 = 8, and sends 8 to Bob. Bob chooses a secret b = 15, computes B = 5^15 mod 23 = 19, and sends 19 to Alice. Alice computes B^a = 19^6 mod 23 = 2. Bob computes A^b = 8^15 mod 23 = 2. They now share the number 2, and the eavesdropper, who saw 23, 5, 8, and 19, must find 2 from those.

Why do they get the same number? Because B^a = (g^b)^a = g^(ab) and A^b = (g^a)^b = g^(ab). The exponents multiply, and multiplication does not care about order. The eavesdropper knows g^a and g^b and wants g^(ab); the only known way to get there is to recover a or b, which is a discrete logarithm.

Why does the exchange not leak the secret some other way? Because the only information about a that leaves Alice's computer is g^a, and recovering a from g^a is the problem that is assumed hard. That assumption, that the discrete logarithm problem modulo a well-chosen prime has no fast solution, has the same status as the assumption that factoring is hard behind RSA: no proof, and fifty years of failed attempts.

Why the prime must be chosen with care

Not every prime is safe, and the reason is the structure of the group of residues. If p - 1 has only small prime factors, the Pohlig-Hellman algorithm of 1978 computes discrete logarithms modulo p quickly: it solves the problem modulo each prime factor of p - 1 separately and combines the answers with the Chinese remainder theorem. So p is chosen with p - 1 = 2q for a large prime q, a so-called safe prime, and g is chosen to generate the subgroup of order q. For 23 we have 22 = 2 × 11, so 23 is a safe prime, which is why the toy example uses it.

There is a second trap, which is a property of the exchange rather than of the prime. If Bob can be tricked into using a g of small order, say an element whose powers cycle after 2 or 3 steps, then the shared secret takes only 2 or 3 possible values, and an attacker tries them all. Real implementations check that the incoming number lies in the right subgroup, and the ones that forgot have been broken. This is exactly the theory of orders of Unit 9: the order of g divides p - 1, and the security of the exchange is the size of that order.

Logjam

In 2015 a team of fourteen researchers led by David Adrian and Nadia Heninger published an attack called Logjam. Two facts combined. First, the fastest known method for discrete logarithms modulo p, the number field sieve, spends most of its effort in a precomputation that depends only on p; once that is done, each individual logarithm modulo that p takes minutes. Second, most servers on the internet used the same handful of primes, built into the software. For 512-bit primes, which some servers still accepted as an "export-grade" option left over from the 1990s, the precomputation took the team about a week on a few thousand cores, and afterwards they could break any connection to the 8 percent of the top million websites that supported those primes. They estimated that a precomputation for a 1024-bit prime was within the budget of a national intelligence agency, and that two such precomputations would cover a large share of all VPN and SSH traffic of the time.

The remedy was to retire the small primes, move to 2048 bits, and increasingly to abandon the integers altogether: most connections today use the same exchange on an elliptic curve, where the group of points plays the role of the residues modulo p and the number field sieve does not apply. The arithmetic of Alice and Bob is unchanged; only the group is different. The Logjam paper, which is free to read, is the excursion of Unit 9 of the masterclass.

Back to Gauss

Gauss called the exponent k with g^k ≡ h the index of h, and he compiled tables of indices for primes up to 100 so that multiplication modulo p could be done by adding indices, as logarithm tables turn multiplication into addition. His tables are discrete logarithm tables, and Diffie and Hellman's insight was that for a large prime the table cannot be compiled while the entries can still be computed one at a time. The idea that a function could be easy in one direction and hard in the other had no name in 1801; it is now called a one-way function, and it is the foundation of the whole of public-key cryptography.

Unit 9 of the masterclass proves the existence of primitive roots, computes the index table modulo 17, carries out the exchange above and a baby-step giant-step computation of a discrete logarithm modulo 101, and explains why 1/7 has period 6, which is the same theory wearing different clothes.

Study the integers properly

The NT Masterclass: weekly units, quizzes, a final exam, and a certificate.
About the program