I'm reading the ECDSA paper and they say you can only use ECDSA with odd-power fields $p$ or with binary fields $2^m$. Why not other power prime fields?

  • 2
    $\begingroup$ Which ECDSA paper is that? The NIST one? If so, it is likely that it restricts to $\mathbb{F}_p$ and $\mathbb{F}_{{2}^{m}}$ because those are the only standardized curves. $\endgroup$ Aug 18 '15 at 9:25
  • $\begingroup$ yes the NIST paper @SamuelNeves this makes sense! Any idea if $\mathbb{F}_{p^m}$ for $p > 2$ is just idiotic? $\endgroup$ Aug 18 '15 at 15:17
  • 2
    $\begingroup$ In view of recent cryptanalysis advances for $\mathbb F_{2^m}$ type fields, I personally would not trust anything except $\mathbb F_p$ for large $p$. Using $\mathbb F_{p^m}$ has potentially the same risk, that someone might find an index-calculus style attack that lowers the security from $\approx p^m$ to $\approx p$ (and some constants), in which case extension fields would be a waste of effort. $\endgroup$
    – user2552
    Aug 18 '15 at 15:47
  • 2
    $\begingroup$ $\mathbb{F}_{p^m}$ can work, but it is a more brittle choice since a larger number of attacks have to be considered. It is not idiotic, but the (speed) advantages had better be worth it. As of right now, the only fields where there are considerable advantages are of the form $\mathbb{F}_{p^2}$ for large $p$. $\endgroup$ Aug 18 '15 at 16:15
  • 1
    $\begingroup$ @Bristol: Do you refer to the work by Wenger/Wolfger? They use Pollard's rho. The work by Joye (et al) uses index-calculus, but is about the discrete logarithm problem in $\mathbb{F}^\times$, not in elliptic curves. What research are you referring to? $\endgroup$
    – j.p.
    Oct 6 '15 at 16:05

Form a mathematical point of view, one can define ECDSA over arbitrary finite fields.

Form a security point of view, the most important thing is the size of the group order.

Arithmetic is easy in the case $GF(p)$.

Arithmetic gets more involved for $GF(p^m), m>1$, because you have to perform polynomial divisions.

Arithmetic in $GF(2^m)$ is easy again, because the polynomial division in $GF(2^m)$ can be done by simple feedback shift registers. This makes it especially well suited for implementation in hardware.

  • $\begingroup$ "Arithmetic gets more involved for $GF(p^m), m>1$..."; actually, the fastest known curve with circa 128 bit security is FourQ; it has $m=2$ (and $p= 2^{127}-1$) $\endgroup$
    – poncho
    Oct 3 '15 at 21:23
  • $\begingroup$ Exceptions prove the rule. In general, my statement is correct. And, it has surely more complicated arithmetic than standard curves. $\endgroup$
    – user27950
    Oct 3 '15 at 21:52

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.