5
$\begingroup$

After an answer here, about generate elliptic curves, I've start thinking about the algorithm. The mentioned algorithm will produce curves in the Weierstraß Reduced Form (WRF) over finite fields:

$y^2 = x^3 + ax +b$ with $a,b\in \mathbb{F}_p$

And this WRF is the representation used in the NIST (where $a\equiv-3\pmod p$), Brainpool, and probably some others, that can be used in standards like the extension for OpenPGP or TLS.

But this is only one of many ways to describe elliptic curves. In TLS specification it opens to the possibility to use arbitrary curve definition. Or other alternatives are Montgomery curves like the curve25519 "recently" proposed for EdDSA.

If I like to generate my curve (ignoring the fact that this would affect the maths in the implementations) are there differences between representations? I mean, would be faster to generate random cryptographically good curves depending on the representation? Will curves with different representation and the same bit length, have the same strength?

Improve this question
$\endgroup$
1
  • $\begingroup$ Montgomery curves allow a fast constant time ladder calculation of scalar multiplication, Weierstrass curves are quite slow to do this, so usually a non constant time calculation is done, which is bad. For Montgomery curves of a certain construction it can also be proven that the calculation is complete $\endgroup$
    – Richie Frame
    Mar 11, 2014 at 6:00

1 Answer 1

Reset to default
2
$\begingroup$

No, not all curves are created equal. For one thing, the number of points on an elliptic curve defined over $\mathbf{F}_p$ varies in the interval $[p+1-2\sqrt{p},p+1+2\sqrt{p}]$ (Hasse's Inequality). There are also weak instances which must be avoided, the most catastrophic being when the number of points on the curve is exactly equal to $p$ (anomalous curves) or to $p+1$ (supersingular curves).

Improve this answer
$\endgroup$
3
  • $\begingroup$ @figlesquidge Using $\mathbf{F}_p$ instead of $\mathbb{F}_p$ is a personal choice, please respect that. $\endgroup$
    – fkraiem
    Mar 10, 2014 at 18:58
  • $\begingroup$ Of course its your answer, feel free to do what you want with it! Just changed that since generally that would be a typo. Hope you didn't mind the link being added :) $\endgroup$
    – Cryptographeur
    Mar 10, 2014 at 19:00
  • $\begingroup$ I had hit Enter too soon, sorry. ;) $\endgroup$
    – fkraiem
    Mar 10, 2014 at 19:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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