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

   1 /* -*-c-*-
   2  *
   3  * Scalar multiplication on elliptic curves
   4  *
   5  * (c) 2017 Straylight/Edgeware
   6  */
   7
   8 /*----- Licensing notice --------------------------------------------------*
   9  *
  10  * This file is part of secnet.
  11  * See README for full list of copyright holders.
  12  *
  13  * secnet is free software; you can redistribute it and/or modify it
  14  * under the terms of the GNU General Public License as published by
  15  * the Free Software Foundation; either version d of the License, or
  16  * (at your option) any later version.
  17  *
  18  * secnet is distributed in the hope that it will be useful, but
  19  * WITHOUT ANY WARRANTY; without even the implied warranty of
  20  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  21  * General Public License for more details.
  22  *
  23  * You should have received a copy of the GNU General Public License
  24  * version 3 along with secnet; if not, see
  25  * https://www.gnu.org/licenses/gpl.html.
  26  *
  27  * This file was originally part of Catacomb, but has been automatically
  28  * modified for incorporation into secnet: see `import-catacomb-crypto'
  29  * for details.
  30  *
  31  * Catacomb is free software; you can redistribute it and/or modify
  32  * it under the terms of the GNU Library General Public License as
  33  * published by the Free Software Foundation; either version 2 of the
  34  * License, or (at your option) any later version.
  35  *
  36  * Catacomb is distributed in the hope that it will be useful,
  37  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  38  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  39  * GNU Library General Public License for more details.
  40  *
  41  * You should have received a copy of the GNU Library General Public
  42  * License along with Catacomb; if not, write to the Free
  43  * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  44  * MA 02111-1307, USA.
  45  */
  46
  47 #ifndef CATACOMB_SCMUL_H
  48 #define CATACOMB_SCMUL_H
  49
  50 #ifdef __cplusplus
  51   extern "C" {
  52 #endif
  53
  54 /*----- Macros provided ---------------------------------------------------*/
  55
  56 #define SCMUL_WINLIM(winwd) (1 << (winwd))
  57 #define SCMUL_WINMASK(winwd) (SCMUL_WINLIM(winwd) - 1)
  58 #define SCMUL_TABSZ(winwd) (SCMUL_WINLIM(winwd)/2 + 1)
  59
  60 #define DEFINE_SCMUL(mulfn, f, winwd, scafwd, npiece, addfn, dblfn)     \
  61 void mulfn(f *X, f *Y, f *Z, const scaf_piece n[npiece],                \
  62            const f *X0, const f *Y0, const f *Z0)                       \
  63 {                                                                       \
  64   f VX[SCMUL_TABSZ(winwd)],                                             \
  65     VY[SCMUL_TABSZ(winwd)],                                             \
  66     VZ[SCMUL_TABSZ(winwd)];                                             \
  67   f TX, TY, TZ, UX, UY, UZ;                                             \
  68   unsigned i, j, k, w;                                                  \
  69   uint32 m_neg;                                                         \
  70   scaf_piece ni;                                                        \
  71                                                                         \
  72   /* Build a table of small multiples. */                               \
  73   f##_set(&VX[0], 0); f##_set(&VY[0], 1); f##_set(&VZ[0], 1);           \
  74   VX[1] = *X0; VY[1] = *Y0; VZ[1] = *Z0;                                \
  75   ptdbl(&VX[2], &VY[2], &VZ[2], &VX[1], &VY[1], &VZ[1]);                \
  76   for (i = 3; i < SCMUL_TABSZ(winwd); i += 2) {                         \
  77     addfn(&VX[i], &VY[i], &VZ[i],                                       \
  78           &VX[i - 1], &VY[i - 1], &VZ[i - 1], X0, Y0, Z0);              \
  79     dblfn(&VX[i + 1], &VY[i + 1], &VZ[i + 1],                           \
  80           &VX[(i + 1)/2], &VY[(i + 1)/2], &VZ[(i + 1)/2]);              \
  81   }                                                                     \
  82                                                                         \
  83   /* Now do the multiplication.  We lag a window behind the cursor      \
  84    * position because of the scalar recoding we do.                     \
  85    */                                                                   \
  86   f##_set(&TX, 0); f##_set(&TY, 1); f##_set(&TZ, 1);                    \
  87   for (i = (npiece), w = 0, m_neg = 0; i--; ) {                         \
  88     ni = n[i];                                                          \
  89                                                                         \
  90     /* Work through each window in the scalar piece. */                 \
  91     for (j = 0; j < (scafwd); j += (winwd)) {                           \
  92                                                                         \
  93       /* Shift along by a window. */                                    \
  94       for (k = 0; k < (winwd); k++)                                     \
  95         dblfn(&TX, &TY, &TZ, &TX, &TY, &TZ);                            \
  96                                                                         \
  97       /* Peek at the next window of four bits.  If the top bit is set   \
  98        * we lend a bit leftwards, into w.  It's too late for this to    \
  99        * affect the sign now, but if we negated earlier then the        \
 100        * addition would be wrong.                                       \
 101        */                                                               \
 102       w += (ni >> ((scafwd) - 1))&0x1u;                                 \
 103       w = ((SCMUL_WINLIM(winwd) - w)&m_neg) | (w&~m_neg);               \
 104                                                                         \
 105       /* Collect the entry from the table, and add or subtract. */      \
 106       f##_pickn(&UX, VX, SCMUL_TABSZ(winwd), w);                        \
 107       f##_pickn(&UY, VY, SCMUL_TABSZ(winwd), w);                        \
 108       f##_pickn(&UZ, VZ, SCMUL_TABSZ(winwd), w);                        \
 109       f##_condneg(&UX, &UX, m_neg);                                     \
 110       addfn(&TX, &TY, &TZ, &TX, &TY, &TZ, &UX, &UY, &UZ);               \
 111                                                                         \
 112       /* Move the next window into the delay slot.  If its top bit is   \
 113        * set, then negate it and set m_neg.                             \
 114        */                                                               \
 115       w = (ni >> ((scafwd) - (winwd)))&SCMUL_WINMASK(winwd);            \
 116       m_neg = -(uint32)((w >> ((winwd) - 1))&0x1u);                     \
 117       ni <<= (winwd);                                                   \
 118     }                                                                   \
 119   }                                                                     \
 120                                                                         \
 121   /* Do the final window.  Just fix the sign and go. */                 \
 122   for (k = 0; k < (winwd); k++)                                         \
 123     dblfn(&TX, &TY, &TZ, &TX, &TY, &TZ);                                \
 124   w = ((SCMUL_WINLIM(winwd) - w)&m_neg) | (w&~m_neg);                   \
 125   f##_pickn(&UX, VX, SCMUL_TABSZ(winwd), w);                            \
 126   f##_pickn(&UY, VY, SCMUL_TABSZ(winwd), w);                            \
 127   f##_pickn(&UZ, VZ, SCMUL_TABSZ(winwd), w);                            \
 128   f##_condneg(&UX, &UX, m_neg);                                         \
 129   addfn(X, Y, Z, &TX, &TY, &TZ, &UX, &UY, &UZ);                         \
 130 }
 131
 132 #define SCSIMMUL_WINLIM(winwd) (1 << (winwd))
 133 #define SCSIMMUL_WINMASK(winwd) (SCSIMMUL_WINLIM(winwd) - 1)
 134 #define SCSIMMUL_TABSZ(winwd) (1 << 2*(winwd))
 135
 136 #define DEFINE_SCSIMMUL(simmulfn, f, winwd,                             \
 137                         scafwd, npiece, addfn, dblfn)                   \
 138 void simmulfn(f *X, f *Y, f *Z,                                         \
 139               const scaf_piece n0[npiece],                              \
 140               const f *X0, const f *Y0, const f *Z0,                    \
 141               const scaf_piece n1[npiece],                              \
 142               const f *X1, const f *Y1, const f *Z1)                    \
 143 {                                                                       \
 144   f VX[SCSIMMUL_TABSZ(winwd)],                                          \
 145     VY[SCSIMMUL_TABSZ(winwd)],                                          \
 146     VZ[SCSIMMUL_TABSZ(winwd)];                                          \
 147   f TX, TY, TZ, UX, UY, UZ;                                             \
 148   unsigned i, j, k, w, ni0, ni1;                                        \
 149                                                                         \
 150   /* Build a table of small linear combinations. */                     \
 151   f##_set(&VX[0], 0); f##_set(&VY[0], 1); f##_set(&VZ[0], 1);           \
 152   VX[1] = *X0; VX[SCSIMMUL_WINLIM(winwd)] = *X1;                        \
 153   VY[1] = *Y0; VY[SCSIMMUL_WINLIM(winwd)] = *Y1;                        \
 154   VZ[1] = *Z0; VZ[SCSIMMUL_WINLIM(winwd)] = *Z1;                        \
 155   for (i = 2; i < SCSIMMUL_WINLIM(winwd); i <<= 1) {                    \
 156     dblfn(&VX[i], &VY[i], &VZ[i],                                       \
 157           &VX[i/2], &VY[i/2], &VZ[i/2]);                                \
 158     dblfn(&VX[i*SCSIMMUL_WINLIM(winwd)],                                \
 159           &VY[i*SCSIMMUL_WINLIM(winwd)],                                \
 160           &VZ[i*SCSIMMUL_WINLIM(winwd)],                                \
 161           &VX[i*SCSIMMUL_WINLIM(winwd)/2],                              \
 162           &VY[i*SCSIMMUL_WINLIM(winwd)/2],                              \
 163           &VZ[i*SCSIMMUL_WINLIM(winwd)/2]);                             \
 164   }                                                                     \
 165   for (i = 2; i < SCSIMMUL_TABSZ(winwd); i <<= 1) {                     \
 166     for (j = 1; j < i; j++)                                             \
 167       addfn(&VX[i + j], &VY[i + j], &VZ[i + j],                         \
 168             &VX[i], &VY[i], &VZ[i], &VX[j], &VY[j], &VZ[j]);            \
 169   }                                                                     \
 170                                                                         \
 171   /* Do the multiplication. */                                          \
 172   f##_set(&TX, 0); f##_set(&TY, 1); f##_set(&TZ, 1);                    \
 173   for (i = (npiece); i--; ) {                                           \
 174     ni0 = n0[i]; ni1 = n1[i];                                           \
 175                                                                         \
 176     /* Work through each window in the scalar pieces. */                \
 177     for (j = 0; j < (scafwd); j += (winwd)) {                           \
 178                                                                         \
 179       /* Shift along by a window. */                                    \
 180       for (k = 0; k < (winwd); k++)                                     \
 181         dblfn(&TX, &TY, &TZ, &TX, &TY, &TZ);                            \
 182                                                                         \
 183       /* Collect the next window from the scalars. */                   \
 184       w = (((ni0 >> ((scafwd) - (winwd)))&                              \
 185             SCSIMMUL_WINMASK(winwd)) |                                  \
 186            ((ni1 >> ((scafwd) - 2*(winwd)))&                            \
 187             (SCSIMMUL_WINMASK(winwd) << (winwd))));                     \
 188       ni0 <<= (winwd); ni1 <<= (winwd);                                 \
 189                                                                         \
 190       /* Collect the entry from the table, and add. */                  \
 191       f##_pickn(&UX, VX, SCSIMMUL_TABSZ(winwd), w);                     \
 192       f##_pickn(&UY, VY, SCSIMMUL_TABSZ(winwd), w);                     \
 193       f##_pickn(&UZ, VZ, SCSIMMUL_TABSZ(winwd), w);                     \
 194       addfn(&TX, &TY, &TZ, &TX, &TY, &TZ, &UX, &UY, &UZ);               \
 195     }                                                                   \
 196   }                                                                     \
 197                                                                         \
 198   /* Done. */                                                           \
 199   *X = TX; *Y = TY; *Z = TZ;                                            \
 200 }
 201
 202 /*----- That's all, folks -------------------------------------------------*/
 203
 204 #ifdef __cplusplus
 205   }
 206 #endif
 207
 208 #endif