ecc-521.c

   1 /* ecc-521.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 "ecc.h"
  41 #include "ecc-internal.h"
  42
  43 #define USE_REDC 0
  44
  45 #include "ecc-521.h"
  46
  47 #if HAVE_NATIVE_ecc_521_modp
  48 #define ecc_521_modp nettle_ecc_521_modp
  49 void
  50 ecc_521_modp (const struct ecc_modulo *m, mp_limb_t *rp);
  51
  52 #else
  53
  54 #define B_SHIFT (521 % GMP_NUMB_BITS)
  55 #define BMODP_SHIFT (GMP_NUMB_BITS - B_SHIFT)
  56 #define BMODP ((mp_limb_t) 1 << BMODP_SHIFT)
  57
  58 /* Result may be *slightly* larger than 2^521 */
  59 static void
  60 ecc_521_modp (const struct ecc_modulo *m UNUSED, mp_limb_t *rp)
  61 {
  62   /* FIXME: Should use mpn_addlsh_n_ip1 */
  63   mp_limb_t hi;
  64   /* Reduce from 2*ECC_LIMB_SIZE to ECC_LIMB_SIZE + 1 */
  65   rp[ECC_LIMB_SIZE]
  66     = mpn_addmul_1 (rp, rp + ECC_LIMB_SIZE, ECC_LIMB_SIZE, BMODP);
  67   hi = mpn_addmul_1 (rp, rp + ECC_LIMB_SIZE, 1, BMODP);
  68   hi = sec_add_1 (rp + 1, rp + 1, ECC_LIMB_SIZE - 1, hi);
  69
  70   /* Combine hi with top bits, and add in. */
  71   hi = (hi << BMODP_SHIFT) | (rp[ECC_LIMB_SIZE-1] >> B_SHIFT);
  72   rp[ECC_LIMB_SIZE-1] = (rp[ECC_LIMB_SIZE-1]
  73                          & (((mp_limb_t) 1 << B_SHIFT)-1))
  74     + sec_add_1 (rp, rp, ECC_LIMB_SIZE - 1, hi);
  75 }
  76 #endif
  77
  78 const struct ecc_curve nettle_secp_521r1 =
  79 {
  80   {
  81     521,
  82     ECC_LIMB_SIZE,
  83     ECC_BMODP_SIZE,
  84     ECC_REDC_SIZE,
  85     ECC_MOD_INV_ITCH (ECC_LIMB_SIZE),
  86     0,
  87
  88     ecc_p,
  89     ecc_Bmodp,
  90     ecc_Bmodp_shifted,
  91     ecc_redc_ppm1,
  92     ecc_pp1h,
  93
  94     ecc_521_modp,
  95     ecc_521_modp,
  96     ecc_mod_inv,
  97     NULL,
  98   },
  99   {
 100     521,
 101     ECC_LIMB_SIZE,
 102     ECC_BMODQ_SIZE,
 103     0,
 104     ECC_MOD_INV_ITCH (ECC_LIMB_SIZE),
 105     0,
 106
 107     ecc_q,
 108     ecc_Bmodq,
 109     ecc_Bmodq_shifted,
 110     NULL,
 111     ecc_qp1h,
 112
 113     ecc_mod,
 114     ecc_mod,
 115     ecc_mod_inv,
 116     NULL,
 117   },
 118
 119   USE_REDC,
 120   ECC_PIPPENGER_K,
 121   ECC_PIPPENGER_C,
 122
 123   ECC_ADD_JJJ_ITCH (ECC_LIMB_SIZE),
 124   ECC_MUL_A_ITCH (ECC_LIMB_SIZE),
 125   ECC_MUL_G_ITCH (ECC_LIMB_SIZE),
 126   ECC_J_TO_A_ITCH (ECC_LIMB_SIZE),
 127
 128   ecc_add_jjj,
 129   ecc_mul_a,
 130   ecc_mul_g,
 131   ecc_j_to_a,
 132
 133   ecc_b,
 134   ecc_g,
 135   NULL,
 136   ecc_unit,
 137   ecc_table
 138 };
 139