The simplest inner loop for scalar multiplication, computing the curve point nP given an integer n and a curve point P, looks like this:
The simplest way to implement + is to copy the "addition formulas" from an ECC book. But for Weierstrass curves this doesn't work: the scalar-multiplication formulas consistently fail random tests. The problem is that the standard Weierstrass "addition formulas" don't always work: in particular, they fail for the doublings Q+Q.
Because this implementation fails random tests, it will be fixed. The simplest fix is as follows:
This passes random tests, but it still fails if Q happens to match P. This will not be caught by random tests.
Maybe the implementor instead has "+" check for its inputs being equal. But this is less likely as an implementation strategy: it produces a slower and more complicated implementation. Furthermore, it does not catch all the failure cases. For example, the standard Weierstrass addition formulas fail if Q happens to match -P. This will not be caught by random tests.
Attackers can trigger these failure cases inside typical ECC protocols, and in some cases can learn part of all of n by analyzing the responses. See, e.g., 2003 Izu–Takagi.
Complete addition laws
2007 Bernstein–Lange showed that the Edwards addition law is complete for every complete Edwards curve E. This means that, for every rational point P on E, and for every rational point Q on E, the Edwards addition law for inputs P and Q produces as output exactly P+Q. There are no exceptional cases. The Edwards addition law can be used for complete single-scalar multiplication, complete double-scalar multiplication, etc.
2006 Bernstein had shown a more limited form of completeness for the Montgomery ladder on Montgomery curves y^2=x^3+Ax^2+x with a unique point of order 2, i.e., with A^2-4 not a square. Specifically, given X0(P) as input, the Montgomery ladder always produces X0(nP) as output; here X0(P) means 0 if P=0, and otherwise the x-coordinate of P. It is possible that ladders provide completeness for other curves, but the analysis is not easy; the only literature is a second 2006 Bernstein paper on this topic.
Subsequent research has introduced other complete scalar-multiplication formulas. However, many of these formulas are considerably slower and more complicated than standard incomplete scalar-multiplication formulas, creating major conflicts between simplicity, efficiency, and security.
SafeCurves requires curves to support simple, fast, complete, constant-time single-coordinate single-scalar multiplication. This includes the SafeCurves ladder requirement but goes further by requiring completeness. SafeCurves also requires curves to support simple, fast, complete, constant-time multi-scalar multiplication.
Does completeness of a curve guarantee completeness of the addition law?
No. For example, on complete Edwards curves, the original Edwards addition law is complete, but the dual addition law introduced in 2008 Hisil–Wong–Carter–Dawson is not. The SafeCurves requirement ensures that completeness is a viable option but does not ensure that it is the only option.
The following table reports the support for complete scalar multiplication on various existing curves:
Version: This is version 2013.10.14 of the complete.html web page.