ecc-mul-a.c 4.71 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
/* ecc-mul-a.c

   Copyright (C) 2013 Niels Möller

   This file is part of GNU Nettle.

   GNU Nettle is free software: you can redistribute it and/or
   modify it under the terms of either:

     * the GNU Lesser General Public License as published by the Free
       Software Foundation; either version 3 of the License, or (at your
       option) any later version.

   or

     * the GNU General Public License as published by the Free
       Software Foundation; either version 2 of the License, or (at your
       option) any later version.

   or both in parallel, as here.

   GNU Nettle is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   General Public License for more details.

   You should have received copies of the GNU General Public License and
   the GNU Lesser General Public License along with this program.  If
   not, see http://www.gnu.org/licenses/.
*/
Niels Möller's avatar
Niels Möller committed
31

32
/* Development of Nettle's ECC support was funded by the .SE Internet Fund. */
Niels Möller's avatar
Niels Möller committed
33 34 35 36 37 38 39 40 41 42

#if HAVE_CONFIG_H
# include "config.h"
#endif

#include <assert.h>

#include "ecc.h"
#include "ecc-internal.h"

43 44 45 46 47 48
/* Binary algorithm needs 6*ecc->p.size + scratch for ecc_add_jja.
   Current total is 12 ecc->p.size, at most 864 bytes.

   Window algorithm needs (3<<w) * ecc->p.size for the table,
   3*ecc->p.size for a temporary point, and scratch for
   ecc_add_jjj. */
Niels Möller's avatar
Niels Möller committed
49 50 51 52

#if ECC_MUL_A_WBITS == 0
void
ecc_mul_a (const struct ecc_curve *ecc,
53
	   mp_limb_t *r,
Niels Möller's avatar
Niels Möller committed
54 55 56 57
	   const mp_limb_t *np, const mp_limb_t *p,
	   mp_limb_t *scratch)
{
#define tp scratch
58 59
#define pj (scratch + 3*ecc->p.size)
#define scratch_out (scratch + 6*ecc->p.size)
Niels Möller's avatar
Niels Möller committed
60 61 62 63 64

  int is_zero;

  unsigned i;

65
  ecc_a_to_j (ecc, pj, p);
66
  mpn_zero (r, 3*ecc->p.size);
Niels Möller's avatar
Niels Möller committed
67
  
68
  for (i = ecc->p.size, is_zero = 1; i-- > 0; )
Niels Möller's avatar
Niels Möller committed
69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84
    {
      mp_limb_t w = np[i];
      mp_limb_t bit;

      for (bit = (mp_limb_t) 1 << (GMP_NUMB_BITS - 1);
	   bit > 0;
	   bit >>= 1)
	{
	  int digit;

	  ecc_dup_jj (ecc, r, r, scratch_out);
	  ecc_add_jja (ecc, tp, r, pj, scratch_out);

	  digit = (w & bit) > 0;
	  /* If is_zero is set, r is the zero point,
	     and ecc_add_jja produced garbage. */
85
	  cnd_copy (is_zero, tp, pj, 3*ecc->p.size);
Niels Möller's avatar
Niels Möller committed
86 87
	  is_zero &= ~digit;
	  /* If we had a one-bit, use the sum. */
88
	  cnd_copy (digit, r, tp, 3*ecc->p.size);
Niels Möller's avatar
Niels Möller committed
89 90 91 92 93 94 95 96
	}
    }
}
#else /* ECC_MUL_A_WBITS > 1 */

#define TABLE_SIZE (1U << ECC_MUL_A_WBITS)
#define TABLE_MASK (TABLE_SIZE - 1)

97
#define TABLE(j) (table + (j) * 3*ecc->p.size)
Niels Möller's avatar
Niels Möller committed
98 99 100 101

static void
table_init (const struct ecc_curve *ecc,
	    mp_limb_t *table, unsigned bits,
102
	    const mp_limb_t *p,
Niels Möller's avatar
Niels Möller committed
103 104 105 106 107
	    mp_limb_t *scratch)
{
  unsigned size = 1 << bits;
  unsigned j;

108
  mpn_zero (TABLE(0), 3*ecc->p.size);
109
  ecc_a_to_j (ecc, TABLE(1), p);
Niels Möller's avatar
Niels Möller committed
110 111 112 113 114 115 116 117 118 119

  for (j = 2; j < size; j += 2)
    {
      ecc_dup_jj (ecc, TABLE(j), TABLE(j/2), scratch);
      ecc_add_jja (ecc, TABLE(j+1), TABLE(j), TABLE(1), scratch);
    }  
}

void
ecc_mul_a (const struct ecc_curve *ecc,
120
	   mp_limb_t *r,
Niels Möller's avatar
Niels Möller committed
121 122 123 124
	   const mp_limb_t *np, const mp_limb_t *p,
	   mp_limb_t *scratch)
{
#define tp scratch
125 126
#define table (scratch + 3*ecc->p.size)
  mp_limb_t *scratch_out = table + (3*ecc->p.size << ECC_MUL_A_WBITS);
Niels Möller's avatar
Niels Möller committed
127 128
  int is_zero = 0;

129 130
  /* Avoid the mp_bitcnt_t type for compatibility with older GMP
     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;
Niels Möller's avatar
Niels Möller committed
133 134 135 136 137

  mp_size_t limb_index = bit_index / GMP_NUMB_BITS;
  unsigned shift = bit_index % GMP_NUMB_BITS;
  mp_limb_t w, bits;

138
  table_init (ecc, table, ECC_MUL_A_WBITS, p, scratch_out);
Niels Möller's avatar
Niels Möller committed
139 140 141

  w = np[limb_index];
  bits = w >> shift;
142
  if (limb_index < ecc->p.size - 1)
Niels Möller's avatar
Niels Möller committed
143 144 145 146
    bits |= np[limb_index + 1] << (GMP_NUMB_BITS - shift);

  assert (bits < TABLE_SIZE);

147
  sec_tabselect (r, 3*ecc->p.size, table, TABLE_SIZE, bits);
Niels Möller's avatar
Niels Möller committed
148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173
  is_zero = (bits == 0);

  for (;;)
    {
      unsigned j;
      if (shift >= ECC_MUL_A_WBITS)
	{
	  shift -= ECC_MUL_A_WBITS;
	  bits = w >> shift;
	}
      else
	{
	  if (limb_index == 0)
	    {
	      assert (shift == 0);
	      break;
	    }
	  bits = w << (ECC_MUL_A_WBITS - shift);
	  w = np[--limb_index];
	  shift = shift + GMP_NUMB_BITS - ECC_MUL_A_WBITS;
	  bits |= w >> shift;
	}
      for (j = 0; j < ECC_MUL_A_WBITS; j++)
	ecc_dup_jj (ecc, r, r, scratch_out);

      bits &= TABLE_MASK;
174 175
      sec_tabselect (tp, 3*ecc->p.size, table, TABLE_SIZE, bits);
      cnd_copy (is_zero, r, tp, 3*ecc->p.size);
Niels Möller's avatar
Niels Möller committed
176 177 178 179
      ecc_add_jjj (ecc, tp, tp, r, scratch_out);

      /* Use the sum when valid. ecc_add_jja produced garbage if
	 is_zero != 0 or bits == 0, . */	  
180
      cnd_copy (bits & (is_zero - 1), r, tp, 3*ecc->p.size);
Niels Möller's avatar
Niels Möller committed
181 182 183 184 185 186 187
      is_zero &= (bits == 0);
    }
#undef table
#undef tp
}

#endif /* ECC_MUL_A_WBITS > 1 */