I'm reading the Wikipedia entry where we have
- Alice and Bob agrees on a prime number,
p, and a base,
g, in advance. For our example, let's assume that
- Alice chooses a secret integer
awhose value is 6 and computes
A = g^a mod p. In this example, A has the value of 8.
- 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.
- Alice sends
Ato Bob and Bob sends
- To obtain the shared secret, Alice computes
s = B^a mod p. In this example, Alice obtains the value of
- To obtain the shared secret, Bob computes
s = A^b mod p. In this example, Bob obtains the vlaue of
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=g^a mod p or
B = g^b mod p but that both of these can only be done by guessing every number from
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