ecc-generic-redc.c

   1 /* ecc-generic-redc.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-internal.h"
  32
  33 void
  34 ecc_generic_redc (const struct ecc_curve *ecc, mp_limb_t *rp)
  35 {
  36   unsigned i;
  37   mp_limb_t hi, cy;
  38   unsigned shift = ecc->size * GMP_NUMB_BITS - ecc->bit_size;
  39   mp_size_t k = ecc->redc_size;
  40
  41   assert (k != 0);
  42   if (k > 0)
  43     {
  44       /* Use that 1 = p + 1, and that at least one low limb of p + 1 is zero. */
  45       for (i = 0; i < ecc->size; i++)
  46         rp[i] = mpn_addmul_1 (rp + i + k,
  47                               ecc->redc_ppm1, ecc->size - k, rp[i]);
  48       hi = mpn_add_n (rp, rp, rp + ecc->size, ecc->size);
  49       if (shift > 0)
  50         {
  51           hi = (hi << shift) | (rp[ecc->size - 1] >> (GMP_NUMB_BITS - shift));
  52           rp[ecc->size - 1] = (rp[ecc->size - 1]
  53                                & (((mp_limb_t) 1 << (GMP_NUMB_BITS - shift)) - 1))
  54             + mpn_addmul_1 (rp, ecc->Bmodp_shifted, ecc->size-1, hi);
  55
  56         }
  57       else
  58         {
  59           cy = cnd_sub_n (hi, rp, ecc->p, ecc->size);
  60           assert (cy == hi);
  61         }
  62     }
  63   else
  64     {
  65       /* Use that 1 = - (p - 1), and that at least one low limb of p -
  66          1 is zero. */
  67       k = -k;
  68       for (i = 0; i < ecc->size; i++)
  69         rp[i] = mpn_submul_1 (rp + i + k,
  70                               ecc->redc_ppm1, ecc->size - k, rp[i]);
  71       hi = mpn_sub_n (rp, rp + ecc->size, rp, ecc->size);
  72       cy = cnd_add_n (hi, rp, ecc->p, ecc->size);
  73       assert (cy == hi);
  74
  75       if (shift > 0)
  76         {
  77           /* Result is always < 2p, provided that
  78              2^shift * Bmodp_shifted <= p */
  79           hi = (rp[ecc->size - 1] >> (GMP_NUMB_BITS - shift));
  80           rp[ecc->size - 1] = (rp[ecc->size - 1]
  81                                & (((mp_limb_t) 1 << (GMP_NUMB_BITS - shift)) - 1))
  82             + mpn_addmul_1 (rp, ecc->Bmodp_shifted, ecc->size-1, hi);
  83         }
  84     }
  85 }