# ECDSA signing process

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)

• 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. – Ruggero Mar 22 '19 at 10:16
• @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. – Bobo Mar 22 '19 at 11:52
• 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. – Ruggero Mar 22 '19 at 13:59

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