1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ There is no way you can manually make an ECDSA signature. $\endgroup$ – Melab Jan 13 '18 at 11:34
  • $\begingroup$ By manually, I meant signing a message without an external library. $\endgroup$ – user2298995 Jan 13 '18 at 12:57
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks for your answer. Can you please comment on the equation and final result I received? Is it correct? Also, if the equation only gives us R, how can we get S? $\endgroup$ – user2298995 Jan 13 '18 at 18:00

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.