1
$\begingroup$

So, I kinda get the mathematics behind the ECDSA, but I can't seem to find precise information about private key generation. In other words, do we have to generate private key, each time we generate a signature? Coz, if a public key is known, then through using the discrete logarithm we can get the private key, and thus we have a problem.

$\endgroup$
1
  • $\begingroup$ Could you show us how can you solve the DLog on a curve of size> 256? $\endgroup$
    – kelalaka
    Nov 4, 2021 at 10:33

1 Answer 1

3
$\begingroup$

There are two secret values associated with an ECDSA signature: one long term and one single-use. In the notation of the Wikipedia ECDSA article, there is the private (signing) key $d_a$ and corresponding public (verification) key $Q_A$ which is related to the private key by $Q_A=d_AG$ where $G$ is a publicly known generator for the elliptic curve group. The elliptic curve group should be chosen so that recovering $d_A$ from $Q_A$ is infeasible. This is known as the elliptic curve discrete logarithm problem.

However, in the generation of each signature there is another value $k$ which must remain secret. This is because the signature will produce two values $(r,s)$ which satisfy $$ks\equiv h+rd_A\pmod\ell$$ where $h$ is the (known) hash value of the data being signed. If $k$ is known then $d_A$ can be computed from the above equation. Moreover, if the same $k$ value is ever used in two different signatures, the same $r$ value is produced so that the signatures are $(r,s_1)$and $(r,s_2)$. We then have $$s_1h_2+s_1rd_A\equiv s_2h_1+s_2rd_A\pmod\ell\Rightarrow s_1h_2-s_2h_1\equiv (s_2-s_1)rd_A\pmod\ell$$ and again $d_A$ can be recovered.

Thus although $Q_A$ (and hence $d_A$) can be used multiple times, it is vital that each $k$ is used at most once. Failure to do this led to the infamous PS3 failure among others.

$\endgroup$

Your Answer

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

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