lib/nettle/ecc_mulmod.c

   1 /*
   2  * Copyright (C) 2011-2012 Free Software Foundation, Inc.
   3  *
   4  * This file is part of GNUTLS.
   5  *
   6  * The GNUTLS library is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU Lesser General Public License
   8  * as published by the Free Software Foundation; either version 3 of
   9  * the License, or (at your option) any later version.
  10  *
  11  * This library is distributed in the hope that it will be useful, but
  12  * WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14  * Lesser General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU Lesser General Public License
  17  * along with this program.  If not, see <http://www.gnu.org/licenses/>
  18  *
  19  */
  20
  21 /* Based on public domain code of LibTomCrypt by Tom St Denis.
  22  * Adapted to gmp and nettle by Nikos Mavrogiannopoulos.
  23  */
  24
  25 #include "ecc.h"
  26
  27 /* size of sliding window, don't change this! */
  28 #define WINSIZE 4
  29
  30 /*
  31    Perform a point multiplication
  32    @param k    The scalar to multiply by
  33    @param G    The base point
  34    @param R    [out] Destination for kG
  35    @param modulus  The modulus of the field the ECC curve is in
  36    @param map      Boolean whether to map back to affine or not (1==map, 0 == leave in projective)
  37    @return CRYPT_OK on success
  38 */
  39 int
  40 ecc_mulmod (mpz_t k, ecc_point * G, ecc_point * R, mpz_t a, mpz_t modulus,
  41                 int map)
  42
  43 {
  44    ecc_point *tG, *M[8];
  45    int        i, j, err, bitidx;
  46    int        first, bitbuf, bitcpy, mode;
  47
  48    if (k == NULL || G == NULL || R == NULL || modulus == NULL)
  49      return -1;
  50
  51   /* alloc ram for window temps */
  52   for (i = 0; i < 8; i++) {
  53       M[i] = ecc_new_point();
  54       if (M[i] == NULL) {
  55          for (j = 0; j < i; j++) {
  56              ecc_del_point(M[j]);
  57          }
  58
  59          return -1;
  60       }
  61   }
  62
  63    /* make a copy of G incase R==G */
  64    tG = ecc_new_point();
  65    if (tG == NULL)
  66      {
  67        err = -1;
  68        goto done;
  69      }
  70
  71    /* tG = G  and convert to montgomery */
  72    mpz_set (tG->x, G->x);
  73    mpz_set (tG->y, G->y);
  74    mpz_set (tG->z, G->z);
  75
  76    /* calc the M tab, which holds kG for k==8..15 */
  77    /* M[0] == 8G */
  78    if ((err = ecc_projective_dbl_point (tG, M[0], a, modulus)) != 0)
  79      goto done;
  80
  81    if ((err = ecc_projective_dbl_point (M[0], M[0], a, modulus)) != 0)
  82      goto done;
  83
  84    if ((err = ecc_projective_dbl_point (M[0], M[0], a, modulus)) != 0)
  85      goto done;
  86
  87    /* now find (8+k)G for k=1..7 */
  88    for (j = 9; j < 16; j++) {
  89      if (ecc_projective_add_point(M[j-9], tG, M[j-8], a, modulus) != 0)
  90        goto done;
  91    }
  92
  93    /* setup sliding window */
  94    mode   = 0;
  95    bitidx = mpz_size (k) * GMP_NUMB_BITS - 1;
  96    bitcpy = bitbuf = 0;
  97    first  = 1;
  98
  99    /* perform ops */
 100    for (;;) {
 101      /* grab next digit as required */
 102      if (bitidx == -1) {
 103        break;
 104      }
 105
 106      /* grab the next msb from the ltiplicand */
 107      i = mpz_tstbit (k, bitidx--);
 108
 109      /* skip leading zero bits */
 110      if (mode == 0 && i == 0) {
 111         continue;
 112      }
 113
 114      /* if the bit is zero and mode == 1 then we double */
 115      if (mode == 1 && i == 0) {
 116         if ((err = ecc_projective_dbl_point(R, R, a, modulus)) != 0)
 117           goto done;
 118         continue;
 119      }
 120
 121      /* else we add it to the window */
 122      bitbuf |= (i << (WINSIZE - ++bitcpy));
 123      mode = 2;
 124
 125      if (bitcpy == WINSIZE) {
 126        /* if this is the first window we do a simple copy */
 127        if (first == 1) {
 128           /* R = kG [k = first window] */
 129           mpz_set(R->x, M[bitbuf-8]->x);
 130           mpz_set(R->y, M[bitbuf-8]->y);
 131           mpz_set(R->z, M[bitbuf-8]->z);
 132           first = 0;
 133        } else {
 134          /* normal window */
 135          /* ok window is filled so double as required and add  */
 136          /* double first */
 137          for (j = 0; j < WINSIZE; j++) {
 138            if ((err = ecc_projective_dbl_point(R, R, a, modulus)) != 0)
 139              goto done;
 140          }
 141
 142          /* then add, bitbuf will be 8..15 [8..2^WINSIZE] guaranteed */
 143          if ((err = ecc_projective_add_point(R, M[bitbuf-8], R, a, modulus)) != 0)
 144            goto done;
 145        }
 146        /* empty window and reset */
 147        bitcpy = bitbuf = 0;
 148        mode = 1;
 149     }
 150   }
 151
 152    /* if bits remain then double/add */
 153    if (mode == 2 && bitcpy > 0) {
 154      /* double then add */
 155      for (j = 0; j < bitcpy; j++) {
 156        /* only double if we have had at least one add first */
 157        if (first == 0) {
 158           if ((err = ecc_projective_dbl_point(R, R, a, modulus)) != 0)
 159             goto done;
 160        }
 161
 162        bitbuf <<= 1;
 163        if ((bitbuf & (1 << WINSIZE)) != 0) {
 164          if (first == 1){
 165             /* first add, so copy */
 166             mpz_set(R->x, tG->x);
 167             mpz_set(R->y, tG->y);
 168             mpz_set(R->z, tG->z);
 169             first = 0;
 170          } else {
 171             /* then add */
 172             if ((err = ecc_projective_add_point(R, tG, R, a, modulus)) != 0)
 173               goto done;
 174          }
 175        }
 176      }
 177    }
 178
 179    /* map R back from projective space */
 180    if (map) {
 181       err = ecc_map(R, modulus);
 182    } else {
 183       err = 0;
 184    }
 185 done:
 186    ecc_del_point(tG);
 187    for (i = 0; i < 8; i++) {
 188        ecc_del_point(M[i]);
 189    }
 190    return err;
 191 }
 192