9
$\begingroup$

I think we're all aware of the "classical" Weierstrass (short?) elliptic curve equation: $y^2\equiv x^3 + ax +b \pmod p$. Well known examples of these curves include the NIST's and Brainpool ones.

Now there's also the "Montgomery" representation: $by^2\equiv x^3 + ax^2 + x \pmod p$ where the famous Curve25519 is an example for.

To get things even more complicated there are "Edwards" and "Twisted Edwards" curves (of which I don't even have the general equations). A well-known sample would be Ed25519 I think.

  • Now what are the equations of these curves ([twisted] edwards only)?
  • Can they be converted into each other?
  • What are the computational advantages over using a given curve equation over another?
  • Are there any security implications (including side-channels) in choosing a specific equation?
$\endgroup$
11
$\begingroup$

All of these are answered by the SafeCurves project:

  • For twisted Edwards curves, $ax^2 + y^2 \equiv 1 + dx^2y^2 \pmod p$. Edwards curves are the special case a = 1.
  • Edwards curves can be converted to Montgomery form.
    Montgomery curves can be converted to Weierstrass form.
    Some, but not all, Weierstrass curves can be converted to Montgomery form.
  • The Montgomery ladder (applicable only to Edwards and Montgomery curves) is faster than standard weierstrass point multiplication methods.
  • the Montgomery ladder is constant-time, while the standard Weierstrass point multiplication methods are not.
    The Brier-Joye ladder allows constant-time point multiplication on Weierstrass curves, but is much slower than the standard point multiplication methods.
    The EdDSA signature scheme is only supported by twisted Edwards curves.
$\endgroup$
  • $\begingroup$ nice summary :) But a small "follow-up" question: What are the advantages of (twisted) Edwards curves over Montgomery curves in terms of speed / security (if there are any)? $\endgroup$ – SEJPM Jun 16 '15 at 20:34
  • 1
    $\begingroup$ EdDSA requires a twisted edwards curve. that's pretty much the only practical difference between edwards and montgomery curves. $\endgroup$ – lily wilson Jun 16 '15 at 21:43
  • $\begingroup$ I quickly edited your answer to look more appealing and include your comment before accepting it. If you don't like my edits, you can roll them back or just make another edit. $\endgroup$ – SEJPM Jun 17 '15 at 19:09

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.