Home | History | Annotate | Download | only in ec
      1 /* crypto/ec/ecp_oct.c */
      2 /* Includes code written by Lenka Fibikova <fibikova (at) exp-math.uni-essen.de>
      3  * for the OpenSSL project.
      4  * Includes code written by Bodo Moeller for the OpenSSL project.
      5 */
      6 /* ====================================================================
      7  * Copyright (c) 1998-2002 The OpenSSL Project.  All rights reserved.
      8  *
      9  * Redistribution and use in source and binary forms, with or without
     10  * modification, are permitted provided that the following conditions
     11  * are met:
     12  *
     13  * 1. Redistributions of source code must retain the above copyright
     14  *    notice, this list of conditions and the following disclaimer.
     15  *
     16  * 2. Redistributions in binary form must reproduce the above copyright
     17  *    notice, this list of conditions and the following disclaimer in
     18  *    the documentation and/or other materials provided with the
     19  *    distribution.
     20  *
     21  * 3. All advertising materials mentioning features or use of this
     22  *    software must display the following acknowledgment:
     23  *    "This product includes software developed by the OpenSSL Project
     24  *    for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
     25  *
     26  * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
     27  *    endorse or promote products derived from this software without
     28  *    prior written permission. For written permission, please contact
     29  *    openssl-core (at) openssl.org.
     30  *
     31  * 5. Products derived from this software may not be called "OpenSSL"
     32  *    nor may "OpenSSL" appear in their names without prior written
     33  *    permission of the OpenSSL Project.
     34  *
     35  * 6. Redistributions of any form whatsoever must retain the following
     36  *    acknowledgment:
     37  *    "This product includes software developed by the OpenSSL Project
     38  *    for use in the OpenSSL Toolkit (http://www.openssl.org/)"
     39  *
     40  * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
     41  * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
     42  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
     43  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OpenSSL PROJECT OR
     44  * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
     45  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
     46  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
     47  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
     48  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
     49  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
     50  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
     51  * OF THE POSSIBILITY OF SUCH DAMAGE.
     52  * ====================================================================
     53  *
     54  * This product includes cryptographic software written by Eric Young
     55  * (eay (at) cryptsoft.com).  This product includes software written by Tim
     56  * Hudson (tjh (at) cryptsoft.com).
     57  *
     58  */
     59 /* ====================================================================
     60  * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED.
     61  * Portions of this software developed by SUN MICROSYSTEMS, INC.,
     62  * and contributed to the OpenSSL project.
     63  */
     64 
     65 #include <openssl/err.h>
     66 #include <openssl/symhacks.h>
     67 
     68 #include "ec_lcl.h"
     69 
     70 int ec_GFp_simple_set_compressed_coordinates(const EC_GROUP *group, EC_POINT *point,
     71 	const BIGNUM *x_, int y_bit, BN_CTX *ctx)
     72 	{
     73 	BN_CTX *new_ctx = NULL;
     74 	BIGNUM *tmp1, *tmp2, *x, *y;
     75 	int ret = 0;
     76 
     77 	/* clear error queue*/
     78 	ERR_clear_error();
     79 
     80 	if (ctx == NULL)
     81 		{
     82 		ctx = new_ctx = BN_CTX_new();
     83 		if (ctx == NULL)
     84 			return 0;
     85 		}
     86 
     87 	y_bit = (y_bit != 0);
     88 
     89 	BN_CTX_start(ctx);
     90 	tmp1 = BN_CTX_get(ctx);
     91 	tmp2 = BN_CTX_get(ctx);
     92 	x = BN_CTX_get(ctx);
     93 	y = BN_CTX_get(ctx);
     94 	if (y == NULL) goto err;
     95 
     96 	/* Recover y.  We have a Weierstrass equation
     97 	 *     y^2 = x^3 + a*x + b,
     98 	 * so  y  is one of the square roots of  x^3 + a*x + b.
     99 	 */
    100 
    101 	/* tmp1 := x^3 */
    102 	if (!BN_nnmod(x, x_, &group->field,ctx)) goto err;
    103 	if (group->meth->field_decode == 0)
    104 		{
    105 		/* field_{sqr,mul} work on standard representation */
    106 		if (!group->meth->field_sqr(group, tmp2, x_, ctx)) goto err;
    107 		if (!group->meth->field_mul(group, tmp1, tmp2, x_, ctx)) goto err;
    108 		}
    109 	else
    110 		{
    111 		if (!BN_mod_sqr(tmp2, x_, &group->field, ctx)) goto err;
    112 		if (!BN_mod_mul(tmp1, tmp2, x_, &group->field, ctx)) goto err;
    113 		}
    114 
    115 	/* tmp1 := tmp1 + a*x */
    116 	if (group->a_is_minus3)
    117 		{
    118 		if (!BN_mod_lshift1_quick(tmp2, x, &group->field)) goto err;
    119 		if (!BN_mod_add_quick(tmp2, tmp2, x, &group->field)) goto err;
    120 		if (!BN_mod_sub_quick(tmp1, tmp1, tmp2, &group->field)) goto err;
    121 		}
    122 	else
    123 		{
    124 		if (group->meth->field_decode)
    125 			{
    126 			if (!group->meth->field_decode(group, tmp2, &group->a, ctx)) goto err;
    127 			if (!BN_mod_mul(tmp2, tmp2, x, &group->field, ctx)) goto err;
    128 			}
    129 		else
    130 			{
    131 			/* field_mul works on standard representation */
    132 			if (!group->meth->field_mul(group, tmp2, &group->a, x, ctx)) goto err;
    133 			}
    134 
    135 		if (!BN_mod_add_quick(tmp1, tmp1, tmp2, &group->field)) goto err;
    136 		}
    137 
    138 	/* tmp1 := tmp1 + b */
    139 	if (group->meth->field_decode)
    140 		{
    141 		if (!group->meth->field_decode(group, tmp2, &group->b, ctx)) goto err;
    142 		if (!BN_mod_add_quick(tmp1, tmp1, tmp2, &group->field)) goto err;
    143 		}
    144 	else
    145 		{
    146 		if (!BN_mod_add_quick(tmp1, tmp1, &group->b, &group->field)) goto err;
    147 		}
    148 
    149 	if (!BN_mod_sqrt(y, tmp1, &group->field, ctx))
    150 		{
    151 		unsigned long err = ERR_peek_last_error();
    152 
    153 		if (ERR_GET_LIB(err) == ERR_LIB_BN && ERR_GET_REASON(err) == BN_R_NOT_A_SQUARE)
    154 			{
    155 			ERR_clear_error();
    156 			ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES, EC_R_INVALID_COMPRESSED_POINT);
    157 			}
    158 		else
    159 			ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES, ERR_R_BN_LIB);
    160 		goto err;
    161 		}
    162 
    163 	if (y_bit != BN_is_odd(y))
    164 		{
    165 		if (BN_is_zero(y))
    166 			{
    167 			int kron;
    168 
    169 			kron = BN_kronecker(x, &group->field, ctx);
    170 			if (kron == -2) goto err;
    171 
    172 			if (kron == 1)
    173 				ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES, EC_R_INVALID_COMPRESSION_BIT);
    174 			else
    175 				/* BN_mod_sqrt() should have cought this error (not a square) */
    176 				ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES, EC_R_INVALID_COMPRESSED_POINT);
    177 			goto err;
    178 			}
    179 		if (!BN_usub(y, &group->field, y)) goto err;
    180 		}
    181 	if (y_bit != BN_is_odd(y))
    182 		{
    183 		ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES, ERR_R_INTERNAL_ERROR);
    184 		goto err;
    185 		}
    186 
    187 	if (!EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx)) goto err;
    188 
    189 	ret = 1;
    190 
    191  err:
    192 	BN_CTX_end(ctx);
    193 	if (new_ctx != NULL)
    194 		BN_CTX_free(new_ctx);
    195 	return ret;
    196 	}
    197 
    198 
    199 size_t ec_GFp_simple_point2oct(const EC_GROUP *group, const EC_POINT *point, point_conversion_form_t form,
    200 	unsigned char *buf, size_t len, BN_CTX *ctx)
    201 	{
    202 	size_t ret;
    203 	BN_CTX *new_ctx = NULL;
    204 	int used_ctx = 0;
    205 	BIGNUM *x, *y;
    206 	size_t field_len, i, skip;
    207 
    208 	if ((form != POINT_CONVERSION_COMPRESSED)
    209 		&& (form != POINT_CONVERSION_UNCOMPRESSED)
    210 		&& (form != POINT_CONVERSION_HYBRID))
    211 		{
    212 		ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, EC_R_INVALID_FORM);
    213 		goto err;
    214 		}
    215 
    216 	if (EC_POINT_is_at_infinity(group, point))
    217 		{
    218 		/* encodes to a single 0 octet */
    219 		if (buf != NULL)
    220 			{
    221 			if (len < 1)
    222 				{
    223 				ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, EC_R_BUFFER_TOO_SMALL);
    224 				return 0;
    225 				}
    226 			buf[0] = 0;
    227 			}
    228 		return 1;
    229 		}
    230 
    231 
    232 	/* ret := required output buffer length */
    233 	field_len = BN_num_bytes(&group->field);
    234 	ret = (form == POINT_CONVERSION_COMPRESSED) ? 1 + field_len : 1 + 2*field_len;
    235 
    236 	/* if 'buf' is NULL, just return required length */
    237 	if (buf != NULL)
    238 		{
    239 		if (len < ret)
    240 			{
    241 			ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, EC_R_BUFFER_TOO_SMALL);
    242 			goto err;
    243 			}
    244 
    245 		if (ctx == NULL)
    246 			{
    247 			ctx = new_ctx = BN_CTX_new();
    248 			if (ctx == NULL)
    249 				return 0;
    250 			}
    251 
    252 		BN_CTX_start(ctx);
    253 		used_ctx = 1;
    254 		x = BN_CTX_get(ctx);
    255 		y = BN_CTX_get(ctx);
    256 		if (y == NULL) goto err;
    257 
    258 		if (!EC_POINT_get_affine_coordinates_GFp(group, point, x, y, ctx)) goto err;
    259 
    260 		if ((form == POINT_CONVERSION_COMPRESSED || form == POINT_CONVERSION_HYBRID) && BN_is_odd(y))
    261 			buf[0] = form + 1;
    262 		else
    263 			buf[0] = form;
    264 
    265 		i = 1;
    266 
    267 		skip = field_len - BN_num_bytes(x);
    268 		if (skip > field_len)
    269 			{
    270 			ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR);
    271 			goto err;
    272 			}
    273 		while (skip > 0)
    274 			{
    275 			buf[i++] = 0;
    276 			skip--;
    277 			}
    278 		skip = BN_bn2bin(x, buf + i);
    279 		i += skip;
    280 		if (i != 1 + field_len)
    281 			{
    282 			ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR);
    283 			goto err;
    284 			}
    285 
    286 		if (form == POINT_CONVERSION_UNCOMPRESSED || form == POINT_CONVERSION_HYBRID)
    287 			{
    288 			skip = field_len - BN_num_bytes(y);
    289 			if (skip > field_len)
    290 				{
    291 				ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR);
    292 				goto err;
    293 				}
    294 			while (skip > 0)
    295 				{
    296 				buf[i++] = 0;
    297 				skip--;
    298 				}
    299 			skip = BN_bn2bin(y, buf + i);
    300 			i += skip;
    301 			}
    302 
    303 		if (i != ret)
    304 			{
    305 			ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR);
    306 			goto err;
    307 			}
    308 		}
    309 
    310 	if (used_ctx)
    311 		BN_CTX_end(ctx);
    312 	if (new_ctx != NULL)
    313 		BN_CTX_free(new_ctx);
    314 	return ret;
    315 
    316  err:
    317 	if (used_ctx)
    318 		BN_CTX_end(ctx);
    319 	if (new_ctx != NULL)
    320 		BN_CTX_free(new_ctx);
    321 	return 0;
    322 	}
    323 
    324 
    325 int ec_GFp_simple_oct2point(const EC_GROUP *group, EC_POINT *point,
    326 	const unsigned char *buf, size_t len, BN_CTX *ctx)
    327 	{
    328 	point_conversion_form_t form;
    329 	int y_bit;
    330 	BN_CTX *new_ctx = NULL;
    331 	BIGNUM *x, *y;
    332 	size_t field_len, enc_len;
    333 	int ret = 0;
    334 
    335 	if (len == 0)
    336 		{
    337 		ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_BUFFER_TOO_SMALL);
    338 		return 0;
    339 		}
    340 	form = buf[0];
    341 	y_bit = form & 1;
    342 	form = form & ~1U;
    343 	if ((form != 0)	&& (form != POINT_CONVERSION_COMPRESSED)
    344 		&& (form != POINT_CONVERSION_UNCOMPRESSED)
    345 		&& (form != POINT_CONVERSION_HYBRID))
    346 		{
    347 		ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
    348 		return 0;
    349 		}
    350 	if ((form == 0 || form == POINT_CONVERSION_UNCOMPRESSED) && y_bit)
    351 		{
    352 		ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
    353 		return 0;
    354 		}
    355 
    356 	if (form == 0)
    357 		{
    358 		if (len != 1)
    359 			{
    360 			ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
    361 			return 0;
    362 			}
    363 
    364 		return EC_POINT_set_to_infinity(group, point);
    365 		}
    366 
    367 	field_len = BN_num_bytes(&group->field);
    368 	enc_len = (form == POINT_CONVERSION_COMPRESSED) ? 1 + field_len : 1 + 2*field_len;
    369 
    370 	if (len != enc_len)
    371 		{
    372 		ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
    373 		return 0;
    374 		}
    375 
    376 	if (ctx == NULL)
    377 		{
    378 		ctx = new_ctx = BN_CTX_new();
    379 		if (ctx == NULL)
    380 			return 0;
    381 		}
    382 
    383 	BN_CTX_start(ctx);
    384 	x = BN_CTX_get(ctx);
    385 	y = BN_CTX_get(ctx);
    386 	if (y == NULL) goto err;
    387 
    388 	if (!BN_bin2bn(buf + 1, field_len, x)) goto err;
    389 	if (BN_ucmp(x, &group->field) >= 0)
    390 		{
    391 		ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
    392 		goto err;
    393 		}
    394 
    395 	if (form == POINT_CONVERSION_COMPRESSED)
    396 		{
    397 		if (!EC_POINT_set_compressed_coordinates_GFp(group, point, x, y_bit, ctx)) goto err;
    398 		}
    399 	else
    400 		{
    401 		if (!BN_bin2bn(buf + 1 + field_len, field_len, y)) goto err;
    402 		if (BN_ucmp(y, &group->field) >= 0)
    403 			{
    404 			ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
    405 			goto err;
    406 			}
    407 		if (form == POINT_CONVERSION_HYBRID)
    408 			{
    409 			if (y_bit != BN_is_odd(y))
    410 				{
    411 				ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
    412 				goto err;
    413 				}
    414 			}
    415 
    416 		if (!EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx)) goto err;
    417 		}
    418 
    419 	if (!EC_POINT_is_on_curve(group, point, ctx)) /* test required by X9.62 */
    420 		{
    421 		ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_POINT_IS_NOT_ON_CURVE);
    422 		goto err;
    423 		}
    424 
    425 	ret = 1;
    426 
    427  err:
    428 	BN_CTX_end(ctx);
    429 	if (new_ctx != NULL)
    430 		BN_CTX_free(new_ctx);
    431 	return ret;
    432 	}
    433 
    434