git.samba.org - gd/nettle/blob - ecc-mul-a-eh.c

   1 /* ecc-mul-a-eh.c
   2
   3    Copyright (C) 2013, 2014 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 #if HAVE_CONFIG_H
  33 # include "config.h"
  34 #endif
  35
  36 #include <assert.h>
  37
  38 #include "ecc.h"
  39 #include "ecc-internal.h"
  40
  41 /* Binary algorithm needs 6*ecc->p.size + scratch for ecc_add_ehh,
  42    total 13 ecc->p.size
  43
  44    Window algorithm needs (3<<w) * ecc->p.size for the table,
  45    3*ecc->p.size for a temporary point, and scratch for
  46    ecc_add_ehh. */
  47
  48 #if ECC_MUL_A_EH_WBITS == 0
  49 void
  50 ecc_mul_a_eh (const struct ecc_curve *ecc,
  51               mp_limb_t *r,
  52               const mp_limb_t *np, const mp_limb_t *p,
  53               mp_limb_t *scratch)
  54 {
  55 #define pe scratch
  56 #define tp (scratch + 3*ecc->p.size)
  57 #define scratch_out (scratch + 6*ecc->p.size)
  58
  59   unsigned i;
  60
  61   ecc_a_to_j (ecc, pe, p);
  62
  63   /* x = 0, y = 1, z = 1 */
  64   mpn_zero (r, 3*ecc->p.size);
  65   r[ecc->p.size] = r[2*ecc->p.size] = 1;
  66
  67   for (i = ecc->p.size; i-- > 0; )
  68     {
  69       mp_limb_t w = np[i];
  70       mp_limb_t bit;
  71
  72       for (bit = (mp_limb_t) 1 << (GMP_NUMB_BITS - 1);
  73            bit > 0;
  74            bit >>= 1)
  75         {
  76           int digit;
  77
  78           ecc_dup_eh (ecc, r, r, scratch_out);
  79           ecc_add_ehh (ecc, tp, r, pe, scratch_out);
  80
  81           digit = (w & bit) > 0;
  82           /* If we had a one-bit, use the sum. */
  83           cnd_copy (digit, r, tp, 3*ecc->p.size);
  84         }
  85     }
  86 }
  87 #else /* ECC_MUL_A_EH_WBITS > 1 */
  88
  89 #define TABLE_SIZE (1U << ECC_MUL_A_EH_WBITS)
  90 #define TABLE_MASK (TABLE_SIZE - 1)
  91
  92 #define TABLE(j) (table + (j) * 3*ecc->p.size)
  93
  94 static void
  95 table_init (const struct ecc_curve *ecc,
  96             mp_limb_t *table, unsigned bits,
  97             const mp_limb_t *p,
  98             mp_limb_t *scratch)
  99 {
 100   unsigned size = 1 << bits;
 101   unsigned j;
 102
 103   mpn_zero (TABLE(0), 3*ecc->p.size);
 104   TABLE(0)[ecc->p.size] = TABLE(0)[2*ecc->p.size] = 1;
 105
 106   ecc_a_to_j (ecc, TABLE(1), p);
 107
 108   for (j = 2; j < size; j += 2)
 109     {
 110       ecc_dup_eh (ecc, TABLE(j), TABLE(j/2), scratch);
 111       ecc_add_ehh (ecc, TABLE(j+1), TABLE(j), TABLE(1), scratch);
 112     }
 113 }
 114
 115 void
 116 ecc_mul_a_eh (const struct ecc_curve *ecc,
 117               mp_limb_t *r,
 118               const mp_limb_t *np, const mp_limb_t *p,
 119               mp_limb_t *scratch)
 120 {
 121 #define tp scratch
 122 #define table (scratch + 3*ecc->p.size)
 123   mp_limb_t *scratch_out = table + (3*ecc->p.size << ECC_MUL_A_EH_WBITS);
 124
 125   /* Avoid the mp_bitcnt_t type for compatibility with older GMP
 126      versions. */
 127   unsigned blocks = (ecc->p.bit_size + ECC_MUL_A_EH_WBITS - 1) / ECC_MUL_A_EH_WBITS;
 128   unsigned bit_index = (blocks-1) * ECC_MUL_A_EH_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_EH_WBITS, p, scratch_out);
 135
 136   w = np[limb_index];
 137   bits = w >> shift;
 138   if (limb_index < ecc->p.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->p.size, table, TABLE_SIZE, bits);
 144
 145   for (;;)
 146     {
 147       unsigned j;
 148       if (shift >= ECC_MUL_A_EH_WBITS)
 149         {
 150           shift -= ECC_MUL_A_EH_WBITS;
 151           bits = w >> shift;
 152         }
 153       else
 154         {
 155           if (limb_index == 0)
 156             {
 157               assert (shift == 0);
 158               break;
 159             }
 160           bits = w << (ECC_MUL_A_EH_WBITS - shift);
 161           w = np[--limb_index];
 162           shift = shift + GMP_NUMB_BITS - ECC_MUL_A_EH_WBITS;
 163           bits |= w >> shift;
 164         }
 165       for (j = 0; j < ECC_MUL_A_EH_WBITS; j++)
 166         ecc_dup_eh (ecc, r, r, scratch_out);
 167
 168       bits &= TABLE_MASK;
 169       sec_tabselect (tp, 3*ecc->p.size, table, TABLE_SIZE, bits);
 170       ecc_add_ehh (ecc, r, tp, r, scratch_out);
 171     }
 172 #undef table
 173 #undef tp
 174 }
 175
 176 #endif /* ECC_MUL_A_EH_WBITS > 1 */