What is the deeper reason, a group must have prime order for usage in cryptography?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ As a rule of thumb: We want statements as exact as possible. Most of the time that's either "drawn at random (uniformly)" or "prime", because then everything is clear, or calculations based on those exact statements. If something is really unspecific (e.g. "could have large prime factors or not, we don't know for sure"), we have to assume the worst case. And that's usually on the level of "can be ignored / has no meaningful influence". $\endgroup$– tyloNov 11, 2016 at 18:59
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
Well, it doesn't have to. In short, as a consequence of the Pohlig-Hellman algorithm the ECDLP is only as hard as the largest prime order subgroup. So the requirement is that there exist a large prime order subgroup. In (a little) more detail:
Elliptic-curve cryptography is mostly based on the Elliptic Curve Discrete Logarithm Problem (ECDLP). That means that given some elliptic curve $E$, we want that the ECDLP is hard in $E$.
Suppose that the group $E$ has order $p_1p_2\cdots p_n$ for some (not necessarily distinct) primes $p_1,\ldots,p_n$. Then the Pohlig-Hellman algorithm reduces the ECDLP in $E$ to ECDLP in subgroups $G_i$ of order $p_i$ respectively. If all the $p_i$ are small, this means that ECDLP is easy in all $G_i$, e.g. by simply building a table of all $p_i$ elements. This leads to a solution of an ECDLP in $E$. Hence to make the ECDLP hard in $E$, we need that at least one of the $p_i$ is large.
For example, prime order elliptic curves trivially have a large prime order subgroup (the group itself!). On the other hand, Montgomery curves (e.g. Curve25519) have order 4*n, so can never be prime. To securely base protocols on Montgomery curves we have to make sure that $n$ has at least one very large prime factor.
$\begingroup$
$\endgroup$
It's due a general performance/security tradeoff for discrete logarithm based cryptography.
It doesn't apply to ECC only, but it's a generic rule.
If the order is composite then it is possible (see Pohlig-Hellman Algorithm ) to split the computation of the discrete logarithm in each prime-order subgroup and then compute the final result through the Chinese Reminder Theorem.
For example, let's assume ECC and that your curve's order $n$ is prime. So you use scalars which are of the same size of $n$ and the best generic attack (Pollard's Rho) requires about $\sqrt{n}$ group operations. If, instead, suppose your curve's order is $n_1*n_2$ where $n_1$ and $n_2$ are of the same size of $n$. Then you would use scalars which are double the size of $n$ but the best attack would not require $\sqrt{n_1*n_2}$ group operations but only $\sqrt{n_1}+\sqrt{n_2}$, meaning that you are losing significantly in computation speed (also because you have to use a field of size double then before) but you are gaining about a factor 2 in security.
