[Cfrg] Leading zero bits in the Montgomery ladder

[Robert Ransom <[e-mail]>]

Traditionally, Montgomery's formulas are stated as a recurrence
relation which computes the x coordinates of 2*n*P and (2*n + 1)*P
from the x coordinates of n*P and (n + 1)*P.  This definition suggests
that the number of ladder steps depends on the position of the most
significant non-zero bit of the scalar.

This is not true: the Montgomery ladder can be used with leading zero
bits.  For example, Adam Langley's curve25519-donna always performs a
ladder step for a leading zero bit at the beginning of each scalar.
Experimentally, it produces correct results, so it must be correct, at
least except for a handful of exceptional cases.

The fact that the Montgomery ladder allows leading zero bits is
somewhat well known, and was almost explicitly stated by Dr. Bernstein
in his recent presentation to CFRG, but I've never seen a good
description of the Montgomery ladder which explains *why* this is
true.


The best description of the Montgomery ladder that I know of (for a
mathematician) is in section 8 of
<http://echidna.maths.usyd.edu.au/~kohel/pub/indocrypt.pdf>;
unfortunately, the scalar multiplication algorithm presented there is
incorrect.  My description below is based on Kohel's, but uses a
different definition of the Kummer-oriented curve, and a different
algorithm for scalar multiplication.

* *Over an algebraically closed field*, a ‘Kummer variety’ K of a
  group variety E is an algebraic variety, specified along with a map
  k from E to the K such that k(P) = k(-P) for each element P of E,
  k(P) is not equal to k(Q) unless Q = P or Q = -P, and every element
  of K is of the form k(P).

  In the non-algebraically-closed fields which must be used for
  cryptography, not every point on K corresponds to an element of E
  over the same base field; the other points represent elements of the
  quadratic twist of E.  ‘Twist security’ means that both the curve
  and its quadratic twist have group structures suitable for
  cryptographic use, so that software can safely use a point on the
  Kummer variety without checking which curve it belongs to.

  When E is an elliptic curve, K is always the whole projective line
  P^1.

  The Kummer variety usually used for Montgomery curves is P^1, with
  each affine point (x : y : 1) mapped to (x : 1) (i.e. discarding the
  y coordinate), and the point at infinity O = (0 : 1 : 0) mapped to
  (1 : 0).

* The ‘Kummer-oriented curve’ for scalar multiplication of a point P
  such that 2*P is not equal to O is an elliptic curve isomorphic to
  E.  It consists of the set of pairs (k(Q), k(R)) where Q and R are
  points on E, such that R - Q = P.  A point Q on E corresponds to
  (k(Q), k(Q + P)) on the Kummer-oriented curve; I will denote this
  map from E as koc.

  (When 2*P = O, koc(Q) = koc(-Q), so the Kummer-oriented curve is
  neither isomorphic to E nor an elliptic curve.  However, the
  abstract Montgomery ladder algorithm stated below does work
  correctly in this case (ignoring the possibility of exceptional
  cases in the formulas used).)

  Two operations on the Kummer-oriented curve are important here:

  - Doubling on the Kummer-oriented curve maps (k(Q), k(Q + P)) to
    (k(2*Q), k(2*Q + P)) = (k(2*Q), k((Q + P) + Q)), and is
    implemented using explicit formulas for doubling (to obtain the
    first coordinate) and differential addition (to obtain the second
    coordinate; note that (Q+P) - Q = P is known) on the Kummer
    variety.  (Kohel denotes this map using the Greek letter phi; I
    will denote it as f.)

  - Exchanging the two coordinates of a point on the Kummer-oriented
    curve maps koc(Q) = (k(Q), k(Q + P)) to (k(Q + P), k(Q)) = (k(-Q -
    P), k(-Q)) = koc(-Q - P); thus, the result is a point on the
    curve.  (Kohel denotes this map using the Greek letter sigma; I
    will denote it as s.)

  For a point Q on the Kummer-oriented curve, s(Q) = -Q - P, f(s(Q)) =
  -2*Q - 2*P, and s(f(s(Q))) = (2*Q + 2*P) - P = 2*Q + P.

* Given k(P) as input, the Montgomery ladder's state Q (a point on the
  Kummer-oriented curve) is initialized as Q = koc(O) = (k(O), k(P)).

  The ladder processes a scalar one bit at a time, starting from the
  most significant end.  To process a zero bit, Q is replaced with
  f(Q) = 2*Q; to process a one bit, Q is replaced with s(f(s(Q))) =
  2*Q + P.

  Traditionally, the first scalar bit processed by the Montgomery
  ladder is the most significant one bit; however, in the abstract,
  processing a leading zero bit does not change the state (since
  f(koc(O)) = koc(2*O) = koc(O)), so it is safe unless an exceptional
  case occurs in the formulas.


To check whether a leading zero bit can trigger exceptional cases in
Montgomery's formulas, I evaluated the formula ‘ladd-1984-m-3’ from
<http://hyperelliptic.org/EFD/g1p/data/montgom/xz/ladder/ladd-1987-m-3>
by hand for the case of a leading zero bit: P1 arbitrary, P2 = O = (1
: 0), and P3 = -P1 (which has the same representation as P1).

When P1 and P3 are the point at infinity ((1 : 0)) or the x=0 point of
order 2 ((0 : 1)), the output P5 is undefined; otherwise, P5 is
defined and equal (when compared as an element of P^1) to P3.
Dr. Bernstein's modified x-coordinate function (which maps the point
at infinity, the x=0 point of order 2, and the undefined point to 0)
makes these exceptional cases harmless.

In all of these cases, P4 = P2.


Robert Ransom