SafeCurves:
choosing safe curves for elliptic-curve cryptography


Introduction
Curve parameters:
Fields
Equations
Base points
Prime proofs
ECDLP security:
Rho
Transfers
Discriminants
Rigidity
ECC security:
Ladders
Twists
Completeness
Indistinguishability
More information:
References
Verification

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


Version: This is version 2013.10.14 of the complete.html web page.