ecc-modp.c

   1 /* ecc-modp.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 /* Routines for modp arithmetic. All values are ecc->size limbs, but
  34    not necessarily < p. */
  35
  36 void
  37 ecc_modp_add (const struct ecc_curve *ecc, mp_limb_t *rp,
  38               const mp_limb_t *ap, const mp_limb_t *bp)
  39 {
  40   mp_limb_t cy;
  41   cy = mpn_add_n (rp, ap, bp, ecc->size);
  42   cy = cnd_add_n (cy, rp, ecc->Bmodp, ecc->size);
  43   cy = cnd_add_n (cy, rp, ecc->Bmodp, ecc->size);
  44   assert (cy == 0);
  45 }
  46
  47 void
  48 ecc_modp_sub (const struct ecc_curve *ecc, mp_limb_t *rp,
  49               const mp_limb_t *ap, const mp_limb_t *bp)
  50 {
  51   mp_limb_t cy;
  52   cy = mpn_sub_n (rp, ap, bp, ecc->size);
  53   cy = cnd_sub_n (cy, rp, ecc->Bmodp, ecc->size);
  54   cy = cnd_sub_n (cy, rp, ecc->Bmodp, ecc->size);
  55   assert (cy == 0);
  56 }
  57
  58 void
  59 ecc_modp_sub_1 (const struct ecc_curve *ecc, mp_limb_t *rp,
  60                 const mp_limb_t *ap, mp_limb_t b)
  61 {
  62   mp_size_t i;
  63
  64   for (i = 0; i < ecc->size; i++)
  65     {
  66       mp_limb_t cy = ap[i] < b;
  67       rp[i] = ap[i] - b;
  68       b = cy;
  69     }
  70   b = cnd_sub_n (b, rp, ecc->Bmodp, ecc->size);
  71   assert (b == 0);
  72 }
  73
  74 void
  75 ecc_modp_mul_1 (const struct ecc_curve *ecc, mp_limb_t *rp,
  76                 const mp_limb_t *ap, mp_limb_t b)
  77 {
  78   mp_limb_t hi;
  79
  80   assert (b <= 0xffffffff);
  81   hi = mpn_mul_1 (rp, ap, ecc->size, b);
  82   hi = mpn_addmul_1 (rp, ecc->Bmodp, ecc->size, hi);
  83   assert (hi <= 1);
  84   hi = cnd_add_n (hi, rp, ecc->Bmodp, ecc->size);
  85   /* Sufficient if b < B^size / p */
  86   assert (hi == 0);
  87 }
  88
  89 void
  90 ecc_modp_addmul_1 (const struct ecc_curve *ecc, mp_limb_t *rp,
  91                    const mp_limb_t *ap, mp_limb_t b)
  92 {
  93   mp_limb_t hi;
  94
  95   assert (b <= 0xffffffff);
  96   hi = mpn_addmul_1 (rp, ap, ecc->size, b);
  97   hi = mpn_addmul_1 (rp, ecc->Bmodp, ecc->size, hi);
  98   assert (hi <= 1);
  99   hi = cnd_add_n (hi, rp, ecc->Bmodp, ecc->size);
 100   /* Sufficient roughly if b < B^size / p */
 101   assert (hi == 0);
 102 }
 103
 104 void
 105 ecc_modp_submul_1 (const struct ecc_curve *ecc, mp_limb_t *rp,
 106                    const mp_limb_t *ap, mp_limb_t b)
 107 {
 108   mp_limb_t hi;
 109
 110   assert (b <= 0xffffffff);
 111   hi = mpn_submul_1 (rp, ap, ecc->size, b);
 112   hi = mpn_submul_1 (rp, ecc->Bmodp, ecc->size, hi);
 113   assert (hi <= 1);
 114   hi = cnd_sub_n (hi, rp, ecc->Bmodp, ecc->size);
 115   /* Sufficient roughly if b < B^size / p */
 116   assert (hi == 0);
 117 }
 118
 119 /* NOTE: mul and sqr needs 2*ecc->size limbs at rp */
 120 void
 121 ecc_modp_mul (const struct ecc_curve *ecc, mp_limb_t *rp,
 122               const mp_limb_t *ap, const mp_limb_t *bp)
 123 {
 124   mpn_mul_n (rp, ap, bp, ecc->size);
 125   ecc->reduce (ecc, rp);
 126 }
 127
 128 void
 129 ecc_modp_sqr (const struct ecc_curve *ecc, mp_limb_t *rp,
 130               const mp_limb_t *ap)
 131 {
 132   mpn_sqr (rp, ap, ecc->size);
 133   ecc->reduce (ecc, rp);
 134 }
 135
 136 void
 137 ecc_modp_inv (const struct ecc_curve *ecc, mp_limb_t *rp, mp_limb_t *ap,
 138               mp_limb_t *scratch)
 139 {
 140   sec_modinv (rp, ap, ecc->size, ecc->p, ecc->pp1h, ecc->bit_size, scratch);
 141 }
 142