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?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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.
-
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$ Feb 6, 2018 at 1:24