Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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$?

share|improve this question
1  
    
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$ ? –  T.B Jul 25 at 7:11
    
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"? –  DrLecter Jul 25 at 7:16
    
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? –  T.B Jul 25 at 7:44

2 Answers 2

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$).

share|improve this answer

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$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.