Diffie–Hellman key exchange, why it's hard to break it?

Question

I'm a bit confused why it's hard to break Diffie–Hellman

Let's take the example

ALICE has G, a, and n

BOB had G, b and n

Eve (the third party) succeded to intercept G, n, $G^a, G^b$

ALICE generate the key G^(ab) mod n

BOB generate same key G^ba mod n

What I don't understand is why Eve cant' get a or b by knowing G^a and G^b.?

For me he can just use dichotomy:

Eve will take a random number r_a.

    if G^r_a$ < G^a /* already known */
        increase(r_a); /* by power ietration for example, +1 +100, +1000, +10000 */
    else 
        decrease(r_a);
    adjust(r_a);

Answer 1

The straight-forward method you outlined doesn't work, because $G^a$ is not monotonic in $a$; we can have $G^{r_a} < G^a$ even though $r_a > a$. This happens because we're working modulo $n$, rather than doing exponentiation in the real numbers or integers.

For example, if we have $n=101$ and $G=2$ (for a toy example), then we have:

$$G^8 = 54 > G^{10} = 14$$

even though $8 < 10$

In fact, a practical method for doing probabilistic [1] evaluation of whether $a < b$ given $G^a \bmod n, G^b \bmod n$ (for the values of $n$ we actually use in cryptography) would be of great interest (and would essentially break all crypto based on modular exponentation)

---

[1] By probabilistic evaluation, I mean that the method doesn't have to give us the correct answer in all cases; it would be sufficient if it was correct with some probability somewhat more than 0.5