1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ "$rd_A$ is a curve point; nope; both $r$ and $d_A$ are integers. $\endgroup$ – poncho Apr 18 at 18:29
1
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ ECDSA (and ECDH) is defined for p^m m>1 when p=2 (only), but that variant is massively unpopular and very little used -- apparently fortunately so, as I believe there have been some advances against curves over small-characteristic fields, and 2 certainly qualifies as small. $\endgroup$ – dave_thompson_085 Apr 19 at 1:03

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.