5
$\begingroup$

In a book about cryptography and elliptic curves, there was a mention that not all curves are secure, and a statement than in order to pick a secure curve the curve must satisfy 3 requirements.

  1. The curve's equation is $y^2 = x^3 + ax + b\quad\pmod p$
  2. with $4a^3 + 27b^2 \neq 0\quad\pmod p $
  3. and the order $\#E(\mathbb F_p)$ of the Elliptic Curve group is prime.

The third point is weird since in DLP like Diffie-Hellman modulo $p$, the order $p-1$ can be any number not necessarily a prime (maybe it can be extra secure if it's a prime I don't know).

I understand the first statement of course but I'm completely lost on why the other two statements must be true for an elliptic to be secure. So if someone can explain why statements 2/3 must be true for a good elliptic curve and what can happen if these two conditions aren't true. Any small example with small $p, a, b$ will be really appreciated so I can understand the mathematics behind it.

$\endgroup$
0
8
$\begingroup$
  1. $y^2 = x^3 + ax + b\bmod p$ is the Short Weierstrass equation. The theory behind it is here

    Using Bezout’s Theorem, it can be shown that every irreducible cubic has a flex (a point where the tangent intersects the curve with multiplicity three) or a singular point (a point where there is no tangent because both partial derivatives are zero). [Reducible cubics consist of a line and a conic, which are easy to study.] An irreducible cubic with a flex can be affinely transformed into a Weierstrass equation: $$Y^2 + a_1 XY + a_3 Y = X^3 + a_2 X^2 + a_4 X + a_6$$

    And this can be converted into a short Weierstrass equation if $p$ is larger than $3$. The transformation can be achieved by

    Change $y\longrightarrow y-(a_1x+a_3)/2$, now the new equation has of the form $$y^2=x^3+Ax^2+Bx+C.$$ And now change $x\longrightarrow x-A/3$, now the new equation has of the form $$y^2=x^3+ax+b.$$

    The reason for $p \neq 2,3$ can be seen from the divisions. Also one should note that the two changes of variables are invertible, therefore their composition, too. This concludes that the rational points on both equations are in bijective correspondence.

    For $p=2$ and $p=3$ there are other short forms. In Cryptography we work in either binary extension fields ($\mathbb{F}_{2^m}$) which no more secure and large prime fields ($\mathbb{F}_{p}$) and on their extensions ($\mathbb{F}_{p^m}$).

  2. If the discriminant is not different than zero ($\Delta = 0$) then the curve is singular then the DLP is easy. Geometrically, this means that the graph has cusps, self-intersections (node), or isolated points.

    Cusp; when $\Delta=0$ and $a=0$ ( $y^2 = x^3$); Cusp

    Intersection or Node; when $\Delta=0$ and $a\neq 0$ ( $y^2 = x^3 +3x +1$);

    enter image description here

    Acnode (isolated point); $y^2 + x^3 + x^2$, at $(0,0)$

    enter image description here Note these draws are not in the finite fields where we cannot see such figures to see those. A curve with the finite field just points when we draw on the plane as below and we cannot see the above singular points, however, we can still calculate them.

    enter image description here

    The above is the point of the curve over $\operatorname{GF}(307)$ with the curve equation $ y^2 = x^3 + x^2 + x$ and this curve group is isomorphic to $ Z/160 + Z/2$

And, Wolfram has a nice page about those singular points.

  1. This is not completely true. Some curves have prime order ( i.e. $\#E(\mathbb F_p)$ is a prime) and all of the elements other than the identity can be a generator ( see the blow theorem).

    Some curves don't have prime order, like the Curve25519, it has a co-factor $h=8$ i.e. $h = \frac{\#E(\mathbb F_p)}{n}$ where $n$ is the order of the generator point $G$. In this case, we chose the largest prime and select a generator for it.

There is also twist security related to the order that one must consider. Although the NIST P-224 has co-factor 1 ( i.e. it has prime order), it doesn't have the twisted security.


Theorem: Let $E$ ben elliptic curve group over the finite field $\mathbb{F_q}$. Then $$E(\mathbb{F_q}) \simeq \mathbb{Z_p} \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 order of the curve is prime then it must be $E(\mathbb{F_q}) \simeq \mathbb{Z_p}$.

$\endgroup$
1
  • 1
    $\begingroup$ Thank's a lot this helped me out. $\endgroup$ – Khaled Gaber Dec 13 '20 at 13:54

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.