# Order of subgroups formed by Elliptic Curves with a Cofactor

In this question:

Why are the lower 3 bits of curve25519/ed25519 secret keys cleared during creation?

The answer indicates that the order of all points on the curve over the finite field 2^255 - 19 is 8 times the size of the subgroup formed by G.

i.e. the subgroup size is 𝑝1=2^252+27742317777372353535851937790883648493 whereas the number of points in the curve itself is 8(𝑝1).

The answer then states: "This means that there are a few remaining points that have small order."

However, as stated in the answer the few remaining points are in fact 8 times the number of points in the cyclic subgroup G.

So how can one conclude that the remaining points form small order groups?

Isn't there scope for a group within the set of remaining points to be bigger than 𝑝1?

How do we know the other points not inside 𝑝1, form a variety of small order groups?

The answer indicates that the order of all points on the curve over the finite field $$2^{255} - 19$$ is 8 times the size of the subgroup formed by $$G$$.

Obviously, this is incorrect, and Samuel never claims it.

This curve defines a group with $$8q$$ elements (with $$q = 2^{252} + 27742317777372353535851937790883648493$$ prime), and the factorization of $$8q = 2 \times 2 \times 2 \times q$$. Hence, the possible orders of points are $$1, 2, 4, 8, q, 2q, 4q, 8q$$. In addition, this curve happens to be a cycle curve (not all elliptic curve groups are), and so for each possible order, there are in factor at least one group element with that order.

$$G$$ happens to be one of the points of order $$q$$ (actually, it didn't just 'happen', a point of that order was deliberately selected to be $$G$$).

How do we know the other points not inside 𝑝1, form a variety of small order groups?

Because we know the complete factorization of the number of points on the curve ($$8q$$). If there is a subgroup of size $$\lambda$$, that would imply that $$\lambda$$ was a factor of $$8q$$. We know all the values that are a factor of $$8q$$, and there are none between 8 and $$q$$; hence, there cannot be any subgroups with a size between 8 and $$q$$.

• @Woodstock ‘The [total] number of points on the curve is $8p_1$’ does not mean ‘the order of every point on the curve is $8p_1$.’ – Squeamish Ossifrage Nov 20 '19 at 15:49
• Yes, there is a subgroup of order $2q$ (also $4q$ and $8q$), but they are not interesting because using them brings no security benefit (Pohlig-Hellman) and actually opens some security risks (small subgroup attacks). – fkraiem Nov 20 '19 at 21:00