Attack the Toy

Brute Force the Discrete Log

Tiny Diffie-Hellman groups can be searched directly. This lesson recovers Alice's secret by recomputing powers of the public generator.

highlighted = computed this step

Why the toy can be attacked

If p is tiny, an attacker can try exponents in order until a public value appears. The table recomputes g to the k power modulo p for each row.

gk mod pg^k\bmod p
Brute force the discrete logDiscrete log rows are recomputed until the target public value appears.Brute force the discrete log - recovered=6quantityvaluek=15k=22k=310k=44k=520k=6 recovered8

Target Alice's public value

Alice published A=8. The attacker tries k values until g to k equals that target.

A=8A=8
Brute force the discrete logDiscrete log rows are recomputed until the target public value appears.Brute force the discrete log - recovered=6quantityvaluek=15k=22k=310k=44k=520k=6 recovered8

Read the brute-force rows

The rows show 5, 2, 10, 4, 20, then 8.

g6 mod p=8g^6\bmod p=8
Brute force the discrete logDiscrete log rows are recomputed until the target public value appears.Brute force the discrete log - recovered=6quantityvaluek=15k=22k=310k=44k=520k=6 recovered8

Recover the secret

The hit row recovers Alice's exponent a=6. This is why deployed groups must be huge.

a=6a=6
Brute force the discrete logDiscrete log rows are recomputed until the target public value appears.Brute force the discrete log - recovered=6quantityvaluek=15k=22k=310k=44k=520k=6 recovered8

Summary

The toy discrete log recovers a=6. NOTE: toy-modulus; no-side-channel; no-production; never-roll-your-own. Exact arithmetic on a deliberately tiny toy modulus; real DH uses 2048+ bit groups inside authenticated reviewed protocols.

tiny group breaks instantly\text{tiny group breaks instantly}
Brute force the discrete logDiscrete log rows are recomputed until the target public value appears.Brute force the discrete log - recovered=6quantityvaluek=15k=22k=310k=44k=520k=6 recovered8