lib/nettle/ecc_mulmod.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 #include "ecc.h"
  24
  25
  26 /*
  27    Perform a point multiplication using wMNAF representation
  28    @param k    The scalar to multiply by
  29    @param G    The base point
  30    @param R    [out] Destination for kG
  31    @param a        The curve's A value
  32    @param modulus  The modulus of the field the ECC curve is in
  33    @param map      Boolean whether to map back to affine or not (1 == map, 0 == leave in projective)
  34    @return     GNUTLS_E_SUCCESS on success
  35 */
  36 int
  37 ecc_mulmod (mpz_t k, ecc_point * G, ecc_point * R, mpz_t a,
  38                   mpz_t modulus, int map)
  39 {
  40   ecc_point *pos[WMNAF_PRECOMPUTED_LENGTH], *neg[WMNAF_PRECOMPUTED_LENGTH];
  41   int i, j, err;
  42
  43   signed char *wmnaf = NULL;
  44   size_t wmnaf_len;
  45   signed char digit;
  46
  47   if (k == NULL || G == NULL || R == NULL || modulus == NULL)
  48     return GNUTLS_E_RECEIVED_ILLEGAL_PARAMETER;
  49
  50   /* alloc ram for precomputed values */
  51   for (i = 0; i < WMNAF_PRECOMPUTED_LENGTH; ++i)
  52     {
  53       pos[i] = ecc_new_point ();
  54       neg[i] = ecc_new_point ();
  55       if (pos[i] == NULL || neg[i] == NULL)
  56         {
  57           for (j = 0; j < i; ++j)
  58             {
  59               ecc_del_point (pos[j]);
  60               ecc_del_point (neg[j]);
  61             }
  62
  63           return GNUTLS_E_MEMORY_ERROR;
  64         }
  65     }
  66
  67   /* fill in pos and neg arrays with precomputed values
  68    * pos holds kG for k ==  1, 3, 5, ..., (2^w - 1)
  69    * neg holds kG for k == -1,-3,-5, ...,-(2^w - 1)
  70    */
  71
  72   /* pos[0] == 2G for a while, later it will be set to the expected 1G */
  73   if ((err = ecc_projective_dbl_point (G, pos[0], a, modulus)) != 0)
  74     goto done;
  75
  76   /* pos[1] == 3G */
  77   if ((err =
  78        ecc_projective_add_point (pos[0], G, pos[1], a, modulus)) != 0)
  79     goto done;
  80
  81   /* fill in kG for k = 5, 7, ..., (2^w - 1) */
  82   for (j = 2; j < WMNAF_PRECOMPUTED_LENGTH; ++j)
  83     {
  84       if ((err =
  85            ecc_projective_add_point (pos[j - 1], pos[0], pos[j], a,
  86                                         modulus)) != 0)
  87         goto done;
  88     }
  89
  90   /* set pos[0] == 1G as expected
  91    * after this step we don't need G at all
  92    * and can change it without worries even if R == G */
  93   mpz_set (pos[0]->x, G->x);
  94   mpz_set (pos[0]->y, G->y);
  95   mpz_set (pos[0]->z, G->z);
  96
  97   /* neg[i] == -pos[i] */
  98   for (j = 0; j < WMNAF_PRECOMPUTED_LENGTH; ++j)
  99     {
 100       if ((err = ecc_projective_negate_point (pos[j], neg[j], modulus)) != 0)
 101         goto done;
 102     }
 103
 104   /* calculate wMNAF */
 105   wmnaf = ecc_wMNAF (k, &wmnaf_len);
 106   if (!wmnaf)
 107     {
 108       err = GNUTLS_E_INTERNAL_ERROR;
 109       goto done;
 110     }
 111
 112   /* actual point computation */
 113
 114   /* set R to neutral */
 115   mpz_set_ui (R->x, 1);
 116   mpz_set_ui (R->y, 1);
 117   mpz_set_ui (R->z, 0);
 118
 119   /* perform ops */
 120   for (j = wmnaf_len - 1; j >= 0; --j)
 121     {
 122       if ((err = ecc_projective_dbl_point (R, R, a, modulus)) != 0)
 123         goto done;
 124
 125       digit = wmnaf[j];
 126
 127       if (digit)
 128         {
 129           if (digit > 0)
 130             {
 131               if ((err =
 132                    ecc_projective_add_point (R, pos[(digit / 2)], R, a,
 133                                                 modulus)) != 0)
 134                 goto done;
 135             }
 136           else
 137             {
 138               if ((err =
 139                    ecc_projective_add_point (R, neg[(-digit / 2)], R, a,
 140                                                 modulus)) != 0)
 141                 goto done;
 142             }
 143         }
 144     }
 145
 146
 147   /* map R back from projective space */
 148   if (map)
 149     {
 150       err = ecc_map (R, modulus);
 151     }
 152   else
 153     {
 154       err = GNUTLS_E_SUCCESS;
 155     }
 156 done:
 157   for (i = 0; i < WMNAF_PRECOMPUTED_LENGTH; ++i)
 158     {
 159       ecc_del_point (pos[i]);
 160       ecc_del_point (neg[i]);
 161     }
 162   if (wmnaf)
 163     free (wmnaf);
 164   return err;
 165 }