I am implementing ECDSA over $GF(2^n)$. I am following RFC 6979 and compare my results with the example in Appendix A (which uses curve SECT163K1).
My calculation of $r$ is correct, but I am struggling with $s$.
A few parameters determine $s$ and I am not sure which one I got right and which wrong.
$s=k^{-1} * (m + r * d_A) \mod q$
$q$ is the order of the curve's generator (in other sources refered to as $n$). $r$ is correct/was given and $d_A$ was given, which leaves $k^{-1}$ and $m$.
m
The hash of the message is h1 = AF2B DBE1 AA9B 6EC1 E2AD E1D6 94F4 1FC7 1A83 1D02 68E9 8915 6211 3D8A 62AD D1BF
, which is shortened with bits2int(h1, 163)
. I presume it to be correct.
m = 5795 edf0 d54d b760f 156f 0eb4 a7a0 fe38 d418 e813
$k^{-1}$
The value of $k$ was given in the example with 2 3AF4 074C 90A0 2B3F E61D 286D 5C87 F425 E6BD D81B
. I calculated $k^{2^{162}-2} \mod q$ to get. I checked it with $k^{-1}*k = 1$. The algorithm also works with other curves and $k$'s. I also checked the results against the Python package BitVector, which also implements a modular inversion in $GF(2^n)$.
k^-1 = 3 759d 2532 cdd0 d539 5f03 eaed b650 3045 d218 9bad
I implemented all operations in "binary" (i.e. addition as xor, mod as polynomial division, ...).
Other intermediate results:
$r * d_A$: 14d1 14fe1 04b4 a34f 3bf6 fd30 02aa f767 3ed8 c786
$m + r * d_A$: 4 344f 90ec 506f d540 2e99 f384 a50a 095f eac0 2f95
$s$: b957 16f7 2680 def2 d19f d596 6a2e 93fe 8c0c fea9
Question
What goes wrong, where is the error?
I can also post my (Python) code, but I would have to clean it up first.