ecc-mul-a-eh.c 4.33 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 31 32 33 34 35 36 37 38 39 40
/* ecc-mul-a-eh.c

   Copyright (C) 2013, 2014 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/.
*/

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

#include <assert.h>

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

41 42
/* Binary algorithm needs 6*ecc->p.size + scratch for ecc_add_ehh,
   total 13 ecc->p.size
43

44 45 46
   Window algorithm needs (3<<w) * ecc->p.size for the table,
   3*ecc->p.size for a temporary point, and scratch for
   ecc_add_ehh. */
47 48 49 50 51 52 53 54 55

#if ECC_MUL_A_EH_WBITS == 0
void
ecc_mul_a_eh (const struct ecc_curve *ecc,
	      mp_limb_t *r,
	      const mp_limb_t *np, const mp_limb_t *p,
	      mp_limb_t *scratch)
{
#define pe scratch
Niels Möller's avatar
Niels Möller committed
56 57
#define tp (scratch + 3*ecc->p.size)
#define scratch_out (scratch + 6*ecc->p.size)
58 59 60

  unsigned i;

61
  ecc_a_to_j (ecc, pe, p);
62 63

  /* x = 0, y = 1, z = 1 */
Niels Möller's avatar
Niels Möller committed
64 65
  mpn_zero (r, 3*ecc->p.size);
  r[ecc->p.size] = r[2*ecc->p.size] = 1;
66
  
Niels Möller's avatar
Niels Möller committed
67
  for (i = ecc->p.size; i-- > 0; )
68 69 70 71 72 73 74 75 76 77
    {
      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;

78 79
	  ecc->dup (ecc, r, r, scratch_out);
	  ecc->add_hhh (ecc, tp, r, pe, scratch_out);
80 81 82

	  digit = (w & bit) > 0;
	  /* If we had a one-bit, use the sum. */
Niels Möller's avatar
Niels Möller committed
83
	  cnd_copy (digit, r, tp, 3*ecc->p.size);
84 85 86 87 88 89 90 91
	}
    }
}
#else /* ECC_MUL_A_EH_WBITS > 1 */

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

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

static void
table_init (const struct ecc_curve *ecc,
	    mp_limb_t *table, unsigned bits,
	    const mp_limb_t *p,
	    mp_limb_t *scratch)
{
  unsigned size = 1 << bits;
  unsigned j;

Niels Möller's avatar
Niels Möller committed
103 104
  mpn_zero (TABLE(0), 3*ecc->p.size);
  TABLE(0)[ecc->p.size] = TABLE(0)[2*ecc->p.size] = 1;
105

106
  ecc_a_to_j (ecc, TABLE(1), p);
107 108 109

  for (j = 2; j < size; j += 2)
    {
110 111
      ecc->dup (ecc, TABLE(j), TABLE(j/2), scratch);
      ecc->add_hhh (ecc, TABLE(j+1), TABLE(j), TABLE(1), scratch);
112 113 114 115 116 117 118 119 120 121
    }
}

void
ecc_mul_a_eh (const struct ecc_curve *ecc,
	      mp_limb_t *r,
	      const mp_limb_t *np, const mp_limb_t *p,
	      mp_limb_t *scratch)
{
#define tp scratch
Niels Möller's avatar
Niels Möller committed
122 123
#define table (scratch + 3*ecc->p.size)
  mp_limb_t *scratch_out = table + (3*ecc->p.size << ECC_MUL_A_EH_WBITS);
124 125 126

  /* Avoid the mp_bitcnt_t type for compatibility with older GMP
     versions. */
Niels Möller's avatar
Niels Möller committed
127
  unsigned blocks = (ecc->p.bit_size + ECC_MUL_A_EH_WBITS - 1) / ECC_MUL_A_EH_WBITS;
128 129 130 131 132 133 134 135 136 137
  unsigned bit_index = (blocks-1) * ECC_MUL_A_EH_WBITS;

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

  table_init (ecc, table, ECC_MUL_A_EH_WBITS, p, scratch_out);

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

  assert (bits < TABLE_SIZE);

Niels Möller's avatar
Niels Möller committed
143
  sec_tabselect (r, 3*ecc->p.size, table, TABLE_SIZE, bits);
144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165

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

      bits &= TABLE_MASK;
Niels Möller's avatar
Niels Möller committed
169
      sec_tabselect (tp, 3*ecc->p.size, table, TABLE_SIZE, bits);
170
      ecc->add_hhh (ecc, r, tp, r, scratch_out);
171 172 173 174 175 176
    }
#undef table
#undef tp
}

#endif /* ECC_MUL_A_EH_WBITS > 1 */