Diffie-Hellman protocol: Clarifications

Question

I'm reading the Wikipedia entry where we have

1. Alice and Bob agrees on a prime number, p, and a base, g, in advance. For our example, let's assume that p=23 and g=5.
2. Alice chooses a secret integer a whose value is 6 and computes A = g^a mod p. In this example, A has the value of 8.
3. Bob chooses a secret integer b whose value is 15 and computes B = g^b mod p. In this example, B has the value of 19.
4. Alice sends A to Bob and Bob sends B to alice.
5. To obtain the shared secret, Alice computes s = B^a mod p. In this example, Alice obtains the value of s=2
6. To obtain the shared secret, Bob computes s = A^b mod p. In this example, Bob obtains the vlaue of s=2.

Now, I understand that the protocol is not unbreakable but it works because there is no efficient way to figure out the secret number for Eve quickly.

Is it correct that the main task for Eve is to solve for either a from A=g^a mod p or b from B = g^b mod p but that both of these can only be done by guessing every number from 1 to p-1 (worst case)?

If so, why is this considered more than polynomially hard since the computation is linear in the size of the prime p?

Answer 1

Your assumption is correct, that is called the Discrete Logarithm Problem.

The complexity of the problem is linear to the number of elements of the group but exponential to the number of bits of the group's size (These days you usually use a 2048 bit prime for a DH exchange, meaning that there are ~ 2^2048 elements in the group)