33
$\begingroup$

In cryptography, an elliptic curve is a group based on a finite field $GF(p^k)$; this group has $n$ elements on it, and we work on a prime-sized subgroup of size $q$. We denote the value $h = n/q$ as the cofactor of the curve.

My question is: why would we ever want to consider using a curve which has a cofactor $h>1$? Or, in other words, why would we consider using an elliptic curve that had a composite number of points? After all, the discrete log problem can be solved in $O(\sqrt{n / h})$ time; if we were to select a curve with $h>1$, we are deliberately making this problem easier.

Now, if $h$ is small, we're not making it much easier; if (for example) $p^k \ge 2^{256}$ and $h \le 4$, this would still appear to be an intractible problem. On the other hand, I don't know if we want to make the attacker's job any easier than necessary, unless we gain some other benefit from it (perhaps making some other attack harder, or gaining some computational efficiency).

So, is there any benefit for using a curve with a cofactor > 1?

Improve this question
$\endgroup$
1
  • $\begingroup$ Is there a method for producing a curve with cofactor 1? Isn't it enough to make sure that $q$ is large? $\endgroup$
    – Myath
    Apr 18, 2016 at 19:46

3 Answers 3

Reset to default
20
$\begingroup$

I do not have any hard data to back this up, but an educated guess is that relaxing the cofactor to be "small" instead of "1" was done to allow Koblitz curves — which in early days looked like an attractive choice for implementation.

Koblitz curves over binary fields are of the form $y^2 + xy = x^3 + a x^2 + 1$.
The cofactor is at least $4$ when $a = 0$, and $2$ when $a = 1$.

Improve this answer
$\endgroup$
3
  • 3
    $\begingroup$ I did a bit more research, and it turns out that with any even characteristic curves (p=2), then the number of points is almost always even. In particular, if k is odd, then the number of points would always be even unless it happens to be in the form $2^k+ i 2^{(k+1)/2} + 1$ for $i \in (-1, 0, 1)$ (and I suspect those don't correspond to curves you'd want to do cryptography in). So, yes, it would appear that they allow $h>1$ to allow even characteristic curves. $\endgroup$
    – poncho
    Jun 13, 2012 at 13:46
  • $\begingroup$ Yeah, you're right. Whenever the $xy$ coefficient is nonzero, there's a trivial order 2 point. When it's not, you get either singular (unusable) or supersingular (weaker) curves. $\endgroup$
    – Samuel Neves
    Jun 13, 2012 at 18:15
  • $\begingroup$ then why we do care about even characteristic curves that imply even number of points since they are not secure? $\endgroup$
    – curious
    Apr 21, 2013 at 14:51
27
$\begingroup$

Montgomery and twisted Edwards curves have even order, but the group law can be implemented using multiplication which is usually fast whereas curve operations in Weierstrass models involve inversions. So that is why these curves are popular and we have to live with cofactors $> 1$.

There are other reasons to prefer to use prime-order elliptic curves (e.g., small subgroup attacks). So you are right that in an ideal world one would used prime order curves. But sometimes it is worth the trouble to use a more efficient curve model.

Improve this answer
$\endgroup$
1
$\begingroup$

When it comes to practical and standard backed solutions using h = 1 is rather common. This is to prevent small subgroup attacks.

  1. Brainpool Curves standard defines h=1 as a requirement: https://www.rfc-editor.org/rfc/rfc5639 (page 17)

cofactor is set to 1.

  1. All NIST curves below have h=1 as well (see: http://www.secg.org/SEC2-Ver-1.0.pdf)

    secp192r1

    secp224r1

    secp256r1 (default in all popular FOSS implementations including OpenSSL)

    secp384r1

    secp521r1

An exception is Bernstein's Curve25519 where h = 8 (https://www.rfc-editor.org/rfc/rfc7748#page-4). That one is practically used by Apple in their cloud encryption solutions, and is being moved to NIST SP 800-186, but I didn't see it published yet. As others pointed out, performance issues have been taken into consideration here.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Doesn't that mean that curve25519 has 8 times less valid private keys than a curve with a cofactor of 1? -- If so doesn't that make the curve less than 128bit strong? Why would we work in such a subgroup? Surely we should utilise all valid points on the curve? $\endgroup$
    – Woodstock
    Nov 18, 2019 at 16:18
  • $\begingroup$ @Woodstock h=8 will definitely impact the # of bits since all keys should be multiples of 8. It makes me think that actual key strength is 3 bits shorter than the prime-order curve. $\endgroup$
    – Oleg Gryb
    Nov 18, 2019 at 21:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.