5
$\begingroup$

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?

$\endgroup$
6
  • 3
    $\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, 2015 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, 2015 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, 2015 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, 2015 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, 2015 at 16:05

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
2
  • $\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, 2015 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, 2015 at 21:52
1
$\begingroup$

Note that ECDLP over extension fields is not necessarily harder than ECDLP over the underlying field of prime characteristic, simply because for any power of prime $q$, $E(\mathbb{F}_{q})$ is a subgroup of $E(\mathbb{F}_{q^n})$ and, by Lagrange's theorem, $|E(\mathbb{F}_{q^n})|$ is divisible by $|E(\mathbb{F}_{q})|$. If this happens to be the largest factor, then there is no security gained when using the extended curve.

With $n = 2$, one even has that $|E(\mathbb{F}_{q^2})| = |E(\mathbb{F}_{q})|(2q + 2 - |E(\mathbb{F}_{q})|)$ (see e.g. Silverman AOE, exercise 5.13, and in general, see Weil's conjectures).

Now, it is not clear how this applies to ECDSA, since its exact security is not known, so we cannot rule out the possibility of a different way of exploiting ECDSA with the added structure.

EDIT: I should also point out that ECDSA is defined in a subgroup of prime order, and the spec requires to check that the order is prime. It is not clear if security is reduced if the order is (almost) the product of two large primes, but that would be surprising to me.

$\endgroup$

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.