chiark - git - mdw - secnet/blob - montladder.h

   1 /*
   2  * montladder.h: Montgomery's ladder
   3  */
   4 /*
   5  * This file is Free Software.  It has been modified to as part of its
   6  * incorporation into secnet.
   7  *
   8  * Copyright 2017 Mark Wooding
   9  *
  10  * You may redistribute this file and/or modify it under the terms of
  11  * the permissive licence shown below.
  12  *
  13  * You may redistribute secnet as a whole and/or modify it under the
  14  * terms of the GNU General Public License as published by the Free
  15  * Software Foundation; either version 3, or (at your option) any
  16  * later version.
  17  *
  18  * This program is distributed in the hope that it will be useful,
  19  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  20  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  21  * GNU General Public License for more details.
  22  *
  23  * You should have received a copy of the GNU General Public License
  24  * along with this program; if not, see
  25  * https://www.gnu.org/licenses/gpl.html.
  26  */
  27 /*
  28  * Imported from Catacomb (2017-04-30).  The file's original comment headers
  29  * are preserved below.
  30  */
  31 /* -*-c-*-
  32  *
  33  * Definitions for Montgomery's ladder
  34  *
  35  * (c) 2017 Straylight/Edgeware
  36  */
  37
  38 /*----- Licensing notice --------------------------------------------------*
  39  *
  40  * This file is part of Catacomb.
  41  *
  42  * Catacomb is free software; you can redistribute it and/or modify
  43  * it under the terms of the GNU Library General Public License as
  44  * published by the Free Software Foundation; either version 2 of the
  45  * License, or (at your option) any later version.
  46  *
  47  * Catacomb is distributed in the hope that it will be useful,
  48  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  49  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  50  * GNU Library General Public License for more details.
  51  *
  52  * You should have received a copy of the GNU Library General Public
  53  * License along with Catacomb; if not, write to the Free
  54  * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  55  * MA 02111-1307, USA.
  56  */
  57
  58 #ifndef CATACOMB_MONTLADDER_H
  59 #define CATACOMB_MONTLADDER_H
  60
  61 #ifdef __cplusplus
  62   extern "C" {
  63 #endif
  64
  65 /*----- Notes on the Montgomery ladder ------------------------------------*
  66  *
  67  * The algorithm here is Montgomery's famous binary ladder for calculating
  68  * x-coordinates of scalar products on a particular shape of elliptic curve,
  69  * as elucidated by Daniel Bernstein.
  70  *
  71  * Let Q = (x_1, y_1) be the base point, for some unknown y_1 (which will
  72  * turn out to be unimportant).  Define x_n, z_n by x(n Q) = (x_n : z_n).
  73  * Given x_n, z_n, x_{n+1}, z_{n+1}, Montgomery's differential addition
  74  * formulae calculate x_{2i}, z_{2i}, x_{2i+1}, z_{2i+1}.  Furthermore,
  75  * calculating x_{2i}, z_{2i} requires only x_n, z_n, and the calculation of
  76  * x_{2i+1}, z_{2i+1} is symmetrical.
  77  */
  78
  79 /*----- Functions provided ------------------------------------------------*/
  80
  81 /* F designates a field, both naming the type of its elements and acting as a
  82  * prefix for the standard field operations `F_add', `F_sub', `F_mul',
  83  * `F_sqr', and `F_inv' (the last of which should return zero its own
  84  * inverse); and the constant-time utility `F_condswap'.
  85  *
  86  * The macro calculates the x-coordinate of the product k Q, where Q is a
  87  * point on the elliptic curve B y^2 = x^3 + A x^2 + x or its quadratic
  88  * twist, for some irrelevant B.  The x-coordinate of Q is given as X1 (a
  89  * pointer to a field element).  The scalar k is given as a vector of NK
  90  * unsigned integers KW, each containing NBITS significant bits, with the
  91  * least-significant element first.  The result is written to the field
  92  * element pointed to by Z.
  93  *
  94  * The curve coefficient A is given indirectly, as the name of a macro MULA0
  95  * such that
  96  *
  97  *      MULA0(z, x)
  98  *
  99  * will store in z the value (A - 2)/4 x.
 100  */
 101 #define MONT_LADDER(f, mula0, kw, nk, nbits, z, x1) do {                \
 102   f _x, _z, _u, _w;                                                     \
 103   f _t0, _t1, _t2, _t3, _t4;                                            \
 104   uint32 _m = 0, _mm = 0, _k;                                           \
 105   unsigned _i, _j;                                                      \
 106                                                                         \
 107   /* Initialize the main variables.  We'll have, (x, z) and (u, w)      \
 108    * holding (x_n, z_n) and (x_{n+1}, z_{n+1}) in some order, but       \
 109    * there's some weirdness: if m = 0 then (x, z) = (x_n, z_n) and      \
 110    * (u, v) = (x_{n+1}, z_{n+1}); if m /= 0, then the pairs are         \
 111    * swapped over.                                                      \
 112    *                                                                    \
 113    * Initially, we have (x_0, z_0) = (1, 0), representing the identity  \
 114    * at projective-infinity, which works fine; and we have z_1 = 1.     \
 115    */                                                                   \
 116   _u = *(x1); f##_set(&_w, 1); f##_set(&_x, 1); f##_set(&_z, 0);        \
 117                                                                         \
 118   /* The main ladder loop.  Work through each bit of the clamped key. */ \
 119   for (_i = (nk); _i--; ) {                                             \
 120     _k = (kw)[_i];                                                      \
 121     for (_j = 0; _j < (nbits); _j++) {                                  \
 122       /* We're at bit i of the scalar key (represented by 32 (7 - i) +  \
 123        * (31 - j) in our loop variables -- don't worry about that).     \
 124        * Let k = 2^i k_i + k'_i, with 0 <= k'_i < 2^i.  In particular,  \
 125        * then, k_0 = k.  Write Q(i) = (x_i, z_i).                       \
 126        *                                                                \
 127        * We currently have, in (x, z) and (u, w), Q(k_i) and Q(k_i +    \
 128        * 1), in some order.  The ladder step will double the point in   \
 129        * (x, z), and leave the sum of (x : z) and (u : w) in (u, w).    \
 130        */                                                               \
 131                                                                         \
 132       _mm = -((_k >> ((nbits) - 1))&1u); _k <<= 1;                      \
 133       f##_condswap(&_x, &_u, _m ^ _mm);                                 \
 134       f##_condswap(&_z, &_w, _m ^ _mm);                                 \
 135       _m = _mm;                                                         \
 136                                                                         \
 137       f##_add(&_t0, &_x, &_z);          /* x + z */                     \
 138       f##_sub(&_t1, &_x, &_z);          /* x - z */                     \
 139       f##_add(&_t2, &_u, &_w);          /* u + w */                     \
 140       f##_sub(&_t3, &_u, &_w);          /* u - w */                     \
 141       f##_mul(&_t2, &_t2, &_t1);        /* (x - z) (u + w) */           \
 142       f##_mul(&_t3, &_t3, &_t0);        /* (x + z) (u - w) */           \
 143       f##_sqr(&_t0, &_t0);              /* (x + z)^2 */                 \
 144       f##_sqr(&_t1, &_t1);              /* (x - z)^2 */                 \
 145       f##_mul(&_x, &_t0, &_t1);         /* (x + z)^2 (x - z)^2 */       \
 146       f##_sub(&_t1, &_t0, &_t1);        /* (x + z)^2 - (x - z)^2 */     \
 147       mula0(&_t4, &_t1);             /* A_0 ((x + z)^2 - (x - z)^2) */  \
 148       f##_add(&_t0, &_t0, &_t4);        /* A_0 ... + (x + z)^2 */       \
 149       f##_mul(&_z, &_t0, &_t1);  /* (...^2 - ...^2) (A_0 ... + ...) */  \
 150       f##_add(&_t0, &_t2, &_t3); /* (x - z) (u + w) + (x + z) (u - w) */ \
 151       f##_sub(&_t1, &_t2, &_t3); /* (x - z) (u + w) - (x + z) (u - w) */ \
 152       f##_sqr(&_u, &_t0);               /* (... + ...)^2 */             \
 153       f##_sqr(&_t1, &_t1);              /* (... - ...)^2 */             \
 154       f##_mul(&_w, &_t1, (x1));         /* x_1 (... - ...)^2 */         \
 155     }                                                                   \
 156   }                                                                     \
 157                                                                         \
 158   /* Almost done.  Undo the swap, if any. */                            \
 159   f##_condswap(&_x, &_u, _m);                                           \
 160   f##_condswap(&_z, &_w, _m);                                           \
 161                                                                         \
 162   /* And convert to affine. */                                          \
 163   f##_inv(&_t0, &_z);                                                   \
 164   f##_mul((z), &_x, &_t0);                                              \
 165 } while (0)
 166
 167 /*----- That's all, folks -------------------------------------------------*/
 168
 169 #ifdef __cplusplus
 170   }
 171 #endif
 172
 173 #endif