ecc-internal.h

   1 /* ecc-internal.h */
   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 #ifndef NETTLE_ECC_INTERNAL_H_INCLUDED
  26 #define NETTLE_ECC_INTERNAL_H_INCLUDED
  27
  28 #include <gmp.h>
  29
  30 #include "nettle-types.h"
  31 #include "ecc-curve.h"
  32 #include "gmp-glue.h"
  33
  34 /* Name mangling */
  35 #define ecc_generic_modp _nettle_ecc_generic_modp
  36 #define ecc_generic_redc _nettle_ecc_generic_redc
  37 #define ecc_generic_modq _nettle_ecc_generic_modq
  38 #define ecc_modp_add _nettle_ecc_modp_add
  39 #define ecc_modp_sub _nettle_ecc_modp_sub
  40 #define ecc_modp_sub_1 _nettle_ecc_modp_sub_1
  41 #define ecc_modp_mul_1 _nettle_ecc_modp_mul_1
  42 #define ecc_modp_addmul_1 _nettle_ecc_modp_addmul_1
  43 #define ecc_modp_submul_1 _nettle_ecc_modp_submul_1
  44 #define ecc_modp_mul _nettle_ecc_modp_mul
  45 #define ecc_modp_sqr _nettle_ecc_modp_sqr
  46 #define ecc_modp_inv _nettle_ecc_modp_inv
  47 #define ecc_modq_mul _nettle_ecc_modq_mul
  48 #define ecc_modq_add _nettle_ecc_modq_add
  49 #define ecc_modq_inv _nettle_ecc_modq_inv
  50 #define ecc_modq_random _nettle_ecc_modq_random
  51 #define ecc_mod _nettle_ecc_mod
  52 #define ecc_hash _nettle_ecc_hash
  53 #define cnd_copy _nettle_cnd_copy
  54 #define sec_add_1 _nettle_sec_add_1
  55 #define sec_sub_1 _nettle_sec_sub_1
  56 #define sec_tabselect _nettle_sec_tabselect
  57 #define sec_modinv _nettle_sec_modinv
  58
  59 #define ECC_MAX_SIZE ((521 + GMP_NUMB_BITS - 1) / GMP_NUMB_BITS)
  60
  61 /* Window size for ecc_mul_a. Using 4 bits seems like a good choice,
  62    for both Intel x86_64 and ARM Cortex A9. For the larger curves, of
  63    384 and 521 bits, we could improve seepd by a few percent if we go
  64    up to 5 bits, but I don't think that's worth doubling the
  65    storage. */
  66 #define ECC_MUL_A_WBITS 4
  67
  68 /* Reduces from 2*ecc->size to ecc->size. */
  69 /* Required to return a result < 2q. This property is inherited by
  70    modp_mul and modp_add. */
  71 typedef void ecc_mod_func (const struct ecc_curve *ecc, mp_limb_t *rp);
  72
  73 /* Represents an elliptic curve of the form
  74
  75      y^2 = x^3 - 3x + b (mod p)
  76 */
  77 struct ecc_curve
  78 {
  79   unsigned short bit_size;
  80   /* Limb size of elements in the base field, size of a point is
  81      2*size in affine coordinates and 3*size in jacobian
  82      coordinates. */
  83   unsigned short size;
  84   unsigned short Bmodp_size;
  85   unsigned short Bmodq_size;
  86   unsigned short use_redc;
  87   /* +k if p+1 has k low zero limbs, -k if p-1 has k low zero
  88      limbs. */
  89   short redc_size;
  90   unsigned short pippenger_k;
  91   unsigned short pippenger_c;
  92
  93   /* The prime p. */
  94   const mp_limb_t *p;
  95   const mp_limb_t *b;
  96   /* Group order. */
  97   const mp_limb_t *q;
  98   /* Generator, x coordinate followed by y (affine coordinates). */
  99   const mp_limb_t *g;
 100   /* Generator with coordinates in Montgomery form. */
 101   const mp_limb_t *redc_g;
 102
 103   ecc_mod_func *modp;
 104   ecc_mod_func *redc;
 105   ecc_mod_func *reduce;
 106   ecc_mod_func *modq;
 107
 108   /* B^size mod p. Expected to have at least 32 leading zeros
 109      (equality for secp_256r1). */
 110   const mp_limb_t *Bmodp;
 111   /* 2^{bit_size} - p, same value as above, but shifted. */
 112   const mp_limb_t *Bmodp_shifted;
 113   /* (p+1)/2 */
 114   const mp_limb_t *pp1h;
 115   /* p +/- 1, for redc, excluding |redc_size| low limbs. */
 116   const mp_limb_t *redc_ppm1;
 117   /* For redc, same as Bmodp, otherwise 1. */
 118   const mp_limb_t *unit;
 119
 120   /* Similarly, B^size mod q */
 121   const mp_limb_t *Bmodq;
 122   /* 2^{bit_size} - q, same value as above, but shifted. */
 123   const mp_limb_t *Bmodq_shifted;
 124   /* (q+1)/2 */
 125   const mp_limb_t *qp1h;
 126
 127   /* Tables for multiplying by the generator, size determined by k and
 128      c. The first 2^c entries are defined by
 129
 130        T[  j_0 +   j_1 2 +     ... + j_{c-1} 2^{c-1} ]
 131          = j_0 g + j_1 2^k g + ... + j_{c-1} 2^{k(c-1)} g
 132
 133      The following entries differ by powers of 2^{kc},
 134
 135        T[i] = 2^{kc} T[i-2^c]
 136   */
 137   const mp_limb_t *pippenger_table;
 138 };
 139
 140 /* In-place reduction. */
 141 ecc_mod_func ecc_generic_modp;
 142 ecc_mod_func ecc_generic_redc;
 143 ecc_mod_func ecc_generic_modq;
 144
 145
 146 void
 147 ecc_modp_add (const struct ecc_curve *ecc, mp_limb_t *rp,
 148               const mp_limb_t *ap, const mp_limb_t *bp);
 149 void
 150 ecc_modp_sub (const struct ecc_curve *ecc, mp_limb_t *rp,
 151               const mp_limb_t *ap, const mp_limb_t *bp);
 152
 153 void
 154 ecc_modp_sub_1 (const struct ecc_curve *ecc, mp_limb_t *rp,
 155                 const mp_limb_t *ap, mp_limb_t b);
 156
 157 void
 158 ecc_modp_mul_1 (const struct ecc_curve *ecc, mp_limb_t *rp,
 159                 const mp_limb_t *ap, const mp_limb_t b);
 160
 161 void
 162 ecc_modp_addmul_1 (const struct ecc_curve *ecc, mp_limb_t *rp,
 163                    const mp_limb_t *ap, mp_limb_t b);
 164 void
 165 ecc_modp_submul_1 (const struct ecc_curve *ecc, mp_limb_t *rp,
 166                    const mp_limb_t *ap, mp_limb_t b);
 167
 168 /* NOTE: mul and sqr needs 2*ecc->size limbs at rp */
 169 void
 170 ecc_modp_mul (const struct ecc_curve *ecc, mp_limb_t *rp,
 171               const mp_limb_t *ap, const mp_limb_t *bp);
 172
 173 void
 174 ecc_modp_sqr (const struct ecc_curve *ecc, mp_limb_t *rp,
 175               const mp_limb_t *ap);
 176
 177 void
 178 ecc_modp_inv (const struct ecc_curve *ecc, mp_limb_t *rp, mp_limb_t *ap,
 179               mp_limb_t *scratch);
 180
 181 /* mod q operations. */
 182 void
 183 ecc_modq_mul (const struct ecc_curve *ecc, mp_limb_t *rp,
 184               const mp_limb_t *ap, const mp_limb_t *bp);
 185 void
 186 ecc_modq_add (const struct ecc_curve *ecc, mp_limb_t *rp,
 187               const mp_limb_t *ap, const mp_limb_t *bp);
 188
 189 void
 190 ecc_modq_inv (const struct ecc_curve *ecc, mp_limb_t *rp, mp_limb_t *ap,
 191               mp_limb_t *scratch);
 192
 193 void
 194 ecc_modq_random (const struct ecc_curve *ecc, mp_limb_t *xp,
 195                  void *ctx, nettle_random_func *random, mp_limb_t *scratch);
 196
 197 void
 198 ecc_mod (mp_limb_t *rp, mp_size_t rn, mp_size_t mn,
 199          const mp_limb_t *bp, mp_size_t bn,
 200          const mp_limb_t *b_shifted, unsigned shift);
 201
 202 void
 203 ecc_hash (const struct ecc_curve *ecc,
 204           mp_limb_t *hp,
 205           unsigned length, const uint8_t *digest);
 206
 207 void
 208 cnd_copy (int cnd, mp_limb_t *rp, const mp_limb_t *ap, mp_size_t n);
 209
 210 mp_limb_t
 211 sec_add_1 (mp_limb_t *rp, mp_limb_t *ap, mp_size_t n, mp_limb_t b);
 212
 213 mp_limb_t
 214 sec_sub_1 (mp_limb_t *rp, mp_limb_t *ap, mp_size_t n, mp_limb_t b);
 215
 216 void
 217 sec_tabselect (mp_limb_t *rp, mp_size_t rn,
 218                const mp_limb_t *table, unsigned tn,
 219                unsigned k);
 220
 221 void
 222 sec_modinv (mp_limb_t *vp, mp_limb_t *ap, mp_size_t n,
 223             const mp_limb_t *mp, const mp_limb_t *mp1h, mp_size_t bit_size,
 224             mp_limb_t *scratch);
 225
 226 /* Current scratch needs: */
 227 #define ECC_MODINV_ITCH(size) (3*(size))
 228 #define ECC_J_TO_A_ITCH(size) (5*(size))
 229 #define ECC_DUP_JA_ITCH(size) (5*(size))
 230 #define ECC_DUP_JJ_ITCH(size) (5*(size))
 231 #define ECC_ADD_JJA_ITCH(size) (6*(size))
 232 #define ECC_ADD_JJJ_ITCH(size) (8*(size))
 233 #define ECC_MUL_G_ITCH(size) (9*(size))
 234 #if ECC_MUL_A_WBITS == 0
 235 #define ECC_MUL_A_ITCH(size) (12*(size))
 236 #else
 237 #define ECC_MUL_A_ITCH(size) \
 238   (((3 << ECC_MUL_A_WBITS) + 11) * (size))
 239 #endif
 240 #define ECC_ECDSA_SIGN_ITCH(size) (12*(size))
 241 #define ECC_ECDSA_VERIFY_ITCH(size) \
 242   (6*(size) + ECC_MUL_A_ITCH ((size)))
 243 #define ECC_MODQ_RANDOM_ITCH(size) (size)
 244 #define ECC_HASH_ITCH(size) (1+(size))
 245
 246 #endif /* NETTLE_ECC_INTERNAL_H_INCLUDED */