SafeCurves:
choosing safe curves for elliptic-curve cryptography

Ladders

The most important computation in ECC is single-scalar multiplication: computing the curve point nP given an integer n and a curve point P. This is the bottleneck in

• key generation: n is Alice's secret key, P is a standard base point, nP is Alice's public key;
• signing: n is a nonce, P is a standard base point, nP is part of the signature;
• DH: n is Alice's secret key, P is Bob's public key, some hash of nP is the secret key shared between Alice and Bob.

Montgomery curves y^2=x^3+Ax^2+x support a very simple scalar-multiplication method, the Montgomery ladder, introduced by 1987 Montgomery. There are several reasons that the Montgomery ladder is simpler than, e.g., the standard short-Weierstrass scalar-multiplication methods:

• The standard short-Weierstrass methods have two input coordinates, x(P) and y(P). The Montgomery ladder has only one input coordinate, x(P).
• To avoid inner-loop divisions the standard short-Weierstrass methods internally use three coordinates, X and Y and Z, to represent x = X/Z^2 and y = Y/Z^3. The Montgomery ladder uses only two coordinates, X and Z, to represent x = X/Z.
• There are actually many different standard short-Weierstrass methods, using many different addition-subtraction-doubling chains. The simpler chains are slower and leak secret data through timing. The Montgomery ladder uses a single standard chain, always following a simple, highly efficient double-add pattern.

SafeCurves requires curves to support simple, fast, constant-time single-coordinate single-scalar multiplication, avoiding conflicts between simplicity, efficiency, and security. This is not a requirement specifically to use Montgomery curves: there are other types of curves that support simple, fast, constant-time ladders. "Fast" means that implementations of scalar multiplication for the same curve cannot be much faster, and "simple" means that reasonably fast implementations of scalar multiplication for the same curve cannot be much more concise. At this time there are no examples close enough to the edge to warrant quantification of "much".

Isomorphism (and birational equivalence)

One can sometimes convert a short Weierstrass curve y^2=x^3+ax+b to a Montgomery curve as follows. Find r satisfying r^3+ar+b=0. Find s satisfying s^2=3r^2+a. Define u=(x-r)/s, B=1/s^3, and A=3r/s. Then By^2=u^3+Au^2+u. One can perform x-coordinate scalar multiplication on y^2=x^3+ax+b by converting x to u, performing u-coordinate scalar multiplication on By^2=u^3+Au^2+u with the Montgomery ladder, and converting back.

The reason this does not always work is that, for the majority of curves, the field F_p does not contain suitable elements r and s. One can work around this by replacing F_p with an extension field, but this requires much less simple field operations inside scalar multiplication.

In particular, curves of prime order or 2*prime order can never be converted to Montgomery curves over F_p: Montgomery curves always have order divisible by 4.

The Brier–Joye ladder

2003 Brier–Joye presented a constant-time x-coordinate ladder applicable to every short Weierstrass curve y^2=x^3+ax+b. However, the Brier–Joye ladder is much slower than the Montgomery ladder: it requires 19 field operations per bit, many more field operations than standard addition chains for short Weierstrass curves. It thus creates a conflict between efficiency and security.

Specific curves

The following table reports the ladder support for various existing curves:

Curve	Montgomery ladder?	Cofactor
Anomalous	False	1
M-221	True✔	2^3
E-222	True✔	2^2
NIST P-224	False	1
Curve1174	True✔	2^2
Curve25519	True✔	2^3
BN(2,254)	False	1
brainpoolP256t1	False	1
ANSSI FRP256v1	False	1
NIST P-256	False	1
secp256k1	False	1
E-382	True✔	2^2
M-383	True✔	2^3
Curve383187	True✔	2^3
brainpoolP384t1	False	1
NIST P-384	False	1
Curve41417	True✔	2^3
Ed448-Goldilocks	True✔	2^2
M-511	True✔	2^3
E-521	True✔	2^2