1
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

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.