1/* crypto/ec/ec_lcl.h */ 2/* ==================================================================== 3 * Copyright (c) 1998-2001 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 57#include <stdlib.h> 58 59#include <openssl/ec.h> 60 61 62/* Structure details are not part of the exported interface, 63 * so all this may change in future versions. */ 64 65struct ec_method_st { 66 /* used by EC_GROUP_new, EC_GROUP_free, EC_GROUP_clear_free, EC_GROUP_copy: */ 67 int (*group_init)(EC_GROUP *); 68 void (*group_finish)(EC_GROUP *); 69 void (*group_clear_finish)(EC_GROUP *); 70 int (*group_copy)(EC_GROUP *, const EC_GROUP *); 71 72 /* used by EC_GROUP_set_curve_GFp and EC_GROUP_get_curve_GFp: */ 73 int (*group_set_curve_GFp)(EC_GROUP *, const BIGNUM *p, const BIGNUM *a, const BIGNUM *b, BN_CTX *); 74 int (*group_get_curve_GFp)(const EC_GROUP *, BIGNUM *p, BIGNUM *a, BIGNUM *b, BN_CTX *); 75 76 /* used by EC_GROUP_set_generator, EC_GROUP_get0_generator, 77 * EC_GROUP_get_order, EC_GROUP_get_cofactor: 78 */ 79 int (*group_set_generator)(EC_GROUP *, const EC_POINT *generator, 80 const BIGNUM *order, const BIGNUM *cofactor); 81 EC_POINT *(*group_get0_generator)(const EC_GROUP *); 82 int (*group_get_order)(const EC_GROUP *, BIGNUM *order, BN_CTX *); 83 int (*group_get_cofactor)(const EC_GROUP *, BIGNUM *cofactor, BN_CTX *); 84 85 /* used by EC_POINT_new, EC_POINT_free, EC_POINT_clear_free, EC_POINT_copy: */ 86 int (*point_init)(EC_POINT *); 87 void (*point_finish)(EC_POINT *); 88 void (*point_clear_finish)(EC_POINT *); 89 int (*point_copy)(EC_POINT *, const EC_POINT *); 90 91 /* used by EC_POINT_set_to_infinity, 92 * EC_POINT_set_Jprojective_coordinates_GFp, EC_POINT_get_Jprojective_coordinates_GFp, 93 * EC_POINT_set_affine_coordinates_GFp, EC_POINT_get_affine_coordinates_GFp, 94 * EC_POINT_set_compressed_coordinates_GFp: 95 */ 96 int (*point_set_to_infinity)(const EC_GROUP *, EC_POINT *); 97 int (*point_set_Jprojective_coordinates_GFp)(const EC_GROUP *, EC_POINT *, 98 const BIGNUM *x, const BIGNUM *y, const BIGNUM *z, BN_CTX *); 99 int (*point_get_Jprojective_coordinates_GFp)(const EC_GROUP *, const EC_POINT *, 100 BIGNUM *x, BIGNUM *y, BIGNUM *z, BN_CTX *); 101 int (*point_set_affine_coordinates_GFp)(const EC_GROUP *, EC_POINT *, 102 const BIGNUM *x, const BIGNUM *y, BN_CTX *); 103 int (*point_get_affine_coordinates_GFp)(const EC_GROUP *, const EC_POINT *, 104 BIGNUM *x, BIGNUM *y, BN_CTX *); 105 int (*point_set_compressed_coordinates_GFp)(const EC_GROUP *, EC_POINT *, 106 const BIGNUM *x, int y_bit, BN_CTX *); 107 108 /* used by EC_POINT_point2oct, EC_POINT_oct2point: */ 109 size_t (*point2oct)(const EC_GROUP *, const EC_POINT *, point_conversion_form_t form, 110 unsigned char *buf, size_t len, BN_CTX *); 111 int (*oct2point)(const EC_GROUP *, EC_POINT *, 112 const unsigned char *buf, size_t len, BN_CTX *); 113 114 /* used by EC_POINT_add, EC_POINT_dbl, ECP_POINT_invert: */ 115 int (*add)(const EC_GROUP *, EC_POINT *r, const EC_POINT *a, const EC_POINT *b, BN_CTX *); 116 int (*dbl)(const EC_GROUP *, EC_POINT *r, const EC_POINT *a, BN_CTX *); 117 int (*invert)(const EC_GROUP *, EC_POINT *, BN_CTX *); 118 119 /* used by EC_POINT_is_at_infinity, EC_POINT_is_on_curve, EC_POINT_cmp: */ 120 int (*is_at_infinity)(const EC_GROUP *, const EC_POINT *); 121 int (*is_on_curve)(const EC_GROUP *, const EC_POINT *, BN_CTX *); 122 int (*point_cmp)(const EC_GROUP *, const EC_POINT *a, const EC_POINT *b, BN_CTX *); 123 124 /* used by EC_POINT_make_affine, EC_POINTs_make_affine: */ 125 int (*make_affine)(const EC_GROUP *, EC_POINT *, BN_CTX *); 126 int (*points_make_affine)(const EC_GROUP *, size_t num, EC_POINT *[], BN_CTX *); 127 128 129 /* internal functions */ 130 131 /* 'field_mul' and 'field_sqr' can be used by 'add' and 'dbl' so that 132 * the same implementations of point operations can be used with different 133 * optimized implementations of expensive field operations: */ 134 int (*field_mul)(const EC_GROUP *, BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *); 135 int (*field_sqr)(const EC_GROUP *, BIGNUM *r, const BIGNUM *a, BN_CTX *); 136 137 int (*field_encode)(const EC_GROUP *, BIGNUM *r, const BIGNUM *a, BN_CTX *); /* e.g. to Montgomery */ 138 int (*field_decode)(const EC_GROUP *, BIGNUM *r, const BIGNUM *a, BN_CTX *); /* e.g. from Montgomery */ 139 int (*field_set_to_one)(const EC_GROUP *, BIGNUM *r, BN_CTX *); 140} /* EC_METHOD */; 141 142 143struct ec_group_st { 144 const EC_METHOD *meth; 145 146 void *extra_data; 147 void *(*extra_data_dup_func)(void *); 148 void (*extra_data_free_func)(void *); 149 void (*extra_data_clear_free_func)(void *); 150 151 /* All members except 'meth' and 'extra_data...' are handled by 152 * the method functions, even if they appear generic */ 153 154 BIGNUM field; /* Field specification. 155 * For curves over GF(p), this is the modulus. */ 156 157 BIGNUM a, b; /* Curve coefficients. 158 * (Here the assumption is that BIGNUMs can be used 159 * or abused for all kinds of fields, not just GF(p).) 160 * For characteristic > 3, the curve is defined 161 * by a Weierstrass equation of the form 162 * y^2 = x^3 + a*x + b. 163 */ 164 int a_is_minus3; /* enable optimized point arithmetics for special case */ 165 166 EC_POINT *generator; /* optional */ 167 BIGNUM order, cofactor; 168 169 void *field_data1; /* method-specific (e.g., Montgomery structure) */ 170 void *field_data2; /* method-specific */ 171} /* EC_GROUP */; 172 173 174/* Basically a 'mixin' for extra data, but available for EC_GROUPs only 175 * (with visibility limited to 'package' level for now). 176 * We use the function pointers as index for retrieval; this obviates 177 * global ex_data-style index tables. 178 * (Currently, we have one slot only, but is is possible to extend this 179 * if necessary.) */ 180int EC_GROUP_set_extra_data(EC_GROUP *, void *extra_data, void *(*extra_data_dup_func)(void *), 181 void (*extra_data_free_func)(void *), void (*extra_data_clear_free_func)(void *)); 182void *EC_GROUP_get_extra_data(const EC_GROUP *, void *(*extra_data_dup_func)(void *), 183 void (*extra_data_free_func)(void *), void (*extra_data_clear_free_func)(void *)); 184void EC_GROUP_free_extra_data(EC_GROUP *); 185void EC_GROUP_clear_free_extra_data(EC_GROUP *); 186 187 188 189struct ec_point_st { 190 const EC_METHOD *meth; 191 192 /* All members except 'meth' are handled by the method functions, 193 * even if they appear generic */ 194 195 BIGNUM X; 196 BIGNUM Y; 197 BIGNUM Z; /* Jacobian projective coordinates: 198 * (X, Y, Z) represents (X/Z^2, Y/Z^3) if Z != 0 */ 199 int Z_is_one; /* enable optimized point arithmetics for special case */ 200} /* EC_POINT */; 201 202 203 204/* method functions in ecp_smpl.c */ 205int ec_GFp_simple_group_init(EC_GROUP *); 206void ec_GFp_simple_group_finish(EC_GROUP *); 207void ec_GFp_simple_group_clear_finish(EC_GROUP *); 208int ec_GFp_simple_group_copy(EC_GROUP *, const EC_GROUP *); 209int ec_GFp_simple_group_set_curve_GFp(EC_GROUP *, const BIGNUM *p, const BIGNUM *a, const BIGNUM *b, BN_CTX *); 210int ec_GFp_simple_group_get_curve_GFp(const EC_GROUP *, BIGNUM *p, BIGNUM *a, BIGNUM *b, BN_CTX *); 211int ec_GFp_simple_group_set_generator(EC_GROUP *, const EC_POINT *generator, 212 const BIGNUM *order, const BIGNUM *cofactor); 213EC_POINT *ec_GFp_simple_group_get0_generator(const EC_GROUP *); 214int ec_GFp_simple_group_get_order(const EC_GROUP *, BIGNUM *order, BN_CTX *); 215int ec_GFp_simple_group_get_cofactor(const EC_GROUP *, BIGNUM *cofactor, BN_CTX *); 216int ec_GFp_simple_point_init(EC_POINT *); 217void ec_GFp_simple_point_finish(EC_POINT *); 218void ec_GFp_simple_point_clear_finish(EC_POINT *); 219int ec_GFp_simple_point_copy(EC_POINT *, const EC_POINT *); 220int ec_GFp_simple_point_set_to_infinity(const EC_GROUP *, EC_POINT *); 221int ec_GFp_simple_set_Jprojective_coordinates_GFp(const EC_GROUP *, EC_POINT *, 222 const BIGNUM *x, const BIGNUM *y, const BIGNUM *z, BN_CTX *); 223int ec_GFp_simple_get_Jprojective_coordinates_GFp(const EC_GROUP *, const EC_POINT *, 224 BIGNUM *x, BIGNUM *y, BIGNUM *z, BN_CTX *); 225int ec_GFp_simple_point_set_affine_coordinates_GFp(const EC_GROUP *, EC_POINT *, 226 const BIGNUM *x, const BIGNUM *y, BN_CTX *); 227int ec_GFp_simple_point_get_affine_coordinates_GFp(const EC_GROUP *, const EC_POINT *, 228 BIGNUM *x, BIGNUM *y, BN_CTX *); 229int ec_GFp_simple_set_compressed_coordinates_GFp(const EC_GROUP *, EC_POINT *, 230 const BIGNUM *x, int y_bit, BN_CTX *); 231size_t ec_GFp_simple_point2oct(const EC_GROUP *, const EC_POINT *, point_conversion_form_t form, 232 unsigned char *buf, size_t len, BN_CTX *); 233int ec_GFp_simple_oct2point(const EC_GROUP *, EC_POINT *, 234 const unsigned char *buf, size_t len, BN_CTX *); 235int ec_GFp_simple_add(const EC_GROUP *, EC_POINT *r, const EC_POINT *a, const EC_POINT *b, BN_CTX *); 236int ec_GFp_simple_dbl(const EC_GROUP *, EC_POINT *r, const EC_POINT *a, BN_CTX *); 237int ec_GFp_simple_invert(const EC_GROUP *, EC_POINT *, BN_CTX *); 238int ec_GFp_simple_is_at_infinity(const EC_GROUP *, const EC_POINT *); 239int ec_GFp_simple_is_on_curve(const EC_GROUP *, const EC_POINT *, BN_CTX *); 240int ec_GFp_simple_cmp(const EC_GROUP *, const EC_POINT *a, const EC_POINT *b, BN_CTX *); 241int ec_GFp_simple_make_affine(const EC_GROUP *, EC_POINT *, BN_CTX *); 242int ec_GFp_simple_points_make_affine(const EC_GROUP *, size_t num, EC_POINT *[], BN_CTX *); 243int ec_GFp_simple_field_mul(const EC_GROUP *, BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *); 244int ec_GFp_simple_field_sqr(const EC_GROUP *, BIGNUM *r, const BIGNUM *a, BN_CTX *); 245 246 247/* method functions in ecp_mont.c */ 248int ec_GFp_mont_group_init(EC_GROUP *); 249int ec_GFp_mont_group_set_curve_GFp(EC_GROUP *, const BIGNUM *p, const BIGNUM *a, const BIGNUM *b, BN_CTX *); 250void ec_GFp_mont_group_finish(EC_GROUP *); 251void ec_GFp_mont_group_clear_finish(EC_GROUP *); 252int ec_GFp_mont_group_copy(EC_GROUP *, const EC_GROUP *); 253int ec_GFp_mont_field_mul(const EC_GROUP *, BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *); 254int ec_GFp_mont_field_sqr(const EC_GROUP *, BIGNUM *r, const BIGNUM *a, BN_CTX *); 255int ec_GFp_mont_field_encode(const EC_GROUP *, BIGNUM *r, const BIGNUM *a, BN_CTX *); 256int ec_GFp_mont_field_decode(const EC_GROUP *, BIGNUM *r, const BIGNUM *a, BN_CTX *); 257int ec_GFp_mont_field_set_to_one(const EC_GROUP *, BIGNUM *r, BN_CTX *); 258 259 260/* method functions in ecp_recp.c */ 261int ec_GFp_recp_group_init(EC_GROUP *); 262int ec_GFp_recp_group_set_curve_GFp(EC_GROUP *, const BIGNUM *p, const BIGNUM *a, const BIGNUM *b, BN_CTX *); 263void ec_GFp_recp_group_finish(EC_GROUP *); 264void ec_GFp_recp_group_clear_finish(EC_GROUP *); 265int ec_GFp_recp_group_copy(EC_GROUP *, const EC_GROUP *); 266int ec_GFp_recp_field_mul(const EC_GROUP *, BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *); 267int ec_GFp_recp_field_sqr(const EC_GROUP *, BIGNUM *r, const BIGNUM *a, BN_CTX *); 268 269 270/* method functions in ecp_nist.c */ 271int ec_GFp_nist_group_init(EC_GROUP *); 272int ec_GFp_nist_group_set_curve_GFp(EC_GROUP *, const BIGNUM *p, const BIGNUM *a, const BIGNUM *b, BN_CTX *); 273void ec_GFp_nist_group_finish(EC_GROUP *); 274void ec_GFp_nist_group_clear_finish(EC_GROUP *); 275int ec_GFp_nist_group_copy(EC_GROUP *, const EC_GROUP *); 276int ec_GFp_nist_field_mul(const EC_GROUP *, BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *); 277int ec_GFp_nist_field_sqr(const EC_GROUP *, BIGNUM *r, const BIGNUM *a, BN_CTX *); 278