Manual ECDSA signing

Question

I'm trying to understand the step by step process of ECDSA signature. The function should be as follows: S = k^-1 (hash + dA * R) mod p, but I'm trying to understand whether I'm implementing it correctly. In order to run an example, I'll borrow an actual use-case from Bitcoin.

The variables will be as follows: hash: 13981225937542801152472832285710043259607809420725863171548640618989758767092 k: 11253563012059685825953619222107823549092147699031672238385790369351542642469 dA: 32678163117146052705943574521051490808324525286453391448021727749576063492292 p: 115792089237316195423570985008687907853269984665640564039457584007908834671663 R: 36422191471907241029883925342251831624200921388586025344128047678873736520530

First part I'm trying to understand, is what does k^-1 mean. Is it an inversed version of k (same way it's used when generating a public key)? Assuming that it is, we end up with the following equation:

S = 46845980742442032273496636384730466168994452136155887088844811385771348454723 * (13981225937542801152472832285710043259607809420725863171548640618989758767092 + 32678163117146052705943574521051490808324525286453391448021727749576063492292 * 36422191471907241029883925342251831624200921388586025344128047678873736520530) MOD 115792089237316195423570985008687907853269984665640564039457584007908834671663

Which gives us 47948206650808861643197644356522075407904568696590364200235146232910054391376 and in hex: 6A01B9263C7233181FEE2661C53E75C14312A7F4A2426EAEEA3502DCC40F7E50.

However, its length seems to be only half of a valid signature. Did I do the math correctly? Is this only a part of the signature and the rest is generated separately?

Answer 1

What does $k^{-1}$ mean?

In the question's formula $S=k^{-1}(\mathrm{hash}+d_A\cdot R)\bmod p$ , the term $k^{-1}$ is a (or the) multiplicative inverse of $k$ modulo $p$. By definition, that is an integer $i$ such that $(i\cdot k)\equiv1\pmod p$ , that is an integer $i$ such that $p$ divides $(i\cdot k)-1$ (or if we want the multiplicative inverse, additionally $i$ must be such that $0<i<p$ ). Which multiplicative inverse we take does not change the result $S$ .

$k^{-1}$ can be computed using the (half-)extended Euclidean algorithm (see this ); or other methods. Whatever was used, the question has $S$ matching $k$, $\mathrm{hash}$, $d_A$, $R$ and $p$ , and the equation given. But see below why $S$ is wrong.

Its length seems to be only half of a valid signature

Indeed. That's because the signature is $(R,S)$ per some convention; like concatenation of fixed-length octet strings representing $R$ and $S$ per big-endian convention, perhaps with some prefix.

---

Comment on the equation

Oh, I had missed that initially: the question's equation $S=k^{-1}(\mathrm{hash}+d_A\cdot R)\bmod p$ is wrong! There is confusion between the order $p$ of the field (used for coordinates on the elliptic curve secp256k1), and the order $n$ of the point $G$ on the elliptic curve (which for secp256k1 is also the number of points on the elliptic curve, including the point at infinity). The correct equation is $S=k^{-1}(\mathrm{hash}+d_A\cdot R)\bmod n$ . For secp256k1, $n$ is 115792089237316195423570985008687907852837564279074904382605163141518161494337 . That changes $S$ , of course.

If the equation only gives us $R$, how can we get $S$ ?

We obtain $S$ using the equation $S=k^{-1}(\mathrm{hash}+d_A\cdot R)\bmod n$ starting from $k$, $\mathrm{hash}$, $d_A$, $R$ and $n$ .

We must previously have obtained $R$ by computing $k\times G$ . That's by point multiplication on the elliptic curve secp256k1, using arithmetic modulo $p$ (this is not a typo), keeping the $X$ coordinate, and deducing $R$ . The normative way is to compute $R=X\bmod n$ (after having reduced $X$ modulo $p$ so that $0\le X<p$ ), and redoing from start with another $k$ when $R=0$ . However in practice, if we do no get $0<X<n$ , then the process by which $k$ was chosen and $X$ computed is almost certainly broken, and in all other cases $R=X$ .

Update: I confirm that the question's $R$ matches the question's $k$ . Thus all that remains to do is compute $S$ using the appropriate modulus, and format $(R,S)$ into the signature.