# Brute forcing an elliptic curve encrypted key

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?

## 2 Answers

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

• 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. – dave_thompson_085 Feb 26 '17 at 6:39
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

• Why do you not link official documents from secg.org ? What is your answer trying to address? – DannyNiu Dec 31 '19 at 8:36