0
$\begingroup$

I am learning ECC, I am confused a bit how it works for now. To my understanding, G is the starting point, k is how many times you apply the dot operation. And Q is the public key, which is the final point after you apply k times dot operations, like this

Q = kG

And then Q is the public key, and k is the private key. We assume it's really hard to find k given Q and G are known. The thing I don't understand (or I misunderstood) is, if the creator of this pair of key, can calculate k times of G to get Q easily in a reasonable amount of time, why can't attacker do the same? I can start from 1 dot operation, then 2 dot operations .... and eventually, I will hit a point that's the same as Q, and because the creator already did this in a reasonable amount of time, so I guess I can do it too (as they need to do k times of operation for thing like Diffie–Hellman)? And if k is super huge, doesn't it take the creator to take a super long time to generate and use it for key exchange? But I don't think it will be that easy, otherwise, it will be useless, just not sure which part I missed.

$\endgroup$

marked as duplicate by kelalaka, AleksanderRas, Maeher, Maarten Bodewes Sep 9 at 9:34

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

3
$\begingroup$

The creator of the key pair can do it efficiently because he has to calculate $kG$ for only one value of $k$. The cost would be something like $\log(k)$ elliptic curve operations. It's very small.

What you propose is to compute $1G$, $2G$, until you reach $kG$. Since $k$ is a big number (something like $2^{256}$, it is very big), then you have to do $2^{256}$ times more operations than the creator. It is very big.

$\endgroup$
  • $\begingroup$ thanks you so much, also thanks to @fgrieu, the missing part is that I didn't know there's a faster way to calculate kG. Since at very, I thought the dot operation is just something you can do one by one, but it turns out they are actually a field, where you can do double and add to get a crazy huge number easily. $\endgroup$ – Fang-Pen Lin Sep 5 at 1:21

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