Skip to content
Tutorials Center
My learning

Topics

Lesson 34 of 37 · Applications: Codes and Cryptography

Diffie-Hellman and Discrete Logarithms

Use cyclic groups and primitive roots to run a Diffie-Hellman key exchange, then attack a toy instance with baby-step giant-step in Python.

Two people who have never met want to agree on a secret key while everyone listens in. It sounds impossible, but Diffie-Hellman key exchange does it with a cyclic group. The idea is that exponentiation in a group is easy to compute and, in the right group, hard to reverse.

Cyclic groups and primitive roots

For a prime p, the multiplicative group ℤₚ× of nonzero residues has p - 1 elements and is cyclic (a special case of the finite-field fact from earlier). A generator g is called a primitive root modulo p: its powers g¹, g², ..., g^(p-1) run through every nonzero residue.

To test whether g is a primitive root, check that its order is exactly p - 1. It is enough to check that g^((p-1)/r) ≠ 1 for every prime factor r of p - 1.

The key exchange

Public parameters: a prime p and a primitive root g.

  1. Alice picks a secret integer a, and sends A = gᵃ mod p.
  2. Bob picks a secret integer b, and sends B = gᵇ mod p.
  3. Alice computes Bᵃ mod p; Bob computes Aᵇ mod p.

Both obtain g^(ab) mod p, because (gᵇ)ᵃ = g^(ab) = (gᵃ)ᵇ (powers commute: the group is abelian). An eavesdropper sees p, g, A, B but not a or b. To find the shared key she would need to solve a problem such as: given A, find a with gᵃ ≡ A. This is the discrete logarithm problem.

The program below finds primitive roots, then runs a full exchange.

Python Primitive roots and a Diffie-Hellman exchange

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

By a theorem about cyclic groups, the number of primitive roots modulo p is φ(p - 1). For p = 467, p - 1 = 466 = 2 · 233, so φ(466) = 232 primitive roots. The printed count should agree.

The discrete logarithm problem

If g is a primitive root, then every y in ℤₚ× equals gˣ for a unique x mod p - 1. That x is the discrete logarithm of y to base g. Computing gˣ takes about log₂ x multiplications (square and multiply), but undoing it by trying all x takes up to p - 1 steps.

Baby-step giant-step (BSGS) is a smarter attack, which uses about √p steps and √p memory. Write x = i m + j with m = ⌈√(p - 1)⌉:

Text
y = g^(i m + j)   ⇒   y · (g^(-m))^i = g^j

Store the "baby steps" gʲ for j = 0 .. m-1 in a table. Then step through the "giant steps" y · (g^(-m))^i until one lands in the table.

Python Baby-step giant-step discrete logarithm

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The recovered x may differ from secret by a multiple of the order of g, but gˣ still equals y, and that is all an attacker needs. In real deployments p has 2,048 bits or more, and √p steps is hopelessly many.

Choosing good parameters

Group structure affects security. If p - 1 is a product of small primes, the Pohlig-Hellman algorithm splits the discrete logarithm into small pieces by using the subgroup structure of ℤₚ×, and it becomes easy. This is why standards use safe primes p = 2q + 1 (with q prime) or work in a subgroup of large prime order q.

Other groups follow the same pattern. Elliptic-curve Diffie-Hellman replaces ℤₚ× with the group of points on an elliptic curve over a finite field, where the discrete logarithm is harder per bit of key. The protocol is identical.

Diffie-Hellman gives a shared secret, not authentication. Without extra checks, an attacker sitting in the middle can run one exchange with Alice and another with Bob. Real protocols such as TLS combine key exchange with digital signatures.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. A primitive root g modulo a prime p is an element whose powers...

    g generates the whole cyclic group of nonzero residues, so it has order p - 1.
  2. 2. In Diffie-Hellman, what do Alice and Bob both end up computing?

    Alice computes B^a = g^(ba), Bob computes A^b = g^(ab); these are equal.
  3. 3. How many primitive roots does the prime 11 have?

    The count is phi(p - 1) = phi(10) = 4. They are 2, 6, 7 and 8.
  4. 4. What does baby-step giant-step achieve?

    It is a time-memory trade-off for the discrete logarithm, still exponential in the bit length.

Summary

  • ℤₚ× is cyclic; a generator is a primitive root, and there are φ(p - 1) of them.
  • Diffie-Hellman exchanges gᵃ and gᵇ and derives the shared secret g^(ab).
  • Its security rests on the discrete logarithm problem in the chosen group.
  • Baby-step giant-step solves tiny instances in about √p steps; real keys are far beyond reach.
  • Group structure matters: safe primes and prime-order subgroups defeat Pohlig-Hellman, and elliptic curves provide another family of groups.

Next: Practice: Homomorphisms and Quotients