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?

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
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$
8
  • $\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, 2019 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, 2019 at 15:21
  • 1
    $\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, 2019 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, 2019 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, 2019 at 21:00

Your Answer

By clicking โ€œPost Your Answerโ€, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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