1
$\begingroup$

In ECDSA, we use a prime order group $\langle G\rangle$ for cryptographical use. Assume $\#\langle G\rangle = p$. Is there another subgroup in the curve used for ECDSA whose order is also $p$?

$\endgroup$
2
$\begingroup$

This question has two faces;

  1. The number of rational points of the used curve is prime like secp256r1, i.e. $\#C(K) = p$ where $K$ is the field where curve $C$ is defined;

    In the group theory, let $G$ be a finite group and $H$ be a subgroup of $G$. Then the order of $H$ must divide the order of $G$. This the Lagrange's Theorem in group theory. More formally;

    Lagrange's theorem - If $H$ is a subgroup of a group $G$, then ${\displaystyle \left|G\right|=\left[G:H\right]\cdot \left|H\right|.}$

    Below a corollary to the Lagrange theorem;

    If the order of the group is prime then there are no subgroups other than the trivial subgroups.

    Therefore, an order $p$ group has no subgroups other than the trivial subgroups which are the identity group and the group itself.

  2. The number of the rational points of the used curve is not a prime, $\#C(K) = n$;

    This really depends on the group. The Lagrange theorem doesn't guarantee the existence of the subgroups if an integer divides the order of the group.

    Consider the Curve25519 which has a prime order subgroup $n$ and the co-factor is $h=8$ ( $h = \#E(\mathbb{F}_p)/n$) then we have the subgroup of order $2,4,8,n,2n,4n,8n$, i.e. we have all possible subgroups.

    You can find a group that has two prime subgroups of order $p$ the if there are no other subgroups the curve group will be isomorphic to $\mathbb{Z}_p \oplus \mathbb{Z}_p$. Is this possible in Elliptic Curves?

    I haven't seen an example in secure elliptic curves. The reason is simple; we want a large prime subgroup order that is close to the curve order in order to effectively use the curve. If there are two different subgroups of order $p$ then the curve order will be $\geq p^2$. This means you are wasting your computations.


More into theory (4.1 is in the second edition of Washington's Book);

Theorem 4.1: Let $E$ ben elliptic curve group over the finite field $\mathbb{F_q}$. Then $$E(\mathbb{F_q}) \simeq \mathbb{Z_n} > \text{ or } \mathbb{Z_{n_1}} \oplus \mathbb{Z_{n_2}}$$ for some integer $n \geq 1$, or for some integers $n_1,n_2 \geq 1$ with $n_1|n_2$.

If the $E(\mathbb{F_q})$ falls into the first case implies that the subgroup order $r$ must divide $r|n$. But the subgroups of $\mathbb{Z})_n$ are unique. Therefore there cannot be two subgroups that have the same order.

The second case is more interesting [1] [2] [3] since it is a direct product of groups. Since $n_1\mid n_2$ there is a subgroup of $H$ of $\mathbb{Z_{n_2}}$ such that it is isomorphic to $\mathbb{Z_{n_1}}$. Now we have two subgroups of the same order $\Bbb Z_{n_1} \oplus \{0 \}$ and $\{0\} \oplus H$.

As said before we don't prefer curves that can have two different subgroups of order large prime.

$\endgroup$
2
  • $\begingroup$ Yes, I guess there is no another such subgroup in the ECDSA-used curves due to the efficiency concern. But I am just not sure. This is important for my work. Thanks for your answer! $\endgroup$
    – user77340
    Feb 21 at 7:11
  • $\begingroup$ @user77340 if you are not using a self-created curve, then no! You may see the details of the curve on their paper. $\endgroup$
    – kelalaka
    Feb 21 at 7:15

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.