xref: /openbsd-src/lib/libcrypto/ec/ec_lib.c (revision 24bb5fcea3ed904bc467217bdaadb5dfc618d5bf)
1 /* $OpenBSD: ec_lib.c,v 1.39 2021/04/20 17:29:21 tb Exp $ */
2 /*
3  * Originally written by Bodo Moeller for the OpenSSL project.
4  */
5 /* ====================================================================
6  * Copyright (c) 1998-2003 The OpenSSL Project.  All rights reserved.
7  *
8  * Redistribution and use in source and binary forms, with or without
9  * modification, are permitted provided that the following conditions
10  * are met:
11  *
12  * 1. Redistributions of source code must retain the above copyright
13  *    notice, this list of conditions and the following disclaimer.
14  *
15  * 2. Redistributions in binary form must reproduce the above copyright
16  *    notice, this list of conditions and the following disclaimer in
17  *    the documentation and/or other materials provided with the
18  *    distribution.
19  *
20  * 3. All advertising materials mentioning features or use of this
21  *    software must display the following acknowledgment:
22  *    "This product includes software developed by the OpenSSL Project
23  *    for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
24  *
25  * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
26  *    endorse or promote products derived from this software without
27  *    prior written permission. For written permission, please contact
28  *    openssl-core@openssl.org.
29  *
30  * 5. Products derived from this software may not be called "OpenSSL"
31  *    nor may "OpenSSL" appear in their names without prior written
32  *    permission of the OpenSSL Project.
33  *
34  * 6. Redistributions of any form whatsoever must retain the following
35  *    acknowledgment:
36  *    "This product includes software developed by the OpenSSL Project
37  *    for use in the OpenSSL Toolkit (http://www.openssl.org/)"
38  *
39  * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
40  * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
41  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
42  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OpenSSL PROJECT OR
43  * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
44  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
45  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
46  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
47  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
48  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
49  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
50  * OF THE POSSIBILITY OF SUCH DAMAGE.
51  * ====================================================================
52  *
53  * This product includes cryptographic software written by Eric Young
54  * (eay@cryptsoft.com).  This product includes software written by Tim
55  * Hudson (tjh@cryptsoft.com).
56  *
57  */
58 /* ====================================================================
59  * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED.
60  * Binary polynomial ECC support in OpenSSL originally developed by
61  * SUN MICROSYSTEMS, INC., and contributed to the OpenSSL project.
62  */
63 
64 #include <string.h>
65 
66 #include <openssl/opensslconf.h>
67 
68 #include <openssl/err.h>
69 #include <openssl/opensslv.h>
70 
71 #include "bn_lcl.h"
72 #include "ec_lcl.h"
73 
74 /* functions for EC_GROUP objects */
75 
76 EC_GROUP *
77 EC_GROUP_new(const EC_METHOD * meth)
78 {
79 	EC_GROUP *ret;
80 
81 	if (meth == NULL) {
82 		ECerror(EC_R_SLOT_FULL);
83 		return NULL;
84 	}
85 	if (meth->group_init == 0) {
86 		ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
87 		return NULL;
88 	}
89 	ret = malloc(sizeof *ret);
90 	if (ret == NULL) {
91 		ECerror(ERR_R_MALLOC_FAILURE);
92 		return NULL;
93 	}
94 	ret->meth = meth;
95 
96 	ret->extra_data = NULL;
97 
98 	ret->generator = NULL;
99 	BN_init(&ret->order);
100 	BN_init(&ret->cofactor);
101 
102 	ret->curve_name = 0;
103 	ret->asn1_flag = 0;
104 	ret->asn1_form = POINT_CONVERSION_UNCOMPRESSED;
105 
106 	ret->seed = NULL;
107 	ret->seed_len = 0;
108 
109 	if (!meth->group_init(ret)) {
110 		free(ret);
111 		return NULL;
112 	}
113 	return ret;
114 }
115 
116 
117 void
118 EC_GROUP_free(EC_GROUP * group)
119 {
120 	if (!group)
121 		return;
122 
123 	if (group->meth->group_finish != 0)
124 		group->meth->group_finish(group);
125 
126 	EC_EX_DATA_free_all_data(&group->extra_data);
127 
128 	EC_POINT_free(group->generator);
129 	BN_free(&group->order);
130 	BN_free(&group->cofactor);
131 
132 	free(group->seed);
133 
134 	free(group);
135 }
136 
137 
138 void
139 EC_GROUP_clear_free(EC_GROUP * group)
140 {
141 	if (!group)
142 		return;
143 
144 	if (group->meth->group_clear_finish != 0)
145 		group->meth->group_clear_finish(group);
146 	else if (group->meth->group_finish != 0)
147 		group->meth->group_finish(group);
148 
149 	EC_EX_DATA_clear_free_all_data(&group->extra_data);
150 
151 	EC_POINT_clear_free(group->generator);
152 	BN_clear_free(&group->order);
153 	BN_clear_free(&group->cofactor);
154 
155 	freezero(group->seed, group->seed_len);
156 	freezero(group, sizeof *group);
157 }
158 
159 
160 int
161 EC_GROUP_copy(EC_GROUP * dest, const EC_GROUP * src)
162 {
163 	EC_EXTRA_DATA *d;
164 
165 	if (dest->meth->group_copy == 0) {
166 		ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
167 		return 0;
168 	}
169 	if (dest->meth != src->meth) {
170 		ECerror(EC_R_INCOMPATIBLE_OBJECTS);
171 		return 0;
172 	}
173 	if (dest == src)
174 		return 1;
175 
176 	EC_EX_DATA_free_all_data(&dest->extra_data);
177 
178 	for (d = src->extra_data; d != NULL; d = d->next) {
179 		void *t = d->dup_func(d->data);
180 
181 		if (t == NULL)
182 			return 0;
183 		if (!EC_EX_DATA_set_data(&dest->extra_data, t, d->dup_func,
184 		    d->free_func, d->clear_free_func))
185 			return 0;
186 	}
187 
188 	if (src->generator != NULL) {
189 		if (dest->generator == NULL) {
190 			dest->generator = EC_POINT_new(dest);
191 			if (dest->generator == NULL)
192 				return 0;
193 		}
194 		if (!EC_POINT_copy(dest->generator, src->generator))
195 			return 0;
196 	} else {
197 		/* src->generator == NULL */
198 		EC_POINT_clear_free(dest->generator);
199 		dest->generator = NULL;
200 	}
201 
202 	if (!BN_copy(&dest->order, &src->order))
203 		return 0;
204 	if (!BN_copy(&dest->cofactor, &src->cofactor))
205 		return 0;
206 
207 	dest->curve_name = src->curve_name;
208 	dest->asn1_flag = src->asn1_flag;
209 	dest->asn1_form = src->asn1_form;
210 
211 	if (src->seed) {
212 		free(dest->seed);
213 		dest->seed = malloc(src->seed_len);
214 		if (dest->seed == NULL)
215 			return 0;
216 		memcpy(dest->seed, src->seed, src->seed_len);
217 		dest->seed_len = src->seed_len;
218 	} else {
219 		free(dest->seed);
220 		dest->seed = NULL;
221 		dest->seed_len = 0;
222 	}
223 
224 
225 	return dest->meth->group_copy(dest, src);
226 }
227 
228 
229 EC_GROUP *
230 EC_GROUP_dup(const EC_GROUP * a)
231 {
232 	EC_GROUP *t = NULL;
233 
234 	if ((a != NULL) && ((t = EC_GROUP_new(a->meth)) != NULL) &&
235 	    (!EC_GROUP_copy(t, a))) {
236 		EC_GROUP_free(t);
237 		t = NULL;
238 	}
239 	return t;
240 }
241 
242 
243 const EC_METHOD *
244 EC_GROUP_method_of(const EC_GROUP *group)
245 {
246 	return group->meth;
247 }
248 
249 
250 int
251 EC_METHOD_get_field_type(const EC_METHOD *meth)
252 {
253 	return meth->field_type;
254 }
255 
256 /*
257  * Try computing the cofactor from generator order n and field cardinality q.
258  * This works for all curves of cryptographic interest.
259  *
260  * Hasse's theorem: | h * n - (q + 1) | <= 2 * sqrt(q)
261  *
262  * So: h_min = (q + 1 - 2*sqrt(q)) / n and h_max = (q + 1 + 2*sqrt(q)) / n and
263  * therefore h_max - h_min = 4*sqrt(q) / n. So if n > 4*sqrt(q) holds, there is
264  * only one possible value for h:
265  *
266  *	h = \lfloor (h_min + h_max)/2 \rceil = \lfloor (q + 1)/n \rceil
267  *
268  * Otherwise, zero cofactor and return success.
269  */
270 static int
271 ec_guess_cofactor(EC_GROUP *group)
272 {
273 	BN_CTX *ctx = NULL;
274 	BIGNUM *q = NULL;
275 	int ret = 0;
276 
277 	/*
278 	 * If the cofactor is too large, we cannot guess it and default to zero.
279 	 * The RHS of below is a strict overestimate of log(4 * sqrt(q)).
280 	 */
281 	if (BN_num_bits(&group->order) <=
282 	    (BN_num_bits(&group->field) + 1) / 2 + 3) {
283 		BN_zero(&group->cofactor);
284 		return 1;
285 	}
286 
287 	if ((ctx = BN_CTX_new()) == NULL)
288 		goto err;
289 
290 	BN_CTX_start(ctx);
291 	if ((q = BN_CTX_get(ctx)) == NULL)
292 		goto err;
293 
294 	/* Set q = 2**m for binary fields; q = p otherwise. */
295 	if (group->meth->field_type == NID_X9_62_characteristic_two_field) {
296 		BN_zero(q);
297 		if (!BN_set_bit(q, BN_num_bits(&group->field) - 1))
298 			goto err;
299 	} else {
300 		if (!BN_copy(q, &group->field))
301 			goto err;
302 	}
303 
304 	/*
305 	 * Compute
306 	 *     h = \lfloor (q + 1)/n \rceil = \lfloor (q + 1 + n/2) / n \rfloor.
307 	 */
308 
309 	/* h = n/2 */
310 	if (!BN_rshift1(&group->cofactor, &group->order))
311 		goto err;
312 	/* h = 1 + n/2 */
313 	if (!BN_add(&group->cofactor, &group->cofactor, BN_value_one()))
314 		goto err;
315 	/* h = q + 1 + n/2 */
316 	if (!BN_add(&group->cofactor, &group->cofactor, q))
317 		goto err;
318 	/* h = (q + 1 + n/2) / n */
319 	if (!BN_div_ct(&group->cofactor, NULL, &group->cofactor, &group->order,
320 	    ctx))
321 		goto err;
322 
323 	ret = 1;
324  err:
325 	BN_CTX_end(ctx);
326 	BN_CTX_free(ctx);
327 	BN_zero(&group->cofactor);
328 	return ret;
329 }
330 
331 int
332 EC_GROUP_set_generator(EC_GROUP *group, const EC_POINT *generator,
333     const BIGNUM *order, const BIGNUM *cofactor)
334 {
335 	if (generator == NULL) {
336 		ECerror(ERR_R_PASSED_NULL_PARAMETER);
337 		return 0;
338 	}
339 
340 	/* Require group->field >= 1. */
341 	if (BN_is_zero(&group->field) || BN_is_negative(&group->field)) {
342 		ECerror(EC_R_INVALID_FIELD);
343 		return 0;
344 	}
345 
346 	/*
347 	 * Require order >= 1 and enforce an upper bound of at most one bit more
348 	 * than the field cardinality due to Hasse's theorem.
349 	 */
350 	if (order == NULL || BN_is_zero(order) || BN_is_negative(order) ||
351 	    BN_num_bits(order) > BN_num_bits(&group->field) + 1) {
352 		ECerror(EC_R_INVALID_GROUP_ORDER);
353 		return 0;
354 	}
355 
356 	/*
357 	 * Unfortunately, the cofactor is an optional field in many standards.
358 	 * Internally, the library uses a 0 cofactor as a marker for "unknown
359 	 * cofactor".  So accept cofactor == NULL or cofactor >= 0.
360 	 */
361 	if (cofactor != NULL && BN_is_negative(cofactor)) {
362 		ECerror(EC_R_UNKNOWN_COFACTOR);
363 		return 0;
364 	}
365 
366 	if (group->generator == NULL) {
367 		group->generator = EC_POINT_new(group);
368 		if (group->generator == NULL)
369 			return 0;
370 	}
371 	if (!EC_POINT_copy(group->generator, generator))
372 		return 0;
373 
374 	if (!BN_copy(&group->order, order))
375 		return 0;
376 
377 	/* Either take the provided positive cofactor, or try to compute it. */
378 	if (cofactor != NULL && !BN_is_zero(cofactor)) {
379 		if (!BN_copy(&group->cofactor, cofactor))
380 			return 0;
381 	} else if (!ec_guess_cofactor(group))
382 		return 0;
383 
384 	return 1;
385 }
386 
387 
388 const EC_POINT *
389 EC_GROUP_get0_generator(const EC_GROUP *group)
390 {
391 	return group->generator;
392 }
393 
394 
395 int
396 EC_GROUP_get_order(const EC_GROUP *group, BIGNUM *order, BN_CTX *ctx)
397 {
398 	if (!BN_copy(order, &group->order))
399 		return 0;
400 
401 	return !BN_is_zero(order);
402 }
403 
404 
405 int
406 EC_GROUP_get_cofactor(const EC_GROUP *group, BIGNUM *cofactor, BN_CTX *ctx)
407 {
408 	if (!BN_copy(cofactor, &group->cofactor))
409 		return 0;
410 
411 	return !BN_is_zero(&group->cofactor);
412 }
413 
414 
415 void
416 EC_GROUP_set_curve_name(EC_GROUP * group, int nid)
417 {
418 	group->curve_name = nid;
419 }
420 
421 
422 int
423 EC_GROUP_get_curve_name(const EC_GROUP * group)
424 {
425 	return group->curve_name;
426 }
427 
428 
429 void
430 EC_GROUP_set_asn1_flag(EC_GROUP * group, int flag)
431 {
432 	group->asn1_flag = flag;
433 }
434 
435 
436 int
437 EC_GROUP_get_asn1_flag(const EC_GROUP * group)
438 {
439 	return group->asn1_flag;
440 }
441 
442 
443 void
444 EC_GROUP_set_point_conversion_form(EC_GROUP * group,
445     point_conversion_form_t form)
446 {
447 	group->asn1_form = form;
448 }
449 
450 
451 point_conversion_form_t
452 EC_GROUP_get_point_conversion_form(const EC_GROUP * group)
453 {
454 	return group->asn1_form;
455 }
456 
457 
458 size_t
459 EC_GROUP_set_seed(EC_GROUP * group, const unsigned char *p, size_t len)
460 {
461 	if (group->seed) {
462 		free(group->seed);
463 		group->seed = NULL;
464 		group->seed_len = 0;
465 	}
466 	if (!len || !p)
467 		return 1;
468 
469 	if ((group->seed = malloc(len)) == NULL)
470 		return 0;
471 	memcpy(group->seed, p, len);
472 	group->seed_len = len;
473 
474 	return len;
475 }
476 
477 
478 unsigned char *
479 EC_GROUP_get0_seed(const EC_GROUP * group)
480 {
481 	return group->seed;
482 }
483 
484 
485 size_t
486 EC_GROUP_get_seed_len(const EC_GROUP * group)
487 {
488 	return group->seed_len;
489 }
490 
491 int
492 EC_GROUP_set_curve(EC_GROUP *group, const BIGNUM *p, const BIGNUM *a,
493     const BIGNUM *b, BN_CTX *ctx)
494 {
495 	if (group->meth->group_set_curve == NULL) {
496 		ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
497 		return 0;
498 	}
499 	return group->meth->group_set_curve(group, p, a, b, ctx);
500 }
501 
502 int
503 EC_GROUP_get_curve(const EC_GROUP *group, BIGNUM *p, BIGNUM *a, BIGNUM *b,
504     BN_CTX *ctx)
505 {
506 	if (group->meth->group_get_curve == NULL) {
507 		ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
508 		return 0;
509 	}
510 	return group->meth->group_get_curve(group, p, a, b, ctx);
511 }
512 
513 int
514 EC_GROUP_set_curve_GFp(EC_GROUP *group, const BIGNUM *p, const BIGNUM *a,
515     const BIGNUM *b, BN_CTX *ctx)
516 {
517 	return EC_GROUP_set_curve(group, p, a, b, ctx);
518 }
519 
520 int
521 EC_GROUP_get_curve_GFp(const EC_GROUP *group, BIGNUM *p, BIGNUM *a, BIGNUM *b,
522     BN_CTX *ctx)
523 {
524 	return EC_GROUP_get_curve(group, p, a, b, ctx);
525 }
526 
527 #ifndef OPENSSL_NO_EC2M
528 int
529 EC_GROUP_set_curve_GF2m(EC_GROUP *group, const BIGNUM *p, const BIGNUM *a,
530     const BIGNUM *b, BN_CTX *ctx)
531 {
532 	return EC_GROUP_set_curve(group, p, a, b, ctx);
533 }
534 
535 int
536 EC_GROUP_get_curve_GF2m(const EC_GROUP *group, BIGNUM *p, BIGNUM *a,
537     BIGNUM *b, BN_CTX *ctx)
538 {
539 	return EC_GROUP_get_curve(group, p, a, b, ctx);
540 }
541 #endif
542 
543 int
544 EC_GROUP_get_degree(const EC_GROUP * group)
545 {
546 	if (group->meth->group_get_degree == 0) {
547 		ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
548 		return 0;
549 	}
550 	return group->meth->group_get_degree(group);
551 }
552 
553 
554 int
555 EC_GROUP_check_discriminant(const EC_GROUP * group, BN_CTX * ctx)
556 {
557 	if (group->meth->group_check_discriminant == 0) {
558 		ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
559 		return 0;
560 	}
561 	return group->meth->group_check_discriminant(group, ctx);
562 }
563 
564 
565 int
566 EC_GROUP_cmp(const EC_GROUP * a, const EC_GROUP * b, BN_CTX * ctx)
567 {
568 	int r = 0;
569 	BIGNUM *a1, *a2, *a3, *b1, *b2, *b3;
570 	BN_CTX *ctx_new = NULL;
571 
572 	/* compare the field types */
573 	if (EC_METHOD_get_field_type(EC_GROUP_method_of(a)) !=
574 	    EC_METHOD_get_field_type(EC_GROUP_method_of(b)))
575 		return 1;
576 	/* compare the curve name (if present in both) */
577 	if (EC_GROUP_get_curve_name(a) && EC_GROUP_get_curve_name(b) &&
578 	    EC_GROUP_get_curve_name(a) != EC_GROUP_get_curve_name(b))
579 		return 1;
580 
581 	if (!ctx)
582 		ctx_new = ctx = BN_CTX_new();
583 	if (!ctx)
584 		return -1;
585 
586 	BN_CTX_start(ctx);
587 	if ((a1 = BN_CTX_get(ctx)) == NULL)
588 		goto err;
589 	if ((a2 = BN_CTX_get(ctx)) == NULL)
590 		goto err;
591 	if ((a3 = BN_CTX_get(ctx)) == NULL)
592 		goto err;
593 	if ((b1 = BN_CTX_get(ctx)) == NULL)
594 		goto err;
595 	if ((b2 = BN_CTX_get(ctx)) == NULL)
596 		goto err;
597 	if ((b3 = BN_CTX_get(ctx)) == NULL)
598 		goto err;
599 
600 	/*
601 	 * XXX This approach assumes that the external representation of
602 	 * curves over the same field type is the same.
603 	 */
604 	if (!a->meth->group_get_curve(a, a1, a2, a3, ctx) ||
605 	    !b->meth->group_get_curve(b, b1, b2, b3, ctx))
606 		r = 1;
607 
608 	if (r || BN_cmp(a1, b1) || BN_cmp(a2, b2) || BN_cmp(a3, b3))
609 		r = 1;
610 
611 	/* XXX EC_POINT_cmp() assumes that the methods are equal */
612 	if (r || EC_POINT_cmp(a, EC_GROUP_get0_generator(a),
613 		EC_GROUP_get0_generator(b), ctx))
614 		r = 1;
615 
616 	if (!r) {
617 		/* compare the order and cofactor */
618 		if (!EC_GROUP_get_order(a, a1, ctx) ||
619 		    !EC_GROUP_get_order(b, b1, ctx) ||
620 		    !EC_GROUP_get_cofactor(a, a2, ctx) ||
621 		    !EC_GROUP_get_cofactor(b, b2, ctx))
622 			goto err;
623 		if (BN_cmp(a1, b1) || BN_cmp(a2, b2))
624 			r = 1;
625 	}
626 	BN_CTX_end(ctx);
627 	if (ctx_new)
628 		BN_CTX_free(ctx);
629 
630 	return r;
631 
632  err:
633 	BN_CTX_end(ctx);
634 	if (ctx_new)
635 		BN_CTX_free(ctx);
636 	return -1;
637 }
638 
639 /*
640  * Coordinate blinding for EC_POINT.
641  *
642  * The underlying EC_METHOD can optionally implement this function:
643  * underlying implementations should return 0 on errors, or 1 on success.
644  *
645  * This wrapper returns 1 in case the underlying EC_METHOD does not support
646  * coordinate blinding.
647  */
648 int
649 ec_point_blind_coordinates(const EC_GROUP *group, EC_POINT *p, BN_CTX *ctx)
650 {
651 	if (group->meth->blind_coordinates == NULL)
652 		return 1;
653 
654 	return group->meth->blind_coordinates(group, p, ctx);
655 }
656 
657 /* this has 'package' visibility */
658 int
659 EC_EX_DATA_set_data(EC_EXTRA_DATA ** ex_data, void *data,
660     void *(*dup_func) (void *),
661     void (*free_func) (void *),
662     void (*clear_free_func) (void *))
663 {
664 	EC_EXTRA_DATA *d;
665 
666 	if (ex_data == NULL)
667 		return 0;
668 
669 	for (d = *ex_data; d != NULL; d = d->next) {
670 		if (d->dup_func == dup_func && d->free_func == free_func &&
671 		    d->clear_free_func == clear_free_func) {
672 			ECerror(EC_R_SLOT_FULL);
673 			return 0;
674 		}
675 	}
676 
677 	if (data == NULL)
678 		/* no explicit entry needed */
679 		return 1;
680 
681 	d = malloc(sizeof *d);
682 	if (d == NULL)
683 		return 0;
684 
685 	d->data = data;
686 	d->dup_func = dup_func;
687 	d->free_func = free_func;
688 	d->clear_free_func = clear_free_func;
689 
690 	d->next = *ex_data;
691 	*ex_data = d;
692 
693 	return 1;
694 }
695 
696 /* this has 'package' visibility */
697 void *
698 EC_EX_DATA_get_data(const EC_EXTRA_DATA * ex_data,
699     void *(*dup_func) (void *),
700     void (*free_func) (void *),
701     void (*clear_free_func) (void *))
702 {
703 	const EC_EXTRA_DATA *d;
704 
705 	for (d = ex_data; d != NULL; d = d->next) {
706 		if (d->dup_func == dup_func && d->free_func == free_func && d->clear_free_func == clear_free_func)
707 			return d->data;
708 	}
709 
710 	return NULL;
711 }
712 
713 /* this has 'package' visibility */
714 void
715 EC_EX_DATA_free_data(EC_EXTRA_DATA ** ex_data,
716     void *(*dup_func) (void *),
717     void (*free_func) (void *),
718     void (*clear_free_func) (void *))
719 {
720 	EC_EXTRA_DATA **p;
721 
722 	if (ex_data == NULL)
723 		return;
724 
725 	for (p = ex_data; *p != NULL; p = &((*p)->next)) {
726 		if ((*p)->dup_func == dup_func &&
727 		    (*p)->free_func == free_func &&
728 		    (*p)->clear_free_func == clear_free_func) {
729 			EC_EXTRA_DATA *next = (*p)->next;
730 
731 			(*p)->free_func((*p)->data);
732 			free(*p);
733 
734 			*p = next;
735 			return;
736 		}
737 	}
738 }
739 
740 /* this has 'package' visibility */
741 void
742 EC_EX_DATA_clear_free_data(EC_EXTRA_DATA ** ex_data,
743     void *(*dup_func) (void *),
744     void (*free_func) (void *),
745     void (*clear_free_func) (void *))
746 {
747 	EC_EXTRA_DATA **p;
748 
749 	if (ex_data == NULL)
750 		return;
751 
752 	for (p = ex_data; *p != NULL; p = &((*p)->next)) {
753 		if ((*p)->dup_func == dup_func &&
754 		    (*p)->free_func == free_func &&
755 		    (*p)->clear_free_func == clear_free_func) {
756 			EC_EXTRA_DATA *next = (*p)->next;
757 
758 			(*p)->clear_free_func((*p)->data);
759 			free(*p);
760 
761 			*p = next;
762 			return;
763 		}
764 	}
765 }
766 
767 /* this has 'package' visibility */
768 void
769 EC_EX_DATA_free_all_data(EC_EXTRA_DATA ** ex_data)
770 {
771 	EC_EXTRA_DATA *d;
772 
773 	if (ex_data == NULL)
774 		return;
775 
776 	d = *ex_data;
777 	while (d) {
778 		EC_EXTRA_DATA *next = d->next;
779 
780 		d->free_func(d->data);
781 		free(d);
782 
783 		d = next;
784 	}
785 	*ex_data = NULL;
786 }
787 
788 /* this has 'package' visibility */
789 void
790 EC_EX_DATA_clear_free_all_data(EC_EXTRA_DATA ** ex_data)
791 {
792 	EC_EXTRA_DATA *d;
793 
794 	if (ex_data == NULL)
795 		return;
796 
797 	d = *ex_data;
798 	while (d) {
799 		EC_EXTRA_DATA *next = d->next;
800 
801 		d->clear_free_func(d->data);
802 		free(d);
803 
804 		d = next;
805 	}
806 	*ex_data = NULL;
807 }
808 
809 
810 /* functions for EC_POINT objects */
811 
812 EC_POINT *
813 EC_POINT_new(const EC_GROUP * group)
814 {
815 	EC_POINT *ret;
816 
817 	if (group == NULL) {
818 		ECerror(ERR_R_PASSED_NULL_PARAMETER);
819 		return NULL;
820 	}
821 	if (group->meth->point_init == 0) {
822 		ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
823 		return NULL;
824 	}
825 	ret = malloc(sizeof *ret);
826 	if (ret == NULL) {
827 		ECerror(ERR_R_MALLOC_FAILURE);
828 		return NULL;
829 	}
830 	ret->meth = group->meth;
831 
832 	if (!ret->meth->point_init(ret)) {
833 		free(ret);
834 		return NULL;
835 	}
836 	return ret;
837 }
838 
839 
840 void
841 EC_POINT_free(EC_POINT * point)
842 {
843 	if (!point)
844 		return;
845 
846 	if (point->meth->point_finish != 0)
847 		point->meth->point_finish(point);
848 	free(point);
849 }
850 
851 
852 void
853 EC_POINT_clear_free(EC_POINT * point)
854 {
855 	if (!point)
856 		return;
857 
858 	if (point->meth->point_clear_finish != 0)
859 		point->meth->point_clear_finish(point);
860 	else if (point->meth->point_finish != 0)
861 		point->meth->point_finish(point);
862 	freezero(point, sizeof *point);
863 }
864 
865 
866 int
867 EC_POINT_copy(EC_POINT * dest, const EC_POINT * src)
868 {
869 	if (dest->meth->point_copy == 0) {
870 		ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
871 		return 0;
872 	}
873 	if (dest->meth != src->meth) {
874 		ECerror(EC_R_INCOMPATIBLE_OBJECTS);
875 		return 0;
876 	}
877 	if (dest == src)
878 		return 1;
879 	return dest->meth->point_copy(dest, src);
880 }
881 
882 
883 EC_POINT *
884 EC_POINT_dup(const EC_POINT * a, const EC_GROUP * group)
885 {
886 	EC_POINT *t;
887 	int r;
888 
889 	if (a == NULL)
890 		return NULL;
891 
892 	t = EC_POINT_new(group);
893 	if (t == NULL)
894 		return (NULL);
895 	r = EC_POINT_copy(t, a);
896 	if (!r) {
897 		EC_POINT_free(t);
898 		return NULL;
899 	} else
900 		return t;
901 }
902 
903 
904 const EC_METHOD *
905 EC_POINT_method_of(const EC_POINT * point)
906 {
907 	return point->meth;
908 }
909 
910 
911 int
912 EC_POINT_set_to_infinity(const EC_GROUP * group, EC_POINT * point)
913 {
914 	if (group->meth->point_set_to_infinity == 0) {
915 		ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
916 		return 0;
917 	}
918 	if (group->meth != point->meth) {
919 		ECerror(EC_R_INCOMPATIBLE_OBJECTS);
920 		return 0;
921 	}
922 	return group->meth->point_set_to_infinity(group, point);
923 }
924 
925 int
926 EC_POINT_set_Jprojective_coordinates(const EC_GROUP *group, EC_POINT *point,
927     const BIGNUM *x, const BIGNUM *y, const BIGNUM *z, BN_CTX *ctx)
928 {
929 	if (group->meth->point_set_Jprojective_coordinates == NULL) {
930 		ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
931 		return 0;
932 	}
933 	if (group->meth != point->meth) {
934 		ECerror(EC_R_INCOMPATIBLE_OBJECTS);
935 		return 0;
936 	}
937 	return group->meth->point_set_Jprojective_coordinates(group, point,
938 	    x, y, z, ctx);
939 }
940 
941 int
942 EC_POINT_get_Jprojective_coordinates(const EC_GROUP *group,
943     const EC_POINT *point, BIGNUM *x, BIGNUM *y, BIGNUM *z, BN_CTX *ctx)
944 {
945 	if (group->meth->point_get_Jprojective_coordinates == NULL) {
946 		ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
947 		return 0;
948 	}
949 	if (group->meth != point->meth) {
950 		ECerror(EC_R_INCOMPATIBLE_OBJECTS);
951 		return 0;
952 	}
953 	return group->meth->point_get_Jprojective_coordinates(group, point,
954 	    x, y, z, ctx);
955 }
956 
957 int
958 EC_POINT_set_Jprojective_coordinates_GFp(const EC_GROUP *group, EC_POINT *point,
959     const BIGNUM *x, const BIGNUM *y, const BIGNUM *z, BN_CTX *ctx)
960 {
961 	return EC_POINT_set_Jprojective_coordinates(group, point, x, y, z, ctx);
962 }
963 
964 int
965 EC_POINT_get_Jprojective_coordinates_GFp(const EC_GROUP *group,
966     const EC_POINT *point, BIGNUM *x, BIGNUM *y, BIGNUM *z, BN_CTX *ctx)
967 {
968 	return EC_POINT_get_Jprojective_coordinates(group, point, x, y, z, ctx);
969 }
970 
971 int
972 EC_POINT_set_affine_coordinates(const EC_GROUP *group, EC_POINT *point,
973     const BIGNUM *x, const BIGNUM *y, BN_CTX *ctx)
974 {
975 	if (group->meth->point_set_affine_coordinates == NULL) {
976 		ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
977 		return 0;
978 	}
979 	if (group->meth != point->meth) {
980 		ECerror(EC_R_INCOMPATIBLE_OBJECTS);
981 		return 0;
982 	}
983 	if (!group->meth->point_set_affine_coordinates(group, point, x, y, ctx))
984 		return 0;
985 	if (EC_POINT_is_on_curve(group, point, ctx) <= 0) {
986 		ECerror(EC_R_POINT_IS_NOT_ON_CURVE);
987 		return 0;
988 	}
989 	return 1;
990 }
991 
992 int
993 EC_POINT_set_affine_coordinates_GFp(const EC_GROUP *group, EC_POINT *point,
994     const BIGNUM *x, const BIGNUM *y, BN_CTX *ctx)
995 {
996 	return EC_POINT_set_affine_coordinates(group, point, x, y, ctx);
997 }
998 
999 #ifndef OPENSSL_NO_EC2M
1000 int
1001 EC_POINT_set_affine_coordinates_GF2m(const EC_GROUP *group, EC_POINT *point,
1002     const BIGNUM *x, const BIGNUM *y, BN_CTX *ctx)
1003 {
1004 	return EC_POINT_set_affine_coordinates(group, point, x, y, ctx);
1005 }
1006 #endif
1007 
1008 int
1009 EC_POINT_get_affine_coordinates(const EC_GROUP *group, const EC_POINT *point,
1010     BIGNUM *x, BIGNUM *y, BN_CTX *ctx)
1011 {
1012 	if (group->meth->point_get_affine_coordinates == NULL) {
1013 		ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
1014 		return 0;
1015 	}
1016 	if (group->meth != point->meth) {
1017 		ECerror(EC_R_INCOMPATIBLE_OBJECTS);
1018 		return 0;
1019 	}
1020 	return group->meth->point_get_affine_coordinates(group, point, x, y, ctx);
1021 }
1022 
1023 int
1024 EC_POINT_get_affine_coordinates_GFp(const EC_GROUP *group, const EC_POINT *point,
1025     BIGNUM *x, BIGNUM *y, BN_CTX *ctx)
1026 {
1027 	return EC_POINT_get_affine_coordinates(group, point, x, y, ctx);
1028 }
1029 
1030 #ifndef OPENSSL_NO_EC2M
1031 int
1032 EC_POINT_get_affine_coordinates_GF2m(const EC_GROUP *group, const EC_POINT *point,
1033     BIGNUM *x, BIGNUM *y, BN_CTX *ctx)
1034 {
1035 	return EC_POINT_get_affine_coordinates(group, point, x, y, ctx);
1036 }
1037 #endif
1038 
1039 int
1040 EC_POINT_add(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a,
1041     const EC_POINT *b, BN_CTX *ctx)
1042 {
1043 	if (group->meth->add == 0) {
1044 		ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
1045 		return 0;
1046 	}
1047 	if ((group->meth != r->meth) || (r->meth != a->meth) || (a->meth != b->meth)) {
1048 		ECerror(EC_R_INCOMPATIBLE_OBJECTS);
1049 		return 0;
1050 	}
1051 	return group->meth->add(group, r, a, b, ctx);
1052 }
1053 
1054 
1055 int
1056 EC_POINT_dbl(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a, BN_CTX *ctx)
1057 {
1058 	if (group->meth->dbl == 0) {
1059 		ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
1060 		return 0;
1061 	}
1062 	if ((group->meth != r->meth) || (r->meth != a->meth)) {
1063 		ECerror(EC_R_INCOMPATIBLE_OBJECTS);
1064 		return 0;
1065 	}
1066 	return group->meth->dbl(group, r, a, ctx);
1067 }
1068 
1069 
1070 int
1071 EC_POINT_invert(const EC_GROUP *group, EC_POINT *a, BN_CTX *ctx)
1072 {
1073 	if (group->meth->invert == 0) {
1074 		ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
1075 		return 0;
1076 	}
1077 	if (group->meth != a->meth) {
1078 		ECerror(EC_R_INCOMPATIBLE_OBJECTS);
1079 		return 0;
1080 	}
1081 	return group->meth->invert(group, a, ctx);
1082 }
1083 
1084 
1085 int
1086 EC_POINT_is_at_infinity(const EC_GROUP *group, const EC_POINT *point)
1087 {
1088 	if (group->meth->is_at_infinity == 0) {
1089 		ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
1090 		return 0;
1091 	}
1092 	if (group->meth != point->meth) {
1093 		ECerror(EC_R_INCOMPATIBLE_OBJECTS);
1094 		return 0;
1095 	}
1096 	return group->meth->is_at_infinity(group, point);
1097 }
1098 
1099 
1100 int
1101 EC_POINT_is_on_curve(const EC_GROUP * group, const EC_POINT * point, BN_CTX * ctx)
1102 {
1103 	if (group->meth->is_on_curve == 0) {
1104 		ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
1105 		return 0;
1106 	}
1107 	if (group->meth != point->meth) {
1108 		ECerror(EC_R_INCOMPATIBLE_OBJECTS);
1109 		return 0;
1110 	}
1111 	return group->meth->is_on_curve(group, point, ctx);
1112 }
1113 
1114 
1115 int
1116 EC_POINT_cmp(const EC_GROUP *group, const EC_POINT *a, const EC_POINT *b,
1117     BN_CTX * ctx)
1118 {
1119 	if (group->meth->point_cmp == 0) {
1120 		ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
1121 		return -1;
1122 	}
1123 	if ((group->meth != a->meth) || (a->meth != b->meth)) {
1124 		ECerror(EC_R_INCOMPATIBLE_OBJECTS);
1125 		return -1;
1126 	}
1127 	return group->meth->point_cmp(group, a, b, ctx);
1128 }
1129 
1130 
1131 int
1132 EC_POINT_make_affine(const EC_GROUP *group, EC_POINT *point, BN_CTX *ctx)
1133 {
1134 	if (group->meth->make_affine == 0) {
1135 		ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
1136 		return 0;
1137 	}
1138 	if (group->meth != point->meth) {
1139 		ECerror(EC_R_INCOMPATIBLE_OBJECTS);
1140 		return 0;
1141 	}
1142 	return group->meth->make_affine(group, point, ctx);
1143 }
1144 
1145 
1146 int
1147 EC_POINTs_make_affine(const EC_GROUP *group, size_t num, EC_POINT *points[],
1148     BN_CTX *ctx)
1149 {
1150 	size_t i;
1151 
1152 	if (group->meth->points_make_affine == 0) {
1153 		ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
1154 		return 0;
1155 	}
1156 	for (i = 0; i < num; i++) {
1157 		if (group->meth != points[i]->meth) {
1158 			ECerror(EC_R_INCOMPATIBLE_OBJECTS);
1159 			return 0;
1160 		}
1161 	}
1162 	return group->meth->points_make_affine(group, num, points, ctx);
1163 }
1164 
1165 
1166 /* Functions for point multiplication */
1167 int
1168 EC_POINTs_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar,
1169     size_t num, const EC_POINT *points[], const BIGNUM *scalars[], BN_CTX *ctx)
1170 {
1171 	/*
1172 	 * The function pointers must be set, and only support num == 0 and
1173 	 * num == 1.
1174 	 */
1175 	if (group->meth->mul_generator_ct == NULL ||
1176 	    group->meth->mul_single_ct == NULL ||
1177 	    group->meth->mul_double_nonct == NULL ||
1178 	    num > 1) {
1179 		ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
1180 		return 0;
1181 	}
1182 
1183 	/* Either bP or aG + bP, this is sane. */
1184 	if (num == 1 && points != NULL && scalars != NULL)
1185 		return EC_POINT_mul(group, r, scalar, points[0], scalars[0],
1186 		    ctx);
1187 
1188 	/* aG, this is sane */
1189 	if (scalar != NULL && points == NULL && scalars == NULL)
1190 		return EC_POINT_mul(group, r, scalar, NULL, NULL, ctx);
1191 
1192 	/* anything else is an error */
1193 	ECerror(ERR_R_EC_LIB);
1194 	return 0;
1195 }
1196 
1197 int
1198 EC_POINT_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *g_scalar,
1199     const EC_POINT *point, const BIGNUM *p_scalar, BN_CTX *ctx)
1200 {
1201 	if (group->meth->mul_generator_ct == NULL ||
1202 	    group->meth->mul_single_ct == NULL ||
1203 	    group->meth->mul_double_nonct == NULL) {
1204 		ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
1205 		return 0;
1206 	}
1207 	if (g_scalar != NULL && point == NULL && p_scalar == NULL) {
1208 		/*
1209 		 * In this case we want to compute g_scalar * GeneratorPoint:
1210 		 * this codepath is reached most prominently by (ephemeral) key
1211 		 * generation of EC cryptosystems (i.e. ECDSA keygen and sign
1212 		 * setup, ECDH keygen/first half), where the scalar is always
1213 		 * secret. This is why we ignore if BN_FLG_CONSTTIME is actually
1214 		 * set and we always call the constant time version.
1215 		 */
1216 		return group->meth->mul_generator_ct(group, r, g_scalar, ctx);
1217 	}
1218 	if (g_scalar == NULL && point != NULL && p_scalar != NULL) {
1219 		/* In this case we want to compute p_scalar * GenericPoint:
1220 		 * this codepath is reached most prominently by the second half
1221 		 * of ECDH, where the secret scalar is multiplied by the peer's
1222 		 * public point. To protect the secret scalar, we ignore if
1223 		 * BN_FLG_CONSTTIME is actually set and we always call the
1224 		 * constant time version.
1225 		 */
1226 		return group->meth->mul_single_ct(group, r, p_scalar, point,
1227 		    ctx);
1228 	}
1229 	if (g_scalar != NULL && point != NULL && p_scalar != NULL) {
1230 		/*
1231 		 * In this case we want to compute
1232 		 *   g_scalar * GeneratorPoint + p_scalar * GenericPoint:
1233 		 * this codepath is reached most prominently by ECDSA signature
1234 		 * verification. So we call the non-ct version.
1235 		 */
1236 		return group->meth->mul_double_nonct(group, r, g_scalar,
1237 		    p_scalar, point, ctx);
1238 	}
1239 
1240 	/* Anything else is an error. */
1241 	ECerror(ERR_R_EC_LIB);
1242 	return 0;
1243 }
1244 
1245 int
1246 EC_GROUP_precompute_mult(EC_GROUP * group, BN_CTX * ctx)
1247 {
1248 	if (group->meth->precompute_mult != 0)
1249 		return group->meth->precompute_mult(group, ctx);
1250 	else
1251 		return 1;	/* nothing to do, so report success */
1252 }
1253 
1254 int
1255 EC_GROUP_have_precompute_mult(const EC_GROUP * group)
1256 {
1257 	if (group->meth->have_precompute_mult != 0)
1258 		return group->meth->have_precompute_mult(group);
1259 	else
1260 		return 0;	/* cannot tell whether precomputation has
1261 				 * been performed */
1262 }
1263 
1264 EC_KEY *
1265 ECParameters_dup(EC_KEY *key)
1266 {
1267 	unsigned char *p = NULL;
1268 	EC_KEY *k = NULL;
1269 	int len;
1270 
1271 	if (key == NULL)
1272 		return (NULL);
1273 
1274 	if ((len = i2d_ECParameters(key, &p)) > 0)
1275 		k = d2i_ECParameters(NULL, (const unsigned char **)&p, len);
1276 
1277 	return (k);
1278 }
1279