Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question

2 Answers 2

up vote 11 down vote accepted

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

share|improve this answer
2  
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. –  poncho Jun 13 '12 at 13:46
    
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. –  Samuel Neves Jun 13 '12 at 18:15
    
then why we do care about even characteristic curves that imply even number of points since they are not secure? –  curious Apr 21 '13 at 14:51

Montgomery and twisted Edwards curves have even order, but the group law can be implemented using fewer multiplications than Weierstrass models. 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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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