Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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.
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 those who are forced to comply with bureaucratic 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!
