3
$\begingroup$

I am trying to learn how ECDSA works. I do not have a background in maths, but have been following a guide which has built me up from finite fields, elliptic curves. I am unable to figure out how a signature is generated , a description of it is here.

To state what i understand.

  • e = private key
  • G = generator point
  • P = Public key
  • k = Ephemeral key

The public key is a point on the curve computed as

e.G = P

The signing algorithm starts by taking a random target R

kG = R

The guide straight up represents R as follows (where u/v are chosen by user):

uG + vP = kG

I sort of fail to understand how or why this relation holds true. It seems to be starting with a random point on the curve uG and it adds a scalar multiple of the public key (which could be further expressed v.e.G)

$\endgroup$
  • $\begingroup$ I suggest you to have a look at the wiki page about ECDSA, and then come back with questions if anything is not clear, as your question as is, doesn't really make sense. $\endgroup$ – Ruggero Mar 22 at 10:16
  • $\begingroup$ @Ruggero , the wiki page is just plain outlining equations without providing a description as to why. This might be due to my gap in maths. Please take a look at the link (tutorial) i am on as it seems to "dumb" it down for me to understand. We choose a R and inscribe its x co-ordinate in calculation of v and msg hash/s as u.Bottom line being , the verification algo is recomputation of R based on the above values. Yet i fail to understand how the above equality holds true to begin with. i.e a random R computed by addition of some multiple of pubkey and another random point. $\endgroup$ – Bobo Mar 22 at 11:52
  • $\begingroup$ I believe in your link, ecdsa is badly depicted and in my opinion it makes it much more complex, e.g. the way it throws you the $uG + vP = kG$ doesn't make sense. In the wiki you first see the signature generation, then the verification and then it explains why the verification works. $\endgroup$ – Ruggero Mar 22 at 13:59
2
$\begingroup$

Pick a coordinate field $\mathbb F_p$, such as $p = 2^{256} - 2^{32} - 977$. Pick an elliptic curve over $\mathbb F_p$ of the form $y^2 = x^3 + a x + b$, such as $a = 0$ and $b = 7$. (This is the curve secp256k1 used in Bitcoin.) Pick a standard base point $G$ of prime order $\ell$, so that $\ell$ is the smallest positive integer such that $$[\ell]G = \underbrace{G + \cdots + G}_{\text{$\ell$ times}} = \mathcal O.$$ Here $\mathcal O$ is the ‘point at infinity’, or the identity of the group.

An ECDSA public key is a point $P$ on the curve with coordinates $(x(P), y(P))$. An ECDSA signature on a message $m$ under $P$, is a pair $(r, s)$ of integers with $1 < r, s < \ell$ such that the verification equation $$r \equiv f\bigr([H(m) \, s^{-1}]G + [r s^{-1}]A\bigr) \pmod \ell$$ holds, where $f(A) = x(A) \bmod \ell$ is a kind of arbitrary function mapping the $x$ coordinate field $\mathbb F_p$ to the scalar ring $\mathbb Z/\ell\mathbb Z$ (which is a rather weird thing to do, but such is life).

The signer knows the secret scalar $e$ such that $P = [e]G$, in terms of which this equation is $$r = f\bigl([H(m)\,s^{-1}]G + [r s^{-1} e]G\bigr) = f\bigl([H(m) \, s^{-1} + r s^{-1} e]G\bigr),$$ which means the signer can choose a per-signature secret $k$ uniformly at random, derive $r = f([k]G)$, and then solve the scalar equation $$k \equiv H(m)\,s^{-1} + r s^{-1} e \pmod \ell$$ for $s$, by computing $$s := [H(m) \, k^{-1} + r k^{-1} e] \bmod \ell.$$

$\endgroup$

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.