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?

$\endgroup$
5
$\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.)

$\endgroup$
  • 5
    $\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 '17 at 6:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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