ecc-mul-a.c

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