Given an elliptic curve $E$ on $Z_q$. There is a subgroup $<G>$ on $E$, and the order of $<G>$ is $p$, where $p$ is a prime. And the discrete log problem on $<G>$ is hard. Now we randomly sample a group element $G_0$ of $E$. Let $Q$ be the event that $G_0$ falls in $<G>$. Can we say that the probability that $Q$ happens is negligible?
$\begingroup$
$\endgroup$
5
-
$\begingroup$ Only if $<G>$ is negligibly small compared to $E$. For the elliptic curves used in crypto, the topic here, that is never the case, but for the more general topic of elliptic curves in mathematics it can be. $\endgroup$– dave_thompson_085Commented Feb 12, 2021 at 4:11
-
$\begingroup$ But the elliptic curve on $Z_q$ should be isomorphic to a finite cyclic group or direct sum of two finite cyclic subgroups. If the elliptic curve used in crypto is isomorphic to two finite cyclic subgroups and the smaller one is used as the cryptographic group, I think it is possible. Assume here the size of the cryptographic group is $p$, Then the whole size of the elliptic curve should be larger than $p^2$(the size of the smaller sub-group should divide the size of the larger group). Then the probability that $Q$ happens should be smaller than $p/p^2=1/p$, which is negligible. What's wrong? $\endgroup$– Eric_QinCommented Feb 12, 2021 at 6:02
-
$\begingroup$ (Can't fully explain in comment, see answer.) $\endgroup$– dave_thompson_085Commented Feb 12, 2021 at 11:40
-
$\begingroup$ The problem is not random, rather the attacker may control it. See: Curve25519 Key Validation, Lim-Lee small subgroup attack and the twist attack are the cases. $\endgroup$– kelalakaCommented Feb 12, 2021 at 16:08
-
$\begingroup$ Got it. Thank you! $\endgroup$– Eric_QinCommented Feb 13, 2021 at 2:27
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
Yes, every finite group (including an elliptic curve over a finite field) either is a finite cyclic group or is the product (not sum) of at least two (not exactly two) finite cyclic groups, and in the latter case some (or even all) of those subgroups may be relatively small. But for crypto we only use a prime-order subgroup that is large enough to satisfy a specified security parameter, which in practice is set close to the size of the full group of the curve (and also close to the size of the underlying field, per Hasse's theorem). For example the widely-used X9/NIST/SECG curves over $F_p$ were chosen to have prime order, so the only subgroup is the full group and any point chosen as G has that order; this is also stated as having cofactor 1. Bernstein et al's Curve25519 has a full group of order near $2^{255}$ and uses a subgroup of order near $2^{252}$, also stated as cofactor 8; this is not negligible.
If a cryptographic scheme (or implementation of one) that intends to use such a sufficiently-large but proper subgroup fails to ensure or verify that elements (for EC points) purported to be in the subgroup actually are, an attacker may be able to cause it to use values constrained to one of the small subgroups, and thereby gain an advantage; these are generically called small-subgroup attacks and you will find quite a few existing Qs and As about them. 25519 makes privatekeys a multiple of 8 to block this.
That's why your question makes sense for EC mathematics, but not for EC crypto as practiced.
answered Feb 12, 2021 at 11:39
-
$\begingroup$ Ok, I understood. Thank you so much! $\endgroup$– Eric_QinCommented Feb 12, 2021 at 13:28
-
$\begingroup$ You claim "every finite group (including an elliptic curve over a finite field) either is a finite cyclic group or is the product (not sum) of at least two (not exactly two) finite cyclic groups". But I think it is just exactly two finite cyclic groups, if not one. It will not be more than two. It is due to a theorem 4.1 in the book 《Elliptic Curves Number Theory and Cryptography》, Washington $\endgroup$– Eric_QinCommented Feb 20, 2021 at 3:13