A main premise of the Diffie_Hellman key exchange is that calculating a public key from a private key is less complex than calculating a private key from a public key. What are those computational complexitites?
Private variables:
- $Xi\ $ is the private key of user $i$.
- $Xj\ $ is the private key of user $j$.
Public variables:
- $q\ $ is a prime number > $1$
- $g\ $ is a whole number, $1 <= g <= q-1$
- $Yi = g^{Xi} mod\ q\ $ is user $i$'s public key.
- $Yj = g^{Xj} mod\ q\ $ is user $j$'s public key.
The paper claims that the calculation of Y from X, as seen above, requires at most $2 * log_2(q)$ multiplications. Is that correct? It seems to me that the complexity is $X$ multiplications + 1 division. Unless $q$ is a power of $g$ in which case we know right away that the remainder $Y$ is $0$. How do we quantify the complexity here?
An eavesdropper, knowing the values of the public variables, calculates a private key $Xi$ like so:
$g^{Xi} mod\ q = Yi$
$\frac{g^{Xi}}{q} = n + \frac{Yi}{q}$
$g^{Xi} = qn + Yi$
$Xi = log_g(qn + Yi)$
Having two unknown variables ($Xi$ and $n$) and one equation, this equation should have infinitely many solutions. How can we define a computational complexity for calculating $Xi$ (or similarly $Xj$)?
The paper claims that a private key X can be calculated by an eavesdropper like this:
$X = log_g(Y)\ mod\ q$
It also claims that the complexity should be $q^{1/2}$ operations for carefully selected values of $q$. How is that so?