src/third_party/boringssl/src/crypto/ec/internal.h

   1 /* Originally written by Bodo Moeller for the OpenSSL project.
   2  * ====================================================================
   3  * Copyright (c) 1998-2005 The OpenSSL Project.  All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  *
   9  * 1. Redistributions of source code must retain the above copyright
  10  *    notice, this list of conditions and the following disclaimer.
  11  *
  12  * 2. Redistributions in binary form must reproduce the above copyright
  13  *    notice, this list of conditions and the following disclaimer in
  14  *    the documentation and/or other materials provided with the
  15  *    distribution.
  16  *
  17  * 3. All advertising materials mentioning features or use of this
  18  *    software must display the following acknowledgment:
  19  *    "This product includes software developed by the OpenSSL Project
  20  *    for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
  21  *
  22  * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
  23  *    endorse or promote products derived from this software without
  24  *    prior written permission. For written permission, please contact
  25  *    openssl-core@openssl.org.
  26  *
  27  * 5. Products derived from this software may not be called "OpenSSL"
  28  *    nor may "OpenSSL" appear in their names without prior written
  29  *    permission of the OpenSSL Project.
  30  *
  31  * 6. Redistributions of any form whatsoever must retain the following
  32  *    acknowledgment:
  33  *    "This product includes software developed by the OpenSSL Project
  34  *    for use in the OpenSSL Toolkit (http://www.openssl.org/)"
  35  *
  36  * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
  37  * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  38  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  39  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OpenSSL PROJECT OR
  40  * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  41  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  42  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  43  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  44  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
  45  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  46  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
  47  * OF THE POSSIBILITY OF SUCH DAMAGE.
  48  * ====================================================================
  49  *
  50  * This product includes cryptographic software written by Eric Young
  51  * (eay@cryptsoft.com).  This product includes software written by Tim
  52  * Hudson (tjh@cryptsoft.com).
  53  *
  54  */
  55 /* ====================================================================
  56  * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED.
  57  *
  58  * Portions of the attached software ("Contribution") are developed by
  59  * SUN MICROSYSTEMS, INC., and are contributed to the OpenSSL project.
  60  *
  61  * The Contribution is licensed pursuant to the OpenSSL open source
  62  * license provided above.
  63  *
  64  * The elliptic curve binary polynomial software is originally written by
  65  * Sheueling Chang Shantz and Douglas Stebila of Sun Microsystems
  66  * Laboratories. */
  67
  68 #ifndef OPENSSL_HEADER_EC_INTERNAL_H
  69 #define OPENSSL_HEADER_EC_INTERNAL_H
  70
  71 #include <openssl/base.h>
  72
  73 #include <openssl/bn.h>
  74 #include <openssl/ex_data.h>
  75
  76 #if defined(__cplusplus)
  77 extern "C" {
  78 #endif
  79
  80
  81 /* Use default functions for poin2oct, oct2point and compressed coordinates */
  82 #define EC_FLAGS_DEFAULT_OCT 0x1
  83
  84 typedef struct ec_method_st EC_METHOD;
  85
  86 struct ec_method_st {
  87   /* Various method flags */
  88   int flags;
  89
  90   /* used by EC_GROUP_new, EC_GROUP_free, EC_GROUP_clear_free, EC_GROUP_copy: */
  91   int (*group_init)(EC_GROUP *);
  92   void (*group_finish)(EC_GROUP *);
  93   void (*group_clear_finish)(EC_GROUP *);
  94   int (*group_copy)(EC_GROUP *, const EC_GROUP *);
  95
  96   /* used by EC_GROUP_set_curve_GFp, EC_GROUP_get_curve_GFp, */
  97   /* EC_GROUP_set_curve_GF2m, and EC_GROUP_get_curve_GF2m: */
  98   int (*group_set_curve)(EC_GROUP *, const BIGNUM *p, const BIGNUM *a,
  99                          const BIGNUM *b, BN_CTX *);
 100   int (*group_get_curve)(const EC_GROUP *, BIGNUM *p, BIGNUM *a, BIGNUM *b,
 101                          BN_CTX *);
 102
 103   /* used by EC_GROUP_get_degree: */
 104   int (*group_get_degree)(const EC_GROUP *);
 105
 106   /* used by EC_GROUP_check: */
 107   int (*group_check_discriminant)(const EC_GROUP *, BN_CTX *);
 108
 109   /* used by EC_POINT_new, EC_POINT_free, EC_POINT_clear_free, EC_POINT_copy: */
 110   int (*point_init)(EC_POINT *);
 111   void (*point_finish)(EC_POINT *);
 112   void (*point_clear_finish)(EC_POINT *);
 113   int (*point_copy)(EC_POINT *, const EC_POINT *);
 114
 115   /* used by EC_POINT_set_to_infinity,
 116    * EC_POINT_set_Jprojective_coordinates_GFp,
 117    * EC_POINT_get_Jprojective_coordinates_GFp,
 118    * EC_POINT_set_affine_coordinates_GFp,     ..._GF2m,
 119    * EC_POINT_get_affine_coordinates_GFp,     ..._GF2m,
 120    * EC_POINT_set_compressed_coordinates_GFp, ..._GF2m:
 121    */
 122   int (*point_set_to_infinity)(const EC_GROUP *, EC_POINT *);
 123   int (*point_set_Jprojective_coordinates_GFp)(const EC_GROUP *, EC_POINT *,
 124                                                const BIGNUM *x, const BIGNUM *y,
 125                                                const BIGNUM *z, BN_CTX *);
 126   int (*point_get_Jprojective_coordinates_GFp)(const EC_GROUP *,
 127                                                const EC_POINT *, BIGNUM *x,
 128                                                BIGNUM *y, BIGNUM *z, BN_CTX *);
 129   int (*point_set_affine_coordinates)(const EC_GROUP *, EC_POINT *,
 130                                       const BIGNUM *x, const BIGNUM *y,
 131                                       BN_CTX *);
 132   int (*point_get_affine_coordinates)(const EC_GROUP *, const EC_POINT *,
 133                                       BIGNUM *x, BIGNUM *y, BN_CTX *);
 134   int (*point_set_compressed_coordinates)(const EC_GROUP *, EC_POINT *,
 135                                           const BIGNUM *x, int y_bit, BN_CTX *);
 136
 137   /* used by EC_POINT_point2oct, EC_POINT_oct2point: */
 138   size_t (*point2oct)(const EC_GROUP *, const EC_POINT *,
 139                       point_conversion_form_t form, unsigned char *buf,
 140                       size_t len, BN_CTX *);
 141   int (*oct2point)(const EC_GROUP *, EC_POINT *, const unsigned char *buf,
 142                    size_t len, BN_CTX *);
 143
 144   /* used by EC_POINT_add, EC_POINT_dbl, ECP_POINT_invert: */
 145   int (*add)(const EC_GROUP *, EC_POINT *r, const EC_POINT *a,
 146              const EC_POINT *b, BN_CTX *);
 147   int (*dbl)(const EC_GROUP *, EC_POINT *r, const EC_POINT *a, BN_CTX *);
 148   int (*invert)(const EC_GROUP *, EC_POINT *, BN_CTX *);
 149
 150   /* used by EC_POINT_is_at_infinity, EC_POINT_is_on_curve, EC_POINT_cmp: */
 151   int (*is_at_infinity)(const EC_GROUP *, const EC_POINT *);
 152   int (*is_on_curve)(const EC_GROUP *, const EC_POINT *, BN_CTX *);
 153   int (*point_cmp)(const EC_GROUP *, const EC_POINT *a, const EC_POINT *b,
 154                    BN_CTX *);
 155
 156   /* used by EC_POINT_make_affine, EC_POINTs_make_affine: */
 157   int (*make_affine)(const EC_GROUP *, EC_POINT *, BN_CTX *);
 158   int (*points_make_affine)(const EC_GROUP *, size_t num, EC_POINT * [],
 159                             BN_CTX *);
 160
 161   /* used by EC_POINTs_mul, EC_POINT_mul, EC_POINT_precompute_mult,
 162    * EC_POINT_have_precompute_mult
 163    * (default implementations are used if the 'mul' pointer is 0): */
 164   int (*mul)(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar,
 165              size_t num, const EC_POINT *points[], const BIGNUM *scalars[],
 166              BN_CTX *);
 167   int (*precompute_mult)(EC_GROUP *group, BN_CTX *);
 168   int (*have_precompute_mult)(const EC_GROUP *group);
 169
 170
 171   /* internal functions */
 172
 173   /* 'field_mul', 'field_sqr', and 'field_div' can be used by 'add' and 'dbl'
 174    * so that the same implementations of point operations can be used with
 175    * different optimized implementations of expensive field operations: */
 176   int (*field_mul)(const EC_GROUP *, BIGNUM *r, const BIGNUM *a,
 177                    const BIGNUM *b, BN_CTX *);
 178   int (*field_sqr)(const EC_GROUP *, BIGNUM *r, const BIGNUM *a, BN_CTX *);
 179   int (*field_div)(const EC_GROUP *, BIGNUM *r, const BIGNUM *a,
 180                    const BIGNUM *b, BN_CTX *);
 181
 182   int (*field_encode)(const EC_GROUP *, BIGNUM *r, const BIGNUM *a,
 183                       BN_CTX *); /* e.g. to Montgomery */
 184   int (*field_decode)(const EC_GROUP *, BIGNUM *r, const BIGNUM *a,
 185                       BN_CTX *); /* e.g. from Montgomery */
 186   int (*field_set_to_one)(const EC_GROUP *, BIGNUM *r, BN_CTX *);
 187 } /* EC_METHOD */;
 188
 189 const EC_METHOD* EC_GFp_mont_method(void);
 190
 191 struct ec_pre_comp_st;
 192 void ec_pre_comp_free(struct ec_pre_comp_st *pre_comp);
 193 void *ec_pre_comp_dup(struct ec_pre_comp_st *pre_comp);
 194
 195 struct ec_group_st {
 196   const EC_METHOD *meth;
 197
 198   EC_POINT *generator; /* optional */
 199   BIGNUM order, cofactor;
 200
 201   int curve_name; /* optional NID for named curve */
 202   point_conversion_form_t asn1_form;
 203
 204   struct ec_pre_comp_st *pre_comp;
 205
 206   /* The following members are handled by the method functions,
 207    * even if they appear generic */
 208
 209   BIGNUM field; /* Field specification.
 210                  * For curves over GF(p), this is the modulus;
 211                  * for curves over GF(2^m), this is the
 212                  * irreducible polynomial defining the field. */
 213
 214   int poly[6]; /* Field specification for curves over GF(2^m).
 215                 * The irreducible f(t) is then of the form:
 216                 *     t^poly[0] + t^poly[1] + ... + t^poly[k]
 217                 * where m = poly[0] > poly[1] > ... > poly[k] = 0.
 218                 * The array is terminated with poly[k+1]=-1.
 219                 * All elliptic curve irreducibles have at most 5
 220                 * non-zero terms. */
 221
 222   BIGNUM a, b; /* Curve coefficients.
 223                 * (Here the assumption is that BIGNUMs can be used
 224                 * or abused for all kinds of fields, not just GF(p).)
 225                 * For characteristic  > 3,  the curve is defined
 226                 * by a Weierstrass equation of the form
 227                 *     y^2 = x^3 + a*x + b.
 228                 * For characteristic  2,  the curve is defined by
 229                 * an equation of the form
 230                 *     y^2 + x*y = x^3 + a*x^2 + b. */
 231
 232   int a_is_minus3; /* enable optimized point arithmetics for special case */
 233
 234   void *field_data1; /* method-specific (e.g., Montgomery structure) */
 235   void *field_data2; /* method-specific */
 236   int (*field_mod_func)(BIGNUM *, const BIGNUM *, const BIGNUM *,
 237                         BN_CTX *); /* method-specific */
 238 } /* EC_GROUP */;
 239
 240 struct ec_point_st {
 241   const EC_METHOD *meth;
 242
 243   /* All members except 'meth' are handled by the method functions,
 244    * even if they appear generic */
 245
 246   BIGNUM X;
 247   BIGNUM Y;
 248   BIGNUM Z; /* Jacobian projective coordinates:
 249              * (X, Y, Z)  represents  (X/Z^2, Y/Z^3)  if  Z != 0 */
 250   int Z_is_one; /* enable optimized point arithmetics for special case */
 251 } /* EC_POINT */;
 252
 253 EC_GROUP *ec_group_new(const EC_METHOD *meth);
 254
 255 int ec_wNAF_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar,
 256                 size_t num, const EC_POINT *points[], const BIGNUM *scalars[],
 257                 BN_CTX *);
 258 int ec_wNAF_precompute_mult(EC_GROUP *group, BN_CTX *);
 259 int ec_wNAF_have_precompute_mult(const EC_GROUP *group);
 260
 261 /* method functions in simple.c */
 262 int ec_GFp_simple_group_init(EC_GROUP *);
 263 void ec_GFp_simple_group_finish(EC_GROUP *);
 264 void ec_GFp_simple_group_clear_finish(EC_GROUP *);
 265 int ec_GFp_simple_group_copy(EC_GROUP *, const EC_GROUP *);
 266 int ec_GFp_simple_group_set_curve(EC_GROUP *, const BIGNUM *p, const BIGNUM *a,
 267                                   const BIGNUM *b, BN_CTX *);
 268 int ec_GFp_simple_group_get_curve(const EC_GROUP *, BIGNUM *p, BIGNUM *a,
 269                                   BIGNUM *b, BN_CTX *);
 270 int ec_GFp_simple_group_get_degree(const EC_GROUP *);
 271 int ec_GFp_simple_group_check_discriminant(const EC_GROUP *, BN_CTX *);
 272 int ec_GFp_simple_point_init(EC_POINT *);
 273 void ec_GFp_simple_point_finish(EC_POINT *);
 274 void ec_GFp_simple_point_clear_finish(EC_POINT *);
 275 int ec_GFp_simple_point_copy(EC_POINT *, const EC_POINT *);
 276 int ec_GFp_simple_point_set_to_infinity(const EC_GROUP *, EC_POINT *);
 277 int ec_GFp_simple_set_Jprojective_coordinates_GFp(const EC_GROUP *, EC_POINT *,
 278                                                   const BIGNUM *x,
 279                                                   const BIGNUM *y,
 280                                                   const BIGNUM *z, BN_CTX *);
 281 int ec_GFp_simple_get_Jprojective_coordinates_GFp(const EC_GROUP *,
 282                                                   const EC_POINT *, BIGNUM *x,
 283                                                   BIGNUM *y, BIGNUM *z,
 284                                                   BN_CTX *);
 285 int ec_GFp_simple_point_set_affine_coordinates(const EC_GROUP *, EC_POINT *,
 286                                                const BIGNUM *x, const BIGNUM *y,
 287                                                BN_CTX *);
 288 int ec_GFp_simple_point_get_affine_coordinates(const EC_GROUP *,
 289                                                const EC_POINT *, BIGNUM *x,
 290                                                BIGNUM *y, BN_CTX *);
 291 int ec_GFp_simple_set_compressed_coordinates(const EC_GROUP *, EC_POINT *,
 292                                              const BIGNUM *x, int y_bit,
 293                                              BN_CTX *);
 294 int ec_GFp_simple_add(const EC_GROUP *, EC_POINT *r, const EC_POINT *a,
 295                       const EC_POINT *b, BN_CTX *);
 296 int ec_GFp_simple_dbl(const EC_GROUP *, EC_POINT *r, const EC_POINT *a,
 297                       BN_CTX *);
 298 int ec_GFp_simple_invert(const EC_GROUP *, EC_POINT *, BN_CTX *);
 299 int ec_GFp_simple_is_at_infinity(const EC_GROUP *, const EC_POINT *);
 300 int ec_GFp_simple_is_on_curve(const EC_GROUP *, const EC_POINT *, BN_CTX *);
 301 int ec_GFp_simple_cmp(const EC_GROUP *, const EC_POINT *a, const EC_POINT *b,
 302                       BN_CTX *);
 303 int ec_GFp_simple_make_affine(const EC_GROUP *, EC_POINT *, BN_CTX *);
 304 int ec_GFp_simple_points_make_affine(const EC_GROUP *, size_t num,
 305                                      EC_POINT * [], BN_CTX *);
 306 int ec_GFp_simple_field_mul(const EC_GROUP *, BIGNUM *r, const BIGNUM *a,
 307                             const BIGNUM *b, BN_CTX *);
 308 int ec_GFp_simple_field_sqr(const EC_GROUP *, BIGNUM *r, const BIGNUM *a,
 309                             BN_CTX *);
 310
 311 /* method functions in montgomery.c */
 312 int ec_GFp_mont_group_init(EC_GROUP *);
 313 int ec_GFp_mont_group_set_curve(EC_GROUP *, const BIGNUM *p, const BIGNUM *a,
 314                                 const BIGNUM *b, BN_CTX *);
 315 void ec_GFp_mont_group_finish(EC_GROUP *);
 316 void ec_GFp_mont_group_clear_finish(EC_GROUP *);
 317 int ec_GFp_mont_group_copy(EC_GROUP *, const EC_GROUP *);
 318 int ec_GFp_mont_field_mul(const EC_GROUP *, BIGNUM *r, const BIGNUM *a,
 319                           const BIGNUM *b, BN_CTX *);
 320 int ec_GFp_mont_field_sqr(const EC_GROUP *, BIGNUM *r, const BIGNUM *a,
 321                           BN_CTX *);
 322 int ec_GFp_mont_field_encode(const EC_GROUP *, BIGNUM *r, const BIGNUM *a,
 323                              BN_CTX *);
 324 int ec_GFp_mont_field_decode(const EC_GROUP *, BIGNUM *r, const BIGNUM *a,
 325                              BN_CTX *);
 326 int ec_GFp_mont_field_set_to_one(const EC_GROUP *, BIGNUM *r, BN_CTX *);
 327
 328 int ec_point_set_Jprojective_coordinates_GFp(const EC_GROUP *group,
 329                                              EC_POINT *point, const BIGNUM *x,
 330                                              const BIGNUM *y, const BIGNUM *z,
 331                                              BN_CTX *ctx);
 332
 333 struct ec_key_st {
 334   int version;
 335
 336   EC_GROUP *group;
 337
 338   EC_POINT *pub_key;
 339   BIGNUM *priv_key;
 340
 341   unsigned int enc_flag;
 342   point_conversion_form_t conv_form;
 343
 344   int references;
 345   int flags;
 346
 347   ECDSA_METHOD *ecdsa_meth;
 348
 349   CRYPTO_EX_DATA ex_data;
 350 } /* EC_KEY */;
 351
 352 /* curve_data contains data about a built-in elliptic curve. */
 353 struct curve_data {
 354   /* comment is a human-readable string describing the curve. */
 355   const char *comment;
 356   /* param_len is the number of bytes needed to store a field element. */
 357   uint8_t param_len;
 358   /* cofactor is the cofactor of the group (i.e. the number of elements in the
 359    * group divided by the size of the main subgroup. */
 360   uint8_t cofactor; /* promoted to BN_ULONG */
 361   /* data points to an array of 6*|param_len| bytes which hold the field
 362    * elements of the following (in big-endian order): prime, a, b, generator x,
 363    * generator y, order. */
 364   const uint8_t data[];
 365 };
 366
 367 struct built_in_curve {
 368   int nid;
 369   const struct curve_data *data;
 370   const EC_METHOD *(*method)(void);
 371 };
 372
 373 /* OPENSSL_built_in_curves is terminated with an entry where |nid| is
 374  * |NID_undef|. */
 375 extern const struct built_in_curve OPENSSL_built_in_curves[];
 376
 377 #if defined(__cplusplus)
 378 }  /* extern C */
 379 #endif
 380
 381 #endif  /* OPENSSL_HEADER_EC_INTERNAL_H */