ECDSA signing process

Question

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)

Answer 1

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