SafeCurves:
choosing safe curves for elliptic-curve cryptography

Completeness

The simplest inner loop for scalar multiplication, computing the curve point nP given an integer n and a curve point P, looks like this:

• Q ← Q+Q.
• Q ← Q+P if current bit of n is set.

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:

• Q ← dbl(Q).
• Q ← Q+P if current bit of n is set.

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.

Specific curves

The following table reports the support for complete scalar multiplication on various existing curves:

Curve	Complete single-scalar formulas?	Complete multi-scalar formulas?	Number of points of order 2	Number of points of order 4
Anomalous	False	False	0	0
M-221	True✔	True✔	1	2
E-222	True✔	True✔	1	2
NIST P-224	False	False	0	0
Curve1174	True✔	True✔	1	2
Curve25519	True✔	True✔	1	2
BN(2,254)	False	False	0	0
brainpoolP256t1	False	False	0	0
ANSSI FRP256v1	False	False	0	0
NIST P-256	False	False	0	0
secp256k1	False	False	0	0
E-382	True✔	True✔	1	2
M-383	True✔	True✔	1	2
Curve383187	True✔	True✔	1	2
brainpoolP384t1	False	False	0	0
NIST P-384	False	False	0	0
Curve41417	True✔	True✔	1	2
Ed448-Goldilocks	True✔	True✔	1	2
M-511	True✔	True✔	1	2
E-521	True✔	True✔	1	2