ECDSA over $\mathbb{F}_{p^n}$ for $n>1$. How to calculate $r$ and $s$

Question

I'm having some trouble understanding how to calculate $r$ and $s$ as specified in the wikipedia page for ECDSA (https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm)

We can see on step 4 of the signature generation algorithm that they calculate the following:

$r = x_1 \text{mod}\ n$, where $n$ is the order of the group.

However, $x_1$ is an element of $F_{p^m}$, which for $m > 1$ it doesn't make sense to compute it's remainder over an integer.

Similarly on the next step they calculate $s = k^{-1} * (z + r d_A)\ \text{mod}\ n$. However, here I also do not understand what operation they are refering to when they write $z + r d_A$, since $z$ is a number and $rd_A$ is a curve point.

Surely I must be missing something very obvious but I cant figure out what. For $r$ it occurs to me that you could just take the modulus over the corresponding field element to $n$, since all the elements of $F_p$ are also in $F_{p^n}$.

For calculating $z + rd_A$ I'm at a loss though, how do you calculate the sum of an Integer and an element of $F_q$?

Answer 1

However, $x_1$ is an element of $\mathbb{F}_{p^m}$, which for $m>1$ it doesn't make sense to compute it's remainder over an integer.

True; when they defined ECDSA, they did not consider curves over extension fields. This means that ECDSA just isn't defined in that case.

Now, it wouldn't be unreasonable to extend ECDSA to cover that case; the requirement for the $kG$ to $r$ mapping is that it $r$ be computationally uncorrelated to $k$; you might (once you've defined the field representation) treat $x_1$ as an $m$ digit number in the base $p$, and then take that value modulo $n$ (which might be what you suggested...). Of course, any such extension would need to be analyzed before usage...

Also, as for your objection "$r d_A$ is a curve point", no, it is not. $d_A$ is the private key, which is an integer between 0 and $n-1$