Secrets from Primes

Diffie–Hellman calculator

Choose a prime p, a base g and the two private secrets. Teaching-sized, so not secure.

Both sides compute the same shared secret without sending it. The prime is checked exactly (up to 24 digits) and the order of g is shown. Real Diffie–Hellman uses primes of 2048 bits or more, or elliptic curves.

How the exchange works

Alice and Bob agree in public on a prime p and a base g. Alice chooses a secret a and sends A = ga mod p; Bob chooses a secret b and sends B = gb mod p. Alice computes Ba mod p and Bob computes Ab mod p. Both equal gab mod p, the shared secret, which never travels[1][2].

The calculator proves that p is prime (up to 24 digits) and checks 2 ≤ g ≤ p − 2 and 1 ≤ a, b ≤ p − 2. It also reports the order of g: how many different values gx mod p takes. If the order is p − 1, g is a generator and the secret can be any of p − 1 values; a smaller order shrinks the space an eavesdropper must search.

Worked example

With p = 23 and g = 5 (a generator: its order is 22), Alice picks a = 6 and sends 56 mod 23 = 8. Bob picks b = 15 and sends 515 mod 23 = 19. Alice computes 196 mod 23 = 2; Bob computes 815 mod 23 = 2. The shared secret is 2.

What the eavesdropper faces

Eve sees p, g, A and B. To find the secret she must in effect recover a from A = ga mod p, a discrete logarithm. Let Eve search tries a = 0, 1, 2, … in order, up to two million tries: immediate for p = 23, hopeless for a 19-digit prime. Faster algorithms exist, but for well-chosen primes of 2048 bits none is known to finish[3]. Real systems also authenticate the exchange, since an attacker who can alter messages could otherwise run separate exchanges with Alice and Bob. This calculator does neither, so use it only to learn.

Sources

  1. W. Diffie and M. E. Hellman (1976). New directions in cryptography. IEEE Transactions on Information Theory 22 (6), 644–654. doi:10.1109/TIT.1976.1055638. paper
  2. Victor Shoup (2008). A Computational Introduction to Number Theory and Algebra, 2nd edition (Version 2, free PDF). Cambridge University Press. ISBN 9780521516440. textbook
  3. E. Barker (2020). Recommendation for Key Management: Part 1 – General (SP 800-57 Part 1 Rev. 5), §5.6.1.1 and Table 2. National Institute of Standards and Technology. doi:10.6028/NIST.SP.800-57pt1r5. standard