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?

  • $\begingroup$ "square and multiply". Note that computing $a^b$ from $a^{\lfloor b/2\rfloor}$ can be done in at most two multiplications $\endgroup$ – Hagen von Eitzen Oct 14 '17 at 17:53
  • $\begingroup$ Can you please elaborate on how these principles help to solve the problems? $\endgroup$ – Vanilla Godzilla Oct 14 '17 at 17:58

Your Answer

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

Browse other questions tagged or ask your own question.