ec_lib.c revision 352193 
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
71const char EC_version[] = "EC" OPENSSL_VERSION_PTEXT;
72
73/* local function prototypes */
74
75static int ec_precompute_mont_data(EC_GROUP *group);
76
77/* functions for EC_GROUP objects */
78
79EC_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
122void 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
146void 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
175int 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
263EC_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
287const EC_METHOD *EC_GROUP_method_of(const EC_GROUP *group)
288{
289    return group->meth;
290}
291
292int 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 */
310static 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
358int 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
435const EC_POINT *EC_GROUP_get0_generator(const EC_GROUP *group)
436{
437    return group->generator;
438}
439
440BN_MONT_CTX *EC_GROUP_get_mont_data(const EC_GROUP *group)
441{
442    return EC_GROUP_VERSION(group) ? group->mont_data : NULL;
443}
444
445int 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
453int 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
462void EC_GROUP_set_curve_name(EC_GROUP *group, int nid)
463{
464    group->curve_name = nid;
465}
466
467int EC_GROUP_get_curve_name(const EC_GROUP *group)
468{
469    return group->curve_name;
470}
471
472void 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
478int EC_GROUP_get_asn1_flag(const EC_GROUP *group)
479{
480    return group->asn1_flag & EC_GROUP_ASN1_FLAG_MASK;
481}
482
483void EC_GROUP_set_point_conversion_form(EC_GROUP *group,
484                                        point_conversion_form_t form)
485{
486    group->asn1_form = form;
487}
488
489point_conversion_form_t EC_GROUP_get_point_conversion_form(const EC_GROUP
490                                                           *group)
491{
492    return group->asn1_form;
493}
494
495size_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
514unsigned char *EC_GROUP_get0_seed(const EC_GROUP *group)
515{
516    return group->seed;
517}
518
519size_t EC_GROUP_get_seed_len(const EC_GROUP *group)
520{
521    return group->seed_len;
522}
523
524int 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
534int 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
545int 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
556int 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
568int 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
577int 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
587int 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 */
660int 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 */
698void *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 */
715void 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 */
740void 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 */
765void 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 */
785void 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
806EC_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
835void 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
845void 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
858int 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
873EC_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
892const EC_METHOD *EC_POINT_method_of(const EC_POINT *point)
893{
894    return point->meth;
895}
896
897int 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
911int 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
930int 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
949int 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
975int 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
1001int 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
1019int 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
1037int 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
1052int 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
1066int 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
1079int 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 */
1100int 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
1114int 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
1128int 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
1141int 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
1165int 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
1176int 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
1192int 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
1204int 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 */
1228static
1229int 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}
1260
1261/*
1262 * This is just a wrapper around the public functions
1263 *  - EC_GROUP_get_curve_GF2m
1264 *  - EC_GROUP_get_curve_GFp
1265 *
1266 * It is meant to facilitate backporting of code from newer branches, where
1267 * the public API includes a "field agnostic" version of it.
1268 */
1269int ec_group_get_curve(const EC_GROUP *group, BIGNUM *p, BIGNUM *a,
1270                       BIGNUM *b, BN_CTX *ctx)
1271{
1272    int field_nid;
1273
1274    field_nid = EC_METHOD_get_field_type(EC_GROUP_method_of(group));
1275
1276#ifndef OPENSSL_NO_EC2M
1277    if (field_nid == NID_X9_62_characteristic_two_field) {
1278        return EC_GROUP_get_curve_GF2m(group, p, a, b, ctx);
1279    } else
1280#endif /* !def(OPENSSL_NO_EC2M) */
1281    if (field_nid == NID_X9_62_prime_field) {
1282        return EC_GROUP_get_curve_GFp(group, p, a, b, ctx);
1283    } else {
1284        /* this should never happen */
1285        return 0;
1286    }
1287}
1288
1289/*
1290 * This is just a wrapper around the public functions
1291 *   - EC_POINT_get_affine_coordinates_GF2m
1292 *   - EC_POINT_get_affine_coordinates_GFp
1293 *
1294 * It is meant to facilitate backporting of code from newer branches, where
1295 * the public API includes a "field agnostic" version of it.
1296 */
1297int ec_point_get_affine_coordinates(const EC_GROUP *group,
1298                                    const EC_POINT *point, BIGNUM *x,
1299                                    BIGNUM *y, BN_CTX *ctx)
1300{
1301    int field_nid;
1302
1303    field_nid = EC_METHOD_get_field_type(EC_GROUP_method_of(group));
1304
1305#ifndef OPENSSL_NO_EC2M
1306    if (field_nid == NID_X9_62_characteristic_two_field) {
1307        return EC_POINT_get_affine_coordinates_GF2m(group, point, x, y, ctx);
1308    } else
1309#endif /* !def(OPENSSL_NO_EC2M) */
1310    if (field_nid == NID_X9_62_prime_field) {
1311        return EC_POINT_get_affine_coordinates_GFp(group, point, x, y, ctx);
1312    } else {
1313        /* this should never happen */
1314        return 0;
1315    }
1316}
1317