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       ecc_wmnaf_cache = NULL;
  73     }
  74 }
  75
  76 /* initialize single cache entry
  77  * for a curve with the given id */
  78 static int
  79 _ecc_wmnaf_cache_entry_init (gnutls_ecc_curve_cache_entry_t * p,
  80                              gnutls_ecc_curve_t id)
  81 {
  82   int i, j, err;
  83   ecc_point *G;
  84   mpz_t a, modulus;
  85
  86   const gnutls_ecc_curve_entry_st *st = NULL;
  87
  88   if (p == NULL || id == 0)
  89     return GNUTLS_E_RECEIVED_ILLEGAL_PARAMETER;
  90
  91   G = ecc_new_point ();
  92   if (G == NULL)
  93     {
  94       return GNUTLS_E_MEMORY_ERROR;
  95     }
  96
  97   st = _gnutls_ecc_curve_get_params (id);
  98   if (st == NULL)
  99     {
 100       err = GNUTLS_E_INTERNAL_ERROR;
 101       goto done;
 102     }
 103
 104   if ((err = mp_init_multi (&a, &modulus, NULL) != 0))
 105     return err;
 106
 107   /* set id */
 108   p->id = id;
 109
 110   /* set modulus */
 111   mpz_set_str (modulus, st->prime, 16);
 112
 113   /* get generator point */
 114   mpz_set_str (G->x, st->Gx, 16);
 115   mpz_set_str (G->y, st->Gy, 16);
 116   mpz_set_ui (G->z, 1);
 117
 118   /* set A */
 119   mpz_set_str (a, st->A, 16);
 120
 121   /* alloc ram for precomputed values */
 122   for (i = 0; i < WMNAF_PRECOMPUTED_LENGTH; ++i)
 123     {
 124       p->pos[i] = ecc_new_point ();
 125       p->neg[i] = ecc_new_point ();
 126       if (p->pos[i] == NULL || p->neg[i] == NULL)
 127         {
 128           for (j = 0; j < i; ++j)
 129             {
 130               ecc_del_point (p->pos[j]);
 131               ecc_del_point (p->neg[j]);
 132             }
 133
 134           err = GNUTLS_E_MEMORY_ERROR;
 135           goto done;
 136         }
 137     }
 138
 139   /* fill in pos and neg arrays with precomputed values
 140    * pos holds kG for k ==  1, 3, 5, ..., (2^w - 1)
 141    * neg holds kG for k == -1,-3,-5, ...,-(2^w - 1)
 142    */
 143
 144   /* pos[0] == 2G for a while, later it will be set to the expected 1G */
 145   if ((err = ecc_projective_dbl_point (G, p->pos[0], a, modulus)) != 0)
 146     goto done;
 147
 148   /* pos[1] == 3G */
 149   if ((err =
 150        ecc_projective_add_point (p->pos[0], G, p->pos[1], a,
 151                                     modulus)) != 0)
 152     goto done;
 153
 154   /* fill in kG for k = 5, 7, ..., (2^w - 1) */
 155   for (j = 2; j < WMNAF_PRECOMPUTED_LENGTH; ++j)
 156     {
 157       if ((err =
 158            ecc_projective_add_point (p->pos[j - 1], p->pos[0], p->pos[j],
 159                                         a, modulus)) != 0)
 160         goto done;
 161     }
 162
 163   /* set pos[0] == 1G as expected
 164    * after this step we don't need G at all */
 165   mpz_set (p->pos[0]->x, G->x);
 166   mpz_set (p->pos[0]->y, G->y);
 167   mpz_set (p->pos[0]->z, G->z);
 168
 169   /* map to affine all elements in pos
 170    * this will allow to use ecc_projective_madd later
 171    * set neg[i] == -pos[i] */
 172   for (j = 0; j < WMNAF_PRECOMPUTED_LENGTH; ++j)
 173     {
 174       if ((err = ecc_map (p->pos[j], modulus)) != 0)
 175         goto done;
 176
 177       if ((err =
 178            ecc_projective_negate_point (p->pos[j], p->neg[j], modulus)) != 0)
 179         goto done;
 180     }
 181
 182   err = 0;
 183 done:
 184   ecc_del_point (G);
 185   mp_clear_multi (&a, &modulus, NULL);
 186
 187   return err;
 188 }
 189
 190 /* initialize curves caches */
 191 int
 192 ecc_wmnaf_cache_init (void)
 193 {
 194   int j, err;
 195
 196   gnutls_ecc_curve_cache_entry_t *ret;
 197
 198   const gnutls_ecc_curve_t *p;
 199
 200   ret = (gnutls_ecc_curve_cache_entry_t *)
 201     malloc (MAX_ALGOS * sizeof (gnutls_ecc_curve_cache_entry_t));
 202   if (ret == NULL)
 203     return GNUTLS_E_MEMORY_ERROR;
 204
 205   /* get supported curves' ids */
 206   p = gnutls_ecc_curve_list ();
 207
 208   for (j = 0; *p; ++p, ++j)
 209     {
 210       if ((err = _ecc_wmnaf_cache_entry_init (ret + *p - 1, *p)) != 0)
 211         goto done;
 212     }
 213
 214   /* nullify last cache entry id */
 215   ret[j].id = GNUTLS_ECC_CURVE_INVALID;
 216
 217   err = GNUTLS_E_SUCCESS;
 218
 219   ecc_wmnaf_cache = ret;
 220 done:
 221   if (err)
 222     {
 223       int i;
 224       for (i = 0; i < j; ++i)
 225         {
 226           _ecc_wmnaf_cache_entry_free (ret + i);
 227         }
 228
 229       free (ret);
 230       ecc_wmnaf_cache = NULL;
 231     }
 232   return err;
 233 }
 234
 235
 236 /*
 237    Perform a point wMNAF-multiplication utilizing cache
 238    @param k    The scalar to multiply by
 239    @param id   The curve's id
 240    @param R    [out] Destination for kG
 241    @param a        The curve's A value
 242    @param modulus  The modulus of the field the ECC curve is in
 243    @param map      Boolean whether to map back to affine or not (1 == map, 0 == leave in projective)
 244    @return     GNUTLS_E_SUCCESS on success
 245 */
 246 int
 247 ecc_mulmod_cached (mpz_t k, gnutls_ecc_curve_t id, ecc_point * R,
 248                          mpz_t a, mpz_t modulus, int map)
 249 {
 250   int j, err;
 251
 252   gnutls_ecc_curve_cache_entry_t *cache = NULL;
 253   signed char *wmnaf = NULL;
 254   size_t wmnaf_len;
 255   signed char digit;
 256
 257   if (k == NULL || R == NULL || modulus == NULL || id == 0)
 258     return GNUTLS_E_RECEIVED_ILLEGAL_PARAMETER;
 259
 260   /* calculate wMNAF */
 261   wmnaf = ecc_wMNAF (k, &wmnaf_len);
 262   if (!wmnaf)
 263     {
 264       err = GNUTLS_E_INTERNAL_ERROR;
 265       goto done;
 266     }
 267
 268   /* set R to neutral */
 269   mpz_set_ui (R->x, 1);
 270   mpz_set_ui (R->y, 1);
 271   mpz_set_ui (R->z, 0);
 272
 273   /* do cache lookup */
 274   cache = ecc_wmnaf_cache + id - 1;
 275
 276   /* perform ops */
 277   for (j = wmnaf_len - 1; j >= 0; --j)
 278     {
 279       if ((err = ecc_projective_dbl_point (R, R, a, modulus)) != 0)
 280         goto done;
 281
 282       digit = wmnaf[j];
 283
 284       if (digit)
 285         {
 286           if (digit > 0)
 287             {
 288               if ((err =
 289                    ecc_projective_madd (R, cache->pos[(digit / 2)], R, a,
 290                                         modulus)) != 0)
 291                 goto done;
 292             }
 293           else
 294             {
 295               if ((err =
 296                    ecc_projective_madd (R, cache->neg[(-digit / 2)], R, a,
 297                                         modulus)) != 0)
 298                 goto done;
 299             }
 300         }
 301     }
 302
 303
 304   /* map R back from projective space */
 305   if (map)
 306     {
 307       err = ecc_map (R, modulus);
 308     }
 309   else
 310     {
 311       err = GNUTLS_E_SUCCESS;
 312     }
 313 done:
 314   if (wmnaf)
 315     free (wmnaf);
 316   return err;
 317 }
 318
 319 /*
 320    Perform a point wMNAF-multiplication utilizing cache
 321    This version tries to be timing resistant
 322    @param k    The scalar to multiply by
 323    @param id   The curve's id
 324    @param R    [out] Destination for kG
 325    @param a        The curve's A value
 326    @param modulus  The modulus of the field the ECC curve is in
 327    @param map      Boolean whether to map back to affine or not (1 == map, 0 == leave in projective)
 328    @return     GNUTLS_E_SUCCESS on success
 329 */
 330 int
 331 ecc_mulmod_cached_timing (mpz_t k, gnutls_ecc_curve_t id, ecc_point * R,
 332                                 mpz_t a, mpz_t modulus, int map)
 333 {
 334   int j, err;
 335
 336   gnutls_ecc_curve_cache_entry_t *cache = NULL;
 337   signed char *wmnaf = NULL;
 338   size_t wmnaf_len;
 339   signed char digit;
 340   /* point for throttle */
 341   ecc_point *T;
 342
 343   if (k == NULL || R == NULL || modulus == NULL || id == 0)
 344     return GNUTLS_E_RECEIVED_ILLEGAL_PARAMETER;
 345
 346   /* prepare T point */
 347   T = ecc_new_point ();
 348   if (T == NULL)
 349     return GNUTLS_E_MEMORY_ERROR;
 350
 351   /* calculate wMNAF */
 352   wmnaf = ecc_wMNAF (k, &wmnaf_len);
 353   if (!wmnaf)
 354     {
 355       err = GNUTLS_E_INTERNAL_ERROR;
 356       goto done;
 357     }
 358
 359   /* set R to neutral */
 360   mpz_set_ui (R->x, 1);
 361   mpz_set_ui (R->y, 1);
 362   mpz_set_ui (R->z, 0);
 363
 364   /* set T to neutral */
 365   mpz_set_ui (T->x, 1);
 366   mpz_set_ui (T->y, 1);
 367   mpz_set_ui (T->z, 0);
 368
 369   /* do cache lookup */
 370   cache = ecc_wmnaf_cache + id - 1;
 371
 372   /* perform ops */
 373   for (j = wmnaf_len - 1; j >= 0; --j)
 374     {
 375       if ((err = ecc_projective_dbl_point (R, R, a, modulus)) != 0)
 376         goto done;
 377
 378       digit = wmnaf[j];
 379
 380       if (digit)
 381         {
 382           if (digit > 0)
 383             {
 384               if ((err =
 385                    ecc_projective_madd (R, cache->pos[(digit / 2)], R, a,
 386                                         modulus)) != 0)
 387                 goto done;
 388             }
 389           else
 390             {
 391               if ((err =
 392                    ecc_projective_madd (R, cache->neg[(-digit / 2)], R, a,
 393                                         modulus)) != 0)
 394                 goto done;
 395             }
 396         }
 397       else
 398         {
 399           /* we add middle element of pos array as a general case
 400            * there is no real difference between using pos and neg */
 401           if ((err =
 402                ecc_projective_madd (R,
 403                                     cache->
 404                                     pos[(WMNAF_PRECOMPUTED_LENGTH / 2)], T, a,
 405                                     modulus)) != 0)
 406             goto done;
 407         }
 408     }
 409
 410
 411   /* map R back from projective space */
 412   if (map)
 413     {
 414       err = ecc_map (R, modulus);
 415     }
 416   else
 417     {
 418       err = GNUTLS_E_SUCCESS;
 419     }
 420 done:
 421   ecc_del_point (T);
 422   if (wmnaf)
 423     free (wmnaf);
 424   return err;
 425 }
 426
 427 /*
 428    Perform a point wMNAF-multiplication utilizing cache
 429    This function will lookup for an apropriate curve first
 430    This function's definition allows in-place substitution instead of ecc_mulmod
 431    @param k    The scalar to multiply by
 432    @param id   The curve's id
 433    @param R    [out] Destination for kG
 434    @param a        The curve's A value
 435    @param modulus  The modulus of the field the ECC curve is in
 436    @param map      Boolean whether to map back to affine or not (1 == map, 0 == leave in projective)
 437    @return     GNUTLS_E_SUCCESS on success
 438 */
 439 int
 440 ecc_mulmod_cached_lookup (mpz_t k, ecc_point * G, ecc_point * R,
 441                                 mpz_t a, mpz_t modulus, int map)
 442 {
 443   int i, id;
 444
 445   if (k == NULL || G == NULL || R == NULL || modulus == NULL)
 446     return GNUTLS_E_RECEIVED_ILLEGAL_PARAMETER;
 447
 448   for (i = 0; (id = ecc_wmnaf_cache[i].id); ++i)
 449     {
 450       if (!(mpz_cmp (G->x, ecc_wmnaf_cache[i].pos[0]->x)) &&
 451           !(mpz_cmp (G->y, ecc_wmnaf_cache[i].pos[0]->y)))
 452         {
 453           break;
 454         }
 455     }
 456
 457   return ecc_mulmod_cached (k, id, R, a, modulus, map);
 458 }