Cracking Elliptic Curve Cryptography

I am quite new to the study of elliptic curve cryptography and as such I might be asking something with a mundane solution, but I can't easily find such a solution online. My understanding of ECC is that you can generate a private key (some integer $$k$$), a starting point on the curve ($$G$$), and a curve equation, and then generate a public key through finding $$kG$$. My understanding is then that your computer would perform however many operations are required to find $$kG$$ (if $$k$$ was 16 then that would be four operations).

With this data the starting point $$G$$, the curve equation, and the public key is made public. What I am wondering is why can't an attacker try to find out what the private key $$k$$ simply is, take the starting point and perform operations until they reach the public key and as such know what $$k$$ is? Is it based in the fact that the sender only needs 4 operations to calculate $$kG$$ whereas the attacker would need 16 operations (for the given example)?

• You need to guess a private key before you start doing the operations. If we're talking about 256-bit private keys, there are 2^256 keys to try. You'll only reach the target's public key if you guessed the correct private key. That means that, if you pick a random private key and perform operations hoping to reach the target's public key, there is only 0.0000000000...(+66 zeros)...8 chance of success per try. Jul 9 '21 at 5:22
• But if the user's computer for instance took 10 computation to calculate a public key (a simplistic example), the attacker's computer would only need to start at $G$ and perform about 1024 computations to reach the point of $kG$. I can see this is potentially quite a large difference, but it seems like a supercomputer could get through a bigger example within a finite amount of time (weeks or so). Jul 9 '21 at 5:28
• For the sizes currently considered secure (256 or 255 bit up) this 'attack' takes more energy than exists in the universe. You need to control huge numbers -- trillions of trillions -- of other universes, which means you must be a god, and your profile does not identify you as a god. See crypto.stackexchange.com/questions/58373/… and more linked there. Jul 9 '21 at 5:46
• See the wheat and chessboard parable, only with a larger chessboard when it comes to actually used Elliptic Curves (where $k$ can take $n\approx2^{256}$ values). Incidentally, "take the starting point and perform operations until they reach the public key" is far from the best strategy: if there are $n$ possible values of $k$, it requires $\Theta(n)$ steps, when there are strategies that require only $\Theta(\sqrt n)$ steps.
– fgrieu
Jul 9 '21 at 6:48
• "Is it based in the fact that the sender only needs 4 operations to calculate kG whereas the attacker would need 16 operations (for the given example)?" Yes Jul 9 '21 at 15:50

To compute $$kG$$ you need $$O(log(k))$$ operations. (For every bit, double the result and and additionally add $$G$$ if bit is $$1$$). As you mentioned in a comment for around $$k=1024$$ you would need like $$10$$ operations to compute $$kG$$. But this example is way to small for practical use and the exponential effect does not really kick in yet. Normally, when the curve has order around $$2^n$$, $$k$$ would be of a similar magnitude as $$2^n$$.
So for curves with order $$2^{256}$$ish you need around $$log(2^{256})=256$$ operations to compute $$kG$$ but $$2^{256}$$ to attack it. There is only a problem with absurdly small curves with order of maybe up to a few billion or trillion (like in your example).
• You can do better than $2^{256}$. You can use baby-step giant-step to recover $k$ in roughly $2^{128}$ time. Nevertheless, the point stands: it takes polynomial time to compute $kG$, but the best known attacks require exponential time to recover $k$.
• If we are able to say that as an example a computer can calculate 80,000,000,000 operations per a second (eighty computers performing an operation each nano-second), which is approximately $2^{36}$ operations per second, and the fastest attacks can find the key in $2^{n/2}$ operations where $n$ is the key size, wouldn't a key size of 138 be sufficient to essentially make any attack unviable (taking approximately 3200 years to calculate)? Jul 10 '21 at 13:52