Score:1

ECDSA - generating a new private key each time we sign?

mz flag

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.

kelalaka avatar
in flag
Could you show us how can you solve the DLog on a curve of size> 256?
Score:3
ru flag

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.

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.