0
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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

Group theory is your friend.

| improve this answer | |
$\endgroup$
  • $\begingroup$ > Obviously, this is incorrect, and Samuel never claims it. > I feel like he does claim it, what am I misinterpreting? He literally says: "the order of 𝐺- G is 𝑝1=2^252+27742317777372353535851937790883648493 whereas the number of points in the curve itself is 8𝑝1" $\endgroup$ – Woodstock Nov 20 '19 at 15:18
  • $\begingroup$ Otherwise thanks for the answer, it's good. It's not a very intuitive subject so I'm fumbling through it. $\endgroup$ – Woodstock Nov 20 '19 at 15:21
  • $\begingroup$ @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$.’ $\endgroup$ – Squeamish Ossifrage Nov 20 '19 at 15:49
  • $\begingroup$ @SqueamishOssifrage thank you, I thought order meant cardinality here. i.e. p1 is number of points in subgroup, so total number of points isn't 8*2^252...? If not does order here refer to some subgroup number? $\endgroup$ – Woodstock Nov 20 '19 at 15:53
  • 1
    $\begingroup$ 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). $\endgroup$ – fkraiem Nov 20 '19 at 21:00

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.