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

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


Version: This is version 2013.10.13 of the ladder.html web page.