lib/nettle/ecc_mulmod_timing.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 /*
  28   @file ecc_mulmod_timing.c
  29   ECC Crypto, Tom St Denis
  30 */
  31
  32 /*
  33    Perform a point multiplication  (timing resistant)
  34    @param k    The scalar to multiply by
  35    @param G    The base point
  36    @param R    [out] Destination for kG
  37    @param a        The a value of the curve
  38    @param modulus  The modulus of the field the ECC curve is in
  39    @param map      Boolean whether to map back to affine or not (1==map, 0 == leave in projective)
  40    @return 0 on success
  41 */
  42 int
  43 ecc_mulmod_timing (mpz_t k, ecc_point * G, ecc_point * R, mpz_t a, mpz_t modulus,
  44                 int map)
  45 {
  46   ecc_point *tG, *M[3];
  47   int i, j, err;
  48   int bit_to_read;
  49   int mode;
  50
  51   if (k == NULL || G == NULL || R == NULL || modulus == NULL)
  52     return -1;
  53
  54   /* alloc ram for window temps */
  55   for (i = 0; i < 3; i++)
  56     {
  57       M[i] = ecc_new_point ();
  58       if (M[i] == NULL)
  59         {
  60           for (j = 0; j < i; j++)
  61             {
  62               ecc_del_point (M[j]);
  63             }
  64           return -1;
  65         }
  66     }
  67
  68   /* make a copy of G incase R==G */
  69   tG = ecc_new_point ();
  70   if (tG == NULL)
  71     {
  72       err = -1;
  73       goto done;
  74     }
  75
  76   /* tG = G  and convert to montgomery */
  77   mpz_set (tG->x, G->x);
  78   mpz_set (tG->y, G->y);
  79   mpz_set (tG->z, G->z);
  80
  81   /* calc the M tab */
  82   /* M[0] == G */
  83   mpz_set (M[0]->x, tG->x);
  84   mpz_set (M[0]->y, tG->y);
  85   mpz_set (M[0]->z, tG->z);
  86   /* M[1] == 2G */
  87   if ((err = ecc_projective_dbl_point (tG, M[1], a, modulus)) != 0)
  88     {
  89       goto done;
  90     }
  91
  92   /* setup sliding window */
  93   mode = 0;
  94   bit_to_read = mpz_size (k) * GMP_NUMB_BITS - 1;
  95
  96   /* perform ops */
  97   for (;;)
  98     {
  99       /* grab next digit as required */
 100       if (bit_to_read == -1)
 101         break;
 102       i = mpz_tstbit (k, bit_to_read--);
 103
 104       if (mode == 0 && i == 0)
 105         {
 106           /* dummy operations */
 107           if ((err =
 108                ecc_projective_add_point (M[0], M[1], M[2], a,
 109                                              modulus)) != 0)
 110             {
 111               goto done;
 112             }
 113           if ((err =
 114                ecc_projective_dbl_point (M[1], M[2], a, modulus)) != 0)
 115             {
 116               goto done;
 117             }
 118           continue;
 119         }
 120
 121       if (mode == 0 && i == 1)
 122         {
 123           mode = 1;
 124           /* dummy operations */
 125           if ((err =
 126                ecc_projective_add_point (M[0], M[1], M[2], a,
 127                                              modulus)) != 0)
 128             {
 129               goto done;
 130             }
 131           if ((err =
 132                ecc_projective_dbl_point (M[1], M[2], a, modulus)) != 0)
 133             {
 134               goto done;
 135             }
 136           continue;
 137         }
 138
 139       if ((err =
 140            ecc_projective_add_point (M[0], M[1], M[i ^ 1], a,
 141                                          modulus)) != 0)
 142         {
 143           goto done;
 144         }
 145       if ((err = ecc_projective_dbl_point (M[i], M[i], a, modulus)) != 0)
 146         {
 147           goto done;
 148         }
 149     }
 150
 151   /* copy result out */
 152   mpz_set (R->x, M[0]->x);
 153   mpz_set (R->y, M[0]->y);
 154   mpz_set (R->z, M[0]->z);
 155
 156   /* map R back from projective space */
 157   if (map)
 158     {
 159       err = ecc_map (R, modulus);
 160     }
 161   else
 162     {
 163       err = 0;
 164     }
 165 done:
 166   ecc_del_point (tG);
 167   for (i = 0; i < 3; i++)
 168     {
 169       ecc_del_point (M[i]);
 170     }
 171   return err;
 172 }
 173
 174 /* $Source: /cvs/libtom/libtomcrypt/src/pk/ecc/ecc_mulmod_timing.c,v $ */
 175 /* $Revision: 1.13 $ */
 176 /* $Date: 2007/05/12 14:32:35 $ */