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

$\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 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 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 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 at 15:53
  • $\begingroup$ The order of a point $P$ is the smallest positive integer $n$ such that $[n]P$ is the identity. The order of a group is the number of elements in the group. The order of a point $P$ is the same as the order of the subgroup generated by $P$. $\endgroup$ – Squeamish Ossifrage Nov 20 at 15:55

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.