ecc-mul-a.c

   1 /* ecc-mul-a.c
   2
   3    Copyright (C) 2013 Niels Möller
   4
   5    This file is part of GNU Nettle.
   6
   7    GNU Nettle is free software: you can redistribute it and/or
   8    modify it under the terms of either:
   9
  10      * the GNU Lesser General Public License as published by the Free
  11        Software Foundation; either version 3 of the License, or (at your
  12        option) any later version.
  13
  14    or
  15
  16      * the GNU General Public License as published by the Free
  17        Software Foundation; either version 2 of the License, or (at your
  18        option) any later version.
  19
  20    or both in parallel, as here.
  21
  22    GNU Nettle is distributed in the hope that it will be useful,
  23    but WITHOUT ANY WARRANTY; without even the implied warranty of
  24    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  25    General Public License for more details.
  26
  27    You should have received copies of the GNU General Public License and
  28    the GNU Lesser General Public License along with this program.  If
  29    not, see http://www.gnu.org/licenses/.
  30 */
  31
  32 /* Development of Nettle's ECC support was funded by the .SE Internet Fund. */
  33
  34 #if HAVE_CONFIG_H
  35 # include "config.h"
  36 #endif
  37
  38 #include <assert.h>
  39
  40 #include "ecc.h"
  41 #include "ecc-internal.h"
  42
  43 /* Binary algorithm needs 6*ecc->p.size + scratch for ecc_add_jja.
  44    Current total is 12 ecc->p.size, at most 864 bytes.
  45
  46    Window algorithm needs (3<<w) * ecc->p.size for the table,
  47    3*ecc->p.size for a temporary point, and scratch for
  48    ecc_add_jjj. */
  49
  50 #if ECC_MUL_A_WBITS == 0
  51 void
  52 ecc_mul_a (const struct ecc_curve *ecc,
  53            mp_limb_t *r,
  54            const mp_limb_t *np, const mp_limb_t *p,
  55            mp_limb_t *scratch)
  56 {
  57 #define tp scratch
  58 #define pj (scratch + 3*ecc->p.size)
  59 #define scratch_out (scratch + 6*ecc->p.size)
  60
  61   int is_zero;
  62
  63   unsigned i;
  64
  65   ecc_a_to_j (ecc, pj, p);
  66   mpn_zero (r, 3*ecc->p.size);
  67
  68   for (i = ecc->p.size, is_zero = 1; i-- > 0; )
  69     {
  70       mp_limb_t w = np[i];
  71       mp_limb_t bit;
  72
  73       for (bit = (mp_limb_t) 1 << (GMP_NUMB_BITS - 1);
  74            bit > 0;
  75            bit >>= 1)
  76         {
  77           int digit;
  78
  79           ecc_dup_jj (ecc, r, r, scratch_out);
  80           ecc_add_jja (ecc, tp, r, pj, scratch_out);
  81
  82           digit = (w & bit) > 0;
  83           /* If is_zero is set, r is the zero point,
  84              and ecc_add_jja produced garbage. */
  85           cnd_copy (is_zero, tp, pj, 3*ecc->p.size);
  86           is_zero &= ~digit;
  87           /* If we had a one-bit, use the sum. */
  88           cnd_copy (digit, r, tp, 3*ecc->p.size);
  89         }
  90     }
  91 }
  92 #else /* ECC_MUL_A_WBITS > 1 */
  93
  94 #define TABLE_SIZE (1U << ECC_MUL_A_WBITS)
  95 #define TABLE_MASK (TABLE_SIZE - 1)
  96
  97 #define TABLE(j) (table + (j) * 3*ecc->p.size)
  98
  99 static void
 100 table_init (const struct ecc_curve *ecc,
 101             mp_limb_t *table, unsigned bits,
 102             const mp_limb_t *p,
 103             mp_limb_t *scratch)
 104 {
 105   unsigned size = 1 << bits;
 106   unsigned j;
 107
 108   mpn_zero (TABLE(0), 3*ecc->p.size);
 109   ecc_a_to_j (ecc, TABLE(1), p);
 110
 111   for (j = 2; j < size; j += 2)
 112     {
 113       ecc_dup_jj (ecc, TABLE(j), TABLE(j/2), scratch);
 114       ecc_add_jja (ecc, TABLE(j+1), TABLE(j), TABLE(1), scratch);
 115     }
 116 }
 117
 118 void
 119 ecc_mul_a (const struct ecc_curve *ecc,
 120            mp_limb_t *r,
 121            const mp_limb_t *np, const mp_limb_t *p,
 122            mp_limb_t *scratch)
 123 {
 124 #define tp scratch
 125 #define table (scratch + 3*ecc->p.size)
 126   mp_limb_t *scratch_out = table + (3*ecc->p.size << ECC_MUL_A_WBITS);
 127   int is_zero = 0;
 128
 129   /* Avoid the mp_bitcnt_t type for compatibility with older GMP
 130      versions. */
 131   unsigned blocks = (ecc->p.bit_size + ECC_MUL_A_WBITS - 1) / ECC_MUL_A_WBITS;
 132   unsigned bit_index = (blocks-1) * ECC_MUL_A_WBITS;
 133
 134   mp_size_t limb_index = bit_index / GMP_NUMB_BITS;
 135   unsigned shift = bit_index % GMP_NUMB_BITS;
 136   mp_limb_t w, bits;
 137
 138   table_init (ecc, table, ECC_MUL_A_WBITS, p, scratch_out);
 139
 140   w = np[limb_index];
 141   bits = w >> shift;
 142   if (limb_index < ecc->p.size - 1)
 143     bits |= np[limb_index + 1] << (GMP_NUMB_BITS - shift);
 144
 145   assert (bits < TABLE_SIZE);
 146
 147   sec_tabselect (r, 3*ecc->p.size, table, TABLE_SIZE, bits);
 148   is_zero = (bits == 0);
 149
 150   for (;;)
 151     {
 152       unsigned j;
 153       if (shift >= ECC_MUL_A_WBITS)
 154         {
 155           shift -= ECC_MUL_A_WBITS;
 156           bits = w >> shift;
 157         }
 158       else
 159         {
 160           if (limb_index == 0)
 161             {
 162               assert (shift == 0);
 163               break;
 164             }
 165           bits = w << (ECC_MUL_A_WBITS - shift);
 166           w = np[--limb_index];
 167           shift = shift + GMP_NUMB_BITS - ECC_MUL_A_WBITS;
 168           bits |= w >> shift;
 169         }
 170       for (j = 0; j < ECC_MUL_A_WBITS; j++)
 171         ecc_dup_jj (ecc, r, r, scratch_out);
 172
 173       bits &= TABLE_MASK;
 174       sec_tabselect (tp, 3*ecc->p.size, table, TABLE_SIZE, bits);
 175       cnd_copy (is_zero, r, tp, 3*ecc->p.size);
 176       ecc_add_jjj (ecc, tp, tp, r, scratch_out);
 177
 178       /* Use the sum when valid. ecc_add_jja produced garbage if
 179          is_zero != 0 or bits == 0, . */
 180       cnd_copy (bits & (is_zero - 1), r, tp, 3*ecc->p.size);
 181       is_zero &= (bits == 0);
 182     }
 183 #undef table
 184 #undef tp
 185 }
 186
 187 #endif /* ECC_MUL_A_WBITS > 1 */