Calculating $s$ in ECDSA over $GF(2^m)$

Question

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.

Answer 1

Since you're calculating a scalar multiplication value, and the base point has order $q$, you should calculate $s$ in the field $\mathbb{Z}/q\mathbb{Z}$, not in $GF(2^m)$. In particular, this means that you can't use xor or polynomial division to implement addition and modular reduction, but should use regular addition and division instead.

For example, this should give you the value for $k^{-1}$ as:

$$k^{-1} \equiv 2315871241563531210130617073628712209517930583176 \pmod q$$

which is 1 95A7 4210 396D 0D19 E522 8C83 6815 E728 EFD7 9488 in hexadecimal notation.

Since $q$ is prime, the order of $\mathbb{Z}/q\mathbb{Z}$ is $q-1$, so you can easily calculate the inverse of $k$, and then calculate $s$. This gives the correct output:

>>> q = int('4000000000000000000020108A2E0CC0D99F8A5EF', 16)
>>> x = int('09A4D6792295A7F730FC3F2B49CBC0F62E862272F', 16)
>>> k = int('23AF4074C90A02B3FE61D286D5C87F425E6BDD81B', 16)
>>> m = int('5795edf0d54db760f156f0eb4a7a0fe38d418e813', 16)
>>> r = int('113A63990598A3828C407C0F4D2438D990DF99A7F', 16)
>>> k_inverse = pow(k, q-2, q)
>>> s = (k_inverse * (m + r * x)) % q
>>> '%X' % s
'1313A2E03F5412DDB296A22E2C455335545672D9F'