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 */


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

| improve this answer | |
  • 1
    $\begingroup$ now I got it :$ (g^b \bmod{n})^a \bmod{n} = (g^a \bmod{n})^b \bmod{n}$ . hard to prove but this is the secret $\endgroup$ – mikmik Apr 4 at 21:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.