### [Cfrg] Leading zero bits in the Montgomery ladder

Robert Ransom <rransom.8774@gmail.com> Sat, 26 July 2014 05:49 UTC

Return-Path: <rransom.8774@gmail.com>

X-Original-To: cfrg@ietfa.amsl.com

Delivered-To: cfrg@ietfa.amsl.com

Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id C22B61A02FF for <cfrg@ietfa.amsl.com>; Fri, 25 Jul 2014 22:49:07 -0700 (PDT)

X-Virus-Scanned: amavisd-new at amsl.com

X-Spam-Flag: NO

X-Spam-Score: -1.45

X-Spam-Level:

X-Spam-Status: No, score=-1.45 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_ENVFROM_END_DIGIT=0.25, FREEMAIL_FROM=0.001, GB_I_LETTER=-2, MANGLED_CCK=2.3, SPF_PASS=-0.001] autolearn=no

Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id nfMzNMNariJ8 for <cfrg@ietfa.amsl.com>; Fri, 25 Jul 2014 22:49:06 -0700 (PDT)

Received: from mail-qg0-x229.google.com (mail-qg0-x229.google.com [IPv6:2607:f8b0:400d:c04::229]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 5203F1A02F9 for <cfrg@irtf.org>; Fri, 25 Jul 2014 22:49:06 -0700 (PDT)

Received: by mail-qg0-f41.google.com with SMTP id q107so6171045qgd.28 for <cfrg@irtf.org>; Fri, 25 Jul 2014 22:49:05 -0700 (PDT)

DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:date:message-id:subject:from:to:content-type :content-transfer-encoding; bh=Dq02edNnTCv1h3K01ce8NFV/VNoWBmikzQxrwjBPT+A=; b=frwfW+hmamznfHLQHSRXVMPmjCGQXzxJC5ZX91KwXjHsHyIKZGRnsDmSu1KYPOUpBi f3lG2aMvTq5Ig2DbvR9W4HFkzy9K9vqqj1RB0maNlgPXgPzGU+jTRmHkp+/jd2RhTXsy ozikNQDRv23xktFhDElNbFe42N1oIlTWcWNDPScIoE1I5YLOnA4ckwRdRmf8gw8v12tT aHuyBtv0VUCnwx9/uwkONCc1Asr8HkxWxf0fKAXUzlbQYpHgzRCjyw8nuruUgSdHTp7K 5QNa278rZ3VlaYMZcrpLHaup6lc8VZdt+TbiFL0uGwlMWw5X6EiXRIOcf+P/WXij7j49 FkOg==

MIME-Version: 1.0

X-Received: by 10.224.43.196 with SMTP id x4mr32252389qae.63.1406353745358; Fri, 25 Jul 2014 22:49:05 -0700 (PDT)

Received: by 10.140.98.233 with HTTP; Fri, 25 Jul 2014 22:49:05 -0700 (PDT)

Date: Fri, 25 Jul 2014 22:49:05 -0700

Message-ID: <CABqy+sqDy6AjzLSGqLgzf6DvZxqQU6j5z=enimQdd6DaAHayBQ@mail.gmail.com>

From: Robert Ransom <rransom.8774@gmail.com>

To: cfrg@irtf.org

Content-Type: text/plain; charset="UTF-8"

Content-Transfer-Encoding: quoted-printable

Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/2uJzHF2e4eRDsulv_o1YQqfSskE

Subject: [Cfrg] Leading zero bits in the Montgomery ladder

X-BeenThere: cfrg@irtf.org

X-Mailman-Version: 2.1.15

Precedence: list

List-Id: Crypto Forum Research Group <cfrg.irtf.org>

List-Unsubscribe: <http://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>

List-Archive: <http://www.irtf.org/mail-archive/web/cfrg/>

List-Post: <mailto:cfrg@irtf.org>

List-Help: <mailto:cfrg-request@irtf.org?subject=help>

List-Subscribe: <http://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>

X-List-Received-Date: Sat, 26 Jul 2014 05:49:07 -0000

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

- [Cfrg] Leading zero bits in the Montgomery ladder Robert Ransom