1
$\begingroup$

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!

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Consider that in a practical parametrization, $n$ and $k$ have at least 48 decimal digits, rather than 3 in your example. $\endgroup$ – fgrieu♦ Jul 3 '17 at 11:49
1
$\begingroup$

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]$.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ Correction: crypto libraries do not set the msbit of $d$ in order to make brute-force search (or even a square-root time search) harder; it's easy to show it doesn't. Now, there are libraries that do set the msbit, but those libraries do it for subtler reasons (dealing with potential side channel attacks) $\endgroup$ – poncho Jul 3 '17 at 11:22
  • $\begingroup$ Oh good to know! I edited the msb part! $\endgroup$ – TrinityTonic Jul 3 '17 at 16:59

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.