0
$\begingroup$

A noob question, I know, but given n in range [0,q-1], and given an elliptic curve point P, we calculate the public key Q=nP. By doing so, we calculate P+P=2P, 2P+P = 3P, and so we get the values P,2P,3P,...,nP. For the person trying to solve the discrete logarithm, P and Q is known. The brute force way would be to calculate P,2P,... until the result equals Q. Why is this harder than generating the public key? Where is the error here in how I think?

$\endgroup$
8
$\begingroup$

There are actually much more efficient algorithms to calculate the public key, such as the double-and-add method which calculates the public key in at most $2 \times \log_2(n)$ steps. For example, if $n = 11$, instead of calculating $P, 2P, 3P, ...$ up to $11P$, we can repeatedly double the current point or add $P$ to get to $11P$:

$$2P = P + P$$ $$4P = 2P + 2P$$ $$5P = 4P + P$$ $$10P = 5P + 5P$$ $$11P = 10P + P$$

This method has a running time of $O(\log(n))$, while a brute force attack has a running time of $O(n)$. For a $256$ bit key, the double-and-add method takes at most $512$ point additions, while a brute force search would take up to $2^{256}$ point additions.

$\endgroup$
  • 1
    $\begingroup$ To be fair, even a halfwitted attacker wouldn't try the $2^{256}$ point additions. While they may lack the amenity of a convenient algorithm to compute it in merely 512 point additions, they can apply Pollard's rho to find an answer in expected ${\sim}2^{128}$ point additions, which is a never-gonna-happenthfold better than the never-gonna-happen-squared that $2^{256}$ point additions is. $\endgroup$ – Squeamish Ossifrage Feb 6 '18 at 1:24

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.