3 * Definitions for Montgomery's ladder
5 * (c) 2017 Straylight/Edgeware
8 /*----- Licensing notice --------------------------------------------------*
10 * This file is part of Catacomb.
12 * Catacomb is free software; you can redistribute it and/or modify
13 * it under the terms of the GNU Library General Public License as
14 * published by the Free Software Foundation; either version 2 of the
15 * License, or (at your option) any later version.
17 * Catacomb is distributed in the hope that it will be useful,
18 * but WITHOUT ANY WARRANTY; without even the implied warranty of
19 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
20 * GNU Library General Public License for more details.
22 * You should have received a copy of the GNU Library General Public
23 * License along with Catacomb; if not, write to the Free
24 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
28 #ifndef CATACOMB_MONTLADDER_H
29 #define CATACOMB_MONTLADDER_H
35 /*----- Notes on the Montgomery ladder ------------------------------------*
37 * The algorithm here is Montgomery's famous binary ladder for calculating
38 * x-coordinates of scalar products on a particular shape of elliptic curve,
39 * as elucidated by Daniel Bernstein.
41 * Let Q = (x_1, y_1) be the base point, for some unknown y_1 (which will
42 * turn out to be unimportant). Define x_n, z_n by x(n Q) = (x_n : z_n).
43 * Given x_n, z_n, x_{n+1}, z_{n+1}, Montgomery's differential addition
44 * formulae calculate x_{2i}, z_{2i}, x_{2i+1}, z_{2i+1}. Furthermore,
45 * calculating x_{2i}, z_{2i} requires only x_n, z_n, and the calculation of
46 * x_{2i+1}, z_{2i+1} is symmetrical.
49 /*----- Functions provided ------------------------------------------------*/
51 /* F designates a field, both naming the type of its elements and acting as a
52 * prefix for the standard field operations `F_add', `F_sub', `F_mul',
53 * `F_sqr', and `F_inv' (the last of which should return zero its own
54 * inverse); and the constant-time utility `F_condswap'.
56 * The macro calculates the x-coordinate of the product k Q, where Q is a
57 * point on the elliptic curve B y^2 = x^3 + A x^2 + x or its quadratic
58 * twist, for some irrelevant B. The x-coordinate of Q is given as X1 (a
59 * pointer to a field element). The scalar k is given as a vector of NK
60 * unsigned integers KW, each containing NBITS significant bits, with the
61 * least-significant element first. The result is written to the field
62 * element pointed to by Z.
64 * The curve coefficient A is given indirectly, as the name of a macro MULA0
69 * will store in z the value (A - 2)/4 x.
71 #define MONT_LADDER(f, mula0, kw, nk, nbits, z, x1) do { \
73 f _t0, _t1, _t2, _t3, _t4; \
74 uint32 _m = 0, _mm = 0, _k; \
77 /* Initialize the main variables. We'll have, (x, z) and (u, w) \
78 * holding (x_n, z_n) and (x_{n+1}, z_{n+1}) in some order, but \
79 * there's some weirdness: if m = 0 then (x, z) = (x_n, z_n) and \
80 * (u, v) = (x_{n+1}, z_{n+1}); if m /= 0, then the pairs are \
83 * Initially, we have (x_0, z_0) = (1, 0), representing the identity \
84 * at projective-infinity, which works fine; and we have z_1 = 1. \
86 _u = *(x1); f##_set(&_w, 1); f##_set(&_x, 1); f##_set(&_z, 0); \
88 /* The main ladder loop. Work through each bit of the clamped key. */ \
89 for (_i = (nk); _i--; ) { \
91 for (_j = 0; _j < (nbits); _j++) { \
92 /* We're at bit i of the scalar key (represented by 32 (7 - i) + \
93 * (31 - j) in our loop variables -- don't worry about that). \
94 * Let k = 2^i k_i + k'_i, with 0 <= k'_i < 2^i. In particular, \
95 * then, k_0 = k. Write Q(i) = (x_i, z_i). \
97 * We currently have, in (x, z) and (u, w), Q(k_i) and Q(k_i + \
98 * 1), in some order. The ladder step will double the point in \
99 * (x, z), and leave the sum of (x : z) and (u : w) in (u, w). \
102 _mm = -((_k >> ((nbits) - 1))&1u); _k <<= 1; \
103 f##_condswap(&_x, &_u, _m ^ _mm); \
104 f##_condswap(&_z, &_w, _m ^ _mm); \
107 f##_add(&_t0, &_x, &_z); /* x + z */ \
108 f##_sub(&_t1, &_x, &_z); /* x - z */ \
109 f##_add(&_t2, &_u, &_w); /* u + w */ \
110 f##_sub(&_t3, &_u, &_w); /* u - w */ \
111 f##_mul(&_t2, &_t2, &_t1); /* (x - z) (u + w) */ \
112 f##_mul(&_t3, &_t3, &_t0); /* (x + z) (u - w) */ \
113 f##_sqr(&_t0, &_t0); /* (x + z)^2 */ \
114 f##_sqr(&_t1, &_t1); /* (x - z)^2 */ \
115 f##_mul(&_x, &_t0, &_t1); /* (x + z)^2 (x - z)^2 */ \
116 f##_sub(&_t1, &_t0, &_t1); /* (x + z)^2 - (x - z)^2 */ \
117 mula0(&_t4, &_t1); /* A_0 ((x + z)^2 - (x - z)^2) */ \
118 f##_add(&_t0, &_t0, &_t4); /* A_0 ... + (x + z)^2 */ \
119 f##_mul(&_z, &_t0, &_t1); /* (...^2 - ...^2) (A_0 ... + ...) */ \
120 f##_add(&_t0, &_t2, &_t3); /* (x - z) (u + w) + (x + z) (u - w) */ \
121 f##_sub(&_t1, &_t2, &_t3); /* (x - z) (u + w) - (x + z) (u - w) */ \
122 f##_sqr(&_u, &_t0); /* (... + ...)^2 */ \
123 f##_sqr(&_t1, &_t1); /* (... - ...)^2 */ \
124 f##_mul(&_w, &_t1, (x1)); /* x_1 (... - ...)^2 */ \
128 /* Almost done. Undo the swap, if any. */ \
129 f##_condswap(&_x, &_u, _m); \
130 f##_condswap(&_z, &_w, _m); \
132 /* And convert to affine. */ \
133 f##_inv(&_t0, &_z); \
134 f##_mul((z), &_x, &_t0); \
137 /*----- That's all, folks -------------------------------------------------*/