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 thatp=23
andg=5
.- Alice chooses a secret integer
a
whose value is 6 and computesA = 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
A
to Bob and Bob sendsB
to alice.- To obtain the shared secret, Alice computes
s = B^a mod p
. In this example, Alice obtains the value ofs=2
- To obtain the shared secret, Bob computes
s = A^b mod p
. In this example, Bob obtains the vlaue ofs=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
?