lib/nettle/ecc_mulmod_cached.c

   1 /*
   2  * Copyright (C) 2011-2012 Free Software Foundation, Inc.
   3  *
   4  * Author: Ilya Tumaykin
   5  *
   6  * This file is part of GNUTLS.
   7  *
   8  * The GNUTLS library is free software; you can redistribute it and/or
   9  * modify it under the terms of the GNU Lesser General Public License
  10  * as published by the Free Software Foundation; either version 3 of
  11  * the License, or (at your option) any later version.
  12  *
  13  * This library is distributed in the hope that it will be useful, but
  14  * WITHOUT ANY WARRANTY; without even the implied warranty of
  15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  16  * Lesser General Public License for more details.
  17  *
  18  * You should have received a copy of the GNU Lesser General Public License
  19  * along with this program.  If not, see <http://www.gnu.org/licenses/>
  20  *
  21  */
  22
  23 /* needed for gnutls_* types */
  24 #include <gnutls_int.h>
  25 #include <algorithms.h>
  26
  27 #include "ecc.h"
  28
  29
  30 /* per-curve cache structure */
  31 typedef struct
  32 {
  33   /* curve's id */
  34   gnutls_ecc_curve_t id;
  35
  36     /** The array of positive multipliers of G */
  37   ecc_point *pos[WMNAF_PRECOMPUTED_LENGTH];
  38
  39     /** The array of negative multipliers of G */
  40   ecc_point *neg[WMNAF_PRECOMPUTED_LENGTH];
  41 } gnutls_ecc_curve_cache_entry_t;
  42
  43 /* global cache */
  44 static gnutls_ecc_curve_cache_entry_t *ecc_wmnaf_cache = NULL;
  45
  46 /* free single cache entry */
  47 static void
  48 _ecc_wmnaf_cache_entry_free (gnutls_ecc_curve_cache_entry_t * p)
  49 {
  50   int i;
  51
  52   for (i = 0; i < WMNAF_PRECOMPUTED_LENGTH; ++i)
  53     {
  54       ecc_del_point (p->pos[i]);
  55       ecc_del_point (p->neg[i]);
  56     }
  57 }
  58
  59 /* free curves caches */
  60 void
  61 ecc_wmnaf_cache_free (void)
  62 {
  63   gnutls_ecc_curve_cache_entry_t *p = ecc_wmnaf_cache;
  64   if (p)
  65     {
  66       for (; p->id != GNUTLS_ECC_CURVE_INVALID; ++p)
  67         {
  68           _ecc_wmnaf_cache_entry_free (p);
  69         }
  70
  71       free (ecc_wmnaf_cache);
  72     }
  73 }
  74
  75 /* initialize single cache entry
  76  * for a curve with the given id */
  77 static int
  78 _ecc_wmnaf_cache_entry_init (gnutls_ecc_curve_cache_entry_t * p,
  79                              gnutls_ecc_curve_t id)
  80 {
  81   int i, j, err;
  82   ecc_point *G;
  83   mpz_t a, modulus;
  84
  85   const gnutls_ecc_curve_entry_st *st = NULL;
  86
  87   if (p == NULL || id == 0)
  88     return GNUTLS_E_RECEIVED_ILLEGAL_PARAMETER;
  89
  90   G = ecc_new_point ();
  91   if (G == NULL)
  92     {
  93       return GNUTLS_E_MEMORY_ERROR;
  94     }
  95
  96   st = _gnutls_ecc_curve_get_params (id);
  97   if (st == NULL)
  98     {
  99       err = GNUTLS_E_INTERNAL_ERROR;
 100       goto done;
 101     }
 102
 103   if ((err = mp_init_multi (&a, &modulus, NULL) != 0))
 104     return err;
 105
 106   /* set id */
 107   p->id = id;
 108
 109   /* set modulus */
 110   mpz_set_str (modulus, st->prime, 16);
 111
 112   /* get generator point */
 113   mpz_set_str (G->x, st->Gx, 16);
 114   mpz_set_str (G->y, st->Gy, 16);
 115   mpz_set_ui (G->z, 1);
 116
 117   /* set A */
 118   mpz_set_str (a, st->A, 16);
 119
 120   /* alloc ram for precomputed values */
 121   for (i = 0; i < WMNAF_PRECOMPUTED_LENGTH; ++i)
 122     {
 123       p->pos[i] = ecc_new_point ();
 124       p->neg[i] = ecc_new_point ();
 125       if (p->pos[i] == NULL || p->neg[i] == NULL)
 126         {
 127           for (j = 0; j < i; ++j)
 128             {
 129               ecc_del_point (p->pos[j]);
 130               ecc_del_point (p->neg[j]);
 131             }
 132
 133           err = GNUTLS_E_MEMORY_ERROR;
 134           goto done;
 135         }
 136     }
 137
 138   /* fill in pos and neg arrays with precomputed values
 139    * pos holds kG for k ==  1, 3, 5, ..., (2^w - 1)
 140    * neg holds kG for k == -1,-3,-5, ...,-(2^w - 1)
 141    */
 142
 143   /* pos[0] == 2G for a while, later it will be set to the expected 1G */
 144   if ((err = ecc_projective_dbl_point (G, p->pos[0], a, modulus)) != 0)
 145     goto done;
 146
 147   /* pos[1] == 3G */
 148   if ((err =
 149        ecc_projective_add_point (p->pos[0], G, p->pos[1], a,
 150                                     modulus)) != 0)
 151     goto done;
 152
 153   /* fill in kG for k = 5, 7, ..., (2^w - 1) */
 154   for (j = 2; j < WMNAF_PRECOMPUTED_LENGTH; ++j)
 155     {
 156       if ((err =
 157            ecc_projective_add_point (p->pos[j - 1], p->pos[0], p->pos[j],
 158                                         a, modulus)) != 0)
 159         goto done;
 160     }
 161
 162   /* set pos[0] == 1G as expected
 163    * after this step we don't need G at all */
 164   mpz_set (p->pos[0]->x, G->x);
 165   mpz_set (p->pos[0]->y, G->y);
 166   mpz_set (p->pos[0]->z, G->z);
 167
 168   /* map to affine all elements in pos
 169    * this will allow to use ecc_projective_madd later
 170    * set neg[i] == -pos[i] */
 171   for (j = 0; j < WMNAF_PRECOMPUTED_LENGTH; ++j)
 172     {
 173       if ((err = ecc_map (p->pos[j], modulus)) != 0)
 174         goto done;
 175
 176       if ((err =
 177            ecc_projective_negate_point (p->pos[j], p->neg[j], modulus)) != 0)
 178         goto done;
 179     }
 180
 181   err = 0;
 182 done:
 183   ecc_del_point (G);
 184   mp_clear_multi (&a, &modulus, NULL);
 185
 186   return err;
 187 }
 188
 189 /* initialize curves caches */
 190 int
 191 ecc_wmnaf_cache_init (void)
 192 {
 193   int j, err;
 194
 195   gnutls_ecc_curve_cache_entry_t *ret;
 196
 197   const gnutls_ecc_curve_t *p;
 198
 199   ret = (gnutls_ecc_curve_cache_entry_t *)
 200     malloc (MAX_ALGOS * sizeof (gnutls_ecc_curve_cache_entry_t));
 201   if (ret == NULL)
 202     return GNUTLS_E_MEMORY_ERROR;
 203
 204   /* get supported curves' ids */
 205   p = gnutls_ecc_curve_list ();
 206
 207   for (j = 0; *p; ++p, ++j)
 208     {
 209       if ((err = _ecc_wmnaf_cache_entry_init (ret + *p - 1, *p)) != 0)
 210         goto done;
 211     }
 212
 213   /* nullify last cache entry id */
 214   ret[j].id = GNUTLS_ECC_CURVE_INVALID;
 215
 216   err = GNUTLS_E_SUCCESS;
 217
 218   ecc_wmnaf_cache = ret;
 219 done:
 220   if (err)
 221     {
 222       int i;
 223       for (i = 0; i < j; ++i)
 224         {
 225           _ecc_wmnaf_cache_entry_free (ret + i);
 226         }
 227
 228       free (ret);
 229       ecc_wmnaf_cache = NULL;
 230     }
 231   return err;
 232 }
 233
 234
 235 /*
 236    Perform a point wMNAF-multiplication utilizing cache
 237    @param k    The scalar to multiply by
 238    @param id   The curve's id
 239    @param R    [out] Destination for kG
 240    @param a        The curve's A value
 241    @param modulus  The modulus of the field the ECC curve is in
 242    @param map      Boolean whether to map back to affine or not (1 == map, 0 == leave in projective)
 243    @return     GNUTLS_E_SUCCESS on success
 244 */
 245 int
 246 ecc_mulmod_cached (mpz_t k, gnutls_ecc_curve_t id, ecc_point * R,
 247                          mpz_t a, mpz_t modulus, int map)
 248 {
 249   int j, err;
 250
 251   gnutls_ecc_curve_cache_entry_t *cache = NULL;
 252   signed char *wmnaf = NULL;
 253   size_t wmnaf_len;
 254   signed char digit;
 255
 256   if (k == NULL || R == NULL || modulus == NULL || id == 0)
 257     return GNUTLS_E_RECEIVED_ILLEGAL_PARAMETER;
 258
 259   /* calculate wMNAF */
 260   wmnaf = ecc_wMNAF (k, &wmnaf_len);
 261   if (!wmnaf)
 262     {
 263       err = GNUTLS_E_INTERNAL_ERROR;
 264       goto done;
 265     }
 266
 267   /* set R to neutral */
 268   mpz_set_ui (R->x, 1);
 269   mpz_set_ui (R->y, 1);
 270   mpz_set_ui (R->z, 0);
 271
 272   /* do cache lookup */
 273   cache = ecc_wmnaf_cache + id - 1;
 274
 275   /* perform ops */
 276   for (j = wmnaf_len - 1; j >= 0; --j)
 277     {
 278       if ((err = ecc_projective_dbl_point (R, R, a, modulus)) != 0)
 279         goto done;
 280
 281       digit = wmnaf[j];
 282
 283       if (digit)
 284         {
 285           if (digit > 0)
 286             {
 287               if ((err =
 288                    ecc_projective_madd (R, cache->pos[(digit / 2)], R, a,
 289                                         modulus)) != 0)
 290                 goto done;
 291             }
 292           else
 293             {
 294               if ((err =
 295                    ecc_projective_madd (R, cache->neg[(-digit / 2)], R, a,
 296                                         modulus)) != 0)
 297                 goto done;
 298             }
 299         }
 300     }
 301
 302
 303   /* map R back from projective space */
 304   if (map)
 305     {
 306       err = ecc_map (R, modulus);
 307     }
 308   else
 309     {
 310       err = GNUTLS_E_SUCCESS;
 311     }
 312 done:
 313   if (wmnaf)
 314     free (wmnaf);
 315   return err;
 316 }
 317
 318 /*
 319    Perform a point wMNAF-multiplication utilizing cache
 320    This version tries to be timing resistant
 321    @param k    The scalar to multiply by
 322    @param id   The curve's id
 323    @param R    [out] Destination for kG
 324    @param a        The curve's A value
 325    @param modulus  The modulus of the field the ECC curve is in
 326    @param map      Boolean whether to map back to affine or not (1 == map, 0 == leave in projective)
 327    @return     GNUTLS_E_SUCCESS on success
 328 */
 329 int
 330 ecc_mulmod_cached_timing (mpz_t k, gnutls_ecc_curve_t id, ecc_point * R,
 331                                 mpz_t a, mpz_t modulus, int map)
 332 {
 333   int j, err;
 334
 335   gnutls_ecc_curve_cache_entry_t *cache = NULL;
 336   signed char *wmnaf = NULL;
 337   size_t wmnaf_len;
 338   signed char digit;
 339   /* point for throttle */
 340   ecc_point *T;
 341
 342   if (k == NULL || R == NULL || modulus == NULL || id == 0)
 343     return GNUTLS_E_RECEIVED_ILLEGAL_PARAMETER;
 344
 345   /* prepare T point */
 346   T = ecc_new_point ();
 347   if (T == NULL)
 348     return GNUTLS_E_MEMORY_ERROR;
 349
 350   /* calculate wMNAF */
 351   wmnaf = ecc_wMNAF (k, &wmnaf_len);
 352   if (!wmnaf)
 353     {
 354       err = GNUTLS_E_INTERNAL_ERROR;
 355       goto done;
 356     }
 357
 358   /* set R to neutral */
 359   mpz_set_ui (R->x, 1);
 360   mpz_set_ui (R->y, 1);
 361   mpz_set_ui (R->z, 0);
 362
 363   /* set T to neutral */
 364   mpz_set_ui (T->x, 1);
 365   mpz_set_ui (T->y, 1);
 366   mpz_set_ui (T->z, 0);
 367
 368   /* do cache lookup */
 369   cache = ecc_wmnaf_cache + id - 1;
 370
 371   /* perform ops */
 372   for (j = wmnaf_len - 1; j >= 0; --j)
 373     {
 374       if ((err = ecc_projective_dbl_point (R, R, a, modulus)) != 0)
 375         goto done;
 376
 377       digit = wmnaf[j];
 378
 379       if (digit)
 380         {
 381           if (digit > 0)
 382             {
 383               if ((err =
 384                    ecc_projective_madd (R, cache->pos[(digit / 2)], R, a,
 385                                         modulus)) != 0)
 386                 goto done;
 387             }
 388           else
 389             {
 390               if ((err =
 391                    ecc_projective_madd (R, cache->neg[(-digit / 2)], R, a,
 392                                         modulus)) != 0)
 393                 goto done;
 394             }
 395         }
 396       else
 397         {
 398           /* we add middle element of pos array as a general case
 399            * there is no real difference between using pos and neg */
 400           if ((err =
 401                ecc_projective_madd (R,
 402                                     cache->
 403                                     pos[(WMNAF_PRECOMPUTED_LENGTH / 2)], T, a,
 404                                     modulus)) != 0)
 405             goto done;
 406         }
 407     }
 408
 409
 410   /* map R back from projective space */
 411   if (map)
 412     {
 413       err = ecc_map (R, modulus);
 414     }
 415   else
 416     {
 417       err = GNUTLS_E_SUCCESS;
 418     }
 419 done:
 420   ecc_del_point (T);
 421   if (wmnaf)
 422     free (wmnaf);
 423   return err;
 424 }
 425
 426 /*
 427    Perform a point wMNAF-multiplication utilizing cache
 428    This function will lookup for an apropriate curve first
 429    This function's definition allows in-place substitution instead of ecc_mulmod
 430    @param k    The scalar to multiply by
 431    @param id   The curve's id
 432    @param R    [out] Destination for kG
 433    @param a        The curve's A value
 434    @param modulus  The modulus of the field the ECC curve is in
 435    @param map      Boolean whether to map back to affine or not (1 == map, 0 == leave in projective)
 436    @return     GNUTLS_E_SUCCESS on success
 437 */
 438 int
 439 ecc_mulmod_cached_lookup (mpz_t k, ecc_point * G, ecc_point * R,
 440                                 mpz_t a, mpz_t modulus, int map)
 441 {
 442   int i, id;
 443
 444   if (k == NULL || G == NULL || R == NULL || modulus == NULL)
 445     return GNUTLS_E_RECEIVED_ILLEGAL_PARAMETER;
 446
 447   for (i = 0; (id = ecc_wmnaf_cache[i].id); ++i)
 448     {
 449       if (!(mpz_cmp (G->x, ecc_wmnaf_cache[i].pos[0]->x)) &&
 450           !(mpz_cmp (G->y, ecc_wmnaf_cache[i].pos[0]->y)))
 451         {
 452           break;
 453         }
 454     }
 455
 456   return ecc_mulmod_cached (k, id, R, a, modulus, map);
 457 }