Home | History | Annotate | Download | only in ec
      1 /* crypto/ec/ec2_smpl.c */
      2 /* ====================================================================
      3  * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED.
      4  *
      5  * The Elliptic Curve Public-Key Crypto Library (ECC Code) included
      6  * herein is developed by SUN MICROSYSTEMS, INC., and is contributed
      7  * to the OpenSSL project.
      8  *
      9  * The ECC Code is licensed pursuant to the OpenSSL open source
     10  * license provided below.
     11  *
     12  * The software is originally written by Sheueling Chang Shantz and
     13  * Douglas Stebila of Sun Microsystems Laboratories.
     14  *
     15  */
     16 /* ====================================================================
     17  * Copyright (c) 1998-2005 The OpenSSL Project.  All rights reserved.
     18  *
     19  * Redistribution and use in source and binary forms, with or without
     20  * modification, are permitted provided that the following conditions
     21  * are met:
     22  *
     23  * 1. Redistributions of source code must retain the above copyright
     24  *    notice, this list of conditions and the following disclaimer.
     25  *
     26  * 2. Redistributions in binary form must reproduce the above copyright
     27  *    notice, this list of conditions and the following disclaimer in
     28  *    the documentation and/or other materials provided with the
     29  *    distribution.
     30  *
     31  * 3. All advertising materials mentioning features or use of this
     32  *    software must display the following acknowledgment:
     33  *    "This product includes software developed by the OpenSSL Project
     34  *    for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
     35  *
     36  * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
     37  *    endorse or promote products derived from this software without
     38  *    prior written permission. For written permission, please contact
     39  *    openssl-core (at) openssl.org.
     40  *
     41  * 5. Products derived from this software may not be called "OpenSSL"
     42  *    nor may "OpenSSL" appear in their names without prior written
     43  *    permission of the OpenSSL Project.
     44  *
     45  * 6. Redistributions of any form whatsoever must retain the following
     46  *    acknowledgment:
     47  *    "This product includes software developed by the OpenSSL Project
     48  *    for use in the OpenSSL Toolkit (http://www.openssl.org/)"
     49  *
     50  * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
     51  * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
     52  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
     53  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OpenSSL PROJECT OR
     54  * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
     55  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
     56  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
     57  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
     58  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
     59  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
     60  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
     61  * OF THE POSSIBILITY OF SUCH DAMAGE.
     62  * ====================================================================
     63  *
     64  * This product includes cryptographic software written by Eric Young
     65  * (eay (at) cryptsoft.com).  This product includes software written by Tim
     66  * Hudson (tjh (at) cryptsoft.com).
     67  *
     68  */
     69 
     70 #include <openssl/err.h>
     71 
     72 #include "ec_lcl.h"
     73 
     74 
     75 const EC_METHOD *EC_GF2m_simple_method(void)
     76 	{
     77 	static const EC_METHOD ret = {
     78 		NID_X9_62_characteristic_two_field,
     79 		ec_GF2m_simple_group_init,
     80 		ec_GF2m_simple_group_finish,
     81 		ec_GF2m_simple_group_clear_finish,
     82 		ec_GF2m_simple_group_copy,
     83 		ec_GF2m_simple_group_set_curve,
     84 		ec_GF2m_simple_group_get_curve,
     85 		ec_GF2m_simple_group_get_degree,
     86 		ec_GF2m_simple_group_check_discriminant,
     87 		ec_GF2m_simple_point_init,
     88 		ec_GF2m_simple_point_finish,
     89 		ec_GF2m_simple_point_clear_finish,
     90 		ec_GF2m_simple_point_copy,
     91 		ec_GF2m_simple_point_set_to_infinity,
     92 		0 /* set_Jprojective_coordinates_GFp */,
     93 		0 /* get_Jprojective_coordinates_GFp */,
     94 		ec_GF2m_simple_point_set_affine_coordinates,
     95 		ec_GF2m_simple_point_get_affine_coordinates,
     96 		ec_GF2m_simple_set_compressed_coordinates,
     97 		ec_GF2m_simple_point2oct,
     98 		ec_GF2m_simple_oct2point,
     99 		ec_GF2m_simple_add,
    100 		ec_GF2m_simple_dbl,
    101 		ec_GF2m_simple_invert,
    102 		ec_GF2m_simple_is_at_infinity,
    103 		ec_GF2m_simple_is_on_curve,
    104 		ec_GF2m_simple_cmp,
    105 		ec_GF2m_simple_make_affine,
    106 		ec_GF2m_simple_points_make_affine,
    107 
    108 		/* the following three method functions are defined in ec2_mult.c */
    109 		ec_GF2m_simple_mul,
    110 		ec_GF2m_precompute_mult,
    111 		ec_GF2m_have_precompute_mult,
    112 
    113 		ec_GF2m_simple_field_mul,
    114 		ec_GF2m_simple_field_sqr,
    115 		ec_GF2m_simple_field_div,
    116 		0 /* field_encode */,
    117 		0 /* field_decode */,
    118 		0 /* field_set_to_one */ };
    119 
    120 	return &ret;
    121 	}
    122 
    123 
    124 /* Initialize a GF(2^m)-based EC_GROUP structure.
    125  * Note that all other members are handled by EC_GROUP_new.
    126  */
    127 int ec_GF2m_simple_group_init(EC_GROUP *group)
    128 	{
    129 	BN_init(&group->field);
    130 	BN_init(&group->a);
    131 	BN_init(&group->b);
    132 	return 1;
    133 	}
    134 
    135 
    136 /* Free a GF(2^m)-based EC_GROUP structure.
    137  * Note that all other members are handled by EC_GROUP_free.
    138  */
    139 void ec_GF2m_simple_group_finish(EC_GROUP *group)
    140 	{
    141 	BN_free(&group->field);
    142 	BN_free(&group->a);
    143 	BN_free(&group->b);
    144 	}
    145 
    146 
    147 /* Clear and free a GF(2^m)-based EC_GROUP structure.
    148  * Note that all other members are handled by EC_GROUP_clear_free.
    149  */
    150 void ec_GF2m_simple_group_clear_finish(EC_GROUP *group)
    151 	{
    152 	BN_clear_free(&group->field);
    153 	BN_clear_free(&group->a);
    154 	BN_clear_free(&group->b);
    155 	group->poly[0] = 0;
    156 	group->poly[1] = 0;
    157 	group->poly[2] = 0;
    158 	group->poly[3] = 0;
    159 	group->poly[4] = 0;
    160 	group->poly[5] = -1;
    161 	}
    162 
    163 
    164 /* Copy a GF(2^m)-based EC_GROUP structure.
    165  * Note that all other members are handled by EC_GROUP_copy.
    166  */
    167 int ec_GF2m_simple_group_copy(EC_GROUP *dest, const EC_GROUP *src)
    168 	{
    169 	int i;
    170 	if (!BN_copy(&dest->field, &src->field)) return 0;
    171 	if (!BN_copy(&dest->a, &src->a)) return 0;
    172 	if (!BN_copy(&dest->b, &src->b)) return 0;
    173 	dest->poly[0] = src->poly[0];
    174 	dest->poly[1] = src->poly[1];
    175 	dest->poly[2] = src->poly[2];
    176 	dest->poly[3] = src->poly[3];
    177 	dest->poly[4] = src->poly[4];
    178 	dest->poly[5] = src->poly[5];
    179 	if (bn_wexpand(&dest->a, (int)(dest->poly[0] + BN_BITS2 - 1) / BN_BITS2) == NULL) return 0;
    180 	if (bn_wexpand(&dest->b, (int)(dest->poly[0] + BN_BITS2 - 1) / BN_BITS2) == NULL) return 0;
    181 	for (i = dest->a.top; i < dest->a.dmax; i++) dest->a.d[i] = 0;
    182 	for (i = dest->b.top; i < dest->b.dmax; i++) dest->b.d[i] = 0;
    183 	return 1;
    184 	}
    185 
    186 
    187 /* Set the curve parameters of an EC_GROUP structure. */
    188 int ec_GF2m_simple_group_set_curve(EC_GROUP *group,
    189 	const BIGNUM *p, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
    190 	{
    191 	int ret = 0, i;
    192 
    193 	/* group->field */
    194 	if (!BN_copy(&group->field, p)) goto err;
    195 	i = BN_GF2m_poly2arr(&group->field, group->poly, 6) - 1;
    196 	if ((i != 5) && (i != 3))
    197 		{
    198 		ECerr(EC_F_EC_GF2M_SIMPLE_GROUP_SET_CURVE, EC_R_UNSUPPORTED_FIELD);
    199 		goto err;
    200 		}
    201 
    202 	/* group->a */
    203 	if (!BN_GF2m_mod_arr(&group->a, a, group->poly)) goto err;
    204 	if(bn_wexpand(&group->a, (int)(group->poly[0] + BN_BITS2 - 1) / BN_BITS2) == NULL) goto err;
    205 	for (i = group->a.top; i < group->a.dmax; i++) group->a.d[i] = 0;
    206 
    207 	/* group->b */
    208 	if (!BN_GF2m_mod_arr(&group->b, b, group->poly)) goto err;
    209 	if(bn_wexpand(&group->b, (int)(group->poly[0] + BN_BITS2 - 1) / BN_BITS2) == NULL) goto err;
    210 	for (i = group->b.top; i < group->b.dmax; i++) group->b.d[i] = 0;
    211 
    212 	ret = 1;
    213   err:
    214 	return ret;
    215 	}
    216 
    217 
    218 /* Get the curve parameters of an EC_GROUP structure.
    219  * If p, a, or b are NULL then there values will not be set but the method will return with success.
    220  */
    221 int ec_GF2m_simple_group_get_curve(const EC_GROUP *group, BIGNUM *p, BIGNUM *a, BIGNUM *b, BN_CTX *ctx)
    222 	{
    223 	int ret = 0;
    224 
    225 	if (p != NULL)
    226 		{
    227 		if (!BN_copy(p, &group->field)) return 0;
    228 		}
    229 
    230 	if (a != NULL)
    231 		{
    232 		if (!BN_copy(a, &group->a)) goto err;
    233 		}
    234 
    235 	if (b != NULL)
    236 		{
    237 		if (!BN_copy(b, &group->b)) goto err;
    238 		}
    239 
    240 	ret = 1;
    241 
    242   err:
    243 	return ret;
    244 	}
    245 
    246 
    247 /* Gets the degree of the field.  For a curve over GF(2^m) this is the value m. */
    248 int ec_GF2m_simple_group_get_degree(const EC_GROUP *group)
    249 	{
    250 	return BN_num_bits(&group->field)-1;
    251 	}
    252 
    253 
    254 /* Checks the discriminant of the curve.
    255  * y^2 + x*y = x^3 + a*x^2 + b is an elliptic curve <=> b != 0 (mod p)
    256  */
    257 int ec_GF2m_simple_group_check_discriminant(const EC_GROUP *group, BN_CTX *ctx)
    258 	{
    259 	int ret = 0;
    260 	BIGNUM *b;
    261 	BN_CTX *new_ctx = NULL;
    262 
    263 	if (ctx == NULL)
    264 		{
    265 		ctx = new_ctx = BN_CTX_new();
    266 		if (ctx == NULL)
    267 			{
    268 			ECerr(EC_F_EC_GF2M_SIMPLE_GROUP_CHECK_DISCRIMINANT, ERR_R_MALLOC_FAILURE);
    269 			goto err;
    270 			}
    271 		}
    272 	BN_CTX_start(ctx);
    273 	b = BN_CTX_get(ctx);
    274 	if (b == NULL) goto err;
    275 
    276 	if (!BN_GF2m_mod_arr(b, &group->b, group->poly)) goto err;
    277 
    278 	/* check the discriminant:
    279 	 * y^2 + x*y = x^3 + a*x^2 + b is an elliptic curve <=> b != 0 (mod p)
    280 	 */
    281 	if (BN_is_zero(b)) goto err;
    282 
    283 	ret = 1;
    284 
    285 err:
    286 	if (ctx != NULL)
    287 		BN_CTX_end(ctx);
    288 	if (new_ctx != NULL)
    289 		BN_CTX_free(new_ctx);
    290 	return ret;
    291 	}
    292 
    293 
    294 /* Initializes an EC_POINT. */
    295 int ec_GF2m_simple_point_init(EC_POINT *point)
    296 	{
    297 	BN_init(&point->X);
    298 	BN_init(&point->Y);
    299 	BN_init(&point->Z);
    300 	return 1;
    301 	}
    302 
    303 
    304 /* Frees an EC_POINT. */
    305 void ec_GF2m_simple_point_finish(EC_POINT *point)
    306 	{
    307 	BN_free(&point->X);
    308 	BN_free(&point->Y);
    309 	BN_free(&point->Z);
    310 	}
    311 
    312 
    313 /* Clears and frees an EC_POINT. */
    314 void ec_GF2m_simple_point_clear_finish(EC_POINT *point)
    315 	{
    316 	BN_clear_free(&point->X);
    317 	BN_clear_free(&point->Y);
    318 	BN_clear_free(&point->Z);
    319 	point->Z_is_one = 0;
    320 	}
    321 
    322 
    323 /* Copy the contents of one EC_POINT into another.  Assumes dest is initialized. */
    324 int ec_GF2m_simple_point_copy(EC_POINT *dest, const EC_POINT *src)
    325 	{
    326 	if (!BN_copy(&dest->X, &src->X)) return 0;
    327 	if (!BN_copy(&dest->Y, &src->Y)) return 0;
    328 	if (!BN_copy(&dest->Z, &src->Z)) return 0;
    329 	dest->Z_is_one = src->Z_is_one;
    330 
    331 	return 1;
    332 	}
    333 
    334 
    335 /* Set an EC_POINT to the point at infinity.
    336  * A point at infinity is represented by having Z=0.
    337  */
    338 int ec_GF2m_simple_point_set_to_infinity(const EC_GROUP *group, EC_POINT *point)
    339 	{
    340 	point->Z_is_one = 0;
    341 	BN_zero(&point->Z);
    342 	return 1;
    343 	}
    344 
    345 
    346 /* Set the coordinates of an EC_POINT using affine coordinates.
    347  * Note that the simple implementation only uses affine coordinates.
    348  */
    349 int ec_GF2m_simple_point_set_affine_coordinates(const EC_GROUP *group, EC_POINT *point,
    350 	const BIGNUM *x, const BIGNUM *y, BN_CTX *ctx)
    351 	{
    352 	int ret = 0;
    353 	if (x == NULL || y == NULL)
    354 		{
    355 		ECerr(EC_F_EC_GF2M_SIMPLE_POINT_SET_AFFINE_COORDINATES, ERR_R_PASSED_NULL_PARAMETER);
    356 		return 0;
    357 		}
    358 
    359 	if (!BN_copy(&point->X, x)) goto err;
    360 	BN_set_negative(&point->X, 0);
    361 	if (!BN_copy(&point->Y, y)) goto err;
    362 	BN_set_negative(&point->Y, 0);
    363 	if (!BN_copy(&point->Z, BN_value_one())) goto err;
    364 	BN_set_negative(&point->Z, 0);
    365 	point->Z_is_one = 1;
    366 	ret = 1;
    367 
    368   err:
    369 	return ret;
    370 	}
    371 
    372 
    373 /* Gets the affine coordinates of an EC_POINT.
    374  * Note that the simple implementation only uses affine coordinates.
    375  */
    376 int ec_GF2m_simple_point_get_affine_coordinates(const EC_GROUP *group, const EC_POINT *point,
    377 	BIGNUM *x, BIGNUM *y, BN_CTX *ctx)
    378 	{
    379 	int ret = 0;
    380 
    381 	if (EC_POINT_is_at_infinity(group, point))
    382 		{
    383 		ECerr(EC_F_EC_GF2M_SIMPLE_POINT_GET_AFFINE_COORDINATES, EC_R_POINT_AT_INFINITY);
    384 		return 0;
    385 		}
    386 
    387 	if (BN_cmp(&point->Z, BN_value_one()))
    388 		{
    389 		ECerr(EC_F_EC_GF2M_SIMPLE_POINT_GET_AFFINE_COORDINATES, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
    390 		return 0;
    391 		}
    392 	if (x != NULL)
    393 		{
    394 		if (!BN_copy(x, &point->X)) goto err;
    395 		BN_set_negative(x, 0);
    396 		}
    397 	if (y != NULL)
    398 		{
    399 		if (!BN_copy(y, &point->Y)) goto err;
    400 		BN_set_negative(y, 0);
    401 		}
    402 	ret = 1;
    403 
    404  err:
    405 	return ret;
    406 	}
    407 
    408 
    409 /* Calculates and sets the affine coordinates of an EC_POINT from the given
    410  * compressed coordinates.  Uses algorithm 2.3.4 of SEC 1.
    411  * Note that the simple implementation only uses affine coordinates.
    412  *
    413  * The method is from the following publication:
    414  *
    415  *     Harper, Menezes, Vanstone:
    416  *     "Public-Key Cryptosystems with Very Small Key Lengths",
    417  *     EUROCRYPT '92, Springer-Verlag LNCS 658,
    418  *     published February 1993
    419  *
    420  * US Patents 6,141,420 and 6,618,483 (Vanstone, Mullin, Agnew) describe
    421  * the same method, but claim no priority date earlier than July 29, 1994
    422  * (and additionally fail to cite the EUROCRYPT '92 publication as prior art).
    423  */
    424 int ec_GF2m_simple_set_compressed_coordinates(const EC_GROUP *group, EC_POINT *point,
    425 	const BIGNUM *x_, int y_bit, BN_CTX *ctx)
    426 	{
    427 	BN_CTX *new_ctx = NULL;
    428 	BIGNUM *tmp, *x, *y, *z;
    429 	int ret = 0, z0;
    430 
    431 	/* clear error queue */
    432 	ERR_clear_error();
    433 
    434 	if (ctx == NULL)
    435 		{
    436 		ctx = new_ctx = BN_CTX_new();
    437 		if (ctx == NULL)
    438 			return 0;
    439 		}
    440 
    441 	y_bit = (y_bit != 0) ? 1 : 0;
    442 
    443 	BN_CTX_start(ctx);
    444 	tmp = BN_CTX_get(ctx);
    445 	x = BN_CTX_get(ctx);
    446 	y = BN_CTX_get(ctx);
    447 	z = BN_CTX_get(ctx);
    448 	if (z == NULL) goto err;
    449 
    450 	if (!BN_GF2m_mod_arr(x, x_, group->poly)) goto err;
    451 	if (BN_is_zero(x))
    452 		{
    453 		if (!BN_GF2m_mod_sqrt_arr(y, &group->b, group->poly, ctx)) goto err;
    454 		}
    455 	else
    456 		{
    457 		if (!group->meth->field_sqr(group, tmp, x, ctx)) goto err;
    458 		if (!group->meth->field_div(group, tmp, &group->b, tmp, ctx)) goto err;
    459 		if (!BN_GF2m_add(tmp, &group->a, tmp)) goto err;
    460 		if (!BN_GF2m_add(tmp, x, tmp)) goto err;
    461 		if (!BN_GF2m_mod_solve_quad_arr(z, tmp, group->poly, ctx))
    462 			{
    463 			unsigned long err = ERR_peek_last_error();
    464 
    465 			if (ERR_GET_LIB(err) == ERR_LIB_BN && ERR_GET_REASON(err) == BN_R_NO_SOLUTION)
    466 				{
    467 				ERR_clear_error();
    468 				ECerr(EC_F_EC_GF2M_SIMPLE_SET_COMPRESSED_COORDINATES, EC_R_INVALID_COMPRESSED_POINT);
    469 				}
    470 			else
    471 				ECerr(EC_F_EC_GF2M_SIMPLE_SET_COMPRESSED_COORDINATES, ERR_R_BN_LIB);
    472 			goto err;
    473 			}
    474 		z0 = (BN_is_odd(z)) ? 1 : 0;
    475 		if (!group->meth->field_mul(group, y, x, z, ctx)) goto err;
    476 		if (z0 != y_bit)
    477 			{
    478 			if (!BN_GF2m_add(y, y, x)) goto err;
    479 			}
    480 		}
    481 
    482 	if (!EC_POINT_set_affine_coordinates_GF2m(group, point, x, y, ctx)) goto err;
    483 
    484 	ret = 1;
    485 
    486  err:
    487 	BN_CTX_end(ctx);
    488 	if (new_ctx != NULL)
    489 		BN_CTX_free(new_ctx);
    490 	return ret;
    491 	}
    492 
    493 
    494 /* Converts an EC_POINT to an octet string.
    495  * If buf is NULL, the encoded length will be returned.
    496  * If the length len of buf is smaller than required an error will be returned.
    497  */
    498 size_t ec_GF2m_simple_point2oct(const EC_GROUP *group, const EC_POINT *point, point_conversion_form_t form,
    499 	unsigned char *buf, size_t len, BN_CTX *ctx)
    500 	{
    501 	size_t ret;
    502 	BN_CTX *new_ctx = NULL;
    503 	int used_ctx = 0;
    504 	BIGNUM *x, *y, *yxi;
    505 	size_t field_len, i, skip;
    506 
    507 	if ((form != POINT_CONVERSION_COMPRESSED)
    508 		&& (form != POINT_CONVERSION_UNCOMPRESSED)
    509 		&& (form != POINT_CONVERSION_HYBRID))
    510 		{
    511 		ECerr(EC_F_EC_GF2M_SIMPLE_POINT2OCT, EC_R_INVALID_FORM);
    512 		goto err;
    513 		}
    514 
    515 	if (EC_POINT_is_at_infinity(group, point))
    516 		{
    517 		/* encodes to a single 0 octet */
    518 		if (buf != NULL)
    519 			{
    520 			if (len < 1)
    521 				{
    522 				ECerr(EC_F_EC_GF2M_SIMPLE_POINT2OCT, EC_R_BUFFER_TOO_SMALL);
    523 				return 0;
    524 				}
    525 			buf[0] = 0;
    526 			}
    527 		return 1;
    528 		}
    529 
    530 
    531 	/* ret := required output buffer length */
    532 	field_len = (EC_GROUP_get_degree(group) + 7) / 8;
    533 	ret = (form == POINT_CONVERSION_COMPRESSED) ? 1 + field_len : 1 + 2*field_len;
    534 
    535 	/* if 'buf' is NULL, just return required length */
    536 	if (buf != NULL)
    537 		{
    538 		if (len < ret)
    539 			{
    540 			ECerr(EC_F_EC_GF2M_SIMPLE_POINT2OCT, EC_R_BUFFER_TOO_SMALL);
    541 			goto err;
    542 			}
    543 
    544 		if (ctx == NULL)
    545 			{
    546 			ctx = new_ctx = BN_CTX_new();
    547 			if (ctx == NULL)
    548 				return 0;
    549 			}
    550 
    551 		BN_CTX_start(ctx);
    552 		used_ctx = 1;
    553 		x = BN_CTX_get(ctx);
    554 		y = BN_CTX_get(ctx);
    555 		yxi = BN_CTX_get(ctx);
    556 		if (yxi == NULL) goto err;
    557 
    558 		if (!EC_POINT_get_affine_coordinates_GF2m(group, point, x, y, ctx)) goto err;
    559 
    560 		buf[0] = form;
    561 		if ((form != POINT_CONVERSION_UNCOMPRESSED) && !BN_is_zero(x))
    562 			{
    563 			if (!group->meth->field_div(group, yxi, y, x, ctx)) goto err;
    564 			if (BN_is_odd(yxi)) buf[0]++;
    565 			}
    566 
    567 		i = 1;
    568 
    569 		skip = field_len - BN_num_bytes(x);
    570 		if (skip > field_len)
    571 			{
    572 			ECerr(EC_F_EC_GF2M_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR);
    573 			goto err;
    574 			}
    575 		while (skip > 0)
    576 			{
    577 			buf[i++] = 0;
    578 			skip--;
    579 			}
    580 		skip = BN_bn2bin(x, buf + i);
    581 		i += skip;
    582 		if (i != 1 + field_len)
    583 			{
    584 			ECerr(EC_F_EC_GF2M_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR);
    585 			goto err;
    586 			}
    587 
    588 		if (form == POINT_CONVERSION_UNCOMPRESSED || form == POINT_CONVERSION_HYBRID)
    589 			{
    590 			skip = field_len - BN_num_bytes(y);
    591 			if (skip > field_len)
    592 				{
    593 				ECerr(EC_F_EC_GF2M_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR);
    594 				goto err;
    595 				}
    596 			while (skip > 0)
    597 				{
    598 				buf[i++] = 0;
    599 				skip--;
    600 				}
    601 			skip = BN_bn2bin(y, buf + i);
    602 			i += skip;
    603 			}
    604 
    605 		if (i != ret)
    606 			{
    607 			ECerr(EC_F_EC_GF2M_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR);
    608 			goto err;
    609 			}
    610 		}
    611 
    612 	if (used_ctx)
    613 		BN_CTX_end(ctx);
    614 	if (new_ctx != NULL)
    615 		BN_CTX_free(new_ctx);
    616 	return ret;
    617 
    618  err:
    619 	if (used_ctx)
    620 		BN_CTX_end(ctx);
    621 	if (new_ctx != NULL)
    622 		BN_CTX_free(new_ctx);
    623 	return 0;
    624 	}
    625 
    626 
    627 /* Converts an octet string representation to an EC_POINT.
    628  * Note that the simple implementation only uses affine coordinates.
    629  */
    630 int ec_GF2m_simple_oct2point(const EC_GROUP *group, EC_POINT *point,
    631 	const unsigned char *buf, size_t len, BN_CTX *ctx)
    632 	{
    633 	point_conversion_form_t form;
    634 	int y_bit;
    635 	BN_CTX *new_ctx = NULL;
    636 	BIGNUM *x, *y, *yxi;
    637 	size_t field_len, enc_len;
    638 	int ret = 0;
    639 
    640 	if (len == 0)
    641 		{
    642 		ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_BUFFER_TOO_SMALL);
    643 		return 0;
    644 		}
    645 	form = buf[0];
    646 	y_bit = form & 1;
    647 	form = form & ~1U;
    648 	if ((form != 0)	&& (form != POINT_CONVERSION_COMPRESSED)
    649 		&& (form != POINT_CONVERSION_UNCOMPRESSED)
    650 		&& (form != POINT_CONVERSION_HYBRID))
    651 		{
    652 		ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
    653 		return 0;
    654 		}
    655 	if ((form == 0 || form == POINT_CONVERSION_UNCOMPRESSED) && y_bit)
    656 		{
    657 		ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
    658 		return 0;
    659 		}
    660 
    661 	if (form == 0)
    662 		{
    663 		if (len != 1)
    664 			{
    665 			ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
    666 			return 0;
    667 			}
    668 
    669 		return EC_POINT_set_to_infinity(group, point);
    670 		}
    671 
    672 	field_len = (EC_GROUP_get_degree(group) + 7) / 8;
    673 	enc_len = (form == POINT_CONVERSION_COMPRESSED) ? 1 + field_len : 1 + 2*field_len;
    674 
    675 	if (len != enc_len)
    676 		{
    677 		ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
    678 		return 0;
    679 		}
    680 
    681 	if (ctx == NULL)
    682 		{
    683 		ctx = new_ctx = BN_CTX_new();
    684 		if (ctx == NULL)
    685 			return 0;
    686 		}
    687 
    688 	BN_CTX_start(ctx);
    689 	x = BN_CTX_get(ctx);
    690 	y = BN_CTX_get(ctx);
    691 	yxi = BN_CTX_get(ctx);
    692 	if (yxi == NULL) goto err;
    693 
    694 	if (!BN_bin2bn(buf + 1, field_len, x)) goto err;
    695 	if (BN_ucmp(x, &group->field) >= 0)
    696 		{
    697 		ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
    698 		goto err;
    699 		}
    700 
    701 	if (form == POINT_CONVERSION_COMPRESSED)
    702 		{
    703 		if (!EC_POINT_set_compressed_coordinates_GF2m(group, point, x, y_bit, ctx)) goto err;
    704 		}
    705 	else
    706 		{
    707 		if (!BN_bin2bn(buf + 1 + field_len, field_len, y)) goto err;
    708 		if (BN_ucmp(y, &group->field) >= 0)
    709 			{
    710 			ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
    711 			goto err;
    712 			}
    713 		if (form == POINT_CONVERSION_HYBRID)
    714 			{
    715 			if (!group->meth->field_div(group, yxi, y, x, ctx)) goto err;
    716 			if (y_bit != BN_is_odd(yxi))
    717 				{
    718 				ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
    719 				goto err;
    720 				}
    721 			}
    722 
    723 		if (!EC_POINT_set_affine_coordinates_GF2m(group, point, x, y, ctx)) goto err;
    724 		}
    725 
    726 	if (!EC_POINT_is_on_curve(group, point, ctx)) /* test required by X9.62 */
    727 		{
    728 		ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_POINT_IS_NOT_ON_CURVE);
    729 		goto err;
    730 		}
    731 
    732 	ret = 1;
    733 
    734  err:
    735 	BN_CTX_end(ctx);
    736 	if (new_ctx != NULL)
    737 		BN_CTX_free(new_ctx);
    738 	return ret;
    739 	}
    740 
    741 
    742 /* Computes a + b and stores the result in r.  r could be a or b, a could be b.
    743  * Uses algorithm A.10.2 of IEEE P1363.
    744  */
    745 int ec_GF2m_simple_add(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a, const EC_POINT *b, BN_CTX *ctx)
    746 	{
    747 	BN_CTX *new_ctx = NULL;
    748 	BIGNUM *x0, *y0, *x1, *y1, *x2, *y2, *s, *t;
    749 	int ret = 0;
    750 
    751 	if (EC_POINT_is_at_infinity(group, a))
    752 		{
    753 		if (!EC_POINT_copy(r, b)) return 0;
    754 		return 1;
    755 		}
    756 
    757 	if (EC_POINT_is_at_infinity(group, b))
    758 		{
    759 		if (!EC_POINT_copy(r, a)) return 0;
    760 		return 1;
    761 		}
    762 
    763 	if (ctx == NULL)
    764 		{
    765 		ctx = new_ctx = BN_CTX_new();
    766 		if (ctx == NULL)
    767 			return 0;
    768 		}
    769 
    770 	BN_CTX_start(ctx);
    771 	x0 = BN_CTX_get(ctx);
    772 	y0 = BN_CTX_get(ctx);
    773 	x1 = BN_CTX_get(ctx);
    774 	y1 = BN_CTX_get(ctx);
    775 	x2 = BN_CTX_get(ctx);
    776 	y2 = BN_CTX_get(ctx);
    777 	s = BN_CTX_get(ctx);
    778 	t = BN_CTX_get(ctx);
    779 	if (t == NULL) goto err;
    780 
    781 	if (a->Z_is_one)
    782 		{
    783 		if (!BN_copy(x0, &a->X)) goto err;
    784 		if (!BN_copy(y0, &a->Y)) goto err;
    785 		}
    786 	else
    787 		{
    788 		if (!EC_POINT_get_affine_coordinates_GF2m(group, a, x0, y0, ctx)) goto err;
    789 		}
    790 	if (b->Z_is_one)
    791 		{
    792 		if (!BN_copy(x1, &b->X)) goto err;
    793 		if (!BN_copy(y1, &b->Y)) goto err;
    794 		}
    795 	else
    796 		{
    797 		if (!EC_POINT_get_affine_coordinates_GF2m(group, b, x1, y1, ctx)) goto err;
    798 		}
    799 
    800 
    801 	if (BN_GF2m_cmp(x0, x1))
    802 		{
    803 		if (!BN_GF2m_add(t, x0, x1)) goto err;
    804 		if (!BN_GF2m_add(s, y0, y1)) goto err;
    805 		if (!group->meth->field_div(group, s, s, t, ctx)) goto err;
    806 		if (!group->meth->field_sqr(group, x2, s, ctx)) goto err;
    807 		if (!BN_GF2m_add(x2, x2, &group->a)) goto err;
    808 		if (!BN_GF2m_add(x2, x2, s)) goto err;
    809 		if (!BN_GF2m_add(x2, x2, t)) goto err;
    810 		}
    811 	else
    812 		{
    813 		if (BN_GF2m_cmp(y0, y1) || BN_is_zero(x1))
    814 			{
    815 			if (!EC_POINT_set_to_infinity(group, r)) goto err;
    816 			ret = 1;
    817 			goto err;
    818 			}
    819 		if (!group->meth->field_div(group, s, y1, x1, ctx)) goto err;
    820 		if (!BN_GF2m_add(s, s, x1)) goto err;
    821 
    822 		if (!group->meth->field_sqr(group, x2, s, ctx)) goto err;
    823 		if (!BN_GF2m_add(x2, x2, s)) goto err;
    824 		if (!BN_GF2m_add(x2, x2, &group->a)) goto err;
    825 		}
    826 
    827 	if (!BN_GF2m_add(y2, x1, x2)) goto err;
    828 	if (!group->meth->field_mul(group, y2, y2, s, ctx)) goto err;
    829 	if (!BN_GF2m_add(y2, y2, x2)) goto err;
    830 	if (!BN_GF2m_add(y2, y2, y1)) goto err;
    831 
    832 	if (!EC_POINT_set_affine_coordinates_GF2m(group, r, x2, y2, ctx)) goto err;
    833 
    834 	ret = 1;
    835 
    836  err:
    837 	BN_CTX_end(ctx);
    838 	if (new_ctx != NULL)
    839 		BN_CTX_free(new_ctx);
    840 	return ret;
    841 	}
    842 
    843 
    844 /* Computes 2 * a and stores the result in r.  r could be a.
    845  * Uses algorithm A.10.2 of IEEE P1363.
    846  */
    847 int ec_GF2m_simple_dbl(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a, BN_CTX *ctx)
    848 	{
    849 	return ec_GF2m_simple_add(group, r, a, a, ctx);
    850 	}
    851 
    852 
    853 int ec_GF2m_simple_invert(const EC_GROUP *group, EC_POINT *point, BN_CTX *ctx)
    854 	{
    855 	if (EC_POINT_is_at_infinity(group, point) || BN_is_zero(&point->Y))
    856 		/* point is its own inverse */
    857 		return 1;
    858 
    859 	if (!EC_POINT_make_affine(group, point, ctx)) return 0;
    860 	return BN_GF2m_add(&point->Y, &point->X, &point->Y);
    861 	}
    862 
    863 
    864 /* Indicates whether the given point is the point at infinity. */
    865 int ec_GF2m_simple_is_at_infinity(const EC_GROUP *group, const EC_POINT *point)
    866 	{
    867 	return BN_is_zero(&point->Z);
    868 	}
    869 
    870 
    871 /* Determines whether the given EC_POINT is an actual point on the curve defined
    872  * in the EC_GROUP.  A point is valid if it satisfies the Weierstrass equation:
    873  *      y^2 + x*y = x^3 + a*x^2 + b.
    874  */
    875 int ec_GF2m_simple_is_on_curve(const EC_GROUP *group, const EC_POINT *point, BN_CTX *ctx)
    876 	{
    877 	int ret = -1;
    878 	BN_CTX *new_ctx = NULL;
    879 	BIGNUM *lh, *y2;
    880 	int (*field_mul)(const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *);
    881 	int (*field_sqr)(const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
    882 
    883 	if (EC_POINT_is_at_infinity(group, point))
    884 		return 1;
    885 
    886 	field_mul = group->meth->field_mul;
    887 	field_sqr = group->meth->field_sqr;
    888 
    889 	/* only support affine coordinates */
    890 	if (!point->Z_is_one) goto err;
    891 
    892 	if (ctx == NULL)
    893 		{
    894 		ctx = new_ctx = BN_CTX_new();
    895 		if (ctx == NULL)
    896 			return -1;
    897 		}
    898 
    899 	BN_CTX_start(ctx);
    900 	y2 = BN_CTX_get(ctx);
    901 	lh = BN_CTX_get(ctx);
    902 	if (lh == NULL) goto err;
    903 
    904 	/* We have a curve defined by a Weierstrass equation
    905 	 *      y^2 + x*y = x^3 + a*x^2 + b.
    906 	 *  <=> x^3 + a*x^2 + x*y + b + y^2 = 0
    907 	 *  <=> ((x + a) * x + y ) * x + b + y^2 = 0
    908 	 */
    909 	if (!BN_GF2m_add(lh, &point->X, &group->a)) goto err;
    910 	if (!field_mul(group, lh, lh, &point->X, ctx)) goto err;
    911 	if (!BN_GF2m_add(lh, lh, &point->Y)) goto err;
    912 	if (!field_mul(group, lh, lh, &point->X, ctx)) goto err;
    913 	if (!BN_GF2m_add(lh, lh, &group->b)) goto err;
    914 	if (!field_sqr(group, y2, &point->Y, ctx)) goto err;
    915 	if (!BN_GF2m_add(lh, lh, y2)) goto err;
    916 	ret = BN_is_zero(lh);
    917  err:
    918 	if (ctx) BN_CTX_end(ctx);
    919 	if (new_ctx) BN_CTX_free(new_ctx);
    920 	return ret;
    921 	}
    922 
    923 
    924 /* Indicates whether two points are equal.
    925  * Return values:
    926  *  -1   error
    927  *   0   equal (in affine coordinates)
    928  *   1   not equal
    929  */
    930 int ec_GF2m_simple_cmp(const EC_GROUP *group, const EC_POINT *a, const EC_POINT *b, BN_CTX *ctx)
    931 	{
    932 	BIGNUM *aX, *aY, *bX, *bY;
    933 	BN_CTX *new_ctx = NULL;
    934 	int ret = -1;
    935 
    936 	if (EC_POINT_is_at_infinity(group, a))
    937 		{
    938 		return EC_POINT_is_at_infinity(group, b) ? 0 : 1;
    939 		}
    940 
    941 	if (EC_POINT_is_at_infinity(group, b))
    942 		return 1;
    943 
    944 	if (a->Z_is_one && b->Z_is_one)
    945 		{
    946 		return ((BN_cmp(&a->X, &b->X) == 0) && BN_cmp(&a->Y, &b->Y) == 0) ? 0 : 1;
    947 		}
    948 
    949 	if (ctx == NULL)
    950 		{
    951 		ctx = new_ctx = BN_CTX_new();
    952 		if (ctx == NULL)
    953 			return -1;
    954 		}
    955 
    956 	BN_CTX_start(ctx);
    957 	aX = BN_CTX_get(ctx);
    958 	aY = BN_CTX_get(ctx);
    959 	bX = BN_CTX_get(ctx);
    960 	bY = BN_CTX_get(ctx);
    961 	if (bY == NULL) goto err;
    962 
    963 	if (!EC_POINT_get_affine_coordinates_GF2m(group, a, aX, aY, ctx)) goto err;
    964 	if (!EC_POINT_get_affine_coordinates_GF2m(group, b, bX, bY, ctx)) goto err;
    965 	ret = ((BN_cmp(aX, bX) == 0) && BN_cmp(aY, bY) == 0) ? 0 : 1;
    966 
    967   err:
    968 	if (ctx) BN_CTX_end(ctx);
    969 	if (new_ctx) BN_CTX_free(new_ctx);
    970 	return ret;
    971 	}
    972 
    973 
    974 /* Forces the given EC_POINT to internally use affine coordinates. */
    975 int ec_GF2m_simple_make_affine(const EC_GROUP *group, EC_POINT *point, BN_CTX *ctx)
    976 	{
    977 	BN_CTX *new_ctx = NULL;
    978 	BIGNUM *x, *y;
    979 	int ret = 0;
    980 
    981 	if (point->Z_is_one || EC_POINT_is_at_infinity(group, point))
    982 		return 1;
    983 
    984 	if (ctx == NULL)
    985 		{
    986 		ctx = new_ctx = BN_CTX_new();
    987 		if (ctx == NULL)
    988 			return 0;
    989 		}
    990 
    991 	BN_CTX_start(ctx);
    992 	x = BN_CTX_get(ctx);
    993 	y = BN_CTX_get(ctx);
    994 	if (y == NULL) goto err;
    995 
    996 	if (!EC_POINT_get_affine_coordinates_GF2m(group, point, x, y, ctx)) goto err;
    997 	if (!BN_copy(&point->X, x)) goto err;
    998 	if (!BN_copy(&point->Y, y)) goto err;
    999 	if (!BN_one(&point->Z)) goto err;
   1000 
   1001 	ret = 1;
   1002 
   1003   err:
   1004 	if (ctx) BN_CTX_end(ctx);
   1005 	if (new_ctx) BN_CTX_free(new_ctx);
   1006 	return ret;
   1007 	}
   1008 
   1009 
   1010 /* Forces each of the EC_POINTs in the given array to use affine coordinates. */
   1011 int ec_GF2m_simple_points_make_affine(const EC_GROUP *group, size_t num, EC_POINT *points[], BN_CTX *ctx)
   1012 	{
   1013 	size_t i;
   1014 
   1015 	for (i = 0; i < num; i++)
   1016 		{
   1017 		if (!group->meth->make_affine(group, points[i], ctx)) return 0;
   1018 		}
   1019 
   1020 	return 1;
   1021 	}
   1022 
   1023 
   1024 /* Wrapper to simple binary polynomial field multiplication implementation. */
   1025 int ec_GF2m_simple_field_mul(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
   1026 	{
   1027 	return BN_GF2m_mod_mul_arr(r, a, b, group->poly, ctx);
   1028 	}
   1029 
   1030 
   1031 /* Wrapper to simple binary polynomial field squaring implementation. */
   1032 int ec_GF2m_simple_field_sqr(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, BN_CTX *ctx)
   1033 	{
   1034 	return BN_GF2m_mod_sqr_arr(r, a, group->poly, ctx);
   1035 	}
   1036 
   1037 
   1038 /* Wrapper to simple binary polynomial field division implementation. */
   1039 int ec_GF2m_simple_field_div(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
   1040 	{
   1041 	return BN_GF2m_mod_div(r, a, b, &group->field, ctx);
   1042 	}
   1043