• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /* crypto/ec/ecp_smpl.c */
2 /* Includes code written by Lenka Fibikova <fibikova@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@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@cryptsoft.com).  This product includes software written by Tim
56  * Hudson (tjh@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 
EC_GFp_simple_method(void)70 const EC_METHOD *EC_GFp_simple_method(void)
71 	{
72 	static const EC_METHOD ret = {
73 		NID_X9_62_prime_field,
74 		ec_GFp_simple_group_init,
75 		ec_GFp_simple_group_finish,
76 		ec_GFp_simple_group_clear_finish,
77 		ec_GFp_simple_group_copy,
78 		ec_GFp_simple_group_set_curve,
79 		ec_GFp_simple_group_get_curve,
80 		ec_GFp_simple_group_get_degree,
81 		ec_GFp_simple_group_check_discriminant,
82 		ec_GFp_simple_point_init,
83 		ec_GFp_simple_point_finish,
84 		ec_GFp_simple_point_clear_finish,
85 		ec_GFp_simple_point_copy,
86 		ec_GFp_simple_point_set_to_infinity,
87 		ec_GFp_simple_set_Jprojective_coordinates_GFp,
88 		ec_GFp_simple_get_Jprojective_coordinates_GFp,
89 		ec_GFp_simple_point_set_affine_coordinates,
90 		ec_GFp_simple_point_get_affine_coordinates,
91 		ec_GFp_simple_set_compressed_coordinates,
92 		ec_GFp_simple_point2oct,
93 		ec_GFp_simple_oct2point,
94 		ec_GFp_simple_add,
95 		ec_GFp_simple_dbl,
96 		ec_GFp_simple_invert,
97 		ec_GFp_simple_is_at_infinity,
98 		ec_GFp_simple_is_on_curve,
99 		ec_GFp_simple_cmp,
100 		ec_GFp_simple_make_affine,
101 		ec_GFp_simple_points_make_affine,
102 		0 /* mul */,
103 		0 /* precompute_mult */,
104 		0 /* have_precompute_mult */,
105 		ec_GFp_simple_field_mul,
106 		ec_GFp_simple_field_sqr,
107 		0 /* field_div */,
108 		0 /* field_encode */,
109 		0 /* field_decode */,
110 		0 /* field_set_to_one */ };
111 
112 	return &ret;
113 	}
114 
115 
116 /* Most method functions in this file are designed to work with
117  * non-trivial representations of field elements if necessary
118  * (see ecp_mont.c): while standard modular addition and subtraction
119  * are used, the field_mul and field_sqr methods will be used for
120  * multiplication, and field_encode and field_decode (if defined)
121  * will be used for converting between representations.
122 
123  * Functions ec_GFp_simple_points_make_affine() and
124  * ec_GFp_simple_point_get_affine_coordinates() specifically assume
125  * that if a non-trivial representation is used, it is a Montgomery
126  * representation (i.e. 'encoding' means multiplying by some factor R).
127  */
128 
129 
ec_GFp_simple_group_init(EC_GROUP * group)130 int ec_GFp_simple_group_init(EC_GROUP *group)
131 	{
132 	BN_init(&group->field);
133 	BN_init(&group->a);
134 	BN_init(&group->b);
135 	group->a_is_minus3 = 0;
136 	return 1;
137 	}
138 
139 
ec_GFp_simple_group_finish(EC_GROUP * group)140 void ec_GFp_simple_group_finish(EC_GROUP *group)
141 	{
142 	BN_free(&group->field);
143 	BN_free(&group->a);
144 	BN_free(&group->b);
145 	}
146 
147 
ec_GFp_simple_group_clear_finish(EC_GROUP * group)148 void ec_GFp_simple_group_clear_finish(EC_GROUP *group)
149 	{
150 	BN_clear_free(&group->field);
151 	BN_clear_free(&group->a);
152 	BN_clear_free(&group->b);
153 	}
154 
155 
ec_GFp_simple_group_copy(EC_GROUP * dest,const EC_GROUP * src)156 int ec_GFp_simple_group_copy(EC_GROUP *dest, const EC_GROUP *src)
157 	{
158 	if (!BN_copy(&dest->field, &src->field)) return 0;
159 	if (!BN_copy(&dest->a, &src->a)) return 0;
160 	if (!BN_copy(&dest->b, &src->b)) return 0;
161 
162 	dest->a_is_minus3 = src->a_is_minus3;
163 
164 	return 1;
165 	}
166 
167 
ec_GFp_simple_group_set_curve(EC_GROUP * group,const BIGNUM * p,const BIGNUM * a,const BIGNUM * b,BN_CTX * ctx)168 int ec_GFp_simple_group_set_curve(EC_GROUP *group,
169 	const BIGNUM *p, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
170 	{
171 	int ret = 0;
172 	BN_CTX *new_ctx = NULL;
173 	BIGNUM *tmp_a;
174 
175 	/* p must be a prime > 3 */
176 	if (BN_num_bits(p) <= 2 || !BN_is_odd(p))
177 		{
178 		ECerr(EC_F_EC_GFP_SIMPLE_GROUP_SET_CURVE, EC_R_INVALID_FIELD);
179 		return 0;
180 		}
181 
182 	if (ctx == NULL)
183 		{
184 		ctx = new_ctx = BN_CTX_new();
185 		if (ctx == NULL)
186 			return 0;
187 		}
188 
189 	BN_CTX_start(ctx);
190 	tmp_a = BN_CTX_get(ctx);
191 	if (tmp_a == NULL) goto err;
192 
193 	/* group->field */
194 	if (!BN_copy(&group->field, p)) goto err;
195 	BN_set_negative(&group->field, 0);
196 
197 	/* group->a */
198 	if (!BN_nnmod(tmp_a, a, p, ctx)) goto err;
199 	if (group->meth->field_encode)
200 		{ if (!group->meth->field_encode(group, &group->a, tmp_a, ctx)) goto err; }
201 	else
202 		if (!BN_copy(&group->a, tmp_a)) goto err;
203 
204 	/* group->b */
205 	if (!BN_nnmod(&group->b, b, p, ctx)) goto err;
206 	if (group->meth->field_encode)
207 		if (!group->meth->field_encode(group, &group->b, &group->b, ctx)) goto err;
208 
209 	/* group->a_is_minus3 */
210 	if (!BN_add_word(tmp_a, 3)) goto err;
211 	group->a_is_minus3 = (0 == BN_cmp(tmp_a, &group->field));
212 
213 	ret = 1;
214 
215  err:
216 	BN_CTX_end(ctx);
217 	if (new_ctx != NULL)
218 		BN_CTX_free(new_ctx);
219 	return ret;
220 	}
221 
222 
ec_GFp_simple_group_get_curve(const EC_GROUP * group,BIGNUM * p,BIGNUM * a,BIGNUM * b,BN_CTX * ctx)223 int ec_GFp_simple_group_get_curve(const EC_GROUP *group, BIGNUM *p, BIGNUM *a, BIGNUM *b, BN_CTX *ctx)
224 	{
225 	int ret = 0;
226 	BN_CTX *new_ctx = NULL;
227 
228 	if (p != NULL)
229 		{
230 		if (!BN_copy(p, &group->field)) return 0;
231 		}
232 
233 	if (a != NULL || b != NULL)
234 		{
235 		if (group->meth->field_decode)
236 			{
237 			if (ctx == NULL)
238 				{
239 				ctx = new_ctx = BN_CTX_new();
240 				if (ctx == NULL)
241 					return 0;
242 				}
243 			if (a != NULL)
244 				{
245 				if (!group->meth->field_decode(group, a, &group->a, ctx)) goto err;
246 				}
247 			if (b != NULL)
248 				{
249 				if (!group->meth->field_decode(group, b, &group->b, ctx)) goto err;
250 				}
251 			}
252 		else
253 			{
254 			if (a != NULL)
255 				{
256 				if (!BN_copy(a, &group->a)) goto err;
257 				}
258 			if (b != NULL)
259 				{
260 				if (!BN_copy(b, &group->b)) goto err;
261 				}
262 			}
263 		}
264 
265 	ret = 1;
266 
267  err:
268 	if (new_ctx)
269 		BN_CTX_free(new_ctx);
270 	return ret;
271 	}
272 
273 
ec_GFp_simple_group_get_degree(const EC_GROUP * group)274 int ec_GFp_simple_group_get_degree(const EC_GROUP *group)
275 	{
276 	return BN_num_bits(&group->field);
277 	}
278 
279 
ec_GFp_simple_group_check_discriminant(const EC_GROUP * group,BN_CTX * ctx)280 int ec_GFp_simple_group_check_discriminant(const EC_GROUP *group, BN_CTX *ctx)
281 	{
282 	int ret = 0;
283 	BIGNUM *a,*b,*order,*tmp_1,*tmp_2;
284 	const BIGNUM *p = &group->field;
285 	BN_CTX *new_ctx = NULL;
286 
287 	if (ctx == NULL)
288 		{
289 		ctx = new_ctx = BN_CTX_new();
290 		if (ctx == NULL)
291 			{
292 			ECerr(EC_F_EC_GFP_SIMPLE_GROUP_CHECK_DISCRIMINANT, ERR_R_MALLOC_FAILURE);
293 			goto err;
294 			}
295 		}
296 	BN_CTX_start(ctx);
297 	a = BN_CTX_get(ctx);
298 	b = BN_CTX_get(ctx);
299 	tmp_1 = BN_CTX_get(ctx);
300 	tmp_2 = BN_CTX_get(ctx);
301 	order = BN_CTX_get(ctx);
302 	if (order == NULL) goto err;
303 
304 	if (group->meth->field_decode)
305 		{
306 		if (!group->meth->field_decode(group, a, &group->a, ctx)) goto err;
307 		if (!group->meth->field_decode(group, b, &group->b, ctx)) goto err;
308 		}
309 	else
310 		{
311 		if (!BN_copy(a, &group->a)) goto err;
312 		if (!BN_copy(b, &group->b)) goto err;
313 		}
314 
315 	/* check the discriminant:
316 	 * y^2 = x^3 + a*x + b is an elliptic curve <=> 4*a^3 + 27*b^2 != 0 (mod p)
317          * 0 =< a, b < p */
318 	if (BN_is_zero(a))
319 		{
320 		if (BN_is_zero(b)) goto err;
321 		}
322 	else if (!BN_is_zero(b))
323 		{
324 		if (!BN_mod_sqr(tmp_1, a, p, ctx)) goto err;
325 		if (!BN_mod_mul(tmp_2, tmp_1, a, p, ctx)) goto err;
326 		if (!BN_lshift(tmp_1, tmp_2, 2)) goto err;
327 		/* tmp_1 = 4*a^3 */
328 
329 		if (!BN_mod_sqr(tmp_2, b, p, ctx)) goto err;
330 		if (!BN_mul_word(tmp_2, 27)) goto err;
331 		/* tmp_2 = 27*b^2 */
332 
333 		if (!BN_mod_add(a, tmp_1, tmp_2, p, ctx)) goto err;
334 		if (BN_is_zero(a)) goto err;
335 		}
336 	ret = 1;
337 
338 err:
339 	if (ctx != NULL)
340 		BN_CTX_end(ctx);
341 	if (new_ctx != NULL)
342 		BN_CTX_free(new_ctx);
343 	return ret;
344 	}
345 
346 
ec_GFp_simple_point_init(EC_POINT * point)347 int ec_GFp_simple_point_init(EC_POINT *point)
348 	{
349 	BN_init(&point->X);
350 	BN_init(&point->Y);
351 	BN_init(&point->Z);
352 	point->Z_is_one = 0;
353 
354 	return 1;
355 	}
356 
357 
ec_GFp_simple_point_finish(EC_POINT * point)358 void ec_GFp_simple_point_finish(EC_POINT *point)
359 	{
360 	BN_free(&point->X);
361 	BN_free(&point->Y);
362 	BN_free(&point->Z);
363 	}
364 
365 
ec_GFp_simple_point_clear_finish(EC_POINT * point)366 void ec_GFp_simple_point_clear_finish(EC_POINT *point)
367 	{
368 	BN_clear_free(&point->X);
369 	BN_clear_free(&point->Y);
370 	BN_clear_free(&point->Z);
371 	point->Z_is_one = 0;
372 	}
373 
374 
ec_GFp_simple_point_copy(EC_POINT * dest,const EC_POINT * src)375 int ec_GFp_simple_point_copy(EC_POINT *dest, const EC_POINT *src)
376 	{
377 	if (!BN_copy(&dest->X, &src->X)) return 0;
378 	if (!BN_copy(&dest->Y, &src->Y)) return 0;
379 	if (!BN_copy(&dest->Z, &src->Z)) return 0;
380 	dest->Z_is_one = src->Z_is_one;
381 
382 	return 1;
383 	}
384 
385 
ec_GFp_simple_point_set_to_infinity(const EC_GROUP * group,EC_POINT * point)386 int ec_GFp_simple_point_set_to_infinity(const EC_GROUP *group, EC_POINT *point)
387 	{
388 	point->Z_is_one = 0;
389 	BN_zero(&point->Z);
390 	return 1;
391 	}
392 
393 
ec_GFp_simple_set_Jprojective_coordinates_GFp(const EC_GROUP * group,EC_POINT * point,const BIGNUM * x,const BIGNUM * y,const BIGNUM * z,BN_CTX * ctx)394 int ec_GFp_simple_set_Jprojective_coordinates_GFp(const EC_GROUP *group, EC_POINT *point,
395 	const BIGNUM *x, const BIGNUM *y, const BIGNUM *z, BN_CTX *ctx)
396 	{
397 	BN_CTX *new_ctx = NULL;
398 	int ret = 0;
399 
400 	if (ctx == NULL)
401 		{
402 		ctx = new_ctx = BN_CTX_new();
403 		if (ctx == NULL)
404 			return 0;
405 		}
406 
407 	if (x != NULL)
408 		{
409 		if (!BN_nnmod(&point->X, x, &group->field, ctx)) goto err;
410 		if (group->meth->field_encode)
411 			{
412 			if (!group->meth->field_encode(group, &point->X, &point->X, ctx)) goto err;
413 			}
414 		}
415 
416 	if (y != NULL)
417 		{
418 		if (!BN_nnmod(&point->Y, y, &group->field, ctx)) goto err;
419 		if (group->meth->field_encode)
420 			{
421 			if (!group->meth->field_encode(group, &point->Y, &point->Y, ctx)) goto err;
422 			}
423 		}
424 
425 	if (z != NULL)
426 		{
427 		int Z_is_one;
428 
429 		if (!BN_nnmod(&point->Z, z, &group->field, ctx)) goto err;
430 		Z_is_one = BN_is_one(&point->Z);
431 		if (group->meth->field_encode)
432 			{
433 			if (Z_is_one && (group->meth->field_set_to_one != 0))
434 				{
435 				if (!group->meth->field_set_to_one(group, &point->Z, ctx)) goto err;
436 				}
437 			else
438 				{
439 				if (!group->meth->field_encode(group, &point->Z, &point->Z, ctx)) goto err;
440 				}
441 			}
442 		point->Z_is_one = Z_is_one;
443 		}
444 
445 	ret = 1;
446 
447  err:
448 	if (new_ctx != NULL)
449 		BN_CTX_free(new_ctx);
450 	return ret;
451 	}
452 
453 
ec_GFp_simple_get_Jprojective_coordinates_GFp(const EC_GROUP * group,const EC_POINT * point,BIGNUM * x,BIGNUM * y,BIGNUM * z,BN_CTX * ctx)454 int ec_GFp_simple_get_Jprojective_coordinates_GFp(const EC_GROUP *group, const EC_POINT *point,
455 	BIGNUM *x, BIGNUM *y, BIGNUM *z, BN_CTX *ctx)
456 	{
457 	BN_CTX *new_ctx = NULL;
458 	int ret = 0;
459 
460 	if (group->meth->field_decode != 0)
461 		{
462 		if (ctx == NULL)
463 			{
464 			ctx = new_ctx = BN_CTX_new();
465 			if (ctx == NULL)
466 				return 0;
467 			}
468 
469 		if (x != NULL)
470 			{
471 			if (!group->meth->field_decode(group, x, &point->X, ctx)) goto err;
472 			}
473 		if (y != NULL)
474 			{
475 			if (!group->meth->field_decode(group, y, &point->Y, ctx)) goto err;
476 			}
477 		if (z != NULL)
478 			{
479 			if (!group->meth->field_decode(group, z, &point->Z, ctx)) goto err;
480 			}
481 		}
482 	else
483 		{
484 		if (x != NULL)
485 			{
486 			if (!BN_copy(x, &point->X)) goto err;
487 			}
488 		if (y != NULL)
489 			{
490 			if (!BN_copy(y, &point->Y)) goto err;
491 			}
492 		if (z != NULL)
493 			{
494 			if (!BN_copy(z, &point->Z)) goto err;
495 			}
496 		}
497 
498 	ret = 1;
499 
500  err:
501 	if (new_ctx != NULL)
502 		BN_CTX_free(new_ctx);
503 	return ret;
504 	}
505 
506 
ec_GFp_simple_point_set_affine_coordinates(const EC_GROUP * group,EC_POINT * point,const BIGNUM * x,const BIGNUM * y,BN_CTX * ctx)507 int ec_GFp_simple_point_set_affine_coordinates(const EC_GROUP *group, EC_POINT *point,
508 	const BIGNUM *x, const BIGNUM *y, BN_CTX *ctx)
509 	{
510 	if (x == NULL || y == NULL)
511 		{
512 		/* unlike for projective coordinates, we do not tolerate this */
513 		ECerr(EC_F_EC_GFP_SIMPLE_POINT_SET_AFFINE_COORDINATES, ERR_R_PASSED_NULL_PARAMETER);
514 		return 0;
515 		}
516 
517 	return EC_POINT_set_Jprojective_coordinates_GFp(group, point, x, y, BN_value_one(), ctx);
518 	}
519 
520 
ec_GFp_simple_point_get_affine_coordinates(const EC_GROUP * group,const EC_POINT * point,BIGNUM * x,BIGNUM * y,BN_CTX * ctx)521 int ec_GFp_simple_point_get_affine_coordinates(const EC_GROUP *group, const EC_POINT *point,
522 	BIGNUM *x, BIGNUM *y, BN_CTX *ctx)
523 	{
524 	BN_CTX *new_ctx = NULL;
525 	BIGNUM *Z, *Z_1, *Z_2, *Z_3;
526 	const BIGNUM *Z_;
527 	int ret = 0;
528 
529 	if (EC_POINT_is_at_infinity(group, point))
530 		{
531 		ECerr(EC_F_EC_GFP_SIMPLE_POINT_GET_AFFINE_COORDINATES, EC_R_POINT_AT_INFINITY);
532 		return 0;
533 		}
534 
535 	if (ctx == NULL)
536 		{
537 		ctx = new_ctx = BN_CTX_new();
538 		if (ctx == NULL)
539 			return 0;
540 		}
541 
542 	BN_CTX_start(ctx);
543 	Z = BN_CTX_get(ctx);
544 	Z_1 = BN_CTX_get(ctx);
545 	Z_2 = BN_CTX_get(ctx);
546 	Z_3 = BN_CTX_get(ctx);
547 	if (Z_3 == NULL) goto err;
548 
549 	/* transform  (X, Y, Z)  into  (x, y) := (X/Z^2, Y/Z^3) */
550 
551 	if (group->meth->field_decode)
552 		{
553 		if (!group->meth->field_decode(group, Z, &point->Z, ctx)) goto err;
554 		Z_ = Z;
555 		}
556 	else
557 		{
558 		Z_ = &point->Z;
559 		}
560 
561 	if (BN_is_one(Z_))
562 		{
563 		if (group->meth->field_decode)
564 			{
565 			if (x != NULL)
566 				{
567 				if (!group->meth->field_decode(group, x, &point->X, ctx)) goto err;
568 				}
569 			if (y != NULL)
570 				{
571 				if (!group->meth->field_decode(group, y, &point->Y, ctx)) goto err;
572 				}
573 			}
574 		else
575 			{
576 			if (x != NULL)
577 				{
578 				if (!BN_copy(x, &point->X)) goto err;
579 				}
580 			if (y != NULL)
581 				{
582 				if (!BN_copy(y, &point->Y)) goto err;
583 				}
584 			}
585 		}
586 	else
587 		{
588 		if (!BN_mod_inverse(Z_1, Z_, &group->field, ctx))
589 			{
590 			ECerr(EC_F_EC_GFP_SIMPLE_POINT_GET_AFFINE_COORDINATES, ERR_R_BN_LIB);
591 			goto err;
592 			}
593 
594 		if (group->meth->field_encode == 0)
595 			{
596 			/* field_sqr works on standard representation */
597 			if (!group->meth->field_sqr(group, Z_2, Z_1, ctx)) goto err;
598 			}
599 		else
600 			{
601 			if (!BN_mod_sqr(Z_2, Z_1, &group->field, ctx)) goto err;
602 			}
603 
604 		if (x != NULL)
605 			{
606 			/* in the Montgomery case, field_mul will cancel out Montgomery factor in X: */
607 			if (!group->meth->field_mul(group, x, &point->X, Z_2, ctx)) goto err;
608 			}
609 
610 		if (y != NULL)
611 			{
612 			if (group->meth->field_encode == 0)
613 				{
614 				/* field_mul works on standard representation */
615 				if (!group->meth->field_mul(group, Z_3, Z_2, Z_1, ctx)) goto err;
616 				}
617 			else
618 				{
619 				if (!BN_mod_mul(Z_3, Z_2, Z_1, &group->field, ctx)) goto err;
620 				}
621 
622 			/* in the Montgomery case, field_mul will cancel out Montgomery factor in Y: */
623 			if (!group->meth->field_mul(group, y, &point->Y, Z_3, ctx)) goto err;
624 			}
625 		}
626 
627 	ret = 1;
628 
629  err:
630 	BN_CTX_end(ctx);
631 	if (new_ctx != NULL)
632 		BN_CTX_free(new_ctx);
633 	return ret;
634 	}
635 
636 
ec_GFp_simple_set_compressed_coordinates(const EC_GROUP * group,EC_POINT * point,const BIGNUM * x_,int y_bit,BN_CTX * ctx)637 int ec_GFp_simple_set_compressed_coordinates(const EC_GROUP *group, EC_POINT *point,
638 	const BIGNUM *x_, int y_bit, BN_CTX *ctx)
639 	{
640 	BN_CTX *new_ctx = NULL;
641 	BIGNUM *tmp1, *tmp2, *x, *y;
642 	int ret = 0;
643 
644 	/* clear error queue*/
645 	ERR_clear_error();
646 
647 	if (ctx == NULL)
648 		{
649 		ctx = new_ctx = BN_CTX_new();
650 		if (ctx == NULL)
651 			return 0;
652 		}
653 
654 	y_bit = (y_bit != 0);
655 
656 	BN_CTX_start(ctx);
657 	tmp1 = BN_CTX_get(ctx);
658 	tmp2 = BN_CTX_get(ctx);
659 	x = BN_CTX_get(ctx);
660 	y = BN_CTX_get(ctx);
661 	if (y == NULL) goto err;
662 
663 	/* Recover y.  We have a Weierstrass equation
664 	 *     y^2 = x^3 + a*x + b,
665 	 * so  y  is one of the square roots of  x^3 + a*x + b.
666 	 */
667 
668 	/* tmp1 := x^3 */
669 	if (!BN_nnmod(x, x_, &group->field,ctx)) goto err;
670 	if (group->meth->field_decode == 0)
671 		{
672 		/* field_{sqr,mul} work on standard representation */
673 		if (!group->meth->field_sqr(group, tmp2, x_, ctx)) goto err;
674 		if (!group->meth->field_mul(group, tmp1, tmp2, x_, ctx)) goto err;
675 		}
676 	else
677 		{
678 		if (!BN_mod_sqr(tmp2, x_, &group->field, ctx)) goto err;
679 		if (!BN_mod_mul(tmp1, tmp2, x_, &group->field, ctx)) goto err;
680 		}
681 
682 	/* tmp1 := tmp1 + a*x */
683 	if (group->a_is_minus3)
684 		{
685 		if (!BN_mod_lshift1_quick(tmp2, x, &group->field)) goto err;
686 		if (!BN_mod_add_quick(tmp2, tmp2, x, &group->field)) goto err;
687 		if (!BN_mod_sub_quick(tmp1, tmp1, tmp2, &group->field)) goto err;
688 		}
689 	else
690 		{
691 		if (group->meth->field_decode)
692 			{
693 			if (!group->meth->field_decode(group, tmp2, &group->a, ctx)) goto err;
694 			if (!BN_mod_mul(tmp2, tmp2, x, &group->field, ctx)) goto err;
695 			}
696 		else
697 			{
698 			/* field_mul works on standard representation */
699 			if (!group->meth->field_mul(group, tmp2, &group->a, x, ctx)) goto err;
700 			}
701 
702 		if (!BN_mod_add_quick(tmp1, tmp1, tmp2, &group->field)) goto err;
703 		}
704 
705 	/* tmp1 := tmp1 + b */
706 	if (group->meth->field_decode)
707 		{
708 		if (!group->meth->field_decode(group, tmp2, &group->b, ctx)) goto err;
709 		if (!BN_mod_add_quick(tmp1, tmp1, tmp2, &group->field)) goto err;
710 		}
711 	else
712 		{
713 		if (!BN_mod_add_quick(tmp1, tmp1, &group->b, &group->field)) goto err;
714 		}
715 
716 	if (!BN_mod_sqrt(y, tmp1, &group->field, ctx))
717 		{
718 		unsigned long err = ERR_peek_last_error();
719 
720 		if (ERR_GET_LIB(err) == ERR_LIB_BN && ERR_GET_REASON(err) == BN_R_NOT_A_SQUARE)
721 			{
722 			ERR_clear_error();
723 			ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES, EC_R_INVALID_COMPRESSED_POINT);
724 			}
725 		else
726 			ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES, ERR_R_BN_LIB);
727 		goto err;
728 		}
729 
730 	if (y_bit != BN_is_odd(y))
731 		{
732 		if (BN_is_zero(y))
733 			{
734 			int kron;
735 
736 			kron = BN_kronecker(x, &group->field, ctx);
737 			if (kron == -2) goto err;
738 
739 			if (kron == 1)
740 				ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES, EC_R_INVALID_COMPRESSION_BIT);
741 			else
742 				/* BN_mod_sqrt() should have cought this error (not a square) */
743 				ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES, EC_R_INVALID_COMPRESSED_POINT);
744 			goto err;
745 			}
746 		if (!BN_usub(y, &group->field, y)) goto err;
747 		}
748 	if (y_bit != BN_is_odd(y))
749 		{
750 		ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES, ERR_R_INTERNAL_ERROR);
751 		goto err;
752 		}
753 
754 	if (!EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx)) goto err;
755 
756 	ret = 1;
757 
758  err:
759 	BN_CTX_end(ctx);
760 	if (new_ctx != NULL)
761 		BN_CTX_free(new_ctx);
762 	return ret;
763 	}
764 
765 
ec_GFp_simple_point2oct(const EC_GROUP * group,const EC_POINT * point,point_conversion_form_t form,unsigned char * buf,size_t len,BN_CTX * ctx)766 size_t ec_GFp_simple_point2oct(const EC_GROUP *group, const EC_POINT *point, point_conversion_form_t form,
767 	unsigned char *buf, size_t len, BN_CTX *ctx)
768 	{
769 	size_t ret;
770 	BN_CTX *new_ctx = NULL;
771 	int used_ctx = 0;
772 	BIGNUM *x, *y;
773 	size_t field_len, i, skip;
774 
775 	if ((form != POINT_CONVERSION_COMPRESSED)
776 		&& (form != POINT_CONVERSION_UNCOMPRESSED)
777 		&& (form != POINT_CONVERSION_HYBRID))
778 		{
779 		ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, EC_R_INVALID_FORM);
780 		goto err;
781 		}
782 
783 	if (EC_POINT_is_at_infinity(group, point))
784 		{
785 		/* encodes to a single 0 octet */
786 		if (buf != NULL)
787 			{
788 			if (len < 1)
789 				{
790 				ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, EC_R_BUFFER_TOO_SMALL);
791 				return 0;
792 				}
793 			buf[0] = 0;
794 			}
795 		return 1;
796 		}
797 
798 
799 	/* ret := required output buffer length */
800 	field_len = BN_num_bytes(&group->field);
801 	ret = (form == POINT_CONVERSION_COMPRESSED) ? 1 + field_len : 1 + 2*field_len;
802 
803 	/* if 'buf' is NULL, just return required length */
804 	if (buf != NULL)
805 		{
806 		if (len < ret)
807 			{
808 			ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, EC_R_BUFFER_TOO_SMALL);
809 			goto err;
810 			}
811 
812 		if (ctx == NULL)
813 			{
814 			ctx = new_ctx = BN_CTX_new();
815 			if (ctx == NULL)
816 				return 0;
817 			}
818 
819 		BN_CTX_start(ctx);
820 		used_ctx = 1;
821 		x = BN_CTX_get(ctx);
822 		y = BN_CTX_get(ctx);
823 		if (y == NULL) goto err;
824 
825 		if (!EC_POINT_get_affine_coordinates_GFp(group, point, x, y, ctx)) goto err;
826 
827 		if ((form == POINT_CONVERSION_COMPRESSED || form == POINT_CONVERSION_HYBRID) && BN_is_odd(y))
828 			buf[0] = form + 1;
829 		else
830 			buf[0] = form;
831 
832 		i = 1;
833 
834 		skip = field_len - BN_num_bytes(x);
835 		if (skip > field_len)
836 			{
837 			ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR);
838 			goto err;
839 			}
840 		while (skip > 0)
841 			{
842 			buf[i++] = 0;
843 			skip--;
844 			}
845 		skip = BN_bn2bin(x, buf + i);
846 		i += skip;
847 		if (i != 1 + field_len)
848 			{
849 			ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR);
850 			goto err;
851 			}
852 
853 		if (form == POINT_CONVERSION_UNCOMPRESSED || form == POINT_CONVERSION_HYBRID)
854 			{
855 			skip = field_len - BN_num_bytes(y);
856 			if (skip > field_len)
857 				{
858 				ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR);
859 				goto err;
860 				}
861 			while (skip > 0)
862 				{
863 				buf[i++] = 0;
864 				skip--;
865 				}
866 			skip = BN_bn2bin(y, buf + i);
867 			i += skip;
868 			}
869 
870 		if (i != ret)
871 			{
872 			ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR);
873 			goto err;
874 			}
875 		}
876 
877 	if (used_ctx)
878 		BN_CTX_end(ctx);
879 	if (new_ctx != NULL)
880 		BN_CTX_free(new_ctx);
881 	return ret;
882 
883  err:
884 	if (used_ctx)
885 		BN_CTX_end(ctx);
886 	if (new_ctx != NULL)
887 		BN_CTX_free(new_ctx);
888 	return 0;
889 	}
890 
891 
ec_GFp_simple_oct2point(const EC_GROUP * group,EC_POINT * point,const unsigned char * buf,size_t len,BN_CTX * ctx)892 int ec_GFp_simple_oct2point(const EC_GROUP *group, EC_POINT *point,
893 	const unsigned char *buf, size_t len, BN_CTX *ctx)
894 	{
895 	point_conversion_form_t form;
896 	int y_bit;
897 	BN_CTX *new_ctx = NULL;
898 	BIGNUM *x, *y;
899 	size_t field_len, enc_len;
900 	int ret = 0;
901 
902 	if (len == 0)
903 		{
904 		ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_BUFFER_TOO_SMALL);
905 		return 0;
906 		}
907 	form = buf[0];
908 	y_bit = form & 1;
909 	form = form & ~1U;
910 	if ((form != 0)	&& (form != POINT_CONVERSION_COMPRESSED)
911 		&& (form != POINT_CONVERSION_UNCOMPRESSED)
912 		&& (form != POINT_CONVERSION_HYBRID))
913 		{
914 		ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
915 		return 0;
916 		}
917 	if ((form == 0 || form == POINT_CONVERSION_UNCOMPRESSED) && y_bit)
918 		{
919 		ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
920 		return 0;
921 		}
922 
923 	if (form == 0)
924 		{
925 		if (len != 1)
926 			{
927 			ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
928 			return 0;
929 			}
930 
931 		return EC_POINT_set_to_infinity(group, point);
932 		}
933 
934 	field_len = BN_num_bytes(&group->field);
935 	enc_len = (form == POINT_CONVERSION_COMPRESSED) ? 1 + field_len : 1 + 2*field_len;
936 
937 	if (len != enc_len)
938 		{
939 		ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
940 		return 0;
941 		}
942 
943 	if (ctx == NULL)
944 		{
945 		ctx = new_ctx = BN_CTX_new();
946 		if (ctx == NULL)
947 			return 0;
948 		}
949 
950 	BN_CTX_start(ctx);
951 	x = BN_CTX_get(ctx);
952 	y = BN_CTX_get(ctx);
953 	if (y == NULL) goto err;
954 
955 	if (!BN_bin2bn(buf + 1, field_len, x)) goto err;
956 	if (BN_ucmp(x, &group->field) >= 0)
957 		{
958 		ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
959 		goto err;
960 		}
961 
962 	if (form == POINT_CONVERSION_COMPRESSED)
963 		{
964 		if (!EC_POINT_set_compressed_coordinates_GFp(group, point, x, y_bit, ctx)) goto err;
965 		}
966 	else
967 		{
968 		if (!BN_bin2bn(buf + 1 + field_len, field_len, y)) goto err;
969 		if (BN_ucmp(y, &group->field) >= 0)
970 			{
971 			ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
972 			goto err;
973 			}
974 		if (form == POINT_CONVERSION_HYBRID)
975 			{
976 			if (y_bit != BN_is_odd(y))
977 				{
978 				ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
979 				goto err;
980 				}
981 			}
982 
983 		if (!EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx)) goto err;
984 		}
985 
986 	if (!EC_POINT_is_on_curve(group, point, ctx)) /* test required by X9.62 */
987 		{
988 		ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_POINT_IS_NOT_ON_CURVE);
989 		goto err;
990 		}
991 
992 	ret = 1;
993 
994  err:
995 	BN_CTX_end(ctx);
996 	if (new_ctx != NULL)
997 		BN_CTX_free(new_ctx);
998 	return ret;
999 	}
1000 
1001 
ec_GFp_simple_add(const EC_GROUP * group,EC_POINT * r,const EC_POINT * a,const EC_POINT * b,BN_CTX * ctx)1002 int ec_GFp_simple_add(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a, const EC_POINT *b, BN_CTX *ctx)
1003 	{
1004 	int (*field_mul)(const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *);
1005 	int (*field_sqr)(const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
1006 	const BIGNUM *p;
1007 	BN_CTX *new_ctx = NULL;
1008 	BIGNUM *n0, *n1, *n2, *n3, *n4, *n5, *n6;
1009 	int ret = 0;
1010 
1011 	if (a == b)
1012 		return EC_POINT_dbl(group, r, a, ctx);
1013 	if (EC_POINT_is_at_infinity(group, a))
1014 		return EC_POINT_copy(r, b);
1015 	if (EC_POINT_is_at_infinity(group, b))
1016 		return EC_POINT_copy(r, a);
1017 
1018 	field_mul = group->meth->field_mul;
1019 	field_sqr = group->meth->field_sqr;
1020 	p = &group->field;
1021 
1022 	if (ctx == NULL)
1023 		{
1024 		ctx = new_ctx = BN_CTX_new();
1025 		if (ctx == NULL)
1026 			return 0;
1027 		}
1028 
1029 	BN_CTX_start(ctx);
1030 	n0 = BN_CTX_get(ctx);
1031 	n1 = BN_CTX_get(ctx);
1032 	n2 = BN_CTX_get(ctx);
1033 	n3 = BN_CTX_get(ctx);
1034 	n4 = BN_CTX_get(ctx);
1035 	n5 = BN_CTX_get(ctx);
1036 	n6 = BN_CTX_get(ctx);
1037 	if (n6 == NULL) goto end;
1038 
1039 	/* Note that in this function we must not read components of 'a' or 'b'
1040 	 * once we have written the corresponding components of 'r'.
1041 	 * ('r' might be one of 'a' or 'b'.)
1042 	 */
1043 
1044 	/* n1, n2 */
1045 	if (b->Z_is_one)
1046 		{
1047 		if (!BN_copy(n1, &a->X)) goto end;
1048 		if (!BN_copy(n2, &a->Y)) goto end;
1049 		/* n1 = X_a */
1050 		/* n2 = Y_a */
1051 		}
1052 	else
1053 		{
1054 		if (!field_sqr(group, n0, &b->Z, ctx)) goto end;
1055 		if (!field_mul(group, n1, &a->X, n0, ctx)) goto end;
1056 		/* n1 = X_a * Z_b^2 */
1057 
1058 		if (!field_mul(group, n0, n0, &b->Z, ctx)) goto end;
1059 		if (!field_mul(group, n2, &a->Y, n0, ctx)) goto end;
1060 		/* n2 = Y_a * Z_b^3 */
1061 		}
1062 
1063 	/* n3, n4 */
1064 	if (a->Z_is_one)
1065 		{
1066 		if (!BN_copy(n3, &b->X)) goto end;
1067 		if (!BN_copy(n4, &b->Y)) goto end;
1068 		/* n3 = X_b */
1069 		/* n4 = Y_b */
1070 		}
1071 	else
1072 		{
1073 		if (!field_sqr(group, n0, &a->Z, ctx)) goto end;
1074 		if (!field_mul(group, n3, &b->X, n0, ctx)) goto end;
1075 		/* n3 = X_b * Z_a^2 */
1076 
1077 		if (!field_mul(group, n0, n0, &a->Z, ctx)) goto end;
1078 		if (!field_mul(group, n4, &b->Y, n0, ctx)) goto end;
1079 		/* n4 = Y_b * Z_a^3 */
1080 		}
1081 
1082 	/* n5, n6 */
1083 	if (!BN_mod_sub_quick(n5, n1, n3, p)) goto end;
1084 	if (!BN_mod_sub_quick(n6, n2, n4, p)) goto end;
1085 	/* n5 = n1 - n3 */
1086 	/* n6 = n2 - n4 */
1087 
1088 	if (BN_is_zero(n5))
1089 		{
1090 		if (BN_is_zero(n6))
1091 			{
1092 			/* a is the same point as b */
1093 			BN_CTX_end(ctx);
1094 			ret = EC_POINT_dbl(group, r, a, ctx);
1095 			ctx = NULL;
1096 			goto end;
1097 			}
1098 		else
1099 			{
1100 			/* a is the inverse of b */
1101 			BN_zero(&r->Z);
1102 			r->Z_is_one = 0;
1103 			ret = 1;
1104 			goto end;
1105 			}
1106 		}
1107 
1108 	/* 'n7', 'n8' */
1109 	if (!BN_mod_add_quick(n1, n1, n3, p)) goto end;
1110 	if (!BN_mod_add_quick(n2, n2, n4, p)) goto end;
1111 	/* 'n7' = n1 + n3 */
1112 	/* 'n8' = n2 + n4 */
1113 
1114 	/* Z_r */
1115 	if (a->Z_is_one && b->Z_is_one)
1116 		{
1117 		if (!BN_copy(&r->Z, n5)) goto end;
1118 		}
1119 	else
1120 		{
1121 		if (a->Z_is_one)
1122 			{ if (!BN_copy(n0, &b->Z)) goto end; }
1123 		else if (b->Z_is_one)
1124 			{ if (!BN_copy(n0, &a->Z)) goto end; }
1125 		else
1126 			{ if (!field_mul(group, n0, &a->Z, &b->Z, ctx)) goto end; }
1127 		if (!field_mul(group, &r->Z, n0, n5, ctx)) goto end;
1128 		}
1129 	r->Z_is_one = 0;
1130 	/* Z_r = Z_a * Z_b * n5 */
1131 
1132 	/* X_r */
1133 	if (!field_sqr(group, n0, n6, ctx)) goto end;
1134 	if (!field_sqr(group, n4, n5, ctx)) goto end;
1135 	if (!field_mul(group, n3, n1, n4, ctx)) goto end;
1136 	if (!BN_mod_sub_quick(&r->X, n0, n3, p)) goto end;
1137 	/* X_r = n6^2 - n5^2 * 'n7' */
1138 
1139 	/* 'n9' */
1140 	if (!BN_mod_lshift1_quick(n0, &r->X, p)) goto end;
1141 	if (!BN_mod_sub_quick(n0, n3, n0, p)) goto end;
1142 	/* n9 = n5^2 * 'n7' - 2 * X_r */
1143 
1144 	/* Y_r */
1145 	if (!field_mul(group, n0, n0, n6, ctx)) goto end;
1146 	if (!field_mul(group, n5, n4, n5, ctx)) goto end; /* now n5 is n5^3 */
1147 	if (!field_mul(group, n1, n2, n5, ctx)) goto end;
1148 	if (!BN_mod_sub_quick(n0, n0, n1, p)) goto end;
1149 	if (BN_is_odd(n0))
1150 		if (!BN_add(n0, n0, p)) goto end;
1151 	/* now  0 <= n0 < 2*p,  and n0 is even */
1152 	if (!BN_rshift1(&r->Y, n0)) goto end;
1153 	/* Y_r = (n6 * 'n9' - 'n8' * 'n5^3') / 2 */
1154 
1155 	ret = 1;
1156 
1157  end:
1158 	if (ctx) /* otherwise we already called BN_CTX_end */
1159 		BN_CTX_end(ctx);
1160 	if (new_ctx != NULL)
1161 		BN_CTX_free(new_ctx);
1162 	return ret;
1163 	}
1164 
1165 
ec_GFp_simple_dbl(const EC_GROUP * group,EC_POINT * r,const EC_POINT * a,BN_CTX * ctx)1166 int ec_GFp_simple_dbl(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a, BN_CTX *ctx)
1167 	{
1168 	int (*field_mul)(const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *);
1169 	int (*field_sqr)(const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
1170 	const BIGNUM *p;
1171 	BN_CTX *new_ctx = NULL;
1172 	BIGNUM *n0, *n1, *n2, *n3;
1173 	int ret = 0;
1174 
1175 	if (EC_POINT_is_at_infinity(group, a))
1176 		{
1177 		BN_zero(&r->Z);
1178 		r->Z_is_one = 0;
1179 		return 1;
1180 		}
1181 
1182 	field_mul = group->meth->field_mul;
1183 	field_sqr = group->meth->field_sqr;
1184 	p = &group->field;
1185 
1186 	if (ctx == NULL)
1187 		{
1188 		ctx = new_ctx = BN_CTX_new();
1189 		if (ctx == NULL)
1190 			return 0;
1191 		}
1192 
1193 	BN_CTX_start(ctx);
1194 	n0 = BN_CTX_get(ctx);
1195 	n1 = BN_CTX_get(ctx);
1196 	n2 = BN_CTX_get(ctx);
1197 	n3 = BN_CTX_get(ctx);
1198 	if (n3 == NULL) goto err;
1199 
1200 	/* Note that in this function we must not read components of 'a'
1201 	 * once we have written the corresponding components of 'r'.
1202 	 * ('r' might the same as 'a'.)
1203 	 */
1204 
1205 	/* n1 */
1206 	if (a->Z_is_one)
1207 		{
1208 		if (!field_sqr(group, n0, &a->X, ctx)) goto err;
1209 		if (!BN_mod_lshift1_quick(n1, n0, p)) goto err;
1210 		if (!BN_mod_add_quick(n0, n0, n1, p)) goto err;
1211 		if (!BN_mod_add_quick(n1, n0, &group->a, p)) goto err;
1212 		/* n1 = 3 * X_a^2 + a_curve */
1213 		}
1214 	else if (group->a_is_minus3)
1215 		{
1216 		if (!field_sqr(group, n1, &a->Z, ctx)) goto err;
1217 		if (!BN_mod_add_quick(n0, &a->X, n1, p)) goto err;
1218 		if (!BN_mod_sub_quick(n2, &a->X, n1, p)) goto err;
1219 		if (!field_mul(group, n1, n0, n2, ctx)) goto err;
1220 		if (!BN_mod_lshift1_quick(n0, n1, p)) goto err;
1221 		if (!BN_mod_add_quick(n1, n0, n1, p)) goto err;
1222 		/* n1 = 3 * (X_a + Z_a^2) * (X_a - Z_a^2)
1223 		 *    = 3 * X_a^2 - 3 * Z_a^4 */
1224 		}
1225 	else
1226 		{
1227 		if (!field_sqr(group, n0, &a->X, ctx)) goto err;
1228 		if (!BN_mod_lshift1_quick(n1, n0, p)) goto err;
1229 		if (!BN_mod_add_quick(n0, n0, n1, p)) goto err;
1230 		if (!field_sqr(group, n1, &a->Z, ctx)) goto err;
1231 		if (!field_sqr(group, n1, n1, ctx)) goto err;
1232 		if (!field_mul(group, n1, n1, &group->a, ctx)) goto err;
1233 		if (!BN_mod_add_quick(n1, n1, n0, p)) goto err;
1234 		/* n1 = 3 * X_a^2 + a_curve * Z_a^4 */
1235 		}
1236 
1237 	/* Z_r */
1238 	if (a->Z_is_one)
1239 		{
1240 		if (!BN_copy(n0, &a->Y)) goto err;
1241 		}
1242 	else
1243 		{
1244 		if (!field_mul(group, n0, &a->Y, &a->Z, ctx)) goto err;
1245 		}
1246 	if (!BN_mod_lshift1_quick(&r->Z, n0, p)) goto err;
1247 	r->Z_is_one = 0;
1248 	/* Z_r = 2 * Y_a * Z_a */
1249 
1250 	/* n2 */
1251 	if (!field_sqr(group, n3, &a->Y, ctx)) goto err;
1252 	if (!field_mul(group, n2, &a->X, n3, ctx)) goto err;
1253 	if (!BN_mod_lshift_quick(n2, n2, 2, p)) goto err;
1254 	/* n2 = 4 * X_a * Y_a^2 */
1255 
1256 	/* X_r */
1257 	if (!BN_mod_lshift1_quick(n0, n2, p)) goto err;
1258 	if (!field_sqr(group, &r->X, n1, ctx)) goto err;
1259 	if (!BN_mod_sub_quick(&r->X, &r->X, n0, p)) goto err;
1260 	/* X_r = n1^2 - 2 * n2 */
1261 
1262 	/* n3 */
1263 	if (!field_sqr(group, n0, n3, ctx)) goto err;
1264 	if (!BN_mod_lshift_quick(n3, n0, 3, p)) goto err;
1265 	/* n3 = 8 * Y_a^4 */
1266 
1267 	/* Y_r */
1268 	if (!BN_mod_sub_quick(n0, n2, &r->X, p)) goto err;
1269 	if (!field_mul(group, n0, n1, n0, ctx)) goto err;
1270 	if (!BN_mod_sub_quick(&r->Y, n0, n3, p)) goto err;
1271 	/* Y_r = n1 * (n2 - X_r) - n3 */
1272 
1273 	ret = 1;
1274 
1275  err:
1276 	BN_CTX_end(ctx);
1277 	if (new_ctx != NULL)
1278 		BN_CTX_free(new_ctx);
1279 	return ret;
1280 	}
1281 
1282 
ec_GFp_simple_invert(const EC_GROUP * group,EC_POINT * point,BN_CTX * ctx)1283 int ec_GFp_simple_invert(const EC_GROUP *group, EC_POINT *point, BN_CTX *ctx)
1284 	{
1285 	if (EC_POINT_is_at_infinity(group, point) || BN_is_zero(&point->Y))
1286 		/* point is its own inverse */
1287 		return 1;
1288 
1289 	return BN_usub(&point->Y, &group->field, &point->Y);
1290 	}
1291 
1292 
ec_GFp_simple_is_at_infinity(const EC_GROUP * group,const EC_POINT * point)1293 int ec_GFp_simple_is_at_infinity(const EC_GROUP *group, const EC_POINT *point)
1294 	{
1295 	return BN_is_zero(&point->Z);
1296 	}
1297 
1298 
ec_GFp_simple_is_on_curve(const EC_GROUP * group,const EC_POINT * point,BN_CTX * ctx)1299 int ec_GFp_simple_is_on_curve(const EC_GROUP *group, const EC_POINT *point, BN_CTX *ctx)
1300 	{
1301 	int (*field_mul)(const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *);
1302 	int (*field_sqr)(const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
1303 	const BIGNUM *p;
1304 	BN_CTX *new_ctx = NULL;
1305 	BIGNUM *rh, *tmp, *Z4, *Z6;
1306 	int ret = -1;
1307 
1308 	if (EC_POINT_is_at_infinity(group, point))
1309 		return 1;
1310 
1311 	field_mul = group->meth->field_mul;
1312 	field_sqr = group->meth->field_sqr;
1313 	p = &group->field;
1314 
1315 	if (ctx == NULL)
1316 		{
1317 		ctx = new_ctx = BN_CTX_new();
1318 		if (ctx == NULL)
1319 			return -1;
1320 		}
1321 
1322 	BN_CTX_start(ctx);
1323 	rh = BN_CTX_get(ctx);
1324 	tmp = BN_CTX_get(ctx);
1325 	Z4 = BN_CTX_get(ctx);
1326 	Z6 = BN_CTX_get(ctx);
1327 	if (Z6 == NULL) goto err;
1328 
1329 	/* We have a curve defined by a Weierstrass equation
1330 	 *      y^2 = x^3 + a*x + b.
1331 	 * The point to consider is given in Jacobian projective coordinates
1332 	 * where  (X, Y, Z)  represents  (x, y) = (X/Z^2, Y/Z^3).
1333 	 * Substituting this and multiplying by  Z^6  transforms the above equation into
1334 	 *      Y^2 = X^3 + a*X*Z^4 + b*Z^6.
1335 	 * To test this, we add up the right-hand side in 'rh'.
1336 	 */
1337 
1338 	/* rh := X^2 */
1339 	if (!field_sqr(group, rh, &point->X, ctx)) goto err;
1340 
1341 	if (!point->Z_is_one)
1342 		{
1343 		if (!field_sqr(group, tmp, &point->Z, ctx)) goto err;
1344 		if (!field_sqr(group, Z4, tmp, ctx)) goto err;
1345 		if (!field_mul(group, Z6, Z4, tmp, ctx)) goto err;
1346 
1347 		/* rh := (rh + a*Z^4)*X */
1348 		if (group->a_is_minus3)
1349 			{
1350 			if (!BN_mod_lshift1_quick(tmp, Z4, p)) goto err;
1351 			if (!BN_mod_add_quick(tmp, tmp, Z4, p)) goto err;
1352 			if (!BN_mod_sub_quick(rh, rh, tmp, p)) goto err;
1353 			if (!field_mul(group, rh, rh, &point->X, ctx)) goto err;
1354 			}
1355 		else
1356 			{
1357 			if (!field_mul(group, tmp, Z4, &group->a, ctx)) goto err;
1358 			if (!BN_mod_add_quick(rh, rh, tmp, p)) goto err;
1359 			if (!field_mul(group, rh, rh, &point->X, ctx)) goto err;
1360 			}
1361 
1362 		/* rh := rh + b*Z^6 */
1363 		if (!field_mul(group, tmp, &group->b, Z6, ctx)) goto err;
1364 		if (!BN_mod_add_quick(rh, rh, tmp, p)) goto err;
1365 		}
1366 	else
1367 		{
1368 		/* point->Z_is_one */
1369 
1370 		/* rh := (rh + a)*X */
1371 		if (!BN_mod_add_quick(rh, rh, &group->a, p)) goto err;
1372 		if (!field_mul(group, rh, rh, &point->X, ctx)) goto err;
1373 		/* rh := rh + b */
1374 		if (!BN_mod_add_quick(rh, rh, &group->b, p)) goto err;
1375 		}
1376 
1377 	/* 'lh' := Y^2 */
1378 	if (!field_sqr(group, tmp, &point->Y, ctx)) goto err;
1379 
1380 	ret = (0 == BN_ucmp(tmp, rh));
1381 
1382  err:
1383 	BN_CTX_end(ctx);
1384 	if (new_ctx != NULL)
1385 		BN_CTX_free(new_ctx);
1386 	return ret;
1387 	}
1388 
1389 
ec_GFp_simple_cmp(const EC_GROUP * group,const EC_POINT * a,const EC_POINT * b,BN_CTX * ctx)1390 int ec_GFp_simple_cmp(const EC_GROUP *group, const EC_POINT *a, const EC_POINT *b, BN_CTX *ctx)
1391 	{
1392 	/* return values:
1393 	 *  -1   error
1394 	 *   0   equal (in affine coordinates)
1395 	 *   1   not equal
1396 	 */
1397 
1398 	int (*field_mul)(const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *);
1399 	int (*field_sqr)(const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
1400 	BN_CTX *new_ctx = NULL;
1401 	BIGNUM *tmp1, *tmp2, *Za23, *Zb23;
1402 	const BIGNUM *tmp1_, *tmp2_;
1403 	int ret = -1;
1404 
1405 	if (EC_POINT_is_at_infinity(group, a))
1406 		{
1407 		return EC_POINT_is_at_infinity(group, b) ? 0 : 1;
1408 		}
1409 
1410 	if (a->Z_is_one && b->Z_is_one)
1411 		{
1412 		return ((BN_cmp(&a->X, &b->X) == 0) && BN_cmp(&a->Y, &b->Y) == 0) ? 0 : 1;
1413 		}
1414 
1415 	field_mul = group->meth->field_mul;
1416 	field_sqr = group->meth->field_sqr;
1417 
1418 	if (ctx == NULL)
1419 		{
1420 		ctx = new_ctx = BN_CTX_new();
1421 		if (ctx == NULL)
1422 			return -1;
1423 		}
1424 
1425 	BN_CTX_start(ctx);
1426 	tmp1 = BN_CTX_get(ctx);
1427 	tmp2 = BN_CTX_get(ctx);
1428 	Za23 = BN_CTX_get(ctx);
1429 	Zb23 = BN_CTX_get(ctx);
1430 	if (Zb23 == NULL) goto end;
1431 
1432 	/* We have to decide whether
1433 	 *     (X_a/Z_a^2, Y_a/Z_a^3) = (X_b/Z_b^2, Y_b/Z_b^3),
1434 	 * or equivalently, whether
1435 	 *     (X_a*Z_b^2, Y_a*Z_b^3) = (X_b*Z_a^2, Y_b*Z_a^3).
1436 	 */
1437 
1438 	if (!b->Z_is_one)
1439 		{
1440 		if (!field_sqr(group, Zb23, &b->Z, ctx)) goto end;
1441 		if (!field_mul(group, tmp1, &a->X, Zb23, ctx)) goto end;
1442 		tmp1_ = tmp1;
1443 		}
1444 	else
1445 		tmp1_ = &a->X;
1446 	if (!a->Z_is_one)
1447 		{
1448 		if (!field_sqr(group, Za23, &a->Z, ctx)) goto end;
1449 		if (!field_mul(group, tmp2, &b->X, Za23, ctx)) goto end;
1450 		tmp2_ = tmp2;
1451 		}
1452 	else
1453 		tmp2_ = &b->X;
1454 
1455 	/* compare  X_a*Z_b^2  with  X_b*Z_a^2 */
1456 	if (BN_cmp(tmp1_, tmp2_) != 0)
1457 		{
1458 		ret = 1; /* points differ */
1459 		goto end;
1460 		}
1461 
1462 
1463 	if (!b->Z_is_one)
1464 		{
1465 		if (!field_mul(group, Zb23, Zb23, &b->Z, ctx)) goto end;
1466 		if (!field_mul(group, tmp1, &a->Y, Zb23, ctx)) goto end;
1467 		/* tmp1_ = tmp1 */
1468 		}
1469 	else
1470 		tmp1_ = &a->Y;
1471 	if (!a->Z_is_one)
1472 		{
1473 		if (!field_mul(group, Za23, Za23, &a->Z, ctx)) goto end;
1474 		if (!field_mul(group, tmp2, &b->Y, Za23, ctx)) goto end;
1475 		/* tmp2_ = tmp2 */
1476 		}
1477 	else
1478 		tmp2_ = &b->Y;
1479 
1480 	/* compare  Y_a*Z_b^3  with  Y_b*Z_a^3 */
1481 	if (BN_cmp(tmp1_, tmp2_) != 0)
1482 		{
1483 		ret = 1; /* points differ */
1484 		goto end;
1485 		}
1486 
1487 	/* points are equal */
1488 	ret = 0;
1489 
1490  end:
1491 	BN_CTX_end(ctx);
1492 	if (new_ctx != NULL)
1493 		BN_CTX_free(new_ctx);
1494 	return ret;
1495 	}
1496 
1497 
ec_GFp_simple_make_affine(const EC_GROUP * group,EC_POINT * point,BN_CTX * ctx)1498 int ec_GFp_simple_make_affine(const EC_GROUP *group, EC_POINT *point, BN_CTX *ctx)
1499 	{
1500 	BN_CTX *new_ctx = NULL;
1501 	BIGNUM *x, *y;
1502 	int ret = 0;
1503 
1504 	if (point->Z_is_one || EC_POINT_is_at_infinity(group, point))
1505 		return 1;
1506 
1507 	if (ctx == NULL)
1508 		{
1509 		ctx = new_ctx = BN_CTX_new();
1510 		if (ctx == NULL)
1511 			return 0;
1512 		}
1513 
1514 	BN_CTX_start(ctx);
1515 	x = BN_CTX_get(ctx);
1516 	y = BN_CTX_get(ctx);
1517 	if (y == NULL) goto err;
1518 
1519 	if (!EC_POINT_get_affine_coordinates_GFp(group, point, x, y, ctx)) goto err;
1520 	if (!EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx)) goto err;
1521 	if (!point->Z_is_one)
1522 		{
1523 		ECerr(EC_F_EC_GFP_SIMPLE_MAKE_AFFINE, ERR_R_INTERNAL_ERROR);
1524 		goto err;
1525 		}
1526 
1527 	ret = 1;
1528 
1529  err:
1530 	BN_CTX_end(ctx);
1531 	if (new_ctx != NULL)
1532 		BN_CTX_free(new_ctx);
1533 	return ret;
1534 	}
1535 
1536 
ec_GFp_simple_points_make_affine(const EC_GROUP * group,size_t num,EC_POINT * points[],BN_CTX * ctx)1537 int ec_GFp_simple_points_make_affine(const EC_GROUP *group, size_t num, EC_POINT *points[], BN_CTX *ctx)
1538 	{
1539 	BN_CTX *new_ctx = NULL;
1540 	BIGNUM *tmp0, *tmp1;
1541 	size_t pow2 = 0;
1542 	BIGNUM **heap = NULL;
1543 	size_t i;
1544 	int ret = 0;
1545 
1546 	if (num == 0)
1547 		return 1;
1548 
1549 	if (ctx == NULL)
1550 		{
1551 		ctx = new_ctx = BN_CTX_new();
1552 		if (ctx == NULL)
1553 			return 0;
1554 		}
1555 
1556 	BN_CTX_start(ctx);
1557 	tmp0 = BN_CTX_get(ctx);
1558 	tmp1 = BN_CTX_get(ctx);
1559 	if (tmp0  == NULL || tmp1 == NULL) goto err;
1560 
1561 	/* Before converting the individual points, compute inverses of all Z values.
1562 	 * Modular inversion is rather slow, but luckily we can do with a single
1563 	 * explicit inversion, plus about 3 multiplications per input value.
1564 	 */
1565 
1566 	pow2 = 1;
1567 	while (num > pow2)
1568 		pow2 <<= 1;
1569 	/* Now pow2 is the smallest power of 2 satifsying pow2 >= num.
1570 	 * We need twice that. */
1571 	pow2 <<= 1;
1572 
1573 	heap = OPENSSL_malloc(pow2 * sizeof heap[0]);
1574 	if (heap == NULL) goto err;
1575 
1576 	/* The array is used as a binary tree, exactly as in heapsort:
1577 	 *
1578 	 *                               heap[1]
1579 	 *                 heap[2]                     heap[3]
1580 	 *          heap[4]       heap[5]       heap[6]       heap[7]
1581 	 *   heap[8]heap[9] heap[10]heap[11] heap[12]heap[13] heap[14] heap[15]
1582 	 *
1583 	 * We put the Z's in the last line;
1584 	 * then we set each other node to the product of its two child-nodes (where
1585 	 * empty or 0 entries are treated as ones);
1586 	 * then we invert heap[1];
1587 	 * then we invert each other node by replacing it by the product of its
1588 	 * parent (after inversion) and its sibling (before inversion).
1589 	 */
1590 	heap[0] = NULL;
1591 	for (i = pow2/2 - 1; i > 0; i--)
1592 		heap[i] = NULL;
1593 	for (i = 0; i < num; i++)
1594 		heap[pow2/2 + i] = &points[i]->Z;
1595 	for (i = pow2/2 + num; i < pow2; i++)
1596 		heap[i] = NULL;
1597 
1598 	/* set each node to the product of its children */
1599 	for (i = pow2/2 - 1; i > 0; i--)
1600 		{
1601 		heap[i] = BN_new();
1602 		if (heap[i] == NULL) goto err;
1603 
1604 		if (heap[2*i] != NULL)
1605 			{
1606 			if ((heap[2*i + 1] == NULL) || BN_is_zero(heap[2*i + 1]))
1607 				{
1608 				if (!BN_copy(heap[i], heap[2*i])) goto err;
1609 				}
1610 			else
1611 				{
1612 				if (BN_is_zero(heap[2*i]))
1613 					{
1614 					if (!BN_copy(heap[i], heap[2*i + 1])) goto err;
1615 					}
1616 				else
1617 					{
1618 					if (!group->meth->field_mul(group, heap[i],
1619 						heap[2*i], heap[2*i + 1], ctx)) goto err;
1620 					}
1621 				}
1622 			}
1623 		}
1624 
1625 	/* invert heap[1] */
1626 	if (!BN_is_zero(heap[1]))
1627 		{
1628 		if (!BN_mod_inverse(heap[1], heap[1], &group->field, ctx))
1629 			{
1630 			ECerr(EC_F_EC_GFP_SIMPLE_POINTS_MAKE_AFFINE, ERR_R_BN_LIB);
1631 			goto err;
1632 			}
1633 		}
1634 	if (group->meth->field_encode != 0)
1635 		{
1636 		/* in the Montgomery case, we just turned  R*H  (representing H)
1637 		 * into  1/(R*H),  but we need  R*(1/H)  (representing 1/H);
1638 		 * i.e. we have need to multiply by the Montgomery factor twice */
1639 		if (!group->meth->field_encode(group, heap[1], heap[1], ctx)) goto err;
1640 		if (!group->meth->field_encode(group, heap[1], heap[1], ctx)) goto err;
1641 		}
1642 
1643 	/* set other heap[i]'s to their inverses */
1644 	for (i = 2; i < pow2/2 + num; i += 2)
1645 		{
1646 		/* i is even */
1647 		if ((heap[i + 1] != NULL) && !BN_is_zero(heap[i + 1]))
1648 			{
1649 			if (!group->meth->field_mul(group, tmp0, heap[i/2], heap[i + 1], ctx)) goto err;
1650 			if (!group->meth->field_mul(group, tmp1, heap[i/2], heap[i], ctx)) goto err;
1651 			if (!BN_copy(heap[i], tmp0)) goto err;
1652 			if (!BN_copy(heap[i + 1], tmp1)) goto err;
1653 			}
1654 		else
1655 			{
1656 			if (!BN_copy(heap[i], heap[i/2])) goto err;
1657 			}
1658 		}
1659 
1660 	/* we have replaced all non-zero Z's by their inverses, now fix up all the points */
1661 	for (i = 0; i < num; i++)
1662 		{
1663 		EC_POINT *p = points[i];
1664 
1665 		if (!BN_is_zero(&p->Z))
1666 			{
1667 			/* turn  (X, Y, 1/Z)  into  (X/Z^2, Y/Z^3, 1) */
1668 
1669 			if (!group->meth->field_sqr(group, tmp1, &p->Z, ctx)) goto err;
1670 			if (!group->meth->field_mul(group, &p->X, &p->X, tmp1, ctx)) goto err;
1671 
1672 			if (!group->meth->field_mul(group, tmp1, tmp1, &p->Z, ctx)) goto err;
1673 			if (!group->meth->field_mul(group, &p->Y, &p->Y, tmp1, ctx)) goto err;
1674 
1675 			if (group->meth->field_set_to_one != 0)
1676 				{
1677 				if (!group->meth->field_set_to_one(group, &p->Z, ctx)) goto err;
1678 				}
1679 			else
1680 				{
1681 				if (!BN_one(&p->Z)) goto err;
1682 				}
1683 			p->Z_is_one = 1;
1684 			}
1685 		}
1686 
1687 	ret = 1;
1688 
1689  err:
1690 	BN_CTX_end(ctx);
1691 	if (new_ctx != NULL)
1692 		BN_CTX_free(new_ctx);
1693 	if (heap != NULL)
1694 		{
1695 		/* heap[pow2/2] .. heap[pow2-1] have not been allocated locally! */
1696 		for (i = pow2/2 - 1; i > 0; i--)
1697 			{
1698 			if (heap[i] != NULL)
1699 				BN_clear_free(heap[i]);
1700 			}
1701 		OPENSSL_free(heap);
1702 		}
1703 	return ret;
1704 	}
1705 
1706 
ec_GFp_simple_field_mul(const EC_GROUP * group,BIGNUM * r,const BIGNUM * a,const BIGNUM * b,BN_CTX * ctx)1707 int ec_GFp_simple_field_mul(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
1708 	{
1709 	return BN_mod_mul(r, a, b, &group->field, ctx);
1710 	}
1711 
1712 
ec_GFp_simple_field_sqr(const EC_GROUP * group,BIGNUM * r,const BIGNUM * a,BN_CTX * ctx)1713 int ec_GFp_simple_field_sqr(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, BN_CTX *ctx)
1714 	{
1715 	return BN_mod_sqr(r, a, &group->field, ctx);
1716 	}
1717