[crypto/ec] for ECC parameters with NULL or zero cofactor, compute it
[openssl.git] / crypto / ec / ec_lib.c
1 /* crypto/ec/ec_lib.c */
2 /*
3  * Originally written by Bodo Moeller for the OpenSSL project.
4  */
5 /* ====================================================================
6  * Copyright (c) 1998-2019 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/err.h>
67 #include <openssl/opensslv.h>
68
69 #include "ec_lcl.h"
70
71 const char EC_version[] = "EC" OPENSSL_VERSION_PTEXT;
72
73 /* local function prototypes */
74
75 static int ec_precompute_mont_data(EC_GROUP *group);
76
77 /* functions for EC_GROUP objects */
78
79 EC_GROUP *EC_GROUP_new(const EC_METHOD *meth)
80 {
81     EC_GROUP *ret;
82
83     if (meth == NULL) {
84         ECerr(EC_F_EC_GROUP_NEW, EC_R_SLOT_FULL);
85         return NULL;
86     }
87     if (meth->group_init == 0) {
88         ECerr(EC_F_EC_GROUP_NEW, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
89         return NULL;
90     }
91
92     ret = OPENSSL_malloc(sizeof(*ret));
93     if (ret == NULL) {
94         ECerr(EC_F_EC_GROUP_NEW, ERR_R_MALLOC_FAILURE);
95         return NULL;
96     }
97
98     ret->meth = meth;
99
100     ret->extra_data = NULL;
101     ret->mont_data = NULL;
102
103     ret->generator = NULL;
104     BN_init(&ret->order);
105     BN_init(&ret->cofactor);
106
107     ret->curve_name = 0;
108     ret->asn1_flag = ~EC_GROUP_ASN1_FLAG_MASK;
109     ret->asn1_form = POINT_CONVERSION_UNCOMPRESSED;
110
111     ret->seed = NULL;
112     ret->seed_len = 0;
113
114     if (!meth->group_init(ret)) {
115         OPENSSL_free(ret);
116         return NULL;
117     }
118
119     return ret;
120 }
121
122 void EC_GROUP_free(EC_GROUP *group)
123 {
124     if (!group)
125         return;
126
127     if (group->meth->group_finish != 0)
128         group->meth->group_finish(group);
129
130     EC_EX_DATA_free_all_data(&group->extra_data);
131
132     if (EC_GROUP_VERSION(group) && group->mont_data)
133         BN_MONT_CTX_free(group->mont_data);
134
135     if (group->generator != NULL)
136         EC_POINT_free(group->generator);
137     BN_free(&group->order);
138     BN_free(&group->cofactor);
139
140     if (group->seed)
141         OPENSSL_free(group->seed);
142
143     OPENSSL_free(group);
144 }
145
146 void EC_GROUP_clear_free(EC_GROUP *group)
147 {
148     if (!group)
149         return;
150
151     if (group->meth->group_clear_finish != 0)
152         group->meth->group_clear_finish(group);
153     else if (group->meth->group_finish != 0)
154         group->meth->group_finish(group);
155
156     EC_EX_DATA_clear_free_all_data(&group->extra_data);
157
158     if (EC_GROUP_VERSION(group) && group->mont_data)
159         BN_MONT_CTX_free(group->mont_data);
160
161     if (group->generator != NULL)
162         EC_POINT_clear_free(group->generator);
163     BN_clear_free(&group->order);
164     BN_clear_free(&group->cofactor);
165
166     if (group->seed) {
167         OPENSSL_cleanse(group->seed, group->seed_len);
168         OPENSSL_free(group->seed);
169     }
170
171     OPENSSL_cleanse(group, sizeof(*group));
172     OPENSSL_free(group);
173 }
174
175 int EC_GROUP_copy(EC_GROUP *dest, const EC_GROUP *src)
176 {
177     EC_EXTRA_DATA *d;
178
179     if (dest->meth->group_copy == 0) {
180         ECerr(EC_F_EC_GROUP_COPY, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
181         return 0;
182     }
183     if (dest->meth != src->meth) {
184         ECerr(EC_F_EC_GROUP_COPY, EC_R_INCOMPATIBLE_OBJECTS);
185         return 0;
186     }
187     if (dest == src)
188         return 1;
189
190     EC_EX_DATA_free_all_data(&dest->extra_data);
191
192     for (d = src->extra_data; d != NULL; d = d->next) {
193         void *t = d->dup_func(d->data);
194
195         if (t == NULL)
196             return 0;
197         if (!EC_EX_DATA_set_data
198             (&dest->extra_data, t, d->dup_func, d->free_func,
199              d->clear_free_func))
200             return 0;
201     }
202
203     if (EC_GROUP_VERSION(src) && src->mont_data != NULL) {
204         if (dest->mont_data == NULL) {
205             dest->mont_data = BN_MONT_CTX_new();
206             if (dest->mont_data == NULL)
207                 return 0;
208         }
209         if (!BN_MONT_CTX_copy(dest->mont_data, src->mont_data))
210             return 0;
211     } else {
212         /* src->generator == NULL */
213         if (EC_GROUP_VERSION(dest) && dest->mont_data != NULL) {
214             BN_MONT_CTX_free(dest->mont_data);
215             dest->mont_data = NULL;
216         }
217     }
218
219     if (src->generator != NULL) {
220         if (dest->generator == NULL) {
221             dest->generator = EC_POINT_new(dest);
222             if (dest->generator == NULL)
223                 return 0;
224         }
225         if (!EC_POINT_copy(dest->generator, src->generator))
226             return 0;
227     } else {
228         /* src->generator == NULL */
229         if (dest->generator != NULL) {
230             EC_POINT_clear_free(dest->generator);
231             dest->generator = NULL;
232         }
233     }
234
235     if (!BN_copy(&dest->order, &src->order))
236         return 0;
237     if (!BN_copy(&dest->cofactor, &src->cofactor))
238         return 0;
239
240     dest->curve_name = src->curve_name;
241     dest->asn1_flag = src->asn1_flag;
242     dest->asn1_form = src->asn1_form;
243
244     if (src->seed) {
245         if (dest->seed)
246             OPENSSL_free(dest->seed);
247         dest->seed = OPENSSL_malloc(src->seed_len);
248         if (dest->seed == NULL)
249             return 0;
250         if (!memcpy(dest->seed, src->seed, src->seed_len))
251             return 0;
252         dest->seed_len = src->seed_len;
253     } else {
254         if (dest->seed)
255             OPENSSL_free(dest->seed);
256         dest->seed = NULL;
257         dest->seed_len = 0;
258     }
259
260     return dest->meth->group_copy(dest, src);
261 }
262
263 EC_GROUP *EC_GROUP_dup(const EC_GROUP *a)
264 {
265     EC_GROUP *t = NULL;
266     int ok = 0;
267
268     if (a == NULL)
269         return NULL;
270
271     if ((t = EC_GROUP_new(a->meth)) == NULL)
272         return (NULL);
273     if (!EC_GROUP_copy(t, a))
274         goto err;
275
276     ok = 1;
277
278  err:
279     if (!ok) {
280         if (t)
281             EC_GROUP_free(t);
282         return NULL;
283     } else
284         return t;
285 }
286
287 const EC_METHOD *EC_GROUP_method_of(const EC_GROUP *group)
288 {
289     return group->meth;
290 }
291
292 int EC_METHOD_get_field_type(const EC_METHOD *meth)
293 {
294     return meth->field_type;
295 }
296
297 /*-
298  * Try computing cofactor from the generator order (n) and field cardinality (q).
299  * This works for all curves of cryptographic interest.
300  *
301  * Hasse thm: q + 1 - 2*sqrt(q) <= n*h <= q + 1 + 2*sqrt(q)
302  * h_min = (q + 1 - 2*sqrt(q))/n
303  * h_max = (q + 1 + 2*sqrt(q))/n
304  * h_max - h_min = 4*sqrt(q)/n
305  * So if n > 4*sqrt(q) holds, there is only one possible value for h:
306  * h = \lfloor (h_min + h_max)/2 \rceil = \lfloor (q + 1)/n \rceil
307  *
308  * Otherwise, zero cofactor and return success.
309  */
310 static int ec_guess_cofactor(EC_GROUP *group) {
311     int ret = 0;
312     BN_CTX *ctx = NULL;
313     BIGNUM *q = NULL;
314
315     /*-
316      * If the cofactor is too large, we cannot guess it.
317      * The RHS of below is a strict overestimate of lg(4 * sqrt(q))
318      */
319     if (BN_num_bits(&group->order) <= (BN_num_bits(&group->field) + 1) / 2 + 3) {
320         /* default to 0 */
321         BN_zero(&group->cofactor);
322         /* return success */
323         return 1;
324     }
325
326     if ((ctx = BN_CTX_new()) == NULL)
327         return 0;
328
329     BN_CTX_start(ctx);
330     if ((q = BN_CTX_get(ctx)) == NULL)
331         goto err;
332
333     /* set q = 2**m for binary fields; q = p otherwise */
334     if (group->meth->field_type == NID_X9_62_characteristic_two_field) {
335         BN_zero(q);
336         if (!BN_set_bit(q, BN_num_bits(&group->field) - 1))
337             goto err;
338     } else {
339         if (!BN_copy(q, &group->field))
340             goto err;
341     }
342
343     /* compute h = \lfloor (q + 1)/n \rceil = \lfloor (q + 1 + n/2)/n \rfloor */
344     if (!BN_rshift1(&group->cofactor, &group->order) /* n/2 */
345         || !BN_add(&group->cofactor, &group->cofactor, q) /* q + n/2 */
346         /* q + 1 + n/2 */
347         || !BN_add(&group->cofactor, &group->cofactor, BN_value_one())
348         /* (q + 1 + n/2)/n */
349         || !BN_div(&group->cofactor, NULL, &group->cofactor, &group->order, ctx))
350         goto err;
351     ret = 1;
352  err:
353     BN_CTX_end(ctx);
354     BN_CTX_free(ctx);
355     return ret;
356 }
357
358 int EC_GROUP_set_generator(EC_GROUP *group, const EC_POINT *generator,
359                            const BIGNUM *order, const BIGNUM *cofactor)
360 {
361     if (generator == NULL) {
362         ECerr(EC_F_EC_GROUP_SET_GENERATOR, ERR_R_PASSED_NULL_PARAMETER);
363         return 0;
364     }
365
366     /* require group->field >= 1 */
367     if (BN_is_zero(&group->field) || BN_is_negative(&group->field)) {
368         ECerr(EC_F_EC_GROUP_SET_GENERATOR, EC_R_INVALID_FIELD);
369         return 0;
370     }
371
372     /*-
373      * - require order >= 1
374      * - enforce upper bound due to Hasse thm: order can be no more than one bit
375      *   longer than field cardinality
376      */
377     if (order == NULL || BN_is_zero(order) || BN_is_negative(order)
378         || BN_num_bits(order) > BN_num_bits(&group->field) + 1) {
379         ECerr(EC_F_EC_GROUP_SET_GENERATOR, EC_R_INVALID_GROUP_ORDER);
380         return 0;
381     }
382
383     /*-
384      * Unfortunately the cofactor is an optional field in many standards.
385      * Internally, the lib uses 0 cofactor as a marker for "unknown cofactor".
386      * So accept cofactor == NULL or cofactor >= 0.
387      */
388     if (cofactor != NULL && BN_is_negative(cofactor)) {
389         ECerr(EC_F_EC_GROUP_SET_GENERATOR, EC_R_UNKNOWN_COFACTOR);
390         return 0;
391     }
392
393     if (group->generator == NULL) {
394         group->generator = EC_POINT_new(group);
395         if (group->generator == NULL)
396             return 0;
397     }
398     if (!EC_POINT_copy(group->generator, generator))
399         return 0;
400
401     if (!BN_copy(&group->order, order))
402         return 0;
403
404     /* Either take the provided positive cofactor, or try to compute it */
405     if (cofactor != NULL && !BN_is_zero(cofactor)) {
406         if (!BN_copy(&group->cofactor, cofactor))
407             return 0;
408     } else if (!ec_guess_cofactor(group)) {
409         BN_zero(&group->cofactor);
410         return 0;
411     }
412
413     /*-
414      * Access to the `mont_data` field of an EC_GROUP struct should always be
415      * guarded by an EC_GROUP_VERSION(group) check to avoid OOB accesses, as the
416      * group might come from the FIPS module, which does not define the
417      * `mont_data` field inside the EC_GROUP structure.
418      */
419     if (EC_GROUP_VERSION(group)) {
420         /*-
421          * Some groups have an order with
422          * factors of two, which makes the Montgomery setup fail.
423          * |group->mont_data| will be NULL in this case.
424          */
425         if (BN_is_odd(&group->order))
426             return ec_precompute_mont_data(group);
427
428         BN_MONT_CTX_free(group->mont_data);
429         group->mont_data = NULL;
430     }
431
432     return 1;
433 }
434
435 const EC_POINT *EC_GROUP_get0_generator(const EC_GROUP *group)
436 {
437     return group->generator;
438 }
439
440 BN_MONT_CTX *EC_GROUP_get_mont_data(const EC_GROUP *group)
441 {
442     return EC_GROUP_VERSION(group) ? group->mont_data : NULL;
443 }
444
445 int EC_GROUP_get_order(const EC_GROUP *group, BIGNUM *order, BN_CTX *ctx)
446 {
447     if (!BN_copy(order, &group->order))
448         return 0;
449
450     return !BN_is_zero(order);
451 }
452
453 int EC_GROUP_get_cofactor(const EC_GROUP *group, BIGNUM *cofactor,
454                           BN_CTX *ctx)
455 {
456     if (!BN_copy(cofactor, &group->cofactor))
457         return 0;
458
459     return !BN_is_zero(&group->cofactor);
460 }
461
462 void EC_GROUP_set_curve_name(EC_GROUP *group, int nid)
463 {
464     group->curve_name = nid;
465 }
466
467 int EC_GROUP_get_curve_name(const EC_GROUP *group)
468 {
469     return group->curve_name;
470 }
471
472 void EC_GROUP_set_asn1_flag(EC_GROUP *group, int flag)
473 {
474     group->asn1_flag &= ~EC_GROUP_ASN1_FLAG_MASK;
475     group->asn1_flag |= flag & EC_GROUP_ASN1_FLAG_MASK;
476 }
477
478 int EC_GROUP_get_asn1_flag(const EC_GROUP *group)
479 {
480     return group->asn1_flag & EC_GROUP_ASN1_FLAG_MASK;
481 }
482
483 void EC_GROUP_set_point_conversion_form(EC_GROUP *group,
484                                         point_conversion_form_t form)
485 {
486     group->asn1_form = form;
487 }
488
489 point_conversion_form_t EC_GROUP_get_point_conversion_form(const EC_GROUP
490                                                            *group)
491 {
492     return group->asn1_form;
493 }
494
495 size_t EC_GROUP_set_seed(EC_GROUP *group, const unsigned char *p, size_t len)
496 {
497     if (group->seed) {
498         OPENSSL_free(group->seed);
499         group->seed = NULL;
500         group->seed_len = 0;
501     }
502
503     if (!len || !p)
504         return 1;
505
506     if ((group->seed = OPENSSL_malloc(len)) == NULL)
507         return 0;
508     memcpy(group->seed, p, len);
509     group->seed_len = len;
510
511     return len;
512 }
513
514 unsigned char *EC_GROUP_get0_seed(const EC_GROUP *group)
515 {
516     return group->seed;
517 }
518
519 size_t EC_GROUP_get_seed_len(const EC_GROUP *group)
520 {
521     return group->seed_len;
522 }
523
524 int EC_GROUP_set_curve_GFp(EC_GROUP *group, const BIGNUM *p, const BIGNUM *a,
525                            const BIGNUM *b, BN_CTX *ctx)
526 {
527     if (group->meth->group_set_curve == 0) {
528         ECerr(EC_F_EC_GROUP_SET_CURVE_GFP, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
529         return 0;
530     }
531     return group->meth->group_set_curve(group, p, a, b, ctx);
532 }
533
534 int EC_GROUP_get_curve_GFp(const EC_GROUP *group, BIGNUM *p, BIGNUM *a,
535                            BIGNUM *b, BN_CTX *ctx)
536 {
537     if (group->meth->group_get_curve == 0) {
538         ECerr(EC_F_EC_GROUP_GET_CURVE_GFP, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
539         return 0;
540     }
541     return group->meth->group_get_curve(group, p, a, b, ctx);
542 }
543
544 #ifndef OPENSSL_NO_EC2M
545 int EC_GROUP_set_curve_GF2m(EC_GROUP *group, const BIGNUM *p, const BIGNUM *a,
546                             const BIGNUM *b, BN_CTX *ctx)
547 {
548     if (group->meth->group_set_curve == 0) {
549         ECerr(EC_F_EC_GROUP_SET_CURVE_GF2M,
550               ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
551         return 0;
552     }
553     return group->meth->group_set_curve(group, p, a, b, ctx);
554 }
555
556 int EC_GROUP_get_curve_GF2m(const EC_GROUP *group, BIGNUM *p, BIGNUM *a,
557                             BIGNUM *b, BN_CTX *ctx)
558 {
559     if (group->meth->group_get_curve == 0) {
560         ECerr(EC_F_EC_GROUP_GET_CURVE_GF2M,
561               ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
562         return 0;
563     }
564     return group->meth->group_get_curve(group, p, a, b, ctx);
565 }
566 #endif
567
568 int EC_GROUP_get_degree(const EC_GROUP *group)
569 {
570     if (group->meth->group_get_degree == 0) {
571         ECerr(EC_F_EC_GROUP_GET_DEGREE, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
572         return 0;
573     }
574     return group->meth->group_get_degree(group);
575 }
576
577 int EC_GROUP_check_discriminant(const EC_GROUP *group, BN_CTX *ctx)
578 {
579     if (group->meth->group_check_discriminant == 0) {
580         ECerr(EC_F_EC_GROUP_CHECK_DISCRIMINANT,
581               ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
582         return 0;
583     }
584     return group->meth->group_check_discriminant(group, ctx);
585 }
586
587 int EC_GROUP_cmp(const EC_GROUP *a, const EC_GROUP *b, BN_CTX *ctx)
588 {
589     int r = 0;
590     BIGNUM *a1, *a2, *a3, *b1, *b2, *b3;
591     BN_CTX *ctx_new = NULL;
592
593     /* compare the field types */
594     if (EC_METHOD_get_field_type(EC_GROUP_method_of(a)) !=
595         EC_METHOD_get_field_type(EC_GROUP_method_of(b)))
596         return 1;
597     /* compare the curve name (if present in both) */
598     if (EC_GROUP_get_curve_name(a) && EC_GROUP_get_curve_name(b) &&
599         EC_GROUP_get_curve_name(a) != EC_GROUP_get_curve_name(b))
600         return 1;
601
602     if (!ctx)
603         ctx_new = ctx = BN_CTX_new();
604     if (!ctx)
605         return -1;
606
607     BN_CTX_start(ctx);
608     a1 = BN_CTX_get(ctx);
609     a2 = BN_CTX_get(ctx);
610     a3 = BN_CTX_get(ctx);
611     b1 = BN_CTX_get(ctx);
612     b2 = BN_CTX_get(ctx);
613     b3 = BN_CTX_get(ctx);
614     if (!b3) {
615         BN_CTX_end(ctx);
616         if (ctx_new)
617             BN_CTX_free(ctx);
618         return -1;
619     }
620
621     /*
622      * XXX This approach assumes that the external representation of curves
623      * over the same field type is the same.
624      */
625     if (!a->meth->group_get_curve(a, a1, a2, a3, ctx) ||
626         !b->meth->group_get_curve(b, b1, b2, b3, ctx))
627         r = 1;
628
629     if (r || BN_cmp(a1, b1) || BN_cmp(a2, b2) || BN_cmp(a3, b3))
630         r = 1;
631
632     /* XXX EC_POINT_cmp() assumes that the methods are equal */
633     if (r || EC_POINT_cmp(a, EC_GROUP_get0_generator(a),
634                           EC_GROUP_get0_generator(b), ctx))
635         r = 1;
636
637     if (!r) {
638         /* compare the order and cofactor */
639         if (!EC_GROUP_get_order(a, a1, ctx) ||
640             !EC_GROUP_get_order(b, b1, ctx) ||
641             !EC_GROUP_get_cofactor(a, a2, ctx) ||
642             !EC_GROUP_get_cofactor(b, b2, ctx)) {
643             BN_CTX_end(ctx);
644             if (ctx_new)
645                 BN_CTX_free(ctx);
646             return -1;
647         }
648         if (BN_cmp(a1, b1) || BN_cmp(a2, b2))
649             r = 1;
650     }
651
652     BN_CTX_end(ctx);
653     if (ctx_new)
654         BN_CTX_free(ctx);
655
656     return r;
657 }
658
659 /* this has 'package' visibility */
660 int EC_EX_DATA_set_data(EC_EXTRA_DATA **ex_data, void *data,
661                         void *(*dup_func) (void *),
662                         void (*free_func) (void *),
663                         void (*clear_free_func) (void *))
664 {
665     EC_EXTRA_DATA *d;
666
667     if (ex_data == NULL)
668         return 0;
669
670     for (d = *ex_data; d != NULL; d = d->next) {
671         if (d->dup_func == dup_func && d->free_func == free_func
672             && d->clear_free_func == clear_free_func) {
673             ECerr(EC_F_EC_EX_DATA_SET_DATA, EC_R_SLOT_FULL);
674             return 0;
675         }
676     }
677
678     if (data == NULL)
679         /* no explicit entry needed */
680         return 1;
681
682     d = OPENSSL_malloc(sizeof(*d));
683     if (d == NULL)
684         return 0;
685
686     d->data = data;
687     d->dup_func = dup_func;
688     d->free_func = free_func;
689     d->clear_free_func = clear_free_func;
690
691     d->next = *ex_data;
692     *ex_data = d;
693
694     return 1;
695 }
696
697 /* this has 'package' visibility */
698 void *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
707             && d->clear_free_func == clear_free_func)
708             return d->data;
709     }
710
711     return NULL;
712 }
713
714 /* this has 'package' visibility */
715 void 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 && (*p)->free_func == free_func
727             && (*p)->clear_free_func == clear_free_func) {
728             EC_EXTRA_DATA *next = (*p)->next;
729
730             (*p)->free_func((*p)->data);
731             OPENSSL_free(*p);
732
733             *p = next;
734             return;
735         }
736     }
737 }
738
739 /* this has 'package' visibility */
740 void EC_EX_DATA_clear_free_data(EC_EXTRA_DATA **ex_data,
741                                 void *(*dup_func) (void *),
742                                 void (*free_func) (void *),
743                                 void (*clear_free_func) (void *))
744 {
745     EC_EXTRA_DATA **p;
746
747     if (ex_data == NULL)
748         return;
749
750     for (p = ex_data; *p != NULL; p = &((*p)->next)) {
751         if ((*p)->dup_func == dup_func && (*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             OPENSSL_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 {
767     EC_EXTRA_DATA *d;
768
769     if (ex_data == NULL)
770         return;
771
772     d = *ex_data;
773     while (d) {
774         EC_EXTRA_DATA *next = d->next;
775
776         d->free_func(d->data);
777         OPENSSL_free(d);
778
779         d = next;
780     }
781     *ex_data = NULL;
782 }
783
784 /* this has 'package' visibility */
785 void EC_EX_DATA_clear_free_all_data(EC_EXTRA_DATA **ex_data)
786 {
787     EC_EXTRA_DATA *d;
788
789     if (ex_data == NULL)
790         return;
791
792     d = *ex_data;
793     while (d) {
794         EC_EXTRA_DATA *next = d->next;
795
796         d->clear_free_func(d->data);
797         OPENSSL_free(d);
798
799         d = next;
800     }
801     *ex_data = NULL;
802 }
803
804 /* functions for EC_POINT objects */
805
806 EC_POINT *EC_POINT_new(const EC_GROUP *group)
807 {
808     EC_POINT *ret;
809
810     if (group == NULL) {
811         ECerr(EC_F_EC_POINT_NEW, ERR_R_PASSED_NULL_PARAMETER);
812         return NULL;
813     }
814     if (group->meth->point_init == 0) {
815         ECerr(EC_F_EC_POINT_NEW, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
816         return NULL;
817     }
818
819     ret = OPENSSL_malloc(sizeof(*ret));
820     if (ret == NULL) {
821         ECerr(EC_F_EC_POINT_NEW, ERR_R_MALLOC_FAILURE);
822         return NULL;
823     }
824
825     ret->meth = group->meth;
826
827     if (!ret->meth->point_init(ret)) {
828         OPENSSL_free(ret);
829         return NULL;
830     }
831
832     return ret;
833 }
834
835 void EC_POINT_free(EC_POINT *point)
836 {
837     if (!point)
838         return;
839
840     if (point->meth->point_finish != 0)
841         point->meth->point_finish(point);
842     OPENSSL_free(point);
843 }
844
845 void EC_POINT_clear_free(EC_POINT *point)
846 {
847     if (!point)
848         return;
849
850     if (point->meth->point_clear_finish != 0)
851         point->meth->point_clear_finish(point);
852     else if (point->meth->point_finish != 0)
853         point->meth->point_finish(point);
854     OPENSSL_cleanse(point, sizeof(*point));
855     OPENSSL_free(point);
856 }
857
858 int EC_POINT_copy(EC_POINT *dest, const EC_POINT *src)
859 {
860     if (dest->meth->point_copy == 0) {
861         ECerr(EC_F_EC_POINT_COPY, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
862         return 0;
863     }
864     if (dest->meth != src->meth) {
865         ECerr(EC_F_EC_POINT_COPY, EC_R_INCOMPATIBLE_OBJECTS);
866         return 0;
867     }
868     if (dest == src)
869         return 1;
870     return dest->meth->point_copy(dest, src);
871 }
872
873 EC_POINT *EC_POINT_dup(const EC_POINT *a, const EC_GROUP *group)
874 {
875     EC_POINT *t;
876     int r;
877
878     if (a == NULL)
879         return NULL;
880
881     t = EC_POINT_new(group);
882     if (t == NULL)
883         return (NULL);
884     r = EC_POINT_copy(t, a);
885     if (!r) {
886         EC_POINT_free(t);
887         return NULL;
888     } else
889         return t;
890 }
891
892 const EC_METHOD *EC_POINT_method_of(const EC_POINT *point)
893 {
894     return point->meth;
895 }
896
897 int EC_POINT_set_to_infinity(const EC_GROUP *group, EC_POINT *point)
898 {
899     if (group->meth->point_set_to_infinity == 0) {
900         ECerr(EC_F_EC_POINT_SET_TO_INFINITY,
901               ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
902         return 0;
903     }
904     if (group->meth != point->meth) {
905         ECerr(EC_F_EC_POINT_SET_TO_INFINITY, EC_R_INCOMPATIBLE_OBJECTS);
906         return 0;
907     }
908     return group->meth->point_set_to_infinity(group, point);
909 }
910
911 int EC_POINT_set_Jprojective_coordinates_GFp(const EC_GROUP *group,
912                                              EC_POINT *point, const BIGNUM *x,
913                                              const BIGNUM *y, const BIGNUM *z,
914                                              BN_CTX *ctx)
915 {
916     if (group->meth->point_set_Jprojective_coordinates_GFp == 0) {
917         ECerr(EC_F_EC_POINT_SET_JPROJECTIVE_COORDINATES_GFP,
918               ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
919         return 0;
920     }
921     if (group->meth != point->meth) {
922         ECerr(EC_F_EC_POINT_SET_JPROJECTIVE_COORDINATES_GFP,
923               EC_R_INCOMPATIBLE_OBJECTS);
924         return 0;
925     }
926     return group->meth->point_set_Jprojective_coordinates_GFp(group, point, x,
927                                                               y, z, ctx);
928 }
929
930 int EC_POINT_get_Jprojective_coordinates_GFp(const EC_GROUP *group,
931                                              const EC_POINT *point, BIGNUM *x,
932                                              BIGNUM *y, BIGNUM *z,
933                                              BN_CTX *ctx)
934 {
935     if (group->meth->point_get_Jprojective_coordinates_GFp == 0) {
936         ECerr(EC_F_EC_POINT_GET_JPROJECTIVE_COORDINATES_GFP,
937               ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
938         return 0;
939     }
940     if (group->meth != point->meth) {
941         ECerr(EC_F_EC_POINT_GET_JPROJECTIVE_COORDINATES_GFP,
942               EC_R_INCOMPATIBLE_OBJECTS);
943         return 0;
944     }
945     return group->meth->point_get_Jprojective_coordinates_GFp(group, point, x,
946                                                               y, z, ctx);
947 }
948
949 int EC_POINT_set_affine_coordinates_GFp(const EC_GROUP *group,
950                                         EC_POINT *point, const BIGNUM *x,
951                                         const BIGNUM *y, BN_CTX *ctx)
952 {
953     if (group->meth->point_set_affine_coordinates == 0) {
954         ECerr(EC_F_EC_POINT_SET_AFFINE_COORDINATES_GFP,
955               ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
956         return 0;
957     }
958     if (group->meth != point->meth) {
959         ECerr(EC_F_EC_POINT_SET_AFFINE_COORDINATES_GFP,
960               EC_R_INCOMPATIBLE_OBJECTS);
961         return 0;
962     }
963     if (!group->meth->point_set_affine_coordinates(group, point, x, y, ctx))
964         return 0;
965
966     if (EC_POINT_is_on_curve(group, point, ctx) <= 0) {
967         ECerr(EC_F_EC_POINT_SET_AFFINE_COORDINATES_GFP,
968               EC_R_POINT_IS_NOT_ON_CURVE);
969         return 0;
970     }
971     return 1;
972 }
973
974 #ifndef OPENSSL_NO_EC2M
975 int EC_POINT_set_affine_coordinates_GF2m(const EC_GROUP *group,
976                                          EC_POINT *point, const BIGNUM *x,
977                                          const BIGNUM *y, BN_CTX *ctx)
978 {
979     if (group->meth->point_set_affine_coordinates == 0) {
980         ECerr(EC_F_EC_POINT_SET_AFFINE_COORDINATES_GF2M,
981               ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
982         return 0;
983     }
984     if (group->meth != point->meth) {
985         ECerr(EC_F_EC_POINT_SET_AFFINE_COORDINATES_GF2M,
986               EC_R_INCOMPATIBLE_OBJECTS);
987         return 0;
988     }
989     if (!group->meth->point_set_affine_coordinates(group, point, x, y, ctx))
990         return 0;
991
992     if (EC_POINT_is_on_curve(group, point, ctx) <= 0) {
993         ECerr(EC_F_EC_POINT_SET_AFFINE_COORDINATES_GF2M,
994               EC_R_POINT_IS_NOT_ON_CURVE);
995         return 0;
996     }
997     return 1;
998 }
999 #endif
1000
1001 int EC_POINT_get_affine_coordinates_GFp(const EC_GROUP *group,
1002                                         const EC_POINT *point, BIGNUM *x,
1003                                         BIGNUM *y, BN_CTX *ctx)
1004 {
1005     if (group->meth->point_get_affine_coordinates == 0) {
1006         ECerr(EC_F_EC_POINT_GET_AFFINE_COORDINATES_GFP,
1007               ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
1008         return 0;
1009     }
1010     if (group->meth != point->meth) {
1011         ECerr(EC_F_EC_POINT_GET_AFFINE_COORDINATES_GFP,
1012               EC_R_INCOMPATIBLE_OBJECTS);
1013         return 0;
1014     }
1015     return group->meth->point_get_affine_coordinates(group, point, x, y, ctx);
1016 }
1017
1018 #ifndef OPENSSL_NO_EC2M
1019 int EC_POINT_get_affine_coordinates_GF2m(const EC_GROUP *group,
1020                                          const EC_POINT *point, BIGNUM *x,
1021                                          BIGNUM *y, BN_CTX *ctx)
1022 {
1023     if (group->meth->point_get_affine_coordinates == 0) {
1024         ECerr(EC_F_EC_POINT_GET_AFFINE_COORDINATES_GF2M,
1025               ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
1026         return 0;
1027     }
1028     if (group->meth != point->meth) {
1029         ECerr(EC_F_EC_POINT_GET_AFFINE_COORDINATES_GF2M,
1030               EC_R_INCOMPATIBLE_OBJECTS);
1031         return 0;
1032     }
1033     return group->meth->point_get_affine_coordinates(group, point, x, y, ctx);
1034 }
1035 #endif
1036
1037 int EC_POINT_add(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a,
1038                  const EC_POINT *b, BN_CTX *ctx)
1039 {
1040     if (group->meth->add == 0) {
1041         ECerr(EC_F_EC_POINT_ADD, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
1042         return 0;
1043     }
1044     if ((group->meth != r->meth) || (r->meth != a->meth)
1045         || (a->meth != b->meth)) {
1046         ECerr(EC_F_EC_POINT_ADD, EC_R_INCOMPATIBLE_OBJECTS);
1047         return 0;
1048     }
1049     return group->meth->add(group, r, a, b, ctx);
1050 }
1051
1052 int EC_POINT_dbl(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a,
1053                  BN_CTX *ctx)
1054 {
1055     if (group->meth->dbl == 0) {
1056         ECerr(EC_F_EC_POINT_DBL, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
1057         return 0;
1058     }
1059     if ((group->meth != r->meth) || (r->meth != a->meth)) {
1060         ECerr(EC_F_EC_POINT_DBL, EC_R_INCOMPATIBLE_OBJECTS);
1061         return 0;
1062     }
1063     return group->meth->dbl(group, r, a, ctx);
1064 }
1065
1066 int EC_POINT_invert(const EC_GROUP *group, EC_POINT *a, BN_CTX *ctx)
1067 {
1068     if (group->meth->invert == 0) {
1069         ECerr(EC_F_EC_POINT_INVERT, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
1070         return 0;
1071     }
1072     if (group->meth != a->meth) {
1073         ECerr(EC_F_EC_POINT_INVERT, EC_R_INCOMPATIBLE_OBJECTS);
1074         return 0;
1075     }
1076     return group->meth->invert(group, a, ctx);
1077 }
1078
1079 int EC_POINT_is_at_infinity(const EC_GROUP *group, const EC_POINT *point)
1080 {
1081     if (group->meth->is_at_infinity == 0) {
1082         ECerr(EC_F_EC_POINT_IS_AT_INFINITY,
1083               ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
1084         return 0;
1085     }
1086     if (group->meth != point->meth) {
1087         ECerr(EC_F_EC_POINT_IS_AT_INFINITY, EC_R_INCOMPATIBLE_OBJECTS);
1088         return 0;
1089     }
1090     return group->meth->is_at_infinity(group, point);
1091 }
1092
1093 /*
1094  * Check whether an EC_POINT is on the curve or not. Note that the return
1095  * value for this function should NOT be treated as a boolean. Return values:
1096  *  1: The point is on the curve
1097  *  0: The point is not on the curve
1098  * -1: An error occurred
1099  */
1100 int EC_POINT_is_on_curve(const EC_GROUP *group, const EC_POINT *point,
1101                          BN_CTX *ctx)
1102 {
1103     if (group->meth->is_on_curve == 0) {
1104         ECerr(EC_F_EC_POINT_IS_ON_CURVE, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
1105         return 0;
1106     }
1107     if (group->meth != point->meth) {
1108         ECerr(EC_F_EC_POINT_IS_ON_CURVE, EC_R_INCOMPATIBLE_OBJECTS);
1109         return 0;
1110     }
1111     return group->meth->is_on_curve(group, point, ctx);
1112 }
1113
1114 int EC_POINT_cmp(const EC_GROUP *group, const EC_POINT *a, const EC_POINT *b,
1115                  BN_CTX *ctx)
1116 {
1117     if (group->meth->point_cmp == 0) {
1118         ECerr(EC_F_EC_POINT_CMP, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
1119         return -1;
1120     }
1121     if ((group->meth != a->meth) || (a->meth != b->meth)) {
1122         ECerr(EC_F_EC_POINT_CMP, EC_R_INCOMPATIBLE_OBJECTS);
1123         return -1;
1124     }
1125     return group->meth->point_cmp(group, a, b, ctx);
1126 }
1127
1128 int EC_POINT_make_affine(const EC_GROUP *group, EC_POINT *point, BN_CTX *ctx)
1129 {
1130     if (group->meth->make_affine == 0) {
1131         ECerr(EC_F_EC_POINT_MAKE_AFFINE, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
1132         return 0;
1133     }
1134     if (group->meth != point->meth) {
1135         ECerr(EC_F_EC_POINT_MAKE_AFFINE, EC_R_INCOMPATIBLE_OBJECTS);
1136         return 0;
1137     }
1138     return group->meth->make_affine(group, point, ctx);
1139 }
1140
1141 int EC_POINTs_make_affine(const EC_GROUP *group, size_t num,
1142                           EC_POINT *points[], BN_CTX *ctx)
1143 {
1144     size_t i;
1145
1146     if (group->meth->points_make_affine == 0) {
1147         ECerr(EC_F_EC_POINTS_MAKE_AFFINE, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
1148         return 0;
1149     }
1150     for (i = 0; i < num; i++) {
1151         if (group->meth != points[i]->meth) {
1152             ECerr(EC_F_EC_POINTS_MAKE_AFFINE, EC_R_INCOMPATIBLE_OBJECTS);
1153             return 0;
1154         }
1155     }
1156     return group->meth->points_make_affine(group, num, points, ctx);
1157 }
1158
1159 /*
1160  * Functions for point multiplication. If group->meth->mul is 0, we use the
1161  * wNAF-based implementations in ec_mult.c; otherwise we dispatch through
1162  * methods.
1163  */
1164
1165 int EC_POINTs_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar,
1166                   size_t num, const EC_POINT *points[],
1167                   const BIGNUM *scalars[], BN_CTX *ctx)
1168 {
1169     if (group->meth->mul == 0)
1170         /* use default */
1171         return ec_wNAF_mul(group, r, scalar, num, points, scalars, ctx);
1172
1173     return group->meth->mul(group, r, scalar, num, points, scalars, ctx);
1174 }
1175
1176 int EC_POINT_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *g_scalar,
1177                  const EC_POINT *point, const BIGNUM *p_scalar, BN_CTX *ctx)
1178 {
1179     /* just a convenient interface to EC_POINTs_mul() */
1180
1181     const EC_POINT *points[1];
1182     const BIGNUM *scalars[1];
1183
1184     points[0] = point;
1185     scalars[0] = p_scalar;
1186
1187     return EC_POINTs_mul(group, r, g_scalar,
1188                          (point != NULL
1189                           && p_scalar != NULL), points, scalars, ctx);
1190 }
1191
1192 int EC_GROUP_precompute_mult(EC_GROUP *group, BN_CTX *ctx)
1193 {
1194     if (group->meth->mul == 0)
1195         /* use default */
1196         return ec_wNAF_precompute_mult(group, ctx);
1197
1198     if (group->meth->precompute_mult != 0)
1199         return group->meth->precompute_mult(group, ctx);
1200     else
1201         return 1;               /* nothing to do, so report success */
1202 }
1203
1204 int EC_GROUP_have_precompute_mult(const EC_GROUP *group)
1205 {
1206     if (group->meth->mul == 0)
1207         /* use default */
1208         return ec_wNAF_have_precompute_mult(group);
1209
1210     if (group->meth->have_precompute_mult != 0)
1211         return group->meth->have_precompute_mult(group);
1212     else
1213         return 0;               /* cannot tell whether precomputation has
1214                                  * been performed */
1215 }
1216
1217 /*-
1218  * ec_precompute_mont_data sets |group->mont_data| from |group->order| and
1219  * returns one on success. On error it returns zero.
1220  *
1221  * Note: this function must be called only after verifying that
1222  * EC_GROUP_VERSION(group) returns true.
1223  * The reason for this is that access to the `mont_data` field of an EC_GROUP
1224  * struct should always be guarded by an EC_GROUP_VERSION(group) check to avoid
1225  * OOB accesses, as the group might come from the FIPS module, which does not
1226  * define the `mont_data` field inside the EC_GROUP structure.
1227  */
1228 static
1229 int ec_precompute_mont_data(EC_GROUP *group)
1230 {
1231     BN_CTX *ctx = BN_CTX_new();
1232     int ret = 0;
1233
1234     if (group->mont_data) {
1235         BN_MONT_CTX_free(group->mont_data);
1236         group->mont_data = NULL;
1237     }
1238
1239     if (ctx == NULL)
1240         goto err;
1241
1242     group->mont_data = BN_MONT_CTX_new();
1243     if (!group->mont_data)
1244         goto err;
1245
1246     if (!BN_MONT_CTX_set(group->mont_data, &group->order, ctx)) {
1247         BN_MONT_CTX_free(group->mont_data);
1248         group->mont_data = NULL;
1249         goto err;
1250     }
1251
1252     ret = 1;
1253
1254  err:
1255
1256     if (ctx)
1257         BN_CTX_free(ctx);
1258     return ret;
1259 }