If $p$ is a big prime, and the elliptic curve $E$ is defined over $F_p$ by the equation $y^2=x^3+ax+b$ where $a,b\in F_p$. The point on $E/F_p$ together with the infinite point $\mathcal{O}$ form a group $G=\{(x,y):x,y\in F_p;(x,y)\in E/F_p\}\cup\{\mathcal{O}\}$. Then is $G$ a cyclic group? what's the order of $G$?
4
-
1$\begingroup$ crypto.stackexchange.com/questions/15132/… $\endgroup$– DrLecterCommented Jul 25, 2014 at 6:32
-
$\begingroup$ In my definition, is $G$ a cyclic group? And if it's true , supposing $P$ is a generator of $G$, then is it OK to do this: $a \in Z_p^*,Q=aP$ ? $\endgroup$– T.BCommented Jul 25, 2014 at 7:11
-
$\begingroup$ If you want the ECDLP to be hard, you have to take a large subgroup of prime order (which is always cyclic). What do you mean by "OK to do this"? $\endgroup$– DrLecterCommented Jul 25, 2014 at 7:16
-
$\begingroup$ I mean that if $G$ is cyclic, $P$ is a generator of which, is there some problem if I take $a$ from $Z_p^*$ and compute $aP$. By the way, whether the order of $G$ can be $p$ if I understand it as a large subgroup of prime order? $\endgroup$– T.BCommented Jul 25, 2014 at 7:44
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
The cyclic group over the ECDLP problem is posed is a subset of the set of point of the elliptic curve. That is to say, not all the points in the referred curve will be in the cyclic group. What you've called as $G$ confuses with another notation of the generator of a cyclic group $<G>=\{G,[2]G,\cdots,[n]G=\mathcal{O}\}$.
This is the meaning of what you've may heard as the cofactor ($h$). There is a relation between the number of points in the elliptic curve (the cardinal $|E(\mathbb{F}_p)|$) and the order of the mention cyclic group ($org(G)=n$). Following the P1363, the cardinal of a cryptographically good curve should be prime or "almost" prime.
What this almost mean is to factorize in one big number and another very small. $|E(\mathbb{F}_p)|=n\cdot h$, where $n >>> h$. Back to P1363, $h$ shall not be other than $1$, $2$ or $4$. In a $h=1$ your cyclic group fits with the complete set of points in the elliptic curve. On bigger cofactors, smaller the cyclic group; but don't panic, a $192$ bit curve with a cofactor $2$ can be like a $191$ curve with a cofactor $1$ (despite other issues that suggest to avoid cofactor $1$).
$\begingroup$
$\endgroup$
A classical resut is that over a finite field $\mathbb{F}_p$ the group $E(\mathbb{F}_p)$ is either cyclic or isomorphic to the product of two cyclic groups. For the order of the group see this question.
For cryptographic purposes, i.e., when you require that the ECDLP is hard, you will firstly have to rule out some weak curves (supersingular or anomalous curves) and work in a large prime order $q$ subgroup of $E(\mathbb{F}_p)$. A prime order group is always cyclic (which straightforwardly follows from Lagranges' theorem).
So if you have a generator $P$ of this $q$ order subgroup, then the ECDLP is defined as for given point $Q=k\cdot P$ with $k\in \mathbb{Z}_q$, to determine $k$.
