lib/nettle/ecc.h

   1 /*
   2  * Copyright (C) 2011-2012 Free Software Foundation, Inc.
   3  *
   4  * This file is part of GNUTLS.
   5  *
   6  * The GNUTLS library is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU Lesser General Public License
   8  * as published by the Free Software Foundation; either version 3 of
   9  * the License, or (at your option) any later version.
  10  *
  11  * This library is distributed in the hope that it will be useful, but
  12  * WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14  * Lesser General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU Lesser General Public License
  17  * along with this program.  If not, see <http://www.gnu.org/licenses/>
  18  *
  19  */
  20
  21 #include <gmp.h>
  22 #include <nettle/nettle-types.h>
  23 #include <nettle/dsa.h>
  24 #include <nettle/bignum.h>
  25 #include <gnutls_int.h>
  26
  27 /* assume y^2 = x^3 - 3x + b
  28  * instead of the generic y^2 = x^3 + ax + b
  29  *
  30  * (XXX: the generic case has been tested only
  31  *  with the SECG curves.)
  32  */
  33 #define ECC_SECP_CURVES_ONLY
  34
  35 #define PK_PRIVATE 1
  36 #define PK_PUBLIC 2
  37
  38 /* ---- ECC Routines ---- */
  39 /* size of our temp buffers for exported keys */
  40 #define ECC_BUF_SIZE 512
  41
  42 /* max private key size */
  43 #define ECC_MAXSIZE  66
  44
  45 /* wMNAF window size */
  46 #define WMNAF_WINSIZE 4
  47
  48 /* length of a single array of precomputed values for wMNAF
  49  * we have two such arrays for positive and negative multipliers */
  50 #define WMNAF_PRECOMPUTED_LENGTH (1 << (WMNAF_WINSIZE - 1))
  51
  52 /** Structure defines a NIST GF(p) curve */
  53 typedef struct {
  54    /** The size of the curve in octets */
  55    int size;
  56
  57    /** name of curve */
  58    const char *name;
  59
  60    /** The prime that defines the field the curve is in (encoded in hex) */
  61    const char *prime;
  62
  63    /** The fields A param (hex) */
  64    const char *A;
  65
  66    /** The fields B param (hex) */
  67    const char *B;
  68
  69    /** The order of the curve (hex) */
  70    const char *order;
  71
  72    /** The x co-ordinate of the base point on the curve (hex) */
  73    const char *Gx;
  74
  75    /** The y co-ordinate of the base point on the curve (hex) */
  76    const char *Gy;
  77 } ecc_set_type;
  78
  79 /** A point on a ECC curve, stored in Jacbobian format such that (x,y,z) => (x/z^2, y/z^3, 1) when interpretted as affine */
  80 typedef struct {
  81     /** The x co-ordinate */
  82     mpz_t x;
  83
  84     /** The y co-ordinate */
  85     mpz_t y;
  86
  87     /** The z co-ordinate */
  88     mpz_t z;
  89 } ecc_point;
  90
  91 /** An ECC key */
  92 typedef struct {
  93     /** Type of key, PK_PRIVATE or PK_PUBLIC */
  94     int type;
  95
  96     mpz_t prime;
  97     mpz_t order;
  98     mpz_t A;
  99     mpz_t B;
 100     mpz_t Gx;
 101     mpz_t Gy;
 102
 103     /** The public key */
 104     ecc_point pubkey;
 105
 106     /** The private key */
 107     mpz_t k;
 108 } ecc_key;
 109
 110 void ecc_sizes(int *low, int *high);
 111 int  ecc_get_size(ecc_key *key);
 112
 113 int ecc_make_key(void *random_ctx, nettle_random_func random, ecc_key *key, const ecc_set_type *dp, gnutls_ecc_curve_t id);
 114 int ecc_make_key_ex(void *random_ctx, nettle_random_func random, ecc_key *key, mpz_t prime, mpz_t order, mpz_t A, mpz_t B, mpz_t Gx, mpz_t Gy, gnutls_ecc_curve_t id, int timing_res);
 115 void ecc_free(ecc_key *key);
 116
 117 int  ecc_shared_secret(ecc_key *private_key, ecc_key *public_key,
 118                        unsigned char *out, unsigned long *outlen);
 119
 120 int ecc_sign_hash(const unsigned char *in,  unsigned long inlen,
 121                         struct dsa_signature *signature,
 122                         void *random_ctx, nettle_random_func random,
 123                         ecc_key *key, gnutls_ecc_curve_t id);
 124
 125 int  ecc_verify_hash(struct dsa_signature * signature,
 126                      const unsigned char *hash, unsigned long hashlen,
 127                      int *stat, ecc_key *key, gnutls_ecc_curve_t id);
 128
 129 /* low level functions */
 130 ecc_point *ecc_new_point(void);
 131 void       ecc_del_point(ecc_point *p);
 132
 133 /* point ops (mp == montgomery digit) */
 134 /* R = -P */
 135 int ecc_projective_negate_point(ecc_point *P, ecc_point *R, mpz_t modulus);
 136
 137 /* R = 2P */
 138 int ecc_projective_dbl_point(ecc_point *P, ecc_point *R, mpz_t a,  mpz_t modulus);
 139
 140 /* R = P + Q */
 141 int ecc_projective_add_point(ecc_point *P, ecc_point *Q, ecc_point *R, mpz_t A, mpz_t modulus);
 142 int ecc_projective_madd (ecc_point* P, ecc_point* Q, ecc_point* R, mpz_t a, mpz_t modulus);
 143
 144 /* R = kG */
 145 /* wMNAF-based mulmod */
 146 signed char* ecc_wMNAF(mpz_t x, size_t *ret_len);
 147 int ecc_mulmod(mpz_t k, ecc_point *G, ecc_point *R, mpz_t a, mpz_t modulus, int map);
 148
 149 /* cache-enabled wMNAF-based mulmod */
 150 int  ecc_wmnaf_cache_init(void);
 151 void ecc_wmnaf_cache_free(void);
 152 int ecc_mulmod_cached (mpz_t k, gnutls_ecc_curve_t id, ecc_point * R, mpz_t a, mpz_t modulus, int map);
 153 int ecc_mulmod_cached_timing (mpz_t k, gnutls_ecc_curve_t id, ecc_point * R, mpz_t a, mpz_t modulus, int map);
 154 int ecc_mulmod_cached_lookup (mpz_t k, ecc_point *G, ecc_point *R, mpz_t a, mpz_t modulus, int map);
 155
 156 /* check if the given point is neutral point */
 157 int ecc_projective_isneutral(ecc_point *P, mpz_t modulus);
 158
 159 /* map P to affine from projective */
 160 int ecc_map(ecc_point *P, mpz_t modulus);
 161
 162 /* check whether a point lies on the curve */
 163 int ecc_projective_check_point (ecc_point * P, mpz_t b, mpz_t modulus);
 164
 165 /* helper functions */
 166 int mp_init_multi(mpz_t *a, ...);
 167 void mp_clear_multi(mpz_t *a, ...);
 168