Skip to content
Tutorials Center
My learning

Topics

Lesson 32 of 37 ยท Cryptographic Applications

Diffie-Hellman and Discrete Logarithms

Agree on a shared secret over a public channel with Diffie-Hellman, learn the discrete logarithm problem, and attack it with baby-step giant-step and Pohlig-Hellman.

Two people who have never met want to share a secret key, but every message they send can be read by an eavesdropper. This looks impossible, and until 1976 almost everyone thought it was. Then Whitfield Diffie and Martin Hellman published a method that uses nothing but modular exponentiation. It is still the foundation of the key exchange in TLS, SSH and Signal.

The method is secure as long as one problem stays hard: given g, p and g^x mod p, find x. This is the discrete logarithm problem. Exponentiation is fast; the inverse is believed to be slow. This lesson builds the protocol, then attacks it to see where its strength comes from.

The protocol

  1. Alice and Bob publicly agree on a prime p and a base g.
  2. Alice picks a secret a, sends A = g^a mod p.
  3. Bob picks a secret b, sends B = g^b mod p.
  4. Alice computes B^a = g^(ab); Bob computes A^b = g^(ab). Both hold the same secret g^(ab) mod p.

An eavesdropper sees p, g, A, B, but computing g^(ab) from them (the Diffie-Hellman problem) is believed to be as hard as finding a or b.

Python A key exchange in a dozen lines

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 two keys match, although neither secret ever crossed the wire. In practice the shared number is passed through a key-derivation function (a hash) to get a symmetric key.

Why it works, and the role of the order

The secret exponents live in the cyclic group generated by g. The order of g is the smallest k with g^k โ‰ก 1 (mod p). Exponents only matter modulo that order. If g has a small order, there are only a few possible keys, so a good g has large order, ideally a primitive root with order p - 1, or a generator of a large prime-order subgroup.

Python Order of an element and primitive roots

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.

Notice n_order(100, 101) = 2, because 100 โ‰ก -1. Using it as a base would give just two possible public values: a disaster. Group size matters.

Discrete logarithm by brute force

To break DH, the attacker solves g^x โ‰ก A. The naive method tries every x, which takes up to p steps.

Python Brute-force discrete log

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.

For a 20-bit prime this finishes at once, but each extra bit of p doubles the time. For a 2048-bit prime brute force is out of the question.

Baby-step giant-step

Shanks' algorithm trades memory for time. Write x = iยทm + j with m = โŒˆโˆšNโŒ‰ (N is the group order). Then g^x = h becomes h ยท (g^(-m))^i = g^j. Store the baby steps g^j for j < m in a table; then walk the giant steps hยทg^(-mi) until one lands in the table. The cost is about โˆšN multiplications and โˆšN memory.

Python Baby-step giant-step

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.

For this 41-bit prime brute force would need up to about 2^41 (two trillion) steps, while baby-step giant-step needs only about a million (2^20) table entries and steps: square root instead of linear. Real attacks on large groups use Pollard's rho for logs (same memory-free idea as the factoring rho) or index calculus.

Pohlig-Hellman: why safe primes exist

If the group order N = p - 1 factors into small primes, the discrete log splits into small sub-problems, one per prime-power factor, whose answers combine with the Chinese remainder theorem. The cost is then governed by the largest prime factor of the order, not by the order itself. That is why standards use safe primes, p = 2q + 1 with q prime, and work in the subgroup of order q.

Python Pohlig-Hellman breaks a smooth group

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.

When p - 1 is made of tiny primes the attack finishes in an instant, even though p is large. Contrast this with a safe prime, where p - 1 = 2q has one huge factor and the method gains nothing.

Man in the middle

Diffie-Hellman gives a shared secret, not identity. If Mallory intercepts A and B and substitutes her own values, she shares one key with Alice and another with Bob and silently relays everything. The remedy is authentication: signatures (for example the server's RSA or ECDSA certificate in TLS) bind the exchanged values to a known identity.

Python A man in the middle

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 output (True True False) says Mallory can read and re-encrypt all traffic, and Alice and Bob never notice that their keys differ.

ElGamal in one paragraph

Taher ElGamal turned DH into encryption: Bob's public key is B = g^b. To send m, Alice picks a random k, sends (g^k, mยทB^k). Bob computes (g^k)^b = B^k and divides. It is randomized by design, so equal messages encrypt differently.

Python ElGamal encryption

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.

sequenceDiagram
    participant A as Alice
    participant B as Bob
    A->>B: g^a mod p
    B->>A: g^b mod p
    Note over A,B: both compute g^(ab) mod p

The Diffie-Hellman exchange.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does an eavesdropper see in Diffie-Hellman?

    Secrets a and b stay private; the shared secret g^(ab) is hard to compute from the public values.
  2. 2. Baby-step giant-step finds a discrete log in about how many steps for a group of order N?

    m = sqrt(N) baby steps are stored and up to m giant steps are tried.
  3. 3. Why are safe primes p = 2q + 1 preferred?

    Pohlig-Hellman reduces the problem to the largest prime factor of the order.
  4. 4. How is a man-in-the-middle attack on DH prevented?

    DH alone gives no identity guarantee; signatures or certificates bind keys to parties.

Summary

  • Diffie-Hellman: A = g^a, B = g^b, shared secret g^(ab).
  • Security rests on the discrete logarithm problem; g must have large order.
  • Baby-step giant-step costs โˆšN; Pohlig-Hellman exploits smooth group orders, so use safe primes.
  • Unauthenticated DH is open to man-in-the-middle attacks.
  • ElGamal turns DH into randomized public-key encryption.

Next: Elliptic Curves over Finite Fields