Change to check last return value of BN_CTX_get
[openssl.git] / crypto / ec / ecp_smpl.c
1 /*
2  * Copyright 2001-2017 The OpenSSL Project Authors. All Rights Reserved.
3  * Copyright (c) 2002, Oracle and/or its affiliates. All rights reserved
4  *
5  * Licensed under the OpenSSL license (the "License").  You may not use
6  * this file except in compliance with the License.  You can obtain a copy
7  * in the file LICENSE in the source distribution or at
8  * https://www.openssl.org/source/license.html
9  */
10
11 #include <openssl/err.h>
12 #include <openssl/symhacks.h>
13
14 #include "ec_lcl.h"
15
16 const EC_METHOD *EC_GFp_simple_method(void)
17 {
18     static const EC_METHOD ret = {
19         EC_FLAGS_DEFAULT_OCT,
20         NID_X9_62_prime_field,
21         ec_GFp_simple_group_init,
22         ec_GFp_simple_group_finish,
23         ec_GFp_simple_group_clear_finish,
24         ec_GFp_simple_group_copy,
25         ec_GFp_simple_group_set_curve,
26         ec_GFp_simple_group_get_curve,
27         ec_GFp_simple_group_get_degree,
28         ec_group_simple_order_bits,
29         ec_GFp_simple_group_check_discriminant,
30         ec_GFp_simple_point_init,
31         ec_GFp_simple_point_finish,
32         ec_GFp_simple_point_clear_finish,
33         ec_GFp_simple_point_copy,
34         ec_GFp_simple_point_set_to_infinity,
35         ec_GFp_simple_set_Jprojective_coordinates_GFp,
36         ec_GFp_simple_get_Jprojective_coordinates_GFp,
37         ec_GFp_simple_point_set_affine_coordinates,
38         ec_GFp_simple_point_get_affine_coordinates,
39         0, 0, 0,
40         ec_GFp_simple_add,
41         ec_GFp_simple_dbl,
42         ec_GFp_simple_invert,
43         ec_GFp_simple_is_at_infinity,
44         ec_GFp_simple_is_on_curve,
45         ec_GFp_simple_cmp,
46         ec_GFp_simple_make_affine,
47         ec_GFp_simple_points_make_affine,
48         0 /* mul */ ,
49         0 /* precompute_mult */ ,
50         0 /* have_precompute_mult */ ,
51         ec_GFp_simple_field_mul,
52         ec_GFp_simple_field_sqr,
53         0 /* field_div */ ,
54         0 /* field_encode */ ,
55         0 /* field_decode */ ,
56         0,                      /* field_set_to_one */
57         ec_key_simple_priv2oct,
58         ec_key_simple_oct2priv,
59         0, /* set private */
60         ec_key_simple_generate_key,
61         ec_key_simple_check_key,
62         ec_key_simple_generate_public_key,
63         0, /* keycopy */
64         0, /* keyfinish */
65         ecdh_simple_compute_key
66     };
67
68     return &ret;
69 }
70
71 /*
72  * Most method functions in this file are designed to work with
73  * non-trivial representations of field elements if necessary
74  * (see ecp_mont.c): while standard modular addition and subtraction
75  * are used, the field_mul and field_sqr methods will be used for
76  * multiplication, and field_encode and field_decode (if defined)
77  * will be used for converting between representations.
78  *
79  * Functions ec_GFp_simple_points_make_affine() and
80  * ec_GFp_simple_point_get_affine_coordinates() specifically assume
81  * that if a non-trivial representation is used, it is a Montgomery
82  * representation (i.e. 'encoding' means multiplying by some factor R).
83  */
84
85 int ec_GFp_simple_group_init(EC_GROUP *group)
86 {
87     group->field = BN_new();
88     group->a = BN_new();
89     group->b = BN_new();
90     if (group->field == NULL || group->a == NULL || group->b == NULL) {
91         BN_free(group->field);
92         BN_free(group->a);
93         BN_free(group->b);
94         return 0;
95     }
96     group->a_is_minus3 = 0;
97     return 1;
98 }
99
100 void ec_GFp_simple_group_finish(EC_GROUP *group)
101 {
102     BN_free(group->field);
103     BN_free(group->a);
104     BN_free(group->b);
105 }
106
107 void ec_GFp_simple_group_clear_finish(EC_GROUP *group)
108 {
109     BN_clear_free(group->field);
110     BN_clear_free(group->a);
111     BN_clear_free(group->b);
112 }
113
114 int ec_GFp_simple_group_copy(EC_GROUP *dest, const EC_GROUP *src)
115 {
116     if (!BN_copy(dest->field, src->field))
117         return 0;
118     if (!BN_copy(dest->a, src->a))
119         return 0;
120     if (!BN_copy(dest->b, src->b))
121         return 0;
122
123     dest->a_is_minus3 = src->a_is_minus3;
124
125     return 1;
126 }
127
128 int ec_GFp_simple_group_set_curve(EC_GROUP *group,
129                                   const BIGNUM *p, const BIGNUM *a,
130                                   const BIGNUM *b, BN_CTX *ctx)
131 {
132     int ret = 0;
133     BN_CTX *new_ctx = NULL;
134     BIGNUM *tmp_a;
135
136     /* p must be a prime > 3 */
137     if (BN_num_bits(p) <= 2 || !BN_is_odd(p)) {
138         ECerr(EC_F_EC_GFP_SIMPLE_GROUP_SET_CURVE, EC_R_INVALID_FIELD);
139         return 0;
140     }
141
142     if (ctx == NULL) {
143         ctx = new_ctx = BN_CTX_new();
144         if (ctx == NULL)
145             return 0;
146     }
147
148     BN_CTX_start(ctx);
149     tmp_a = BN_CTX_get(ctx);
150     if (tmp_a == NULL)
151         goto err;
152
153     /* group->field */
154     if (!BN_copy(group->field, p))
155         goto err;
156     BN_set_negative(group->field, 0);
157
158     /* group->a */
159     if (!BN_nnmod(tmp_a, a, p, ctx))
160         goto err;
161     if (group->meth->field_encode) {
162         if (!group->meth->field_encode(group, group->a, tmp_a, ctx))
163             goto err;
164     } else if (!BN_copy(group->a, tmp_a))
165         goto err;
166
167     /* group->b */
168     if (!BN_nnmod(group->b, b, p, ctx))
169         goto err;
170     if (group->meth->field_encode)
171         if (!group->meth->field_encode(group, group->b, group->b, ctx))
172             goto err;
173
174     /* group->a_is_minus3 */
175     if (!BN_add_word(tmp_a, 3))
176         goto err;
177     group->a_is_minus3 = (0 == BN_cmp(tmp_a, group->field));
178
179     ret = 1;
180
181  err:
182     BN_CTX_end(ctx);
183     BN_CTX_free(new_ctx);
184     return ret;
185 }
186
187 int ec_GFp_simple_group_get_curve(const EC_GROUP *group, BIGNUM *p, BIGNUM *a,
188                                   BIGNUM *b, BN_CTX *ctx)
189 {
190     int ret = 0;
191     BN_CTX *new_ctx = NULL;
192
193     if (p != NULL) {
194         if (!BN_copy(p, group->field))
195             return 0;
196     }
197
198     if (a != NULL || b != NULL) {
199         if (group->meth->field_decode) {
200             if (ctx == NULL) {
201                 ctx = new_ctx = BN_CTX_new();
202                 if (ctx == NULL)
203                     return 0;
204             }
205             if (a != NULL) {
206                 if (!group->meth->field_decode(group, a, group->a, ctx))
207                     goto err;
208             }
209             if (b != NULL) {
210                 if (!group->meth->field_decode(group, b, group->b, ctx))
211                     goto err;
212             }
213         } else {
214             if (a != NULL) {
215                 if (!BN_copy(a, group->a))
216                     goto err;
217             }
218             if (b != NULL) {
219                 if (!BN_copy(b, group->b))
220                     goto err;
221             }
222         }
223     }
224
225     ret = 1;
226
227  err:
228     BN_CTX_free(new_ctx);
229     return ret;
230 }
231
232 int ec_GFp_simple_group_get_degree(const EC_GROUP *group)
233 {
234     return BN_num_bits(group->field);
235 }
236
237 int ec_GFp_simple_group_check_discriminant(const EC_GROUP *group, BN_CTX *ctx)
238 {
239     int ret = 0;
240     BIGNUM *a, *b, *order, *tmp_1, *tmp_2;
241     const BIGNUM *p = group->field;
242     BN_CTX *new_ctx = NULL;
243
244     if (ctx == NULL) {
245         ctx = new_ctx = BN_CTX_new();
246         if (ctx == NULL) {
247             ECerr(EC_F_EC_GFP_SIMPLE_GROUP_CHECK_DISCRIMINANT,
248                   ERR_R_MALLOC_FAILURE);
249             goto err;
250         }
251     }
252     BN_CTX_start(ctx);
253     a = BN_CTX_get(ctx);
254     b = BN_CTX_get(ctx);
255     tmp_1 = BN_CTX_get(ctx);
256     tmp_2 = BN_CTX_get(ctx);
257     order = BN_CTX_get(ctx);
258     if (order == NULL)
259         goto err;
260
261     if (group->meth->field_decode) {
262         if (!group->meth->field_decode(group, a, group->a, ctx))
263             goto err;
264         if (!group->meth->field_decode(group, b, group->b, ctx))
265             goto err;
266     } else {
267         if (!BN_copy(a, group->a))
268             goto err;
269         if (!BN_copy(b, group->b))
270             goto err;
271     }
272
273     /*-
274      * check the discriminant:
275      * y^2 = x^3 + a*x + b is an elliptic curve <=> 4*a^3 + 27*b^2 != 0 (mod p)
276      * 0 =< a, b < p
277      */
278     if (BN_is_zero(a)) {
279         if (BN_is_zero(b))
280             goto err;
281     } else if (!BN_is_zero(b)) {
282         if (!BN_mod_sqr(tmp_1, a, p, ctx))
283             goto err;
284         if (!BN_mod_mul(tmp_2, tmp_1, a, p, ctx))
285             goto err;
286         if (!BN_lshift(tmp_1, tmp_2, 2))
287             goto err;
288         /* tmp_1 = 4*a^3 */
289
290         if (!BN_mod_sqr(tmp_2, b, p, ctx))
291             goto err;
292         if (!BN_mul_word(tmp_2, 27))
293             goto err;
294         /* tmp_2 = 27*b^2 */
295
296         if (!BN_mod_add(a, tmp_1, tmp_2, p, ctx))
297             goto err;
298         if (BN_is_zero(a))
299             goto err;
300     }
301     ret = 1;
302
303  err:
304     if (ctx != NULL)
305         BN_CTX_end(ctx);
306     BN_CTX_free(new_ctx);
307     return ret;
308 }
309
310 int ec_GFp_simple_point_init(EC_POINT *point)
311 {
312     point->X = BN_new();
313     point->Y = BN_new();
314     point->Z = BN_new();
315     point->Z_is_one = 0;
316
317     if (point->X == NULL || point->Y == NULL || point->Z == NULL) {
318         BN_free(point->X);
319         BN_free(point->Y);
320         BN_free(point->Z);
321         return 0;
322     }
323     return 1;
324 }
325
326 void ec_GFp_simple_point_finish(EC_POINT *point)
327 {
328     BN_free(point->X);
329     BN_free(point->Y);
330     BN_free(point->Z);
331 }
332
333 void ec_GFp_simple_point_clear_finish(EC_POINT *point)
334 {
335     BN_clear_free(point->X);
336     BN_clear_free(point->Y);
337     BN_clear_free(point->Z);
338     point->Z_is_one = 0;
339 }
340
341 int ec_GFp_simple_point_copy(EC_POINT *dest, const EC_POINT *src)
342 {
343     if (!BN_copy(dest->X, src->X))
344         return 0;
345     if (!BN_copy(dest->Y, src->Y))
346         return 0;
347     if (!BN_copy(dest->Z, src->Z))
348         return 0;
349     dest->Z_is_one = src->Z_is_one;
350
351     return 1;
352 }
353
354 int ec_GFp_simple_point_set_to_infinity(const EC_GROUP *group,
355                                         EC_POINT *point)
356 {
357     point->Z_is_one = 0;
358     BN_zero(point->Z);
359     return 1;
360 }
361
362 int ec_GFp_simple_set_Jprojective_coordinates_GFp(const EC_GROUP *group,
363                                                   EC_POINT *point,
364                                                   const BIGNUM *x,
365                                                   const BIGNUM *y,
366                                                   const BIGNUM *z,
367                                                   BN_CTX *ctx)
368 {
369     BN_CTX *new_ctx = NULL;
370     int ret = 0;
371
372     if (ctx == NULL) {
373         ctx = new_ctx = BN_CTX_new();
374         if (ctx == NULL)
375             return 0;
376     }
377
378     if (x != NULL) {
379         if (!BN_nnmod(point->X, x, group->field, ctx))
380             goto err;
381         if (group->meth->field_encode) {
382             if (!group->meth->field_encode(group, point->X, point->X, ctx))
383                 goto err;
384         }
385     }
386
387     if (y != NULL) {
388         if (!BN_nnmod(point->Y, y, group->field, ctx))
389             goto err;
390         if (group->meth->field_encode) {
391             if (!group->meth->field_encode(group, point->Y, point->Y, ctx))
392                 goto err;
393         }
394     }
395
396     if (z != NULL) {
397         int Z_is_one;
398
399         if (!BN_nnmod(point->Z, z, group->field, ctx))
400             goto err;
401         Z_is_one = BN_is_one(point->Z);
402         if (group->meth->field_encode) {
403             if (Z_is_one && (group->meth->field_set_to_one != 0)) {
404                 if (!group->meth->field_set_to_one(group, point->Z, ctx))
405                     goto err;
406             } else {
407                 if (!group->
408                     meth->field_encode(group, point->Z, point->Z, ctx))
409                     goto err;
410             }
411         }
412         point->Z_is_one = Z_is_one;
413     }
414
415     ret = 1;
416
417  err:
418     BN_CTX_free(new_ctx);
419     return ret;
420 }
421
422 int ec_GFp_simple_get_Jprojective_coordinates_GFp(const EC_GROUP *group,
423                                                   const EC_POINT *point,
424                                                   BIGNUM *x, BIGNUM *y,
425                                                   BIGNUM *z, BN_CTX *ctx)
426 {
427     BN_CTX *new_ctx = NULL;
428     int ret = 0;
429
430     if (group->meth->field_decode != 0) {
431         if (ctx == NULL) {
432             ctx = new_ctx = BN_CTX_new();
433             if (ctx == NULL)
434                 return 0;
435         }
436
437         if (x != NULL) {
438             if (!group->meth->field_decode(group, x, point->X, ctx))
439                 goto err;
440         }
441         if (y != NULL) {
442             if (!group->meth->field_decode(group, y, point->Y, ctx))
443                 goto err;
444         }
445         if (z != NULL) {
446             if (!group->meth->field_decode(group, z, point->Z, ctx))
447                 goto err;
448         }
449     } else {
450         if (x != NULL) {
451             if (!BN_copy(x, point->X))
452                 goto err;
453         }
454         if (y != NULL) {
455             if (!BN_copy(y, point->Y))
456                 goto err;
457         }
458         if (z != NULL) {
459             if (!BN_copy(z, point->Z))
460                 goto err;
461         }
462     }
463
464     ret = 1;
465
466  err:
467     BN_CTX_free(new_ctx);
468     return ret;
469 }
470
471 int ec_GFp_simple_point_set_affine_coordinates(const EC_GROUP *group,
472                                                EC_POINT *point,
473                                                const BIGNUM *x,
474                                                const BIGNUM *y, BN_CTX *ctx)
475 {
476     if (x == NULL || y == NULL) {
477         /*
478          * unlike for projective coordinates, we do not tolerate this
479          */
480         ECerr(EC_F_EC_GFP_SIMPLE_POINT_SET_AFFINE_COORDINATES,
481               ERR_R_PASSED_NULL_PARAMETER);
482         return 0;
483     }
484
485     return EC_POINT_set_Jprojective_coordinates_GFp(group, point, x, y,
486                                                     BN_value_one(), ctx);
487 }
488
489 int ec_GFp_simple_point_get_affine_coordinates(const EC_GROUP *group,
490                                                const EC_POINT *point,
491                                                BIGNUM *x, BIGNUM *y,
492                                                BN_CTX *ctx)
493 {
494     BN_CTX *new_ctx = NULL;
495     BIGNUM *Z, *Z_1, *Z_2, *Z_3;
496     const BIGNUM *Z_;
497     int ret = 0;
498
499     if (EC_POINT_is_at_infinity(group, point)) {
500         ECerr(EC_F_EC_GFP_SIMPLE_POINT_GET_AFFINE_COORDINATES,
501               EC_R_POINT_AT_INFINITY);
502         return 0;
503     }
504
505     if (ctx == NULL) {
506         ctx = new_ctx = BN_CTX_new();
507         if (ctx == NULL)
508             return 0;
509     }
510
511     BN_CTX_start(ctx);
512     Z = BN_CTX_get(ctx);
513     Z_1 = BN_CTX_get(ctx);
514     Z_2 = BN_CTX_get(ctx);
515     Z_3 = BN_CTX_get(ctx);
516     if (Z_3 == NULL)
517         goto err;
518
519     /* transform  (X, Y, Z)  into  (x, y) := (X/Z^2, Y/Z^3) */
520
521     if (group->meth->field_decode) {
522         if (!group->meth->field_decode(group, Z, point->Z, ctx))
523             goto err;
524         Z_ = Z;
525     } else {
526         Z_ = point->Z;
527     }
528
529     if (BN_is_one(Z_)) {
530         if (group->meth->field_decode) {
531             if (x != NULL) {
532                 if (!group->meth->field_decode(group, x, point->X, ctx))
533                     goto err;
534             }
535             if (y != NULL) {
536                 if (!group->meth->field_decode(group, y, point->Y, ctx))
537                     goto err;
538             }
539         } else {
540             if (x != NULL) {
541                 if (!BN_copy(x, point->X))
542                     goto err;
543             }
544             if (y != NULL) {
545                 if (!BN_copy(y, point->Y))
546                     goto err;
547             }
548         }
549     } else {
550         if (!BN_mod_inverse(Z_1, Z_, group->field, ctx)) {
551             ECerr(EC_F_EC_GFP_SIMPLE_POINT_GET_AFFINE_COORDINATES,
552                   ERR_R_BN_LIB);
553             goto err;
554         }
555
556         if (group->meth->field_encode == 0) {
557             /* field_sqr works on standard representation */
558             if (!group->meth->field_sqr(group, Z_2, Z_1, ctx))
559                 goto err;
560         } else {
561             if (!BN_mod_sqr(Z_2, Z_1, group->field, ctx))
562                 goto err;
563         }
564
565         if (x != NULL) {
566             /*
567              * in the Montgomery case, field_mul will cancel out Montgomery
568              * factor in X:
569              */
570             if (!group->meth->field_mul(group, x, point->X, Z_2, ctx))
571                 goto err;
572         }
573
574         if (y != NULL) {
575             if (group->meth->field_encode == 0) {
576                 /*
577                  * field_mul works on standard representation
578                  */
579                 if (!group->meth->field_mul(group, Z_3, Z_2, Z_1, ctx))
580                     goto err;
581             } else {
582                 if (!BN_mod_mul(Z_3, Z_2, Z_1, group->field, ctx))
583                     goto err;
584             }
585
586             /*
587              * in the Montgomery case, field_mul will cancel out Montgomery
588              * factor in Y:
589              */
590             if (!group->meth->field_mul(group, y, point->Y, Z_3, ctx))
591                 goto err;
592         }
593     }
594
595     ret = 1;
596
597  err:
598     BN_CTX_end(ctx);
599     BN_CTX_free(new_ctx);
600     return ret;
601 }
602
603 int ec_GFp_simple_add(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a,
604                       const EC_POINT *b, BN_CTX *ctx)
605 {
606     int (*field_mul) (const EC_GROUP *, BIGNUM *, const BIGNUM *,
607                       const BIGNUM *, BN_CTX *);
608     int (*field_sqr) (const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
609     const BIGNUM *p;
610     BN_CTX *new_ctx = NULL;
611     BIGNUM *n0, *n1, *n2, *n3, *n4, *n5, *n6;
612     int ret = 0;
613
614     if (a == b)
615         return EC_POINT_dbl(group, r, a, ctx);
616     if (EC_POINT_is_at_infinity(group, a))
617         return EC_POINT_copy(r, b);
618     if (EC_POINT_is_at_infinity(group, b))
619         return EC_POINT_copy(r, a);
620
621     field_mul = group->meth->field_mul;
622     field_sqr = group->meth->field_sqr;
623     p = group->field;
624
625     if (ctx == NULL) {
626         ctx = new_ctx = BN_CTX_new();
627         if (ctx == NULL)
628             return 0;
629     }
630
631     BN_CTX_start(ctx);
632     n0 = BN_CTX_get(ctx);
633     n1 = BN_CTX_get(ctx);
634     n2 = BN_CTX_get(ctx);
635     n3 = BN_CTX_get(ctx);
636     n4 = BN_CTX_get(ctx);
637     n5 = BN_CTX_get(ctx);
638     n6 = BN_CTX_get(ctx);
639     if (n6 == NULL)
640         goto end;
641
642     /*
643      * Note that in this function we must not read components of 'a' or 'b'
644      * once we have written the corresponding components of 'r'. ('r' might
645      * be one of 'a' or 'b'.)
646      */
647
648     /* n1, n2 */
649     if (b->Z_is_one) {
650         if (!BN_copy(n1, a->X))
651             goto end;
652         if (!BN_copy(n2, a->Y))
653             goto end;
654         /* n1 = X_a */
655         /* n2 = Y_a */
656     } else {
657         if (!field_sqr(group, n0, b->Z, ctx))
658             goto end;
659         if (!field_mul(group, n1, a->X, n0, ctx))
660             goto end;
661         /* n1 = X_a * Z_b^2 */
662
663         if (!field_mul(group, n0, n0, b->Z, ctx))
664             goto end;
665         if (!field_mul(group, n2, a->Y, n0, ctx))
666             goto end;
667         /* n2 = Y_a * Z_b^3 */
668     }
669
670     /* n3, n4 */
671     if (a->Z_is_one) {
672         if (!BN_copy(n3, b->X))
673             goto end;
674         if (!BN_copy(n4, b->Y))
675             goto end;
676         /* n3 = X_b */
677         /* n4 = Y_b */
678     } else {
679         if (!field_sqr(group, n0, a->Z, ctx))
680             goto end;
681         if (!field_mul(group, n3, b->X, n0, ctx))
682             goto end;
683         /* n3 = X_b * Z_a^2 */
684
685         if (!field_mul(group, n0, n0, a->Z, ctx))
686             goto end;
687         if (!field_mul(group, n4, b->Y, n0, ctx))
688             goto end;
689         /* n4 = Y_b * Z_a^3 */
690     }
691
692     /* n5, n6 */
693     if (!BN_mod_sub_quick(n5, n1, n3, p))
694         goto end;
695     if (!BN_mod_sub_quick(n6, n2, n4, p))
696         goto end;
697     /* n5 = n1 - n3 */
698     /* n6 = n2 - n4 */
699
700     if (BN_is_zero(n5)) {
701         if (BN_is_zero(n6)) {
702             /* a is the same point as b */
703             BN_CTX_end(ctx);
704             ret = EC_POINT_dbl(group, r, a, ctx);
705             ctx = NULL;
706             goto end;
707         } else {
708             /* a is the inverse of b */
709             BN_zero(r->Z);
710             r->Z_is_one = 0;
711             ret = 1;
712             goto end;
713         }
714     }
715
716     /* 'n7', 'n8' */
717     if (!BN_mod_add_quick(n1, n1, n3, p))
718         goto end;
719     if (!BN_mod_add_quick(n2, n2, n4, p))
720         goto end;
721     /* 'n7' = n1 + n3 */
722     /* 'n8' = n2 + n4 */
723
724     /* Z_r */
725     if (a->Z_is_one && b->Z_is_one) {
726         if (!BN_copy(r->Z, n5))
727             goto end;
728     } else {
729         if (a->Z_is_one) {
730             if (!BN_copy(n0, b->Z))
731                 goto end;
732         } else if (b->Z_is_one) {
733             if (!BN_copy(n0, a->Z))
734                 goto end;
735         } else {
736             if (!field_mul(group, n0, a->Z, b->Z, ctx))
737                 goto end;
738         }
739         if (!field_mul(group, r->Z, n0, n5, ctx))
740             goto end;
741     }
742     r->Z_is_one = 0;
743     /* Z_r = Z_a * Z_b * n5 */
744
745     /* X_r */
746     if (!field_sqr(group, n0, n6, ctx))
747         goto end;
748     if (!field_sqr(group, n4, n5, ctx))
749         goto end;
750     if (!field_mul(group, n3, n1, n4, ctx))
751         goto end;
752     if (!BN_mod_sub_quick(r->X, n0, n3, p))
753         goto end;
754     /* X_r = n6^2 - n5^2 * 'n7' */
755
756     /* 'n9' */
757     if (!BN_mod_lshift1_quick(n0, r->X, p))
758         goto end;
759     if (!BN_mod_sub_quick(n0, n3, n0, p))
760         goto end;
761     /* n9 = n5^2 * 'n7' - 2 * X_r */
762
763     /* Y_r */
764     if (!field_mul(group, n0, n0, n6, ctx))
765         goto end;
766     if (!field_mul(group, n5, n4, n5, ctx))
767         goto end;               /* now n5 is n5^3 */
768     if (!field_mul(group, n1, n2, n5, ctx))
769         goto end;
770     if (!BN_mod_sub_quick(n0, n0, n1, p))
771         goto end;
772     if (BN_is_odd(n0))
773         if (!BN_add(n0, n0, p))
774             goto end;
775     /* now  0 <= n0 < 2*p,  and n0 is even */
776     if (!BN_rshift1(r->Y, n0))
777         goto end;
778     /* Y_r = (n6 * 'n9' - 'n8' * 'n5^3') / 2 */
779
780     ret = 1;
781
782  end:
783     if (ctx)                    /* otherwise we already called BN_CTX_end */
784         BN_CTX_end(ctx);
785     BN_CTX_free(new_ctx);
786     return ret;
787 }
788
789 int ec_GFp_simple_dbl(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a,
790                       BN_CTX *ctx)
791 {
792     int (*field_mul) (const EC_GROUP *, BIGNUM *, const BIGNUM *,
793                       const BIGNUM *, BN_CTX *);
794     int (*field_sqr) (const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
795     const BIGNUM *p;
796     BN_CTX *new_ctx = NULL;
797     BIGNUM *n0, *n1, *n2, *n3;
798     int ret = 0;
799
800     if (EC_POINT_is_at_infinity(group, a)) {
801         BN_zero(r->Z);
802         r->Z_is_one = 0;
803         return 1;
804     }
805
806     field_mul = group->meth->field_mul;
807     field_sqr = group->meth->field_sqr;
808     p = group->field;
809
810     if (ctx == NULL) {
811         ctx = new_ctx = BN_CTX_new();
812         if (ctx == NULL)
813             return 0;
814     }
815
816     BN_CTX_start(ctx);
817     n0 = BN_CTX_get(ctx);
818     n1 = BN_CTX_get(ctx);
819     n2 = BN_CTX_get(ctx);
820     n3 = BN_CTX_get(ctx);
821     if (n3 == NULL)
822         goto err;
823
824     /*
825      * Note that in this function we must not read components of 'a' once we
826      * have written the corresponding components of 'r'. ('r' might the same
827      * as 'a'.)
828      */
829
830     /* n1 */
831     if (a->Z_is_one) {
832         if (!field_sqr(group, n0, a->X, ctx))
833             goto err;
834         if (!BN_mod_lshift1_quick(n1, n0, p))
835             goto err;
836         if (!BN_mod_add_quick(n0, n0, n1, p))
837             goto err;
838         if (!BN_mod_add_quick(n1, n0, group->a, p))
839             goto err;
840         /* n1 = 3 * X_a^2 + a_curve */
841     } else if (group->a_is_minus3) {
842         if (!field_sqr(group, n1, a->Z, ctx))
843             goto err;
844         if (!BN_mod_add_quick(n0, a->X, n1, p))
845             goto err;
846         if (!BN_mod_sub_quick(n2, a->X, n1, p))
847             goto err;
848         if (!field_mul(group, n1, n0, n2, ctx))
849             goto err;
850         if (!BN_mod_lshift1_quick(n0, n1, p))
851             goto err;
852         if (!BN_mod_add_quick(n1, n0, n1, p))
853             goto err;
854         /*-
855          * n1 = 3 * (X_a + Z_a^2) * (X_a - Z_a^2)
856          *    = 3 * X_a^2 - 3 * Z_a^4
857          */
858     } else {
859         if (!field_sqr(group, n0, a->X, ctx))
860             goto err;
861         if (!BN_mod_lshift1_quick(n1, n0, p))
862             goto err;
863         if (!BN_mod_add_quick(n0, n0, n1, p))
864             goto err;
865         if (!field_sqr(group, n1, a->Z, ctx))
866             goto err;
867         if (!field_sqr(group, n1, n1, ctx))
868             goto err;
869         if (!field_mul(group, n1, n1, group->a, ctx))
870             goto err;
871         if (!BN_mod_add_quick(n1, n1, n0, p))
872             goto err;
873         /* n1 = 3 * X_a^2 + a_curve * Z_a^4 */
874     }
875
876     /* Z_r */
877     if (a->Z_is_one) {
878         if (!BN_copy(n0, a->Y))
879             goto err;
880     } else {
881         if (!field_mul(group, n0, a->Y, a->Z, ctx))
882             goto err;
883     }
884     if (!BN_mod_lshift1_quick(r->Z, n0, p))
885         goto err;
886     r->Z_is_one = 0;
887     /* Z_r = 2 * Y_a * Z_a */
888
889     /* n2 */
890     if (!field_sqr(group, n3, a->Y, ctx))
891         goto err;
892     if (!field_mul(group, n2, a->X, n3, ctx))
893         goto err;
894     if (!BN_mod_lshift_quick(n2, n2, 2, p))
895         goto err;
896     /* n2 = 4 * X_a * Y_a^2 */
897
898     /* X_r */
899     if (!BN_mod_lshift1_quick(n0, n2, p))
900         goto err;
901     if (!field_sqr(group, r->X, n1, ctx))
902         goto err;
903     if (!BN_mod_sub_quick(r->X, r->X, n0, p))
904         goto err;
905     /* X_r = n1^2 - 2 * n2 */
906
907     /* n3 */
908     if (!field_sqr(group, n0, n3, ctx))
909         goto err;
910     if (!BN_mod_lshift_quick(n3, n0, 3, p))
911         goto err;
912     /* n3 = 8 * Y_a^4 */
913
914     /* Y_r */
915     if (!BN_mod_sub_quick(n0, n2, r->X, p))
916         goto err;
917     if (!field_mul(group, n0, n1, n0, ctx))
918         goto err;
919     if (!BN_mod_sub_quick(r->Y, n0, n3, p))
920         goto err;
921     /* Y_r = n1 * (n2 - X_r) - n3 */
922
923     ret = 1;
924
925  err:
926     BN_CTX_end(ctx);
927     BN_CTX_free(new_ctx);
928     return ret;
929 }
930
931 int ec_GFp_simple_invert(const EC_GROUP *group, EC_POINT *point, BN_CTX *ctx)
932 {
933     if (EC_POINT_is_at_infinity(group, point) || BN_is_zero(point->Y))
934         /* point is its own inverse */
935         return 1;
936
937     return BN_usub(point->Y, group->field, point->Y);
938 }
939
940 int ec_GFp_simple_is_at_infinity(const EC_GROUP *group, const EC_POINT *point)
941 {
942     return BN_is_zero(point->Z);
943 }
944
945 int ec_GFp_simple_is_on_curve(const EC_GROUP *group, const EC_POINT *point,
946                               BN_CTX *ctx)
947 {
948     int (*field_mul) (const EC_GROUP *, BIGNUM *, const BIGNUM *,
949                       const BIGNUM *, BN_CTX *);
950     int (*field_sqr) (const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
951     const BIGNUM *p;
952     BN_CTX *new_ctx = NULL;
953     BIGNUM *rh, *tmp, *Z4, *Z6;
954     int ret = -1;
955
956     if (EC_POINT_is_at_infinity(group, point))
957         return 1;
958
959     field_mul = group->meth->field_mul;
960     field_sqr = group->meth->field_sqr;
961     p = group->field;
962
963     if (ctx == NULL) {
964         ctx = new_ctx = BN_CTX_new();
965         if (ctx == NULL)
966             return -1;
967     }
968
969     BN_CTX_start(ctx);
970     rh = BN_CTX_get(ctx);
971     tmp = BN_CTX_get(ctx);
972     Z4 = BN_CTX_get(ctx);
973     Z6 = BN_CTX_get(ctx);
974     if (Z6 == NULL)
975         goto err;
976
977     /*-
978      * We have a curve defined by a Weierstrass equation
979      *      y^2 = x^3 + a*x + b.
980      * The point to consider is given in Jacobian projective coordinates
981      * where  (X, Y, Z)  represents  (x, y) = (X/Z^2, Y/Z^3).
982      * Substituting this and multiplying by  Z^6  transforms the above equation into
983      *      Y^2 = X^3 + a*X*Z^4 + b*Z^6.
984      * To test this, we add up the right-hand side in 'rh'.
985      */
986
987     /* rh := X^2 */
988     if (!field_sqr(group, rh, point->X, ctx))
989         goto err;
990
991     if (!point->Z_is_one) {
992         if (!field_sqr(group, tmp, point->Z, ctx))
993             goto err;
994         if (!field_sqr(group, Z4, tmp, ctx))
995             goto err;
996         if (!field_mul(group, Z6, Z4, tmp, ctx))
997             goto err;
998
999         /* rh := (rh + a*Z^4)*X */
1000         if (group->a_is_minus3) {
1001             if (!BN_mod_lshift1_quick(tmp, Z4, p))
1002                 goto err;
1003             if (!BN_mod_add_quick(tmp, tmp, Z4, p))
1004                 goto err;
1005             if (!BN_mod_sub_quick(rh, rh, tmp, p))
1006                 goto err;
1007             if (!field_mul(group, rh, rh, point->X, ctx))
1008                 goto err;
1009         } else {
1010             if (!field_mul(group, tmp, Z4, group->a, ctx))
1011                 goto err;
1012             if (!BN_mod_add_quick(rh, rh, tmp, p))
1013                 goto err;
1014             if (!field_mul(group, rh, rh, point->X, ctx))
1015                 goto err;
1016         }
1017
1018         /* rh := rh + b*Z^6 */
1019         if (!field_mul(group, tmp, group->b, Z6, ctx))
1020             goto err;
1021         if (!BN_mod_add_quick(rh, rh, tmp, p))
1022             goto err;
1023     } else {
1024         /* point->Z_is_one */
1025
1026         /* rh := (rh + a)*X */
1027         if (!BN_mod_add_quick(rh, rh, group->a, p))
1028             goto err;
1029         if (!field_mul(group, rh, rh, point->X, ctx))
1030             goto err;
1031         /* rh := rh + b */
1032         if (!BN_mod_add_quick(rh, rh, group->b, p))
1033             goto err;
1034     }
1035
1036     /* 'lh' := Y^2 */
1037     if (!field_sqr(group, tmp, point->Y, ctx))
1038         goto err;
1039
1040     ret = (0 == BN_ucmp(tmp, rh));
1041
1042  err:
1043     BN_CTX_end(ctx);
1044     BN_CTX_free(new_ctx);
1045     return ret;
1046 }
1047
1048 int ec_GFp_simple_cmp(const EC_GROUP *group, const EC_POINT *a,
1049                       const EC_POINT *b, BN_CTX *ctx)
1050 {
1051     /*-
1052      * return values:
1053      *  -1   error
1054      *   0   equal (in affine coordinates)
1055      *   1   not equal
1056      */
1057
1058     int (*field_mul) (const EC_GROUP *, BIGNUM *, const BIGNUM *,
1059                       const BIGNUM *, BN_CTX *);
1060     int (*field_sqr) (const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
1061     BN_CTX *new_ctx = NULL;
1062     BIGNUM *tmp1, *tmp2, *Za23, *Zb23;
1063     const BIGNUM *tmp1_, *tmp2_;
1064     int ret = -1;
1065
1066     if (EC_POINT_is_at_infinity(group, a)) {
1067         return EC_POINT_is_at_infinity(group, b) ? 0 : 1;
1068     }
1069
1070     if (EC_POINT_is_at_infinity(group, b))
1071         return 1;
1072
1073     if (a->Z_is_one && b->Z_is_one) {
1074         return ((BN_cmp(a->X, b->X) == 0) && BN_cmp(a->Y, b->Y) == 0) ? 0 : 1;
1075     }
1076
1077     field_mul = group->meth->field_mul;
1078     field_sqr = group->meth->field_sqr;
1079
1080     if (ctx == NULL) {
1081         ctx = new_ctx = BN_CTX_new();
1082         if (ctx == NULL)
1083             return -1;
1084     }
1085
1086     BN_CTX_start(ctx);
1087     tmp1 = BN_CTX_get(ctx);
1088     tmp2 = BN_CTX_get(ctx);
1089     Za23 = BN_CTX_get(ctx);
1090     Zb23 = BN_CTX_get(ctx);
1091     if (Zb23 == NULL)
1092         goto end;
1093
1094     /*-
1095      * We have to decide whether
1096      *     (X_a/Z_a^2, Y_a/Z_a^3) = (X_b/Z_b^2, Y_b/Z_b^3),
1097      * or equivalently, whether
1098      *     (X_a*Z_b^2, Y_a*Z_b^3) = (X_b*Z_a^2, Y_b*Z_a^3).
1099      */
1100
1101     if (!b->Z_is_one) {
1102         if (!field_sqr(group, Zb23, b->Z, ctx))
1103             goto end;
1104         if (!field_mul(group, tmp1, a->X, Zb23, ctx))
1105             goto end;
1106         tmp1_ = tmp1;
1107     } else
1108         tmp1_ = a->X;
1109     if (!a->Z_is_one) {
1110         if (!field_sqr(group, Za23, a->Z, ctx))
1111             goto end;
1112         if (!field_mul(group, tmp2, b->X, Za23, ctx))
1113             goto end;
1114         tmp2_ = tmp2;
1115     } else
1116         tmp2_ = b->X;
1117
1118     /* compare  X_a*Z_b^2  with  X_b*Z_a^2 */
1119     if (BN_cmp(tmp1_, tmp2_) != 0) {
1120         ret = 1;                /* points differ */
1121         goto end;
1122     }
1123
1124     if (!b->Z_is_one) {
1125         if (!field_mul(group, Zb23, Zb23, b->Z, ctx))
1126             goto end;
1127         if (!field_mul(group, tmp1, a->Y, Zb23, ctx))
1128             goto end;
1129         /* tmp1_ = tmp1 */
1130     } else
1131         tmp1_ = a->Y;
1132     if (!a->Z_is_one) {
1133         if (!field_mul(group, Za23, Za23, a->Z, ctx))
1134             goto end;
1135         if (!field_mul(group, tmp2, b->Y, Za23, ctx))
1136             goto end;
1137         /* tmp2_ = tmp2 */
1138     } else
1139         tmp2_ = b->Y;
1140
1141     /* compare  Y_a*Z_b^3  with  Y_b*Z_a^3 */
1142     if (BN_cmp(tmp1_, tmp2_) != 0) {
1143         ret = 1;                /* points differ */
1144         goto end;
1145     }
1146
1147     /* points are equal */
1148     ret = 0;
1149
1150  end:
1151     BN_CTX_end(ctx);
1152     BN_CTX_free(new_ctx);
1153     return ret;
1154 }
1155
1156 int ec_GFp_simple_make_affine(const EC_GROUP *group, EC_POINT *point,
1157                               BN_CTX *ctx)
1158 {
1159     BN_CTX *new_ctx = NULL;
1160     BIGNUM *x, *y;
1161     int ret = 0;
1162
1163     if (point->Z_is_one || EC_POINT_is_at_infinity(group, point))
1164         return 1;
1165
1166     if (ctx == NULL) {
1167         ctx = new_ctx = BN_CTX_new();
1168         if (ctx == NULL)
1169             return 0;
1170     }
1171
1172     BN_CTX_start(ctx);
1173     x = BN_CTX_get(ctx);
1174     y = BN_CTX_get(ctx);
1175     if (y == NULL)
1176         goto err;
1177
1178     if (!EC_POINT_get_affine_coordinates_GFp(group, point, x, y, ctx))
1179         goto err;
1180     if (!EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx))
1181         goto err;
1182     if (!point->Z_is_one) {
1183         ECerr(EC_F_EC_GFP_SIMPLE_MAKE_AFFINE, ERR_R_INTERNAL_ERROR);
1184         goto err;
1185     }
1186
1187     ret = 1;
1188
1189  err:
1190     BN_CTX_end(ctx);
1191     BN_CTX_free(new_ctx);
1192     return ret;
1193 }
1194
1195 int ec_GFp_simple_points_make_affine(const EC_GROUP *group, size_t num,
1196                                      EC_POINT *points[], BN_CTX *ctx)
1197 {
1198     BN_CTX *new_ctx = NULL;
1199     BIGNUM *tmp, *tmp_Z;
1200     BIGNUM **prod_Z = NULL;
1201     size_t i;
1202     int ret = 0;
1203
1204     if (num == 0)
1205         return 1;
1206
1207     if (ctx == NULL) {
1208         ctx = new_ctx = BN_CTX_new();
1209         if (ctx == NULL)
1210             return 0;
1211     }
1212
1213     BN_CTX_start(ctx);
1214     tmp = BN_CTX_get(ctx);
1215     tmp_Z = BN_CTX_get(ctx);
1216     if (tmp_Z == NULL)
1217         goto err;
1218
1219     prod_Z = OPENSSL_malloc(num * sizeof prod_Z[0]);
1220     if (prod_Z == NULL)
1221         goto err;
1222     for (i = 0; i < num; i++) {
1223         prod_Z[i] = BN_new();
1224         if (prod_Z[i] == NULL)
1225             goto err;
1226     }
1227
1228     /*
1229      * Set each prod_Z[i] to the product of points[0]->Z .. points[i]->Z,
1230      * skipping any zero-valued inputs (pretend that they're 1).
1231      */
1232
1233     if (!BN_is_zero(points[0]->Z)) {
1234         if (!BN_copy(prod_Z[0], points[0]->Z))
1235             goto err;
1236     } else {
1237         if (group->meth->field_set_to_one != 0) {
1238             if (!group->meth->field_set_to_one(group, prod_Z[0], ctx))
1239                 goto err;
1240         } else {
1241             if (!BN_one(prod_Z[0]))
1242                 goto err;
1243         }
1244     }
1245
1246     for (i = 1; i < num; i++) {
1247         if (!BN_is_zero(points[i]->Z)) {
1248             if (!group->
1249                 meth->field_mul(group, prod_Z[i], prod_Z[i - 1], points[i]->Z,
1250                                 ctx))
1251                 goto err;
1252         } else {
1253             if (!BN_copy(prod_Z[i], prod_Z[i - 1]))
1254                 goto err;
1255         }
1256     }
1257
1258     /*
1259      * Now use a single explicit inversion to replace every non-zero
1260      * points[i]->Z by its inverse.
1261      */
1262
1263     if (!BN_mod_inverse(tmp, prod_Z[num - 1], group->field, ctx)) {
1264         ECerr(EC_F_EC_GFP_SIMPLE_POINTS_MAKE_AFFINE, ERR_R_BN_LIB);
1265         goto err;
1266     }
1267     if (group->meth->field_encode != 0) {
1268         /*
1269          * In the Montgomery case, we just turned R*H (representing H) into
1270          * 1/(R*H), but we need R*(1/H) (representing 1/H); i.e. we need to
1271          * multiply by the Montgomery factor twice.
1272          */
1273         if (!group->meth->field_encode(group, tmp, tmp, ctx))
1274             goto err;
1275         if (!group->meth->field_encode(group, tmp, tmp, ctx))
1276             goto err;
1277     }
1278
1279     for (i = num - 1; i > 0; --i) {
1280         /*
1281          * Loop invariant: tmp is the product of the inverses of points[0]->Z
1282          * .. points[i]->Z (zero-valued inputs skipped).
1283          */
1284         if (!BN_is_zero(points[i]->Z)) {
1285             /*
1286              * Set tmp_Z to the inverse of points[i]->Z (as product of Z
1287              * inverses 0 .. i, Z values 0 .. i - 1).
1288              */
1289             if (!group->
1290                 meth->field_mul(group, tmp_Z, prod_Z[i - 1], tmp, ctx))
1291                 goto err;
1292             /*
1293              * Update tmp to satisfy the loop invariant for i - 1.
1294              */
1295             if (!group->meth->field_mul(group, tmp, tmp, points[i]->Z, ctx))
1296                 goto err;
1297             /* Replace points[i]->Z by its inverse. */
1298             if (!BN_copy(points[i]->Z, tmp_Z))
1299                 goto err;
1300         }
1301     }
1302
1303     if (!BN_is_zero(points[0]->Z)) {
1304         /* Replace points[0]->Z by its inverse. */
1305         if (!BN_copy(points[0]->Z, tmp))
1306             goto err;
1307     }
1308
1309     /* Finally, fix up the X and Y coordinates for all points. */
1310
1311     for (i = 0; i < num; i++) {
1312         EC_POINT *p = points[i];
1313
1314         if (!BN_is_zero(p->Z)) {
1315             /* turn  (X, Y, 1/Z)  into  (X/Z^2, Y/Z^3, 1) */
1316
1317             if (!group->meth->field_sqr(group, tmp, p->Z, ctx))
1318                 goto err;
1319             if (!group->meth->field_mul(group, p->X, p->X, tmp, ctx))
1320                 goto err;
1321
1322             if (!group->meth->field_mul(group, tmp, tmp, p->Z, ctx))
1323                 goto err;
1324             if (!group->meth->field_mul(group, p->Y, p->Y, tmp, ctx))
1325                 goto err;
1326
1327             if (group->meth->field_set_to_one != 0) {
1328                 if (!group->meth->field_set_to_one(group, p->Z, ctx))
1329                     goto err;
1330             } else {
1331                 if (!BN_one(p->Z))
1332                     goto err;
1333             }
1334             p->Z_is_one = 1;
1335         }
1336     }
1337
1338     ret = 1;
1339
1340  err:
1341     BN_CTX_end(ctx);
1342     BN_CTX_free(new_ctx);
1343     if (prod_Z != NULL) {
1344         for (i = 0; i < num; i++) {
1345             if (prod_Z[i] == NULL)
1346                 break;
1347             BN_clear_free(prod_Z[i]);
1348         }
1349         OPENSSL_free(prod_Z);
1350     }
1351     return ret;
1352 }
1353
1354 int ec_GFp_simple_field_mul(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a,
1355                             const BIGNUM *b, BN_CTX *ctx)
1356 {
1357     return BN_mod_mul(r, a, b, group->field, ctx);
1358 }
1359
1360 int ec_GFp_simple_field_sqr(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a,
1361                             BN_CTX *ctx)
1362 {
1363     return BN_mod_sqr(r, a, group->field, ctx);
1364 }