ecc-384.c

   1 /* ecc-384.c.c */
   2
   3 /* Compile time constant (but machine dependent) tables. */
   4
   5 /* nettle, low-level cryptographics library
   6  *
   7  * Copyright (C) 2013 Niels Möller
   8  *
   9  * The nettle library is free software; you can redistribute it and/or modify
  10  * it under the terms of the GNU Lesser General Public License as published by
  11  * the Free Software Foundation; either version 2.1 of the License, or (at your
  12  * option) any later version.
  13  *
  14  * The nettle library is distributed in the hope that it will be useful, but
  15  * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  16  * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
  17  * License for more details.
  18  *
  19  * You should have received a copy of the GNU Lesser General Public License
  20  * along with the nettle library; see the file COPYING.LIB.  If not, write to
  21  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
  22  * MA 02111-1301, USA.
  23  */
  24
  25 /* Development of Nettle's ECC support was funded by the .SE Internet Fund. */
  26
  27 #if HAVE_CONFIG_H
  28 # include "config.h"
  29 #endif
  30
  31 #include <assert.h>
  32
  33 #include "ecc-internal.h"
  34
  35 #define USE_REDC 0
  36
  37 #include "ecc-384.h"
  38
  39 #if HAVE_NATIVE_ecc_384_modp
  40 #define ecc_384_modp nettle_ecc_384_modp
  41 void
  42 ecc_384_modp (const struct ecc_curve *ecc, mp_limb_t *rp);
  43 #elif GMP_NUMB_BITS == 32
  44
  45 /* Use that 2^{384} = 2^{128} + 2^{96} - 2^{32} + 1, and eliminate 256
  46    bits at a time.
  47
  48    We can get carry == 2 in the first iteration, and I think *only* in
  49    the first iteration. */
  50
  51 /* p is 12 limbs, and B^12 - p = B^4 + B^3 - B + 1. We can eliminate
  52    almost 8 at a time. Do only 7, to avoid additional carry
  53    propagation, followed by 5. */
  54 static void
  55 ecc_384_modp (const struct ecc_curve *ecc, mp_limb_t *rp)
  56 {
  57   mp_limb_t cy, bw;
  58
  59   /* Reduce from 24 to 17 limbs. */
  60   cy = mpn_add_n (rp + 4, rp + 4, rp + 16, 8);
  61   cy = sec_add_1 (rp + 12, rp + 12, 3, cy);
  62
  63   bw = mpn_sub_n (rp + 5, rp + 5, rp + 16, 8);
  64   bw = sec_sub_1 (rp + 13, rp + 13, 3, bw);
  65
  66   cy += mpn_add_n (rp + 7, rp + 7, rp + 16, 8);
  67   cy = sec_add_1 (rp + 15, rp + 15, 1, cy);
  68
  69   cy += mpn_add_n (rp + 8, rp + 8, rp + 16, 8);
  70   assert (bw <= cy);
  71   cy -= bw;
  72
  73   assert (cy <= 2);
  74   rp[16] = cy;
  75
  76   /* Reduce from 17 to 12 limbs */
  77   cy = mpn_add_n (rp, rp, rp + 12, 5);
  78   cy = sec_add_1 (rp + 5, rp + 5, 3, cy);
  79
  80   bw = mpn_sub_n (rp + 1, rp + 1, rp + 12, 5);
  81   bw = sec_sub_1 (rp + 6, rp + 6, 6, bw);
  82
  83   cy += mpn_add_n (rp + 3, rp + 3, rp + 12, 5);
  84   cy = sec_add_1 (rp + 8, rp + 8, 1, cy);
  85
  86   cy += mpn_add_n (rp + 4, rp + 4, rp + 12, 5);
  87   cy = sec_add_1 (rp + 9, rp + 9, 3, cy);
  88
  89   assert (cy >= bw);
  90   cy -= bw;
  91   assert (cy <= 1);
  92   cy = cnd_add_n (cy, rp, ecc->Bmodp, ECC_LIMB_SIZE);
  93   assert (cy == 0);
  94 }
  95 #elif GMP_NUMB_BITS == 64
  96 /* p is 6 limbs, and B^6 - p = B^2 + 2^32 (B - 1) + 1. Eliminate 3
  97    (almost 4) limbs at a time. */
  98 static void
  99 ecc_384_modp (const struct ecc_curve *ecc, mp_limb_t *rp)
 100 {
 101   mp_limb_t tp[6];
 102   mp_limb_t cy;
 103
 104   /* Reduce from 12 to 9 limbs */
 105   tp[0] = 0; /* FIXME: Could use mpn_sub_nc */
 106   mpn_copyi (tp + 1, rp + 8, 3);
 107   tp[4] = rp[11] - mpn_sub_n (tp, tp, rp + 8, 4);
 108   tp[5] = mpn_lshift (tp, tp, 5, 32);
 109
 110   cy = mpn_add_n (rp + 2, rp + 2, rp + 8, 4);
 111   cy = sec_add_1 (rp + 6, rp + 6, 2, cy);
 112
 113   cy += mpn_add_n (rp + 2, rp + 2, tp, 6);
 114   cy += mpn_add_n (rp + 4, rp + 4, rp + 8, 4);
 115
 116   assert (cy <= 2);
 117   rp[8] = cy;
 118
 119   /* Reduce from 9 to 6 limbs */
 120   tp[0] = 0;
 121   mpn_copyi (tp + 1, rp + 6, 2);
 122   tp[3] = rp[8] - mpn_sub_n (tp, tp, rp + 6, 3);
 123   tp[4] = mpn_lshift (tp, tp, 4, 32);
 124
 125   cy = mpn_add_n (rp, rp, rp + 6, 3);
 126   cy = sec_add_1 (rp + 3, rp + 3, 2, cy);
 127   cy += mpn_add_n (rp, rp, tp, 5);
 128   cy += mpn_add_n (rp + 2, rp + 2, rp + 6, 3);
 129
 130   cy = sec_add_1 (rp + 5, rp + 5, 1, cy);
 131   assert (cy <= 1);
 132
 133   cy = cnd_add_n (cy, rp, ecc->Bmodp, ECC_LIMB_SIZE);
 134   assert (cy == 0);
 135 }
 136 #else
 137 #define ecc_384_modp ecc_generic_modp
 138 #endif
 139
 140 const struct ecc_curve nettle_secp_384r1 =
 141 {
 142   384,
 143   ECC_LIMB_SIZE,
 144   ECC_BMODP_SIZE,
 145   ECC_BMODQ_SIZE,
 146   USE_REDC,
 147   ECC_REDC_SIZE,
 148   ECC_PIPPENGER_K,
 149   ECC_PIPPENGER_C,
 150   ecc_p,
 151   ecc_b,
 152   ecc_q,
 153   ecc_g,
 154   ecc_redc_g,
 155   ecc_384_modp,
 156   ECC_REDC_SIZE != 0 ? ecc_generic_redc : NULL,
 157   ecc_384_modp,
 158   ecc_generic_modq,
 159   ecc_Bmodp,
 160   ecc_Bmodp_shifted,
 161   ecc_pp1h,
 162   ecc_redc_ppm1,
 163   ecc_unit,
 164   ecc_Bmodq,
 165   ecc_Bmodq_shifted,
 166   ecc_qp1h,
 167   ecc_table
 168 };