ecc-384.c

   1 /* ecc-384.c
   2
   3    Compile time constant (but machine dependent) tables.
   4
   5    Copyright (C) 2013, 2014 Niels Möller
   6
   7    This file is part of GNU Nettle.
   8
   9    GNU Nettle is free software: you can redistribute it and/or
  10    modify it under the terms of either:
  11
  12      * the GNU Lesser General Public License as published by the Free
  13        Software Foundation; either version 3 of the License, or (at your
  14        option) any later version.
  15
  16    or
  17
  18      * the GNU General Public License as published by the Free
  19        Software Foundation; either version 2 of the License, or (at your
  20        option) any later version.
  21
  22    or both in parallel, as here.
  23
  24    GNU Nettle is distributed in the hope that it will be useful,
  25    but WITHOUT ANY WARRANTY; without even the implied warranty of
  26    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  27    General Public License for more details.
  28
  29    You should have received copies of the GNU General Public License and
  30    the GNU Lesser General Public License along with this program.  If
  31    not, see http://www.gnu.org/licenses/.
  32 */
  33
  34 /* Development of Nettle's ECC support was funded by the .SE Internet Fund. */
  35
  36 #if HAVE_CONFIG_H
  37 # include "config.h"
  38 #endif
  39
  40 #include <assert.h>
  41
  42 #include "ecc.h"
  43 #include "ecc-internal.h"
  44
  45 #define USE_REDC 0
  46
  47 #include "ecc-384.h"
  48
  49 #if HAVE_NATIVE_ecc_384_modp
  50 #define ecc_384_modp nettle_ecc_384_modp
  51 void
  52 ecc_384_modp (const struct ecc_modulo *m, mp_limb_t *rp);
  53 #elif GMP_NUMB_BITS == 32
  54
  55 /* Use that 2^{384} = 2^{128} + 2^{96} - 2^{32} + 1, and eliminate 256
  56    bits at a time.
  57
  58    We can get carry == 2 in the first iteration, and I think *only* in
  59    the first iteration. */
  60
  61 /* p is 12 limbs, and B^12 - p = B^4 + B^3 - B + 1. We can eliminate
  62    almost 8 at a time. Do only 7, to avoid additional carry
  63    propagation, followed by 5. */
  64 static void
  65 ecc_384_modp (const struct ecc_modulo *p, mp_limb_t *rp)
  66 {
  67   mp_limb_t cy, bw;
  68
  69   /* Reduce from 24 to 17 limbs. */
  70   cy = mpn_add_n (rp + 4, rp + 4, rp + 16, 8);
  71   cy = sec_add_1 (rp + 12, rp + 12, 3, cy);
  72
  73   bw = mpn_sub_n (rp + 5, rp + 5, rp + 16, 8);
  74   bw = sec_sub_1 (rp + 13, rp + 13, 3, bw);
  75
  76   cy += mpn_add_n (rp + 7, rp + 7, rp + 16, 8);
  77   cy = sec_add_1 (rp + 15, rp + 15, 1, cy);
  78
  79   cy += mpn_add_n (rp + 8, rp + 8, rp + 16, 8);
  80   assert (bw <= cy);
  81   cy -= bw;
  82
  83   assert (cy <= 2);
  84   rp[16] = cy;
  85
  86   /* Reduce from 17 to 12 limbs */
  87   cy = mpn_add_n (rp, rp, rp + 12, 5);
  88   cy = sec_add_1 (rp + 5, rp + 5, 3, cy);
  89
  90   bw = mpn_sub_n (rp + 1, rp + 1, rp + 12, 5);
  91   bw = sec_sub_1 (rp + 6, rp + 6, 6, bw);
  92
  93   cy += mpn_add_n (rp + 3, rp + 3, rp + 12, 5);
  94   cy = sec_add_1 (rp + 8, rp + 8, 1, cy);
  95
  96   cy += mpn_add_n (rp + 4, rp + 4, rp + 12, 5);
  97   cy = sec_add_1 (rp + 9, rp + 9, 3, cy);
  98
  99   assert (cy >= bw);
 100   cy -= bw;
 101   assert (cy <= 1);
 102   cy = cnd_add_n (cy, rp, p->B, ECC_LIMB_SIZE);
 103   assert (cy == 0);
 104 }
 105 #elif GMP_NUMB_BITS == 64
 106 /* p is 6 limbs, and B^6 - p = B^2 + 2^32 (B - 1) + 1. Eliminate 3
 107    (almost 4) limbs at a time. */
 108 static void
 109 ecc_384_modp (const struct ecc_modulo *p, mp_limb_t *rp)
 110 {
 111   mp_limb_t tp[6];
 112   mp_limb_t cy;
 113
 114   /* Reduce from 12 to 9 limbs */
 115   tp[0] = 0; /* FIXME: Could use mpn_sub_nc */
 116   mpn_copyi (tp + 1, rp + 8, 3);
 117   tp[4] = rp[11] - mpn_sub_n (tp, tp, rp + 8, 4);
 118   tp[5] = mpn_lshift (tp, tp, 5, 32);
 119
 120   cy = mpn_add_n (rp + 2, rp + 2, rp + 8, 4);
 121   cy = sec_add_1 (rp + 6, rp + 6, 2, cy);
 122
 123   cy += mpn_add_n (rp + 2, rp + 2, tp, 6);
 124   cy += mpn_add_n (rp + 4, rp + 4, rp + 8, 4);
 125
 126   assert (cy <= 2);
 127   rp[8] = cy;
 128
 129   /* Reduce from 9 to 6 limbs */
 130   tp[0] = 0;
 131   mpn_copyi (tp + 1, rp + 6, 2);
 132   tp[3] = rp[8] - mpn_sub_n (tp, tp, rp + 6, 3);
 133   tp[4] = mpn_lshift (tp, tp, 4, 32);
 134
 135   cy = mpn_add_n (rp, rp, rp + 6, 3);
 136   cy = sec_add_1 (rp + 3, rp + 3, 2, cy);
 137   cy += mpn_add_n (rp, rp, tp, 5);
 138   cy += mpn_add_n (rp + 2, rp + 2, rp + 6, 3);
 139
 140   cy = sec_add_1 (rp + 5, rp + 5, 1, cy);
 141   assert (cy <= 1);
 142
 143   cy = cnd_add_n (cy, rp, p->B, ECC_LIMB_SIZE);
 144   assert (cy == 0);
 145 }
 146 #else
 147 #define ecc_384_modp ecc_mod
 148 #endif
 149
 150 const struct ecc_curve nettle_secp_384r1 =
 151 {
 152   {
 153     384,
 154     ECC_LIMB_SIZE,
 155     ECC_BMODP_SIZE,
 156     ECC_REDC_SIZE,
 157     ECC_MOD_INV_ITCH (ECC_LIMB_SIZE),
 158     0,
 159
 160     ecc_p,
 161     ecc_Bmodp,
 162     ecc_Bmodp_shifted,
 163     ecc_redc_ppm1,
 164     ecc_pp1h,
 165
 166     ecc_384_modp,
 167     ecc_384_modp,
 168     ecc_mod_inv,
 169     NULL,
 170   },
 171   {
 172     384,
 173     ECC_LIMB_SIZE,
 174     ECC_BMODQ_SIZE,
 175     0,
 176     ECC_MOD_INV_ITCH (ECC_LIMB_SIZE),
 177     0,
 178
 179     ecc_q,
 180     ecc_Bmodq,
 181     ecc_Bmodq_shifted,
 182     NULL,
 183     ecc_qp1h,
 184
 185     ecc_mod,
 186     ecc_mod,
 187     ecc_mod_inv,
 188     NULL,
 189   },
 190
 191   USE_REDC,
 192   ECC_PIPPENGER_K,
 193   ECC_PIPPENGER_C,
 194
 195   ECC_ADD_JJJ_ITCH (ECC_LIMB_SIZE),
 196   ECC_MUL_A_ITCH (ECC_LIMB_SIZE),
 197   ECC_MUL_G_ITCH (ECC_LIMB_SIZE),
 198   ECC_J_TO_A_ITCH (ECC_LIMB_SIZE),
 199
 200   ecc_add_jjj,
 201   ecc_mul_a,
 202   ecc_mul_g,
 203   ecc_j_to_a,
 204
 205   ecc_b,
 206   ecc_g,
 207   NULL,
 208   ecc_unit,
 209   ecc_table
 210 };