X-Git-Url: https://git.distorted.org.uk/~mdw/secnet/blobdiff_plain/ae8cd973b817f81c075ab20e84d3239125146f24..8a7654a695e8ecdc8c14dced445839a7a7e6a8ca:/montladder.h

diff --git a/montladder.h b/montladder.h
new file mode 100644
index 0000000..bcd3539
--- /dev/null
+++ b/montladder.h
@@ -0,0 +1,162 @@
+/* -*-c-*-
+ *
+ * Definitions for Montgomery's ladder
+ *
+ * (c) 2017 Straylight/Edgeware
+ */
+
+/*----- Licensing notice --------------------------------------------------*
+ *
+ * This file is part of secnet.
+ * See README for full list of copyright holders.
+ *
+ * secnet is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version d of the License, or
+ * (at your option) any later version.
+ *
+ * secnet is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * version 3 along with secnet; if not, see
+ * https://www.gnu.org/licenses/gpl.html.
+ *
+ * This file was originally part of Catacomb, but has been automatically
+ * modified for incorporation into secnet: see `import-catacomb-crypto'
+ * for details.
+ *
+ * Catacomb is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU Library General Public License as
+ * published by the Free Software Foundation; either version 2 of the
+ * License, or (at your option) any later version.
+ *
+ * Catacomb is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU Library General Public License for more details.
+ *
+ * You should have received a copy of the GNU Library General Public
+ * License along with Catacomb; if not, write to the Free
+ * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
+ * MA 02111-1307, USA.
+ */
+
+#ifndef CATACOMB_MONTLADDER_H
+#define CATACOMB_MONTLADDER_H
+
+#ifdef __cplusplus
+  extern "C" {
+#endif
+
+/*----- Notes on the Montgomery ladder ------------------------------------*
+ *
+ * The algorithm here is Montgomery's famous binary ladder for calculating
+ * x-coordinates of scalar products on a particular shape of elliptic curve,
+ * as elucidated by Daniel Bernstein.
+ *
+ * Let Q = (x_1, y_1) be the base point, for some unknown y_1 (which will
+ * turn out to be unimportant).  Define x_n, z_n by x(n Q) = (x_n : z_n).
+ * Given x_n, z_n, x_{n+1}, z_{n+1}, Montgomery's differential addition
+ * formulae calculate x_{2i}, z_{2i}, x_{2i+1}, z_{2i+1}.  Furthermore,
+ * calculating x_{2i}, z_{2i} requires only x_n, z_n, and the calculation of
+ * x_{2i+1}, z_{2i+1} is symmetrical.
+ */
+
+/*----- Functions provided ------------------------------------------------*/
+
+/* F designates a field, both naming the type of its elements and acting as a
+ * prefix for the standard field operations `F_add', `F_sub', `F_mul',
+ * `F_sqr', and `F_inv' (the last of which should return zero its own
+ * inverse); and the constant-time utility `F_condswap'.
+ *
+ * The macro calculates the x-coordinate of the product k Q, where Q is a
+ * point on the elliptic curve B y^2 = x^3 + A x^2 + x or its quadratic
+ * twist, for some irrelevant B.  The x-coordinate of Q is given as X1 (a
+ * pointer to a field element).  The scalar k is given as a vector of NK
+ * unsigned integers KW, each containing NBITS significant bits, with the
+ * least-significant element first.  The result is written to the field
+ * element pointed to by Z.
+ *
+ * The curve coefficient A is given indirectly, as the name of a macro MULA0
+ * such that
+ *
+ *	MULA0(z, x)
+ *
+ * will store in z the value (A - 2)/4 x.
+ */
+#define MONT_LADDER(f, mula0, kw, nk, nbits, z, x1) do {		\
+  f _x, _z, _u, _w;							\
+  f _t0, _t1, _t2, _t3, _t4;						\
+  uint32 _m = 0, _mm = 0, _k;						\
+  unsigned _i, _j;							\
+									\
+  /* Initialize the main variables.  We'll have, (x, z) and (u, w)	\
+   * holding (x_n, z_n) and (x_{n+1}, z_{n+1}) in some order, but	\
+   * there's some weirdness: if m = 0 then (x, z) = (x_n, z_n) and	\
+   * (u, v) = (x_{n+1}, z_{n+1}); if m /= 0, then the pairs are		\
+   * swapped over.							\
+   *									\
+   * Initially, we have (x_0, z_0) = (1, 0), representing the identity	\
+   * at projective-infinity, which works fine; and we have z_1 = 1.	\
+   */									\
+  _u = *(x1); f##_set(&_w, 1); f##_set(&_x, 1); f##_set(&_z, 0);	\
+									\
+  /* The main ladder loop.  Work through each bit of the clamped key. */ \
+  for (_i = (nk); _i--; ) {						\
+    _k = (kw)[_i];							\
+    for (_j = 0; _j < (nbits); _j++) {					\
+      /* We're at bit i of the scalar key (represented by 32 (7 - i) +	\
+       * (31 - j) in our loop variables -- don't worry about that).	\
+       * Let k = 2^i k_i + k'_i, with 0 <= k'_i < 2^i.  In particular,	\
+       * then, k_0 = k.  Write Q(i) = (x_i, z_i).			\
+       *								\
+       * We currently have, in (x, z) and (u, w), Q(k_i) and Q(k_i +	\
+       * 1), in some order.  The ladder step will double the point in	\
+       * (x, z), and leave the sum of (x : z) and (u : w) in (u, w).	\
+       */								\
+									\
+      _mm = -((_k >> ((nbits) - 1))&1u); _k <<= 1;			\
+      f##_condswap(&_x, &_u, _m ^ _mm);					\
+      f##_condswap(&_z, &_w, _m ^ _mm);					\
+      _m = _mm;								\
+									\
+      f##_add(&_t0, &_x, &_z);		/* x + z */			\
+      f##_sub(&_t1, &_x, &_z);		/* x - z */			\
+      f##_add(&_t2, &_u, &_w);		/* u + w */			\
+      f##_sub(&_t3, &_u, &_w);		/* u - w */			\
+      f##_mul(&_t2, &_t2, &_t1);	/* (x - z) (u + w) */		\
+      f##_mul(&_t3, &_t3, &_t0);	/* (x + z) (u - w) */		\
+      f##_sqr(&_t0, &_t0);		/* (x + z)^2 */			\
+      f##_sqr(&_t1, &_t1);		/* (x - z)^2 */			\
+      f##_mul(&_x, &_t0, &_t1);		/* (x + z)^2 (x - z)^2 */	\
+      f##_sub(&_t1, &_t0, &_t1);	/* (x + z)^2 - (x - z)^2 */	\
+      mula0(&_t4, &_t1);	     /* A_0 ((x + z)^2 - (x - z)^2) */	\
+      f##_add(&_t0, &_t0, &_t4);	/* A_0 ... + (x + z)^2 */	\
+      f##_mul(&_z, &_t0, &_t1);	 /* (...^2 - ...^2) (A_0 ... + ...) */	\
+      f##_add(&_t0, &_t2, &_t3); /* (x - z) (u + w) + (x + z) (u - w) */ \
+      f##_sub(&_t1, &_t2, &_t3); /* (x - z) (u + w) - (x + z) (u - w) */ \
+      f##_sqr(&_u, &_t0);		/* (... + ...)^2 */		\
+      f##_sqr(&_t1, &_t1);		/* (... - ...)^2 */		\
+      f##_mul(&_w, &_t1, (x1));		/* x_1 (... - ...)^2 */		\
+    }									\
+  }									\
+									\
+  /* Almost done.  Undo the swap, if any. */				\
+  f##_condswap(&_x, &_u, _m);						\
+  f##_condswap(&_z, &_w, _m);						\
+									\
+  /* And convert to affine. */						\
+  f##_inv(&_t0, &_z);							\
+  f##_mul((z), &_x, &_t0);						\
+} while (0)
+
+/*----- That's all, folks -------------------------------------------------*/
+
+#ifdef __cplusplus
+  }
+#endif
+
+#endif