Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I hear a lot about why Montgomery curves are used in ECC, and one reason is that the same algorithm can be used to do both point addition and doubling (this is not true for the Weierstrass normal form).

What are the most prominent unsafe features of curves, and ways one can screw up an ECDH implementation? Are there "more" ways to screw up with the WNF as opposed to the Montgomery form?

Can you point me to an overview of the problems associated with curves in WNF?

share|improve this question

1 Answer 1

up vote 5 down vote accepted

The problem doesn't lie with curves in Weierstrass form necessarily, but with naive implementations of elliptic curve arithmetic on such curves.

Basically, if you implement an ECC scheme (ECDH, ECDSA or whatever) on a smart card using a curve in Weierstrass form in the most straightforward way possible (by writing a simple double-and-add loop for exponentiation using textbook formulas for addition and doubling), then anyone can basically take the smart card, perform power analysis while the scheme is running, and directly read off your secret exponent from the power trace because additions and doubling produce quite different patterns on the trace.

See e.g. J.-S. Coron, "Resistance against differential power analysis for elliptic curve cryptosystems", CHES 1999, for some of the basic attacks and countermeasures.

Using appropriate countermeasures, you can certainly implement elliptic curve cryptography on Weierstrass curves in a way that is largely secure against side-channels. The argument of proponents of other curve forms (such as Montgomery curves if you want ECDH, or curves with unified arithmetic like Edwards curves for signatures and other applications) is that, as you say, implementations are easier to get right with those other forms (and as a side benefit, they tend to have better performance characteristics as well). See also this related answer by Thomas Pornin.

For example, the Montgomery ladder, which is the standard way in which you would implement exponentiation on a Montgomery curve, is safe against simple power analysis without having to add in any other countermeasure. Of course, if you want to protect against stronger physical attackers, you may still need to add other countermeasures to your implementation (against DPA, fault attacks, etc.), but the basics are covered, so the situation is really a bit better than with Weierstrass form, where the most standard exponentiation algorithm is leaky and countermeasures tend to be costly.


Side note: the idea that on Montgomery curves "the same algorithm can be used to do both point addition and doubling" isn't entirely correct. Typically, people use Montgomery curves for the very efficient x-only differential-addition and doubling operation that can be used to do efficient, SPA-secure exponentiation up to sign (the Montgomery ladder). But you can't really do point addition at all (certainly not x-only point addition, since it's not well-defined, and if you're going to use two components, you might as well use a better suited curve form).

It's twisted Edwards curves (among others) that admit addition formulas that can also be used for doubling. Now it turns out that any Montgomery curve is birationally equivalent to a twisted Edwards curve and vice versa (you can use any such curve in one form or the other depending on the application) so the distinction might sound a bit academic, but all of these curves can also be put in Weierstrass form as well, after all, so the difference certainly matters as far as implementations are concerned.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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