3
$\begingroup$

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)?

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ 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. $\endgroup$
    – MaiaVictor
    Commented Jul 9, 2021 at 5:22
  • $\begingroup$ 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). $\endgroup$
    – James
    Commented Jul 9, 2021 at 5:28
  • 2
    $\begingroup$ 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. $\endgroup$
    – dave_thompson_085
    Commented Jul 9, 2021 at 5:46
  • 4
    $\begingroup$ 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. $\endgroup$
    – fgrieu ♦
    Commented Jul 9, 2021 at 6:48
  • 1
    $\begingroup$ "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 $\endgroup$
    – PrincePolka
    Commented Jul 9, 2021 at 15:50

1 Answer 1

Reset to default
5
$\begingroup$

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).

Improve this answer
$\endgroup$
4
  • 4
    $\begingroup$ 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$. $\endgroup$
    – AAA
    Commented Jul 9, 2021 at 16:17
  • 1
    $\begingroup$ 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)? $\endgroup$
    – James
    Commented Jul 10, 2021 at 13:52
  • 1
    $\begingroup$ As an additional alternative, if there is so much worry about Quantum Computing perhaps being able to attack encryption of smaller key sizes, wouldn't it be sufficiently possible to create an Elliptic Curve Cryptosystem with large key sizes without taking too long to calculate (1024 operations doesn't seem like it would take too long for a modern computer to perform, even if each operation took 1,000,000 nanoseconds to perform)? $\endgroup$
    – James
    Commented Jul 10, 2021 at 13:57
  • $\begingroup$ @AAA is there any publicly known implementation of baby-step giant-step for Elliptic Curve Encryption? $\endgroup$
    – Gabriel Garrett
    Commented Dec 27, 2021 at 6:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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