ecc-internal.h

   1 /* ecc-internal.h
   2
   3    Copyright (C) 2013, 2014 Niels Möller
   4
   5    This file is part of GNU Nettle.
   6
   7    GNU Nettle is free software: you can redistribute it and/or
   8    modify it under the terms of either:
   9
  10      * the GNU Lesser General Public License as published by the Free
  11        Software Foundation; either version 3 of the License, or (at your
  12        option) any later version.
  13
  14    or
  15
  16      * the GNU General Public License as published by the Free
  17        Software Foundation; either version 2 of the License, or (at your
  18        option) any later version.
  19
  20    or both in parallel, as here.
  21
  22    GNU Nettle is distributed in the hope that it will be useful,
  23    but WITHOUT ANY WARRANTY; without even the implied warranty of
  24    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  25    General Public License for more details.
  26
  27    You should have received copies of the GNU General Public License and
  28    the GNU Lesser General Public License along with this program.  If
  29    not, see http://www.gnu.org/licenses/.
  30 */
  31
  32 /* Development of Nettle's ECC support was funded by the .SE Internet Fund. */
  33
  34 #ifndef NETTLE_ECC_INTERNAL_H_INCLUDED
  35 #define NETTLE_ECC_INTERNAL_H_INCLUDED
  36
  37 #include "nettle-types.h"
  38 #include "bignum.h"
  39 #include "ecc-curve.h"
  40 #include "gmp-glue.h"
  41
  42 /* Name mangling */
  43 #define ecc_pp1_redc _nettle_ecc_pp1_redc
  44 #define ecc_pm1_redc _nettle_ecc_pm1_redc
  45 #define ecc_mod_add _nettle_ecc_mod_add
  46 #define ecc_mod_sub _nettle_ecc_mod_sub
  47 #define ecc_mod_mul_1 _nettle_ecc_mod_mul_1
  48 #define ecc_mod_addmul_1 _nettle_ecc_mod_addmul_1
  49 #define ecc_mod_submul_1 _nettle_ecc_mod_submul_1
  50 #define ecc_mod_mul _nettle_ecc_mod_mul
  51 #define ecc_mod_sqr _nettle_ecc_mod_sqr
  52 #define ecc_mod_random _nettle_ecc_mod_random
  53 #define ecc_mod _nettle_ecc_mod
  54 #define ecc_mod_inv _nettle_ecc_mod_inv
  55 #define ecc_hash _nettle_ecc_hash
  56 #define ecc_a_to_j _nettle_ecc_a_to_j
  57 #define ecc_j_to_a _nettle_ecc_j_to_a
  58 #define ecc_eh_to_a _nettle_ecc_eh_to_a
  59 #define ecc_dup_jj _nettle_ecc_dup_jj
  60 #define ecc_add_jja _nettle_ecc_add_jja
  61 #define ecc_add_jjj _nettle_ecc_add_jjj
  62 #define ecc_dup_eh _nettle_ecc_dup_eh
  63 #define ecc_add_eh _nettle_ecc_add_eh
  64 #define ecc_add_ehh _nettle_ecc_add_ehh
  65 #define ecc_mul_g _nettle_ecc_mul_g
  66 #define ecc_mul_a _nettle_ecc_mul_a
  67 #define ecc_mul_g_eh _nettle_ecc_mul_g_eh
  68 #define ecc_mul_a_eh _nettle_ecc_mul_a_eh
  69 #define cnd_copy _nettle_cnd_copy
  70 #define sec_add_1 _nettle_sec_add_1
  71 #define sec_sub_1 _nettle_sec_sub_1
  72 #define sec_tabselect _nettle_sec_tabselect
  73 #define sec_modinv _nettle_sec_modinv
  74 #define curve25519_eh_to_x _nettle_curve25519_eh_to_x
  75
  76 /* Keep this structure internal for now. It's misnamed (since it's
  77    really implementing the equivalent twisted Edwards curve, with
  78    different coordinates). And we're not quite ready to provide
  79    general ecc operations over an arbitrary type of curve. */
  80 extern const struct ecc_curve _nettle_curve25519;
  81
  82 #define ECC_MAX_SIZE ((521 + GMP_NUMB_BITS - 1) / GMP_NUMB_BITS)
  83
  84 /* Window size for ecc_mul_a. Using 4 bits seems like a good choice,
  85    for both Intel x86_64 and ARM Cortex A9. For the larger curves, of
  86    384 and 521 bits, we could improve speed by a few percent if we go
  87    up to 5 bits, but I don't think that's worth doubling the
  88    storage. */
  89 #define ECC_MUL_A_WBITS 4
  90 /* And for ecc_mul_a_eh */
  91 #define ECC_MUL_A_EH_WBITS 4
  92
  93 struct ecc_modulo;
  94
  95 /* Reduces from 2*ecc->size to ecc->size. */
  96 /* Required to return a result < 2q. This property is inherited by
  97    mod_mul and mod_sqr. */
  98 typedef void ecc_mod_func (const struct ecc_modulo *m, mp_limb_t *rp);
  99
 100 typedef void ecc_mod_inv_func (const struct ecc_modulo *m,
 101                                mp_limb_t *vp, const mp_limb_t *ap,
 102                                mp_limb_t *scratch);
 103
 104 /* Computes the square root of (u/v) (mod p) */
 105 typedef int ecc_mod_sqrt_func (const struct ecc_modulo *m,
 106                                mp_limb_t *rp,
 107                                const mp_limb_t *up, const mp_limb_t *vp,
 108                                mp_limb_t *scratch);
 109
 110 typedef void ecc_add_func (const struct ecc_curve *ecc,
 111                            mp_limb_t *r,
 112                            const mp_limb_t *p, const mp_limb_t *q,
 113                            mp_limb_t *scratch);
 114
 115 typedef void ecc_mul_g_func (const struct ecc_curve *ecc, mp_limb_t *r,
 116                              const mp_limb_t *np, mp_limb_t *scratch);
 117
 118 typedef void ecc_mul_func (const struct ecc_curve *ecc,
 119                            mp_limb_t *r,
 120                            const mp_limb_t *np, const mp_limb_t *p,
 121                            mp_limb_t *scratch);
 122
 123 typedef void ecc_h_to_a_func (const struct ecc_curve *ecc,
 124                               int flags,
 125                               mp_limb_t *r, const mp_limb_t *p,
 126                               mp_limb_t *scratch);
 127
 128 struct ecc_modulo
 129 {
 130   unsigned short bit_size;
 131   unsigned short size;
 132   unsigned short B_size;
 133   unsigned short redc_size;
 134   unsigned short invert_itch;
 135   unsigned short sqrt_itch;
 136
 137   const mp_limb_t *m;
 138   /* B^size mod m. Expected to have at least 32 leading zeros
 139      (equality for secp_256r1). */
 140   const mp_limb_t *B;
 141   /* 2^{bit_size} - p, same value as above, but shifted. */
 142   const mp_limb_t *B_shifted;
 143   /* m +/- 1, for redc, excluding redc_size low limbs. */
 144   const mp_limb_t *redc_mpm1;
 145   /* (m+1)/2 */
 146   const mp_limb_t *mp1h;
 147
 148   ecc_mod_func *mod;
 149   ecc_mod_func *reduce;
 150   ecc_mod_inv_func *invert;
 151   ecc_mod_sqrt_func *sqrt;
 152 };
 153
 154 /* Represents an elliptic curve of the form
 155
 156      y^2 = x^3 - 3x + b (mod p)
 157 */
 158 struct ecc_curve
 159 {
 160   /* The prime p. */
 161   struct ecc_modulo p;
 162   /* Group order. FIXME: Currently, many fucntions rely on q.size ==
 163      p.size. This has to change for radix-51 implementation of
 164      curve25519 mod p arithmetic. */
 165   struct ecc_modulo q;
 166
 167   unsigned short use_redc;
 168   unsigned short pippenger_k;
 169   unsigned short pippenger_c;
 170
 171   unsigned short add_hhh_itch;
 172   unsigned short mul_itch;
 173   unsigned short mul_g_itch;
 174   unsigned short h_to_a_itch;
 175
 176   ecc_add_func *add_hhh;
 177   ecc_mul_func *mul;
 178   ecc_mul_g_func *mul_g;
 179   ecc_h_to_a_func *h_to_a;
 180
 181   /* Curve constant */
 182   const mp_limb_t *b;
 183   /* Generator, x coordinate followed by y (affine coordinates).
 184      Currently used only by the test suite. */
 185   const mp_limb_t *g;
 186   /* If non-NULL, the constant needed for transformation to the
 187      equivalent Edwards curve. */
 188   const mp_limb_t *edwards_root;
 189
 190   /* For redc, same as B mod p, otherwise 1. */
 191   const mp_limb_t *unit;
 192
 193   /* Tables for multiplying by the generator, size determined by k and
 194      c. The first 2^c entries are defined by
 195
 196        T[  j_0 +   j_1 2 +     ... + j_{c-1} 2^{c-1} ]
 197          = j_0 g + j_1 2^k g + ... + j_{c-1} 2^{k(c-1)} g
 198
 199      The following entries differ by powers of 2^{kc},
 200
 201        T[i] = 2^{kc} T[i-2^c]
 202   */
 203   const mp_limb_t *pippenger_table;
 204 };
 205
 206 /* In-place reduction. */
 207 ecc_mod_func ecc_mod;
 208 ecc_mod_func ecc_pp1_redc;
 209 ecc_mod_func ecc_pm1_redc;
 210
 211 ecc_mod_inv_func ecc_mod_inv;
 212
 213 void
 214 ecc_mod_add (const struct ecc_modulo *m, mp_limb_t *rp,
 215              const mp_limb_t *ap, const mp_limb_t *bp);
 216 void
 217 ecc_mod_sub (const struct ecc_modulo *m, mp_limb_t *rp,
 218              const mp_limb_t *ap, const mp_limb_t *bp);
 219
 220 void
 221 ecc_mod_mul_1 (const struct ecc_modulo *m, mp_limb_t *rp,
 222                const mp_limb_t *ap, const mp_limb_t b);
 223
 224 void
 225 ecc_mod_addmul_1 (const struct ecc_modulo *m, mp_limb_t *rp,
 226                   const mp_limb_t *ap, mp_limb_t b);
 227 void
 228 ecc_mod_submul_1 (const struct ecc_modulo *m, mp_limb_t *rp,
 229                   const mp_limb_t *ap, mp_limb_t b);
 230
 231 /* NOTE: mul and sqr needs 2*ecc->size limbs at rp */
 232 void
 233 ecc_mod_mul (const struct ecc_modulo *m, mp_limb_t *rp,
 234              const mp_limb_t *ap, const mp_limb_t *bp);
 235
 236 void
 237 ecc_mod_sqr (const struct ecc_modulo *m, mp_limb_t *rp,
 238              const mp_limb_t *ap);
 239
 240 #define ecc_modp_add(ecc, r, a, b) \
 241   ecc_mod_add (&(ecc)->p, (r), (a), (b))
 242 #define ecc_modp_sub(ecc, r, a, b) \
 243   ecc_mod_sub (&(ecc)->p, (r), (a), (b))
 244 #define ecc_modp_mul_1(ecc, r, a, b) \
 245   ecc_mod_mul_1 (&(ecc)->p, (r), (a), (b))
 246 #define ecc_modp_addmul_1(ecc, r, a, b) \
 247   ecc_mod_addmul_1 (&(ecc)->p, (r), (a), (b))
 248 #define ecc_modp_submul_1(ecc, r, a, b) \
 249   ecc_mod_submul_1 (&(ecc)->p, (r), (a), (b))
 250 #define ecc_modp_mul(ecc, r, a, b) \
 251   ecc_mod_mul (&(ecc)->p, (r), (a), (b))
 252 #define ecc_modp_sqr(ecc, r, a) \
 253   ecc_mod_sqr (&(ecc)->p, (r), (a))
 254
 255 #define ecc_modq_add(ecc, r, a, b) \
 256   ecc_mod_add (&(ecc)->q, (r), (a), (b))
 257 #define ecc_modq_mul(ecc, r, a, b) \
 258   ecc_mod_mul (&(ecc)->q, (r), (a), (b))
 259
 260 /* mod q operations. */
 261 void
 262 ecc_mod_random (const struct ecc_modulo *m, mp_limb_t *xp,
 263                 void *ctx, nettle_random_func *random, mp_limb_t *scratch);
 264
 265 void
 266 ecc_hash (const struct ecc_modulo *m,
 267           mp_limb_t *hp,
 268           size_t length, const uint8_t *digest);
 269
 270 /* Converts a point P in affine coordinates into a point R in jacobian
 271    coordinates. */
 272 void
 273 ecc_a_to_j (const struct ecc_curve *ecc,
 274             mp_limb_t *r, const mp_limb_t *p);
 275
 276 /* Converts a point P in jacobian coordinates into a point R in affine
 277    coordinates. If op == 1, produce x coordinate only. If op == 2,
 278    produce the x coordiante only, and in also it modulo q. FIXME: For
 279    the public interface, have separate for the three cases, and use
 280    this flag argument only for the internal ecc->h_to_a function. */
 281 void
 282 ecc_j_to_a (const struct ecc_curve *ecc,
 283             int op,
 284             mp_limb_t *r, const mp_limb_t *p,
 285             mp_limb_t *scratch);
 286
 287 /* Converts a point P on an Edwards curve to affine coordinates on
 288    the corresponding Montgomery curve. */
 289 void
 290 ecc_eh_to_a (const struct ecc_curve *ecc,
 291              int op,
 292              mp_limb_t *r, const mp_limb_t *p,
 293              mp_limb_t *scratch);
 294
 295 /* Group operations */
 296
 297 /* Point doubling, with jacobian input and output. Corner cases:
 298    Correctly sets R = 0 (r_Z = 0) if p = 0 or 2p = 0. */
 299 void
 300 ecc_dup_jj (const struct ecc_curve *ecc,
 301             mp_limb_t *r, const mp_limb_t *p,
 302             mp_limb_t *scratch);
 303
 304 /* Point addition, with jacobian output, one jacobian input and one
 305    affine input. Corner cases: Fails for the cases
 306
 307      P = Q != 0                       Duplication of non-zero point
 308      P = 0, Q != 0 or P != 0, Q = 0   One input zero
 309
 310      Correctly gives R = 0 if P = Q = 0 or P = -Q. */
 311 void
 312 ecc_add_jja (const struct ecc_curve *ecc,
 313              mp_limb_t *r, const mp_limb_t *p, const mp_limb_t *q,
 314              mp_limb_t *scratch);
 315
 316 /* Point addition with Jacobian input and output. */
 317 void
 318 ecc_add_jjj (const struct ecc_curve *ecc,
 319              mp_limb_t *r, const mp_limb_t *p, const mp_limb_t *q,
 320              mp_limb_t *scratch);
 321
 322 /* Point doubling on an Edwards curve, with homogeneous
 323    cooordinates. */
 324 void
 325 ecc_dup_eh (const struct ecc_curve *ecc,
 326             mp_limb_t *r, const mp_limb_t *p,
 327             mp_limb_t *scratch);
 328
 329 void
 330 ecc_add_eh (const struct ecc_curve *ecc,
 331             mp_limb_t *r, const mp_limb_t *p, const mp_limb_t *q,
 332             mp_limb_t *scratch);
 333
 334 void
 335 ecc_add_ehh (const struct ecc_curve *ecc,
 336              mp_limb_t *r, const mp_limb_t *p, const mp_limb_t *q,
 337              mp_limb_t *scratch);
 338
 339 /* Computes N * the group generator. N is an array of ecc_size()
 340    limbs. It must be in the range 0 < N < group order, then R != 0,
 341    and the algorithm can work without any intermediate values getting
 342    to zero. */
 343 void
 344 ecc_mul_g (const struct ecc_curve *ecc, mp_limb_t *r,
 345            const mp_limb_t *np, mp_limb_t *scratch);
 346
 347 /* Computes N * P. The scalar N is the same as for ecc_mul_g. P is a
 348    non-zero point on the curve, in affine coordinates. Output R is a
 349    non-zero point, in Jacobian coordinates. */
 350 void
 351 ecc_mul_a (const struct ecc_curve *ecc,
 352            mp_limb_t *r,
 353            const mp_limb_t *np, const mp_limb_t *p,
 354            mp_limb_t *scratch);
 355
 356 void
 357 ecc_mul_g_eh (const struct ecc_curve *ecc, mp_limb_t *r,
 358               const mp_limb_t *np, mp_limb_t *scratch);
 359
 360 void
 361 ecc_mul_a_eh (const struct ecc_curve *ecc,
 362               mp_limb_t *r,
 363               const mp_limb_t *np, const mp_limb_t *p,
 364               mp_limb_t *scratch);
 365
 366 void
 367 cnd_copy (int cnd, mp_limb_t *rp, const mp_limb_t *ap, mp_size_t n);
 368
 369 mp_limb_t
 370 sec_add_1 (mp_limb_t *rp, mp_limb_t *ap, mp_size_t n, mp_limb_t b);
 371
 372 mp_limb_t
 373 sec_sub_1 (mp_limb_t *rp, mp_limb_t *ap, mp_size_t n, mp_limb_t b);
 374
 375 void
 376 sec_tabselect (mp_limb_t *rp, mp_size_t rn,
 377                const mp_limb_t *table, unsigned tn,
 378                unsigned k);
 379
 380 void
 381 curve25519_eh_to_x (mp_limb_t *xp, const mp_limb_t *p,
 382                     mp_limb_t *scratch);
 383
 384 /* Current scratch needs: */
 385 #define ECC_MOD_INV_ITCH(size) (2*(size))
 386 #define ECC_J_TO_A_ITCH(size) (5*(size))
 387 #define ECC_EH_TO_A_ITCH(size, inv) (2*(size)+(inv))
 388 #define ECC_DUP_JJ_ITCH(size) (5*(size))
 389 #define ECC_DUP_EH_ITCH(size) (5*(size))
 390 #define ECC_ADD_JJA_ITCH(size) (6*(size))
 391 #define ECC_ADD_JJJ_ITCH(size) (8*(size))
 392 #define ECC_ADD_EH_ITCH(size) (6*(size))
 393 #define ECC_ADD_EHH_ITCH(size) (7*(size))
 394 #define ECC_MUL_G_ITCH(size) (9*(size))
 395 #define ECC_MUL_G_EH_ITCH(size) (9*(size))
 396 #if ECC_MUL_A_WBITS == 0
 397 #define ECC_MUL_A_ITCH(size) (12*(size))
 398 #else
 399 #define ECC_MUL_A_ITCH(size) \
 400   (((3 << ECC_MUL_A_WBITS) + 11) * (size))
 401 #endif
 402 #if ECC_MUL_A_EH_WBITS == 0
 403 #define ECC_MUL_A_EH_ITCH(size) (13*(size))
 404 #else
 405 #define ECC_MUL_A_EH_ITCH(size) \
 406   (((3 << ECC_MUL_A_EH_WBITS) + 10) * (size))
 407 #endif
 408 #define ECC_ECDSA_SIGN_ITCH(size) (12*(size))
 409 #define ECC_MOD_RANDOM_ITCH(size) (size)
 410 #define ECC_HASH_ITCH(size) (1+(size))
 411
 412 #endif /* NETTLE_ECC_INTERNAL_H_INCLUDED */