discrete logarithm problem of ecc

Question

I have read a lot about the discrete logarithm problem of ecc, but I still do not understand the problem as follows:

We have domain parameters: (p, E, P, n, h), where n is the order group of P.

The process of creating privatekey - publickey is as follows:

1. Select a random number k under [1, n - 1]
2. Calculate Q = kP
3. Return Q is publickey, k is privatekey.

As far as I know, domain paramters and Q will be public. But, suppose I was the eavesdropper, I know P produces 1000 points (as the parameter n), because Q = kP so Q will be a point in point set generated by P, so I can generate order group P and see the position of Q for privatekey k (since k is in [1, n-1]).

For example: P generate 0P, P, 2P, 3P, ... 1000P. I choose k under [1,999] is 120 -> Q = 120P -> position of Q in the order group P is 120 -> k = 120.

So if I know P and Q, then I know privatekey then ??? So where is it safe?

I suppose so because NIST gives you some recommended domain parameters and I think the order group has to be pre-calculated to save on computational cost.

Thank you for everyone's help!

Answer 1

The poblem of computing the private key $d$ from the public key $Q$ is indeed referred to as $ECDLP$. It is crucial that you choose the domain parameters so that the $ECDLP$ is intractable. Concerning your choice of $d$ ... it is too small and can thus be computed efficiently. Imagine $d$ not having 7 Bits like in your example but 192-, 384- or even 512 Bits. You wouldn't get very far using your method (or any other currently known and implementable algorithm).

In order for the $ECDLP$ to be intractable, $d$ must be adequately chosen so that you cannot just brute-force all values for $d$ until you find a $d$ so that $dP = Q$. This is why curves that are considered as secure today use large values for $n$ and $p$ and create a random value $d$ in the range $[1\dots n-1]$.