3
$\begingroup$

While reading about Elliptical Curves and ECDSA, I found a paper ECDSA Security in Bitcoin and Ethereum: a Research Survey by Hartwig Mayer. On page 6, the authors say:

The curve secp256k1 does not allow the Montgomery ladder implementation.

Is this true? And if so, why? I don't see why Montgomery methods wouldn't be usable with secp256k1.

$\endgroup$
6
$\begingroup$

The Montgomery ladder, in particular Montgomery's fast doubling and differential addition formula in $(X : Z)$ coordinates on p. 261, works only for curves which admit a Montgomery form $B y^2 = x^3 + A x^2 + x$. Any curve over a field $k$ with a Montgomery form necessarily has a point of order 2 among the $k$-rational points, namely $P = (0, 0)$: the negation map sends $(x, y)$ to $(x, -y)$, so since $-P = (0, -0) = (0, 0) = P$, we must have $[2]P = P + P = P - P = \mathcal O$.

secp256k1 is the curve $y^2 = x^3 + 7$ over the field $\mathbb F_p$ where $p = 2^{256} - 2^{32} - 977$. Its group of $\mathbb F_p$-rational points has large prime order, so by Lagrange's theorem it has no points of order 2, and hence it does not have a Montgomery form.

That said, there is a much slower single-coordinate ladder that encourages constant-time arithmetic, namely the Brier–Joye ladder, which works for any short Weierstrass curve $y^2 = x^3 - a x + b$ including secp256k1. It is so much slower that the standard variable-time addition chains for short Weierstrass curves are tempting, which is why SafeCurves recommends, for Diffie–Hellman protocols, the use of $x$-restricted DH functions in Montgomery curves instead to avoid a conflict between efficiency and security in implementation.

This doesn't matter as much for signature, which is what Bitcoin etc. use secp256k1 for, because most signature schemes—ECDSA as used by Bitcoin and Ethereum, and by statist pigs compliant with bureaucratic conformance standards; EdDSA as used by everyone else—involve the $y$ coordinate, which neither ladder computes; fixed-base-point scalar multiplication, which can be done faster than variable-base-point scalar multiplication; and multiple-point scalar multiplications, which can be done faster than multiple single-point scalar multiplications. There are signature schemes computed with single-coordinate ladders, such as qDSA, but these are a little exotic and not much used—certainly not in Bitcoin or Ethereum!

$\endgroup$
  • $\begingroup$ I would argue that the Montgomery ladder is an exponentiation algorithm, which works for any structure that has a doubling and differential addition operation. In particular it can be used in any group, so I think your first sentence is a little misleading. Of course the question whether it is efficient is another matter! $\endgroup$ – CurveEnthusiast Mar 16 '18 at 16:34
  • $\begingroup$ @CurveEnthusiast I guess you could say the Montgomery ladder is the general exponentiation algorithm with doubling and differential addition which can be instantiated with Montgomery's double and differential-add formulae on Montgomery curves, or with Brier and Joye's double and differential-add formulae on any short Weierstrass curves, but usually I've just seen the instantiations named ‘the Montgomery ladder’ vs. ‘the Brier–Joye ladder’. The algorithm is apparently so obvious that Montgomery didn't bother to spell it out and just called it ‘the binary method’ with a one-line summary. $\endgroup$ – Squeamish Ossifrage Mar 16 '18 at 16:53
  • 1
    $\begingroup$ @CurveEnthusiast I emphasized that what makes the Montgomery ladder peculiar to Montgomery curves is Montgomery's fast doubling and addition in XZ coordinates in curves of that form. Better? $\endgroup$ – Squeamish Ossifrage Mar 16 '18 at 17:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.