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

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$$?

• "$rd_A$ is a curve point; nope; both $r$ and $d_A$ are integers. Apr 18, 2019 at 18:29

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.
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$$