@@@ delete old catcomb import
[secnet] / montladder.h
diff --git a/montladder.h b/montladder.h
deleted file mode 100644 (file)
index 4292158..0000000
+++ /dev/null
@@ -1,173 +0,0 @@
-/*
- * montladder.h: Montgomery's ladder
- */
-/*
- * This file is Free Software.  It has been modified to as part of its
- * incorporation into secnet.
- *
- * Copyright 2017 Mark Wooding
- *
- * You may redistribute this file and/or modify it under the terms of
- * the permissive licence shown below.
- *
- * You may redistribute secnet as a whole and/or modify it under the
- * terms of the GNU General Public License as published by the Free
- * Software Foundation; either version 3, or (at your option) any
- * later version.
- *
- * This program 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
- * along with this program; if not, see
- * https://www.gnu.org/licenses/gpl.html.
- */
-/*
- * Imported from Catacomb (2017-04-30).  The file's original comment headers
- * are preserved below.
- */
-/* -*-c-*-
- *
- * Definitions for Montgomery's ladder
- *
- * (c) 2017 Straylight/Edgeware
- */
-
-/*----- Licensing notice --------------------------------------------------*
- *
- * This file is part of Catacomb.
- *
- * 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