ecc-mod.c

   1 /* ecc-mod.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 /* Computes r mod m, where m is of size mn. bp holds B^mn mod m, as mn
  34    limbs, but the upper mn - bn libms are zero. */
  35 void
  36 ecc_mod (mp_limb_t *rp, mp_size_t rn, mp_size_t mn,
  37          const mp_limb_t *bp, mp_size_t bn,
  38          const mp_limb_t *b_shifted, unsigned shift)
  39 {
  40   mp_limb_t hi;
  41   mp_size_t sn = mn - bn;
  42   mp_size_t i;
  43
  44   assert (sn > 0);
  45
  46   /* FIXME: Could use mpn_addmul_2. */
  47   /* Eliminate sn = mn - bn limbs at a time */
  48   if (bp[bn-1] < ((mp_limb_t) 1 << (GMP_NUMB_BITS - 1)))
  49     {
  50       /* Multiply sn + 1 limbs at a time, so we get a mn+1 limb
  51          product. Then we can absorb the carry in the high limb */
  52       while (rn > 2 * mn - bn)
  53         {
  54           rn -= sn;
  55
  56           for (i = 0; i <= sn; i++)
  57             rp[rn+i-1] = mpn_addmul_1 (rp + rn - mn - 1 + i, bp, bn, rp[rn+i-1]);
  58           rp[rn-1] = rp[rn+sn-1]
  59             + mpn_add_n (rp + rn - sn - 1, rp + rn - sn - 1, rp + rn - 1, sn);
  60         }
  61       goto final_limbs;
  62     }
  63   else
  64     {
  65       while (rn >= 2 * mn - bn)
  66         {
  67           rn -= sn;
  68
  69           for (i = 0; i < sn; i++)
  70             rp[rn+i] = mpn_addmul_1 (rp + rn - mn + i, bp, bn, rp[rn+i]);
  71
  72           hi = mpn_add_n (rp + rn - sn, rp + rn - sn, rp + rn, sn);
  73           hi = cnd_add_n (hi, rp + rn - mn, bp, mn);
  74           assert (hi == 0);
  75         }
  76     }
  77
  78   if (rn > mn)
  79     {
  80     final_limbs:
  81       sn = rn - mn;
  82
  83       for (i = 0; i < sn; i++)
  84         rp[mn+i] = mpn_addmul_1 (rp + i, bp, bn, rp[mn+i]);
  85
  86       hi = mpn_add_n (rp + bn, rp + bn, rp + mn, sn);
  87       hi = sec_add_1 (rp + bn + sn, rp + bn + sn, mn - bn - sn, hi);
  88     }
  89
  90   if (shift > 0)
  91     {
  92       /* Combine hi with top bits, add in */
  93       hi = (hi << shift) | (rp[mn-1] >> (GMP_NUMB_BITS - shift));
  94       rp[mn-1] = (rp[mn-1] & (((mp_limb_t) 1 << (GMP_NUMB_BITS - shift)) - 1))
  95         + mpn_addmul_1 (rp, b_shifted, mn-1, hi);
  96     }
  97   else
  98     {
  99       hi = cnd_add_n (hi, rp, bp, mn);
 100       assert (hi == 0);
 101     }
 102 }