ecc-secp521r1.c

   1 /* ecc-secp521r1.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-internal.h"
  41
  42 #define USE_REDC 0
  43
  44 #include "ecc-secp521r1.h"
  45
  46 #define B_SHIFT (521 % GMP_NUMB_BITS)
  47
  48 #if HAVE_NATIVE_ecc_secp521r1_modp
  49 #define ecc_secp521r1_modp _nettle_ecc_secp521r1_modp
  50 void
  51 ecc_secp521r1_modp (const struct ecc_modulo *m, mp_limb_t *rp, mp_limb_t *xp);
  52
  53 #else
  54
  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_secp521r1_modp (const struct ecc_modulo *m UNUSED, mp_limb_t *rp, mp_limb_t *xp)
  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   xp[ECC_LIMB_SIZE]
  66     = mpn_addmul_1 (xp, xp + ECC_LIMB_SIZE, ECC_LIMB_SIZE, BMODP);
  67   hi = mpn_addmul_1 (xp, xp + ECC_LIMB_SIZE, 1, BMODP);
  68   hi = sec_add_1 (xp + 1, xp + 1, ECC_LIMB_SIZE - 1, hi);
  69
  70   /* Combine hi with top bits, and add in. */
  71   hi = (hi << BMODP_SHIFT) | (xp[ECC_LIMB_SIZE-1] >> B_SHIFT);
  72   rp[ECC_LIMB_SIZE-1] = (xp[ECC_LIMB_SIZE-1]
  73                          & (((mp_limb_t) 1 << B_SHIFT)-1))
  74     + sec_add_1 (rp, xp, ECC_LIMB_SIZE - 1, hi);
  75 }
  76 #endif
  77
  78 #define ECC_SECP521R1_INV_ITCH (3*ECC_LIMB_SIZE)
  79
  80 static void
  81 ecc_secp521r1_inv (const struct ecc_modulo *p,
  82                    mp_limb_t *rp, const mp_limb_t *ap,
  83                    mp_limb_t *scratch)
  84 {
  85 #define t0 scratch
  86 #define tp (scratch + ECC_LIMB_SIZE)
  87
  88   /* Addition chain for p - 2:
  89
  90      2^{521} - 3
  91      = 1 + 2^2(2^519 - 1)
  92      = 1 + 2^2(1 + 2 (2^518 - 1)
  93      = 1 + 2^2(1 + 2 (2^259 + 1) (1 + 2(2^258 - 1)))
  94      = 1 + 2^2(1 + 2 (2^259 + 1) (1 + 2(2^129 + 1) (2^129 - 1)))
  95      = 1 + 2^2(1 + 2 (2^259 + 1) (1 + 2(2^129 + 1) (1 + 2 (2^128 - 1))))
  96
  97      where
  98
  99      2^{128} - 1 = (2^64 + 1) (2^32+1) (2^16 + 1) (2^8 + 1) (2^4 + 1) (2^2 + 1) (2 + 1)
 100
 101      This addition chain needs 520 squarings and 13 multiplies.
 102   */
 103
 104   ecc_mod_sqr (p, rp, ap, tp);          /* a^2 */
 105   ecc_mod_mul (p, rp, ap, rp, tp);      /* a^3 = a^{2^2 - 1} */
 106   ecc_mod_pow_2kp1 (p, t0, rp, 2, tp);  /* a^15 = a^{2^4 - 1} */
 107   ecc_mod_pow_2kp1 (p, rp, t0, 4, tp);  /* a^{2^8 - 1} */
 108   ecc_mod_pow_2kp1 (p, t0, rp, 8, tp);  /* a^{2^16 - 1} */
 109   ecc_mod_pow_2kp1 (p, rp, t0, 16, tp); /* a^{2^32 - 1} */
 110   ecc_mod_pow_2kp1 (p, t0, rp, 32, tp); /* a^{2^64 - 1} */
 111   ecc_mod_pow_2kp1 (p, rp, t0, 64, tp); /* a^{2^128 - 1} */
 112   ecc_mod_sqr (p, rp, rp, tp);          /* a^{2^129 - 2} */
 113   ecc_mod_mul (p, rp, rp, ap, tp);      /* a^{2^129 - 1} */
 114   ecc_mod_pow_2kp1 (p, t0, rp, 129, tp);/* a^{2^258 - 1} */
 115   ecc_mod_sqr (p, rp, t0, tp);          /* a^{2^259 - 2} */
 116   ecc_mod_mul (p, rp, rp, ap, tp);      /* a^{2^259 - 1} */
 117   ecc_mod_pow_2kp1 (p, t0, rp, 259, tp);/* a^{2^518 - 1} */
 118   ecc_mod_sqr (p, rp, t0, tp);          /* a^{2^519 - 2} */
 119   ecc_mod_mul (p, rp, rp, ap, tp);      /* a^{2^519 - 1} */
 120   ecc_mod_sqr (p, rp, rp, tp);          /* a^{2^520 - 2} */
 121   ecc_mod_sqr (p, rp, rp, tp);          /* a^{2^521 - 4} */
 122   ecc_mod_mul (p, rp, rp, ap, tp);      /* a^{2^521 - 3} */
 123 }
 124
 125 #define ECC_SECP521R1_SQRT_ITCH (2*ECC_LIMB_SIZE)
 126
 127 static int
 128 ecc_secp521r1_sqrt (const struct ecc_modulo *m,
 129                     mp_limb_t *rp,
 130                     const mp_limb_t *cp,
 131                     mp_limb_t *scratch)
 132 {
 133   mp_limb_t hi;
 134
 135   /* This computes the square root modulo p256 using the identity:
 136
 137      sqrt(c) = c^(2^519) (mod P-521)
 138
 139      which can be seen as a special case of Tonelli-Shanks with e=1.
 140   */
 141
 142   ecc_mod_pow_2k (m, rp, cp, 519, scratch);
 143
 144   /* Check result. */
 145   ecc_mod_sqr (m, scratch, rp, scratch);
 146   ecc_mod_sub (m, scratch, scratch, cp);
 147
 148   /* Reduce top bits, since ecc_mod_zero_p requires input < 2p */
 149   hi = scratch[ECC_LIMB_SIZE-1] >> B_SHIFT;
 150   scratch[ECC_LIMB_SIZE-1] = (scratch[ECC_LIMB_SIZE-1]
 151                               & (((mp_limb_t) 1 << B_SHIFT)-1))
 152     + sec_add_1 (scratch, scratch, ECC_LIMB_SIZE - 1, hi);
 153
 154   return ecc_mod_zero_p (m, scratch);
 155 }
 156
 157
 158 const struct ecc_curve _nettle_secp_521r1 =
 159 {
 160   {
 161     521,
 162     ECC_LIMB_SIZE,
 163     ECC_BMODP_SIZE,
 164     ECC_REDC_SIZE,
 165     ECC_SECP521R1_INV_ITCH,
 166     ECC_SECP521R1_SQRT_ITCH,
 167     0,
 168
 169     ecc_p,
 170     ecc_Bmodp,
 171     ecc_Bmodp_shifted,
 172     ecc_Bm2p,
 173     ecc_redc_ppm1,
 174     ecc_pp1h,
 175
 176     ecc_secp521r1_modp,
 177     ecc_secp521r1_modp,
 178     ecc_secp521r1_inv,
 179     ecc_secp521r1_sqrt,
 180     NULL,
 181   },
 182   {
 183     521,
 184     ECC_LIMB_SIZE,
 185     ECC_BMODQ_SIZE,
 186     0,
 187     ECC_MOD_INV_ITCH (ECC_LIMB_SIZE),
 188     0,
 189     0,
 190
 191     ecc_q,
 192     ecc_Bmodq,
 193     ecc_Bmodq_shifted,
 194     ecc_Bm2q,
 195     NULL,
 196     ecc_qp1h,
 197
 198     ecc_mod,
 199     ecc_mod,
 200     ecc_mod_inv,
 201     NULL,
 202     NULL,
 203   },
 204
 205   USE_REDC,
 206   ECC_PIPPENGER_K,
 207   ECC_PIPPENGER_C,
 208
 209   ECC_ADD_JJA_ITCH (ECC_LIMB_SIZE),
 210   ECC_ADD_JJJ_ITCH (ECC_LIMB_SIZE),
 211   ECC_DUP_JJ_ITCH (ECC_LIMB_SIZE),
 212   ECC_MUL_A_ITCH (ECC_LIMB_SIZE),
 213   ECC_MUL_G_ITCH (ECC_LIMB_SIZE),
 214   ECC_J_TO_A_ITCH(ECC_LIMB_SIZE, ECC_SECP521R1_INV_ITCH),
 215
 216   ecc_add_jja,
 217   ecc_add_jjj,
 218   ecc_dup_jj,
 219   ecc_mul_a,
 220   ecc_mul_g,
 221   ecc_j_to_a,
 222
 223   ecc_b,
 224   ecc_unit,
 225   ecc_table
 226 };
 227
 228 const struct ecc_curve *nettle_get_secp_521r1(void)
 229 {
 230   return &_nettle_secp_521r1;
 231 }