3
$\begingroup$

I've been reading about ECC, and what I've established so far (correct me if I'm wrong) is that:

pubKey = privKey * G

where G is some special point on the secp256k1 curve.

Doesn't this mean we could attempt to brute force a private key by using:

privKey = pubKey/G

for all potential values of G.

I know it would require some unfeasible amount of attempts, but what if by chance that one of the first few attempts happened to have the correct value?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
7
$\begingroup$

Doesn't this mean we could attempt to brute force a private key by using:
$$\mathit{privKey} = \mathit{pubKey}/G$$ for all potential values of $G$?

There seems to be a misunderstanding here: $\mathit{pubKey}$ and $G$ are fixed and publicly known, so there's nothing left to brute-force. The operation of "dividing" $\mathit{pubKey}$ by $G$ is (to the best of current public knowledge) computationally infeasible; this is the elliptic-curve discrete logarithm problem (ECDLP). However, of course, one can brute-force by trying all possible values of $\mathit{privKey}$ and checking whether $\mathit{privKey}\cdot G=\mathit{pubKey}$ holds.

what if by chance that one of the first few attempts happened to have the correct value?

This is very much related to this recent question. The bottom line is: Yes, that could happen, but the probability is so incredibly low it is never going to occur in practice. (And in any case, if we're worried about someone just guessing our secret keys by pure luck, there's nothing anyone could do against it anyway.)

Improve this answer
$\endgroup$
1
  • 7
    $\begingroup$ Going a step further, a lucky adversary could guess the plaintext and they don't need the key or ciphertext. In fact they could guess the message before you send it, before you encrypt it, before you think of it, before you generate the key, and before you are born. $\endgroup$
    – dave_thompson_085
    Feb 26, 2017 at 6:39
-1
$\begingroup$

  1. primitive methods defined here

  2. curve domain parameters available here

  3. check whether public_key_xy = scalar_mult(private_key,curve.g) matches expected target

Improve this answer
$\endgroup$
1
  • $\begingroup$ Why do you not link official documents from secg.org ? What is your answer trying to address? $\endgroup$
    – DannyNiu
    Dec 31, 2019 at 8:36

Your Answer

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

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