Why are singular “elliptic” curves bad for crypto?

Question

Consider the algebraic curve given by a short Weierstraß equation $y^2=x^3+ax+b$.

If $4a^3+27b^2=0$, then there are repeated roots of the right-hand side $x^3+ax+b$. How are these repeated roots bad for a discrete-logarithm-based cryptosystem?

Answer 1

When a Weierstraß equation $y^2 = x^3 + Ax + B$ over $\mathbf F_p$ has a null discriminant, then it does not define an elliptic curve: it is a singular curve. In that case, it means the polynomial $x^3 + Ax + B$ has a double or triple root $x_0$ and the point $(x_0, 0)$ is a singular point. All the non-singular points still define a group law with the regular construction as in an elliptic curve.

With a change of variable, you can always come back to these two cases:

• $y^2 = x^3$, then there are exactly $p$ non-singular points and there is an efficient map to the additive group of $\mathbf F_p$ where the discrete logarithm is trivial.

• $y^2 = x^2(x-1)$, then there are $p+1$ or $p-1$ points and there is an efficient map to the multiplicative group of $\mathbf F_{p^2}^*$ (which has $p^2 - 1 = (p-1)(p+1)$ elements) where the discrete logarithm is way easier to compute (but not as easy as the previous case).

In both cases it is very bad for crypto.