Whats the reason for using elliptic curves of order |E| = fr

Question

To be more precise, in the books I sometimes see that they just require you that the order of your elliptic curve is $|E| = fr$, where $f$ is some small integer with possible factors, but $r$ is a large prime. I know that this is ok when working with ECC since, for example, the ECDLP is as hard as the largest prime order subgroup. But why the urge to work with this? Is it in practice easier to generate such order EC? Why not for example work with |E| = r?

Answer 1

Let $E$ be an elliptic curve over a finite field $K$. Then the points that satisfy the curve equation form an abelian group under the point addition. The group's order $q= \#E(K)$ can be prime or composite. If the order is prime, they are called prime curves. Let $p$ be the largest prime such that $p\mid q$. The co-factor $h$ is defined as $h=q/p$.

There are subtle points on having a prime order (i.e. $h=1$) or not ($h>1$).

• When we have prime curves every element is a generator - except the identity element -. This is easy to see with the Lagrange Theorem on the Group Theory; the order of a subgroup divides the group's order. Since the group order is prime, the subgroups all have the same order as the group.

  This is safe from the Pohlig-Hellman attack when the group order is not prime.

• When the $h>1$ we have some subgroups. Consider the Curve25519 where $h=8$ and this implies that there can be subgroups of order $2,4,8,2p,4p,q=8p$ ( Lagrange theorem's inverse is not true in general, however, one can test that there are indeed such subgroups of this curve).

  Of course, one doesn't choose a curve that has two large prime that divides the curve order. So Pohlig-Hellman is not much help here.

  There are still attacks in this case. If the legitimate user doesn't obey the guides they are vulnerable to the Lim–Lee active small-subgroup attacks. If they obey the guides, they are safe against this attack. Of course, we are in the free world not listening to the guidance, then Monero and others had attack points on their implementation. Mike Hamburg removed the burden by constructing the Decaf to mitigate the problem from the hands of legitimate users.

  If you don't obey the guidance, you need point validation.

So why do we use non-prime curves? The answer is in the performance

• The Mongomery Ladder provides a fast and regular structure to calculate scalar multiplication on Montgomery curves. The structure can have side-channel security if correctly implemented. To have a Montgomery representation this curve must have an element of order $4$.

• For prime curves, there is Joye Ladder, however, that is not as fast as Montgomery ladder.