0
$\begingroup$

Why don't prime-order curves have small subgroup attacks?

It seems that I can choose a Generator such that it has a small order, maybe 2 points, and so an attack could generate all of the points in that subgroup and figure out the scalar that exponentiated it.

Why only non-primes this is possible? Do prime fields have subgroups of a certain size, that ensures this?

Also is it correct to say "prime-ordered curves" ? It is the Field that the curve is defined over that has prime order, so I feel like i'm saying it wrong.

$\endgroup$
5
$\begingroup$

In Group theory, it is known that if $G$ is a finite group and $q$ is a prime number dividing the order of $G$ (the number of elements in $G$), then $G$ contains an element of order $q$ (Cauchy's theorem). And the order-$q$ element generates an order $q$ subgroup.

Thus if a group $G$'s order $N$ is not a prime number, then $N$ can be factored and $q_1,\cdots,q_n$ are the prime factors of $N$. For each $q_i$, there must exist a subgroup of order $q_i$. When $q_i$ is small, the subgroup is small. Hence small subgroup attack may be possible.

If a group $G$'s order is a prime number $p$, then by the Lagrange's theorem, the order of every subgroup $H$ of $G$ divides the order of $G$. Now $p$ has only two factors $1$ and $p$, thus $G$ can have two only subgroups: the trivial subgroup containing the identity $\{1\}$, and $G$ itself. There is no other small order sub-groups.

You also need to distinguish the finite field $F_p$ and the curve over the finite field $F_p$. They are two different things. The order of $F_p$ is the $p$ (elements are integers from 0 to $p-1$, inclusive), and the order of the curve over the finite field $F_p$ is the number of points on the curve and is bounded by the Hasse theorem $|order(E(F_p)) - p-1|\le 2\sqrt{p}$. A curve can be prime-ordered (or we can use a prime-ordered subgroup of all the points on the curve if the curve order is composite), but it is not simply because it is over a prime field.

$\endgroup$
  • $\begingroup$ "If $G$ is a cyclic group, then the order-$q$ element generates an order $q$ subgroup." Certainly this is true even if $G$ is not cyclic. ;) $\endgroup$ – fkraiem Jan 14 at 0:31
  • $\begingroup$ @fkraiem Yes, you are right. Will update it. $\endgroup$ – Changyu Dong Jan 14 at 11:08

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.