Breaking Diffie-Hellman:

Eve, the eavesdropper, knows and but not a or b.  Can she find a or b ?  That seems to require solving the discrete logarithm problem (DLP).  It's easy to solve equations like this in real numbers by taking logarithms.  But as far as we know, it's hard to solve these equations modulo p.

Hard Problem #1: The Discrete Logarithm Problem

Given , s and p, find a (if it exists) such that .

The fastest known algorithm for solving the DLP takes something about like

time units.  (The size of the time unit depends on things like how fast the computer is!)  For the fastest single computer today, it would probably take about 50 billion years to factor a number with 300 decimal digits.  However, with networked computers, a large company might be able to improve this by a factor of as much as 1 million!

On the other hand, finding a large prime p is very fast.  Finding a number p which is (probably) prime takes about

time units.  This looks large, but it isn't really; for a 300-digit number this should only take a few minutes.  (Calculating is even faster.)

Next Section