1 /* $OpenBSD: ec_lib.c,v 1.32 2019/09/29 10:09:09 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 *
EC_GROUP_new(const EC_METHOD * meth)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
EC_GROUP_free(EC_GROUP * group)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
EC_GROUP_clear_free(EC_GROUP * group)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
EC_GROUP_copy(EC_GROUP * dest,const EC_GROUP * src)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 *
EC_GROUP_dup(const EC_GROUP * a)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 *
EC_GROUP_method_of(const EC_GROUP * group)244 EC_GROUP_method_of(const EC_GROUP *group)
245 {
246 return group->meth;
247 }
248
249
250 int
EC_METHOD_get_field_type(const EC_METHOD * meth)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
ec_guess_cofactor(EC_GROUP * group)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
EC_GROUP_set_generator(EC_GROUP * group,const EC_POINT * generator,const BIGNUM * order,const BIGNUM * cofactor)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 *
EC_GROUP_get0_generator(const EC_GROUP * group)389 EC_GROUP_get0_generator(const EC_GROUP *group)
390 {
391 return group->generator;
392 }
393
394
395 int
EC_GROUP_get_order(const EC_GROUP * group,BIGNUM * order,BN_CTX * ctx)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
EC_GROUP_get_cofactor(const EC_GROUP * group,BIGNUM * cofactor,BN_CTX * ctx)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
EC_GROUP_set_curve_name(EC_GROUP * group,int nid)416 EC_GROUP_set_curve_name(EC_GROUP * group, int nid)
417 {
418 group->curve_name = nid;
419 }
420
421
422 int
EC_GROUP_get_curve_name(const EC_GROUP * group)423 EC_GROUP_get_curve_name(const EC_GROUP * group)
424 {
425 return group->curve_name;
426 }
427
428
429 void
EC_GROUP_set_asn1_flag(EC_GROUP * group,int flag)430 EC_GROUP_set_asn1_flag(EC_GROUP * group, int flag)
431 {
432 group->asn1_flag = flag;
433 }
434
435
436 int
EC_GROUP_get_asn1_flag(const EC_GROUP * group)437 EC_GROUP_get_asn1_flag(const EC_GROUP * group)
438 {
439 return group->asn1_flag;
440 }
441
442
443 void
EC_GROUP_set_point_conversion_form(EC_GROUP * group,point_conversion_form_t form)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
EC_GROUP_get_point_conversion_form(const EC_GROUP * group)452 EC_GROUP_get_point_conversion_form(const EC_GROUP * group)
453 {
454 return group->asn1_form;
455 }
456
457
458 size_t
EC_GROUP_set_seed(EC_GROUP * group,const unsigned char * p,size_t len)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 *
EC_GROUP_get0_seed(const EC_GROUP * group)479 EC_GROUP_get0_seed(const EC_GROUP * group)
480 {
481 return group->seed;
482 }
483
484
485 size_t
EC_GROUP_get_seed_len(const EC_GROUP * group)486 EC_GROUP_get_seed_len(const EC_GROUP * group)
487 {
488 return group->seed_len;
489 }
490
491
492 int
EC_GROUP_set_curve_GFp(EC_GROUP * group,const BIGNUM * p,const BIGNUM * a,const BIGNUM * b,BN_CTX * ctx)493 EC_GROUP_set_curve_GFp(EC_GROUP * group, const BIGNUM * p, const BIGNUM * a,
494 const BIGNUM * b, BN_CTX * ctx)
495 {
496 if (group->meth->group_set_curve == 0) {
497 ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
498 return 0;
499 }
500 return group->meth->group_set_curve(group, p, a, b, ctx);
501 }
502
503
504 int
EC_GROUP_get_curve_GFp(const EC_GROUP * group,BIGNUM * p,BIGNUM * a,BIGNUM * b,BN_CTX * ctx)505 EC_GROUP_get_curve_GFp(const EC_GROUP * group, BIGNUM * p, BIGNUM * a,
506 BIGNUM * b, BN_CTX * ctx)
507 {
508 if (group->meth->group_get_curve == 0) {
509 ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
510 return 0;
511 }
512 return group->meth->group_get_curve(group, p, a, b, ctx);
513 }
514
515 #ifndef OPENSSL_NO_EC2M
516 int
EC_GROUP_set_curve_GF2m(EC_GROUP * group,const BIGNUM * p,const BIGNUM * a,const BIGNUM * b,BN_CTX * ctx)517 EC_GROUP_set_curve_GF2m(EC_GROUP * group, const BIGNUM * p, const BIGNUM * a,
518 const BIGNUM * b, BN_CTX * ctx)
519 {
520 if (group->meth->group_set_curve == 0) {
521 ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
522 return 0;
523 }
524 return group->meth->group_set_curve(group, p, a, b, ctx);
525 }
526
527
528 int
EC_GROUP_get_curve_GF2m(const EC_GROUP * group,BIGNUM * p,BIGNUM * a,BIGNUM * b,BN_CTX * ctx)529 EC_GROUP_get_curve_GF2m(const EC_GROUP * group, BIGNUM * p, BIGNUM * a,
530 BIGNUM * b, BN_CTX * ctx)
531 {
532 if (group->meth->group_get_curve == 0) {
533 ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
534 return 0;
535 }
536 return group->meth->group_get_curve(group, p, a, b, ctx);
537 }
538 #endif
539
540 int
EC_GROUP_get_degree(const EC_GROUP * group)541 EC_GROUP_get_degree(const EC_GROUP * group)
542 {
543 if (group->meth->group_get_degree == 0) {
544 ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
545 return 0;
546 }
547 return group->meth->group_get_degree(group);
548 }
549
550
551 int
EC_GROUP_check_discriminant(const EC_GROUP * group,BN_CTX * ctx)552 EC_GROUP_check_discriminant(const EC_GROUP * group, BN_CTX * ctx)
553 {
554 if (group->meth->group_check_discriminant == 0) {
555 ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
556 return 0;
557 }
558 return group->meth->group_check_discriminant(group, ctx);
559 }
560
561
562 int
EC_GROUP_cmp(const EC_GROUP * a,const EC_GROUP * b,BN_CTX * ctx)563 EC_GROUP_cmp(const EC_GROUP * a, const EC_GROUP * b, BN_CTX * ctx)
564 {
565 int r = 0;
566 BIGNUM *a1, *a2, *a3, *b1, *b2, *b3;
567 BN_CTX *ctx_new = NULL;
568
569 /* compare the field types */
570 if (EC_METHOD_get_field_type(EC_GROUP_method_of(a)) !=
571 EC_METHOD_get_field_type(EC_GROUP_method_of(b)))
572 return 1;
573 /* compare the curve name (if present in both) */
574 if (EC_GROUP_get_curve_name(a) && EC_GROUP_get_curve_name(b) &&
575 EC_GROUP_get_curve_name(a) != EC_GROUP_get_curve_name(b))
576 return 1;
577
578 if (!ctx)
579 ctx_new = ctx = BN_CTX_new();
580 if (!ctx)
581 return -1;
582
583 BN_CTX_start(ctx);
584 if ((a1 = BN_CTX_get(ctx)) == NULL)
585 goto err;
586 if ((a2 = BN_CTX_get(ctx)) == NULL)
587 goto err;
588 if ((a3 = BN_CTX_get(ctx)) == NULL)
589 goto err;
590 if ((b1 = BN_CTX_get(ctx)) == NULL)
591 goto err;
592 if ((b2 = BN_CTX_get(ctx)) == NULL)
593 goto err;
594 if ((b3 = BN_CTX_get(ctx)) == NULL)
595 goto err;
596
597 /*
598 * XXX This approach assumes that the external representation of
599 * curves over the same field type is the same.
600 */
601 if (!a->meth->group_get_curve(a, a1, a2, a3, ctx) ||
602 !b->meth->group_get_curve(b, b1, b2, b3, ctx))
603 r = 1;
604
605 if (r || BN_cmp(a1, b1) || BN_cmp(a2, b2) || BN_cmp(a3, b3))
606 r = 1;
607
608 /* XXX EC_POINT_cmp() assumes that the methods are equal */
609 if (r || EC_POINT_cmp(a, EC_GROUP_get0_generator(a),
610 EC_GROUP_get0_generator(b), ctx))
611 r = 1;
612
613 if (!r) {
614 /* compare the order and cofactor */
615 if (!EC_GROUP_get_order(a, a1, ctx) ||
616 !EC_GROUP_get_order(b, b1, ctx) ||
617 !EC_GROUP_get_cofactor(a, a2, ctx) ||
618 !EC_GROUP_get_cofactor(b, b2, ctx))
619 goto err;
620 if (BN_cmp(a1, b1) || BN_cmp(a2, b2))
621 r = 1;
622 }
623 BN_CTX_end(ctx);
624 if (ctx_new)
625 BN_CTX_free(ctx);
626
627 return r;
628
629 err:
630 BN_CTX_end(ctx);
631 if (ctx_new)
632 BN_CTX_free(ctx);
633 return -1;
634 }
635
636 /*
637 * Coordinate blinding for EC_POINT.
638 *
639 * The underlying EC_METHOD can optionally implement this function:
640 * underlying implementations should return 0 on errors, or 1 on success.
641 *
642 * This wrapper returns 1 in case the underlying EC_METHOD does not support
643 * coordinate blinding.
644 */
645 int
ec_point_blind_coordinates(const EC_GROUP * group,EC_POINT * p,BN_CTX * ctx)646 ec_point_blind_coordinates(const EC_GROUP *group, EC_POINT *p, BN_CTX *ctx)
647 {
648 if (group->meth->blind_coordinates == NULL)
649 return 1;
650
651 return group->meth->blind_coordinates(group, p, ctx);
652 }
653
654 /* this has 'package' visibility */
655 int
EC_EX_DATA_set_data(EC_EXTRA_DATA ** ex_data,void * data,void * (* dup_func)(void *),void (* free_func)(void *),void (* clear_free_func)(void *))656 EC_EX_DATA_set_data(EC_EXTRA_DATA ** ex_data, void *data,
657 void *(*dup_func) (void *),
658 void (*free_func) (void *),
659 void (*clear_free_func) (void *))
660 {
661 EC_EXTRA_DATA *d;
662
663 if (ex_data == NULL)
664 return 0;
665
666 for (d = *ex_data; d != NULL; d = d->next) {
667 if (d->dup_func == dup_func && d->free_func == free_func &&
668 d->clear_free_func == clear_free_func) {
669 ECerror(EC_R_SLOT_FULL);
670 return 0;
671 }
672 }
673
674 if (data == NULL)
675 /* no explicit entry needed */
676 return 1;
677
678 d = malloc(sizeof *d);
679 if (d == NULL)
680 return 0;
681
682 d->data = data;
683 d->dup_func = dup_func;
684 d->free_func = free_func;
685 d->clear_free_func = clear_free_func;
686
687 d->next = *ex_data;
688 *ex_data = d;
689
690 return 1;
691 }
692
693 /* this has 'package' visibility */
694 void *
EC_EX_DATA_get_data(const EC_EXTRA_DATA * ex_data,void * (* dup_func)(void *),void (* free_func)(void *),void (* clear_free_func)(void *))695 EC_EX_DATA_get_data(const EC_EXTRA_DATA * ex_data,
696 void *(*dup_func) (void *),
697 void (*free_func) (void *),
698 void (*clear_free_func) (void *))
699 {
700 const EC_EXTRA_DATA *d;
701
702 for (d = ex_data; d != NULL; d = d->next) {
703 if (d->dup_func == dup_func && d->free_func == free_func && d->clear_free_func == clear_free_func)
704 return d->data;
705 }
706
707 return NULL;
708 }
709
710 /* this has 'package' visibility */
711 void
EC_EX_DATA_free_data(EC_EXTRA_DATA ** ex_data,void * (* dup_func)(void *),void (* free_func)(void *),void (* clear_free_func)(void *))712 EC_EX_DATA_free_data(EC_EXTRA_DATA ** ex_data,
713 void *(*dup_func) (void *),
714 void (*free_func) (void *),
715 void (*clear_free_func) (void *))
716 {
717 EC_EXTRA_DATA **p;
718
719 if (ex_data == NULL)
720 return;
721
722 for (p = ex_data; *p != NULL; p = &((*p)->next)) {
723 if ((*p)->dup_func == dup_func &&
724 (*p)->free_func == free_func &&
725 (*p)->clear_free_func == clear_free_func) {
726 EC_EXTRA_DATA *next = (*p)->next;
727
728 (*p)->free_func((*p)->data);
729 free(*p);
730
731 *p = next;
732 return;
733 }
734 }
735 }
736
737 /* this has 'package' visibility */
738 void
EC_EX_DATA_clear_free_data(EC_EXTRA_DATA ** ex_data,void * (* dup_func)(void *),void (* free_func)(void *),void (* clear_free_func)(void *))739 EC_EX_DATA_clear_free_data(EC_EXTRA_DATA ** ex_data,
740 void *(*dup_func) (void *),
741 void (*free_func) (void *),
742 void (*clear_free_func) (void *))
743 {
744 EC_EXTRA_DATA **p;
745
746 if (ex_data == NULL)
747 return;
748
749 for (p = ex_data; *p != NULL; p = &((*p)->next)) {
750 if ((*p)->dup_func == dup_func &&
751 (*p)->free_func == free_func &&
752 (*p)->clear_free_func == clear_free_func) {
753 EC_EXTRA_DATA *next = (*p)->next;
754
755 (*p)->clear_free_func((*p)->data);
756 free(*p);
757
758 *p = next;
759 return;
760 }
761 }
762 }
763
764 /* this has 'package' visibility */
765 void
EC_EX_DATA_free_all_data(EC_EXTRA_DATA ** ex_data)766 EC_EX_DATA_free_all_data(EC_EXTRA_DATA ** ex_data)
767 {
768 EC_EXTRA_DATA *d;
769
770 if (ex_data == NULL)
771 return;
772
773 d = *ex_data;
774 while (d) {
775 EC_EXTRA_DATA *next = d->next;
776
777 d->free_func(d->data);
778 free(d);
779
780 d = next;
781 }
782 *ex_data = NULL;
783 }
784
785 /* this has 'package' visibility */
786 void
EC_EX_DATA_clear_free_all_data(EC_EXTRA_DATA ** ex_data)787 EC_EX_DATA_clear_free_all_data(EC_EXTRA_DATA ** ex_data)
788 {
789 EC_EXTRA_DATA *d;
790
791 if (ex_data == NULL)
792 return;
793
794 d = *ex_data;
795 while (d) {
796 EC_EXTRA_DATA *next = d->next;
797
798 d->clear_free_func(d->data);
799 free(d);
800
801 d = next;
802 }
803 *ex_data = NULL;
804 }
805
806
807 /* functions for EC_POINT objects */
808
809 EC_POINT *
EC_POINT_new(const EC_GROUP * group)810 EC_POINT_new(const EC_GROUP * group)
811 {
812 EC_POINT *ret;
813
814 if (group == NULL) {
815 ECerror(ERR_R_PASSED_NULL_PARAMETER);
816 return NULL;
817 }
818 if (group->meth->point_init == 0) {
819 ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
820 return NULL;
821 }
822 ret = malloc(sizeof *ret);
823 if (ret == NULL) {
824 ECerror(ERR_R_MALLOC_FAILURE);
825 return NULL;
826 }
827 ret->meth = group->meth;
828
829 if (!ret->meth->point_init(ret)) {
830 free(ret);
831 return NULL;
832 }
833 return ret;
834 }
835
836
837 void
EC_POINT_free(EC_POINT * point)838 EC_POINT_free(EC_POINT * point)
839 {
840 if (!point)
841 return;
842
843 if (point->meth->point_finish != 0)
844 point->meth->point_finish(point);
845 free(point);
846 }
847
848
849 void
EC_POINT_clear_free(EC_POINT * point)850 EC_POINT_clear_free(EC_POINT * point)
851 {
852 if (!point)
853 return;
854
855 if (point->meth->point_clear_finish != 0)
856 point->meth->point_clear_finish(point);
857 else if (point->meth->point_finish != 0)
858 point->meth->point_finish(point);
859 freezero(point, sizeof *point);
860 }
861
862
863 int
EC_POINT_copy(EC_POINT * dest,const EC_POINT * src)864 EC_POINT_copy(EC_POINT * dest, const EC_POINT * src)
865 {
866 if (dest->meth->point_copy == 0) {
867 ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
868 return 0;
869 }
870 if (dest->meth != src->meth) {
871 ECerror(EC_R_INCOMPATIBLE_OBJECTS);
872 return 0;
873 }
874 if (dest == src)
875 return 1;
876 return dest->meth->point_copy(dest, src);
877 }
878
879
880 EC_POINT *
EC_POINT_dup(const EC_POINT * a,const EC_GROUP * group)881 EC_POINT_dup(const EC_POINT * a, const EC_GROUP * group)
882 {
883 EC_POINT *t;
884 int r;
885
886 if (a == NULL)
887 return NULL;
888
889 t = EC_POINT_new(group);
890 if (t == NULL)
891 return (NULL);
892 r = EC_POINT_copy(t, a);
893 if (!r) {
894 EC_POINT_free(t);
895 return NULL;
896 } else
897 return t;
898 }
899
900
901 const EC_METHOD *
EC_POINT_method_of(const EC_POINT * point)902 EC_POINT_method_of(const EC_POINT * point)
903 {
904 return point->meth;
905 }
906
907
908 int
EC_POINT_set_to_infinity(const EC_GROUP * group,EC_POINT * point)909 EC_POINT_set_to_infinity(const EC_GROUP * group, EC_POINT * point)
910 {
911 if (group->meth->point_set_to_infinity == 0) {
912 ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
913 return 0;
914 }
915 if (group->meth != point->meth) {
916 ECerror(EC_R_INCOMPATIBLE_OBJECTS);
917 return 0;
918 }
919 return group->meth->point_set_to_infinity(group, point);
920 }
921
922
923 int
EC_POINT_set_Jprojective_coordinates_GFp(const EC_GROUP * group,EC_POINT * point,const BIGNUM * x,const BIGNUM * y,const BIGNUM * z,BN_CTX * ctx)924 EC_POINT_set_Jprojective_coordinates_GFp(const EC_GROUP *group, EC_POINT *point,
925 const BIGNUM *x, const BIGNUM *y, const BIGNUM *z, BN_CTX *ctx)
926 {
927 if (group->meth->point_set_Jprojective_coordinates_GFp == 0) {
928 ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
929 return 0;
930 }
931 if (group->meth != point->meth) {
932 ECerror(EC_R_INCOMPATIBLE_OBJECTS);
933 return 0;
934 }
935 return group->meth->point_set_Jprojective_coordinates_GFp(group, point, x, y, z, ctx);
936 }
937
938
939 int
EC_POINT_get_Jprojective_coordinates_GFp(const EC_GROUP * group,const EC_POINT * point,BIGNUM * x,BIGNUM * y,BIGNUM * z,BN_CTX * ctx)940 EC_POINT_get_Jprojective_coordinates_GFp(const EC_GROUP *group,
941 const EC_POINT *point, BIGNUM *x, BIGNUM *y, BIGNUM *z, BN_CTX *ctx)
942 {
943 if (group->meth->point_get_Jprojective_coordinates_GFp == 0) {
944 ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
945 return 0;
946 }
947 if (group->meth != point->meth) {
948 ECerror(EC_R_INCOMPATIBLE_OBJECTS);
949 return 0;
950 }
951 return group->meth->point_get_Jprojective_coordinates_GFp(group, point, x, y, z, ctx);
952 }
953
954
955 int
EC_POINT_set_affine_coordinates_GFp(const EC_GROUP * group,EC_POINT * point,const BIGNUM * x,const BIGNUM * y,BN_CTX * ctx)956 EC_POINT_set_affine_coordinates_GFp(const EC_GROUP *group, EC_POINT *point,
957 const BIGNUM *x, const BIGNUM *y, BN_CTX *ctx)
958 {
959 if (group->meth->point_set_affine_coordinates == 0) {
960 ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
961 return 0;
962 }
963 if (group->meth != point->meth) {
964 ECerror(EC_R_INCOMPATIBLE_OBJECTS);
965 return 0;
966 }
967 return group->meth->point_set_affine_coordinates(group, point, x, y, ctx);
968 }
969
970 #ifndef OPENSSL_NO_EC2M
971 int
EC_POINT_set_affine_coordinates_GF2m(const EC_GROUP * group,EC_POINT * point,const BIGNUM * x,const BIGNUM * y,BN_CTX * ctx)972 EC_POINT_set_affine_coordinates_GF2m(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 == 0) {
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 return group->meth->point_set_affine_coordinates(group, point, x, y, ctx);
984 }
985 #endif
986
987 int
EC_POINT_get_affine_coordinates_GFp(const EC_GROUP * group,const EC_POINT * point,BIGNUM * x,BIGNUM * y,BN_CTX * ctx)988 EC_POINT_get_affine_coordinates_GFp(const EC_GROUP *group, const EC_POINT *point,
989 BIGNUM *x, BIGNUM *y, BN_CTX *ctx)
990 {
991 if (group->meth->point_get_affine_coordinates == 0) {
992 ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
993 return 0;
994 }
995 if (group->meth != point->meth) {
996 ECerror(EC_R_INCOMPATIBLE_OBJECTS);
997 return 0;
998 }
999 return group->meth->point_get_affine_coordinates(group, point, x, y, ctx);
1000 }
1001
1002 #ifndef OPENSSL_NO_EC2M
1003 int
EC_POINT_get_affine_coordinates_GF2m(const EC_GROUP * group,const EC_POINT * point,BIGNUM * x,BIGNUM * y,BN_CTX * ctx)1004 EC_POINT_get_affine_coordinates_GF2m(const EC_GROUP *group, const EC_POINT *point,
1005 BIGNUM *x, BIGNUM *y, BN_CTX *ctx)
1006 {
1007 if (group->meth->point_get_affine_coordinates == 0) {
1008 ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
1009 return 0;
1010 }
1011 if (group->meth != point->meth) {
1012 ECerror(EC_R_INCOMPATIBLE_OBJECTS);
1013 return 0;
1014 }
1015 return group->meth->point_get_affine_coordinates(group, point, x, y, ctx);
1016 }
1017 #endif
1018
1019 int
EC_POINT_add(const EC_GROUP * group,EC_POINT * r,const EC_POINT * a,const EC_POINT * b,BN_CTX * ctx)1020 EC_POINT_add(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a,
1021 const EC_POINT *b, BN_CTX *ctx)
1022 {
1023 if (group->meth->add == 0) {
1024 ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
1025 return 0;
1026 }
1027 if ((group->meth != r->meth) || (r->meth != a->meth) || (a->meth != b->meth)) {
1028 ECerror(EC_R_INCOMPATIBLE_OBJECTS);
1029 return 0;
1030 }
1031 return group->meth->add(group, r, a, b, ctx);
1032 }
1033
1034
1035 int
EC_POINT_dbl(const EC_GROUP * group,EC_POINT * r,const EC_POINT * a,BN_CTX * ctx)1036 EC_POINT_dbl(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a, BN_CTX *ctx)
1037 {
1038 if (group->meth->dbl == 0) {
1039 ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
1040 return 0;
1041 }
1042 if ((group->meth != r->meth) || (r->meth != a->meth)) {
1043 ECerror(EC_R_INCOMPATIBLE_OBJECTS);
1044 return 0;
1045 }
1046 return group->meth->dbl(group, r, a, ctx);
1047 }
1048
1049
1050 int
EC_POINT_invert(const EC_GROUP * group,EC_POINT * a,BN_CTX * ctx)1051 EC_POINT_invert(const EC_GROUP *group, EC_POINT *a, BN_CTX *ctx)
1052 {
1053 if (group->meth->invert == 0) {
1054 ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
1055 return 0;
1056 }
1057 if (group->meth != a->meth) {
1058 ECerror(EC_R_INCOMPATIBLE_OBJECTS);
1059 return 0;
1060 }
1061 return group->meth->invert(group, a, ctx);
1062 }
1063
1064
1065 int
EC_POINT_is_at_infinity(const EC_GROUP * group,const EC_POINT * point)1066 EC_POINT_is_at_infinity(const EC_GROUP *group, const EC_POINT *point)
1067 {
1068 if (group->meth->is_at_infinity == 0) {
1069 ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
1070 return 0;
1071 }
1072 if (group->meth != point->meth) {
1073 ECerror(EC_R_INCOMPATIBLE_OBJECTS);
1074 return 0;
1075 }
1076 return group->meth->is_at_infinity(group, point);
1077 }
1078
1079
1080 int
EC_POINT_is_on_curve(const EC_GROUP * group,const EC_POINT * point,BN_CTX * ctx)1081 EC_POINT_is_on_curve(const EC_GROUP * group, const EC_POINT * point, BN_CTX * ctx)
1082 {
1083 if (group->meth->is_on_curve == 0) {
1084 ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
1085 return 0;
1086 }
1087 if (group->meth != point->meth) {
1088 ECerror(EC_R_INCOMPATIBLE_OBJECTS);
1089 return 0;
1090 }
1091 return group->meth->is_on_curve(group, point, ctx);
1092 }
1093
1094
1095 int
EC_POINT_cmp(const EC_GROUP * group,const EC_POINT * a,const EC_POINT * b,BN_CTX * ctx)1096 EC_POINT_cmp(const EC_GROUP *group, const EC_POINT *a, const EC_POINT *b,
1097 BN_CTX * ctx)
1098 {
1099 if (group->meth->point_cmp == 0) {
1100 ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
1101 return -1;
1102 }
1103 if ((group->meth != a->meth) || (a->meth != b->meth)) {
1104 ECerror(EC_R_INCOMPATIBLE_OBJECTS);
1105 return -1;
1106 }
1107 return group->meth->point_cmp(group, a, b, ctx);
1108 }
1109
1110
1111 int
EC_POINT_make_affine(const EC_GROUP * group,EC_POINT * point,BN_CTX * ctx)1112 EC_POINT_make_affine(const EC_GROUP *group, EC_POINT *point, BN_CTX *ctx)
1113 {
1114 if (group->meth->make_affine == 0) {
1115 ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
1116 return 0;
1117 }
1118 if (group->meth != point->meth) {
1119 ECerror(EC_R_INCOMPATIBLE_OBJECTS);
1120 return 0;
1121 }
1122 return group->meth->make_affine(group, point, ctx);
1123 }
1124
1125
1126 int
EC_POINTs_make_affine(const EC_GROUP * group,size_t num,EC_POINT * points[],BN_CTX * ctx)1127 EC_POINTs_make_affine(const EC_GROUP *group, size_t num, EC_POINT *points[],
1128 BN_CTX *ctx)
1129 {
1130 size_t i;
1131
1132 if (group->meth->points_make_affine == 0) {
1133 ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
1134 return 0;
1135 }
1136 for (i = 0; i < num; i++) {
1137 if (group->meth != points[i]->meth) {
1138 ECerror(EC_R_INCOMPATIBLE_OBJECTS);
1139 return 0;
1140 }
1141 }
1142 return group->meth->points_make_affine(group, num, points, ctx);
1143 }
1144
1145
1146 /* Functions for point multiplication */
1147 int
EC_POINTs_mul(const EC_GROUP * group,EC_POINT * r,const BIGNUM * scalar,size_t num,const EC_POINT * points[],const BIGNUM * scalars[],BN_CTX * ctx)1148 EC_POINTs_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar,
1149 size_t num, const EC_POINT *points[], const BIGNUM *scalars[], BN_CTX *ctx)
1150 {
1151 /*
1152 * The function pointers must be set, and only support num == 0 and
1153 * num == 1.
1154 */
1155 if (group->meth->mul_generator_ct == NULL ||
1156 group->meth->mul_single_ct == NULL ||
1157 group->meth->mul_double_nonct == NULL ||
1158 num > 1) {
1159 ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
1160 return 0;
1161 }
1162
1163 /* Either bP or aG + bP, this is sane. */
1164 if (num == 1 && points != NULL && scalars != NULL)
1165 return EC_POINT_mul(group, r, scalar, points[0], scalars[0],
1166 ctx);
1167
1168 /* aG, this is sane */
1169 if (scalar != NULL && points == NULL && scalars == NULL)
1170 return EC_POINT_mul(group, r, scalar, NULL, NULL, ctx);
1171
1172 /* anything else is an error */
1173 ECerror(ERR_R_EC_LIB);
1174 return 0;
1175 }
1176
1177 int
EC_POINT_mul(const EC_GROUP * group,EC_POINT * r,const BIGNUM * g_scalar,const EC_POINT * point,const BIGNUM * p_scalar,BN_CTX * ctx)1178 EC_POINT_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *g_scalar,
1179 const EC_POINT *point, const BIGNUM *p_scalar, BN_CTX *ctx)
1180 {
1181 if (group->meth->mul_generator_ct == NULL ||
1182 group->meth->mul_single_ct == NULL ||
1183 group->meth->mul_double_nonct == NULL) {
1184 ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
1185 return 0;
1186 }
1187 if (g_scalar != NULL && point == NULL && p_scalar == NULL) {
1188 /*
1189 * In this case we want to compute g_scalar * GeneratorPoint:
1190 * this codepath is reached most prominently by (ephemeral) key
1191 * generation of EC cryptosystems (i.e. ECDSA keygen and sign
1192 * setup, ECDH keygen/first half), where the scalar is always
1193 * secret. This is why we ignore if BN_FLG_CONSTTIME is actually
1194 * set and we always call the constant time version.
1195 */
1196 return group->meth->mul_generator_ct(group, r, g_scalar, ctx);
1197 }
1198 if (g_scalar == NULL && point != NULL && p_scalar != NULL) {
1199 /* In this case we want to compute p_scalar * GenericPoint:
1200 * this codepath is reached most prominently by the second half
1201 * of ECDH, where the secret scalar is multiplied by the peer's
1202 * public point. To protect the secret scalar, we ignore if
1203 * BN_FLG_CONSTTIME is actually set and we always call the
1204 * constant time version.
1205 */
1206 return group->meth->mul_single_ct(group, r, p_scalar, point,
1207 ctx);
1208 }
1209 if (g_scalar != NULL && point != NULL && p_scalar != NULL) {
1210 /*
1211 * In this case we want to compute
1212 * g_scalar * GeneratorPoint + p_scalar * GenericPoint:
1213 * this codepath is reached most prominently by ECDSA signature
1214 * verification. So we call the non-ct version.
1215 */
1216 return group->meth->mul_double_nonct(group, r, g_scalar,
1217 p_scalar, point, ctx);
1218 }
1219
1220 /* Anything else is an error. */
1221 ECerror(ERR_R_EC_LIB);
1222 return 0;
1223 }
1224
1225 int
EC_GROUP_precompute_mult(EC_GROUP * group,BN_CTX * ctx)1226 EC_GROUP_precompute_mult(EC_GROUP * group, BN_CTX * ctx)
1227 {
1228 if (group->meth->precompute_mult != 0)
1229 return group->meth->precompute_mult(group, ctx);
1230 else
1231 return 1; /* nothing to do, so report success */
1232 }
1233
1234 int
EC_GROUP_have_precompute_mult(const EC_GROUP * group)1235 EC_GROUP_have_precompute_mult(const EC_GROUP * group)
1236 {
1237 if (group->meth->have_precompute_mult != 0)
1238 return group->meth->have_precompute_mult(group);
1239 else
1240 return 0; /* cannot tell whether precomputation has
1241 * been performed */
1242 }
1243
1244 EC_KEY *
ECParameters_dup(EC_KEY * key)1245 ECParameters_dup(EC_KEY *key)
1246 {
1247 unsigned char *p = NULL;
1248 EC_KEY *k = NULL;
1249 int len;
1250
1251 if (key == NULL)
1252 return (NULL);
1253
1254 if ((len = i2d_ECParameters(key, &p)) > 0)
1255 k = d2i_ECParameters(NULL, (const unsigned char **)&p, len);
1256
1257 return (k);
1258 }
1259