Update copyright year
[openssl.git] / crypto / ec / ecp_smpl.c
1 /*
2  * Copyright 2001-2018 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     dest->curve_name = src->curve_name;
351
352     return 1;
353 }
354
355 int ec_GFp_simple_point_set_to_infinity(const EC_GROUP *group,
356                                         EC_POINT *point)
357 {
358     point->Z_is_one = 0;
359     BN_zero(point->Z);
360     return 1;
361 }
362
363 int ec_GFp_simple_set_Jprojective_coordinates_GFp(const EC_GROUP *group,
364                                                   EC_POINT *point,
365                                                   const BIGNUM *x,
366                                                   const BIGNUM *y,
367                                                   const BIGNUM *z,
368                                                   BN_CTX *ctx)
369 {
370     BN_CTX *new_ctx = NULL;
371     int ret = 0;
372
373     if (ctx == NULL) {
374         ctx = new_ctx = BN_CTX_new();
375         if (ctx == NULL)
376             return 0;
377     }
378
379     if (x != NULL) {
380         if (!BN_nnmod(point->X, x, group->field, ctx))
381             goto err;
382         if (group->meth->field_encode) {
383             if (!group->meth->field_encode(group, point->X, point->X, ctx))
384                 goto err;
385         }
386     }
387
388     if (y != NULL) {
389         if (!BN_nnmod(point->Y, y, group->field, ctx))
390             goto err;
391         if (group->meth->field_encode) {
392             if (!group->meth->field_encode(group, point->Y, point->Y, ctx))
393                 goto err;
394         }
395     }
396
397     if (z != NULL) {
398         int Z_is_one;
399
400         if (!BN_nnmod(point->Z, z, group->field, ctx))
401             goto err;
402         Z_is_one = BN_is_one(point->Z);
403         if (group->meth->field_encode) {
404             if (Z_is_one && (group->meth->field_set_to_one != 0)) {
405                 if (!group->meth->field_set_to_one(group, point->Z, ctx))
406                     goto err;
407             } else {
408                 if (!group->
409                     meth->field_encode(group, point->Z, point->Z, ctx))
410                     goto err;
411             }
412         }
413         point->Z_is_one = Z_is_one;
414     }
415
416     ret = 1;
417
418  err:
419     BN_CTX_free(new_ctx);
420     return ret;
421 }
422
423 int ec_GFp_simple_get_Jprojective_coordinates_GFp(const EC_GROUP *group,
424                                                   const EC_POINT *point,
425                                                   BIGNUM *x, BIGNUM *y,
426                                                   BIGNUM *z, BN_CTX *ctx)
427 {
428     BN_CTX *new_ctx = NULL;
429     int ret = 0;
430
431     if (group->meth->field_decode != 0) {
432         if (ctx == NULL) {
433             ctx = new_ctx = BN_CTX_new();
434             if (ctx == NULL)
435                 return 0;
436         }
437
438         if (x != NULL) {
439             if (!group->meth->field_decode(group, x, point->X, ctx))
440                 goto err;
441         }
442         if (y != NULL) {
443             if (!group->meth->field_decode(group, y, point->Y, ctx))
444                 goto err;
445         }
446         if (z != NULL) {
447             if (!group->meth->field_decode(group, z, point->Z, ctx))
448                 goto err;
449         }
450     } else {
451         if (x != NULL) {
452             if (!BN_copy(x, point->X))
453                 goto err;
454         }
455         if (y != NULL) {
456             if (!BN_copy(y, point->Y))
457                 goto err;
458         }
459         if (z != NULL) {
460             if (!BN_copy(z, point->Z))
461                 goto err;
462         }
463     }
464
465     ret = 1;
466
467  err:
468     BN_CTX_free(new_ctx);
469     return ret;
470 }
471
472 int ec_GFp_simple_point_set_affine_coordinates(const EC_GROUP *group,
473                                                EC_POINT *point,
474                                                const BIGNUM *x,
475                                                const BIGNUM *y, BN_CTX *ctx)
476 {
477     if (x == NULL || y == NULL) {
478         /*
479          * unlike for projective coordinates, we do not tolerate this
480          */
481         ECerr(EC_F_EC_GFP_SIMPLE_POINT_SET_AFFINE_COORDINATES,
482               ERR_R_PASSED_NULL_PARAMETER);
483         return 0;
484     }
485
486     return EC_POINT_set_Jprojective_coordinates_GFp(group, point, x, y,
487                                                     BN_value_one(), ctx);
488 }
489
490 int ec_GFp_simple_point_get_affine_coordinates(const EC_GROUP *group,
491                                                const EC_POINT *point,
492                                                BIGNUM *x, BIGNUM *y,
493                                                BN_CTX *ctx)
494 {
495     BN_CTX *new_ctx = NULL;
496     BIGNUM *Z, *Z_1, *Z_2, *Z_3;
497     const BIGNUM *Z_;
498     int ret = 0;
499
500     if (EC_POINT_is_at_infinity(group, point)) {
501         ECerr(EC_F_EC_GFP_SIMPLE_POINT_GET_AFFINE_COORDINATES,
502               EC_R_POINT_AT_INFINITY);
503         return 0;
504     }
505
506     if (ctx == NULL) {
507         ctx = new_ctx = BN_CTX_new();
508         if (ctx == NULL)
509             return 0;
510     }
511
512     BN_CTX_start(ctx);
513     Z = BN_CTX_get(ctx);
514     Z_1 = BN_CTX_get(ctx);
515     Z_2 = BN_CTX_get(ctx);
516     Z_3 = BN_CTX_get(ctx);
517     if (Z_3 == NULL)
518         goto err;
519
520     /* transform  (X, Y, Z)  into  (x, y) := (X/Z^2, Y/Z^3) */
521
522     if (group->meth->field_decode) {
523         if (!group->meth->field_decode(group, Z, point->Z, ctx))
524             goto err;
525         Z_ = Z;
526     } else {
527         Z_ = point->Z;
528     }
529
530     if (BN_is_one(Z_)) {
531         if (group->meth->field_decode) {
532             if (x != NULL) {
533                 if (!group->meth->field_decode(group, x, point->X, ctx))
534                     goto err;
535             }
536             if (y != NULL) {
537                 if (!group->meth->field_decode(group, y, point->Y, ctx))
538                     goto err;
539             }
540         } else {
541             if (x != NULL) {
542                 if (!BN_copy(x, point->X))
543                     goto err;
544             }
545             if (y != NULL) {
546                 if (!BN_copy(y, point->Y))
547                     goto err;
548             }
549         }
550     } else {
551         if (!BN_mod_inverse(Z_1, Z_, group->field, ctx)) {
552             ECerr(EC_F_EC_GFP_SIMPLE_POINT_GET_AFFINE_COORDINATES,
553                   ERR_R_BN_LIB);
554             goto err;
555         }
556
557         if (group->meth->field_encode == 0) {
558             /* field_sqr works on standard representation */
559             if (!group->meth->field_sqr(group, Z_2, Z_1, ctx))
560                 goto err;
561         } else {
562             if (!BN_mod_sqr(Z_2, Z_1, group->field, ctx))
563                 goto err;
564         }
565
566         if (x != NULL) {
567             /*
568              * in the Montgomery case, field_mul will cancel out Montgomery
569              * factor in X:
570              */
571             if (!group->meth->field_mul(group, x, point->X, Z_2, ctx))
572                 goto err;
573         }
574
575         if (y != NULL) {
576             if (group->meth->field_encode == 0) {
577                 /*
578                  * field_mul works on standard representation
579                  */
580                 if (!group->meth->field_mul(group, Z_3, Z_2, Z_1, ctx))
581                     goto err;
582             } else {
583                 if (!BN_mod_mul(Z_3, Z_2, Z_1, group->field, ctx))
584                     goto err;
585             }
586
587             /*
588              * in the Montgomery case, field_mul will cancel out Montgomery
589              * factor in Y:
590              */
591             if (!group->meth->field_mul(group, y, point->Y, Z_3, ctx))
592                 goto err;
593         }
594     }
595
596     ret = 1;
597
598  err:
599     BN_CTX_end(ctx);
600     BN_CTX_free(new_ctx);
601     return ret;
602 }
603
604 int ec_GFp_simple_add(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a,
605                       const EC_POINT *b, BN_CTX *ctx)
606 {
607     int (*field_mul) (const EC_GROUP *, BIGNUM *, const BIGNUM *,
608                       const BIGNUM *, BN_CTX *);
609     int (*field_sqr) (const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
610     const BIGNUM *p;
611     BN_CTX *new_ctx = NULL;
612     BIGNUM *n0, *n1, *n2, *n3, *n4, *n5, *n6;
613     int ret = 0;
614
615     if (a == b)
616         return EC_POINT_dbl(group, r, a, ctx);
617     if (EC_POINT_is_at_infinity(group, a))
618         return EC_POINT_copy(r, b);
619     if (EC_POINT_is_at_infinity(group, b))
620         return EC_POINT_copy(r, a);
621
622     field_mul = group->meth->field_mul;
623     field_sqr = group->meth->field_sqr;
624     p = group->field;
625
626     if (ctx == NULL) {
627         ctx = new_ctx = BN_CTX_new();
628         if (ctx == NULL)
629             return 0;
630     }
631
632     BN_CTX_start(ctx);
633     n0 = BN_CTX_get(ctx);
634     n1 = BN_CTX_get(ctx);
635     n2 = BN_CTX_get(ctx);
636     n3 = BN_CTX_get(ctx);
637     n4 = BN_CTX_get(ctx);
638     n5 = BN_CTX_get(ctx);
639     n6 = BN_CTX_get(ctx);
640     if (n6 == NULL)
641         goto end;
642
643     /*
644      * Note that in this function we must not read components of 'a' or 'b'
645      * once we have written the corresponding components of 'r'. ('r' might
646      * be one of 'a' or 'b'.)
647      */
648
649     /* n1, n2 */
650     if (b->Z_is_one) {
651         if (!BN_copy(n1, a->X))
652             goto end;
653         if (!BN_copy(n2, a->Y))
654             goto end;
655         /* n1 = X_a */
656         /* n2 = Y_a */
657     } else {
658         if (!field_sqr(group, n0, b->Z, ctx))
659             goto end;
660         if (!field_mul(group, n1, a->X, n0, ctx))
661             goto end;
662         /* n1 = X_a * Z_b^2 */
663
664         if (!field_mul(group, n0, n0, b->Z, ctx))
665             goto end;
666         if (!field_mul(group, n2, a->Y, n0, ctx))
667             goto end;
668         /* n2 = Y_a * Z_b^3 */
669     }
670
671     /* n3, n4 */
672     if (a->Z_is_one) {
673         if (!BN_copy(n3, b->X))
674             goto end;
675         if (!BN_copy(n4, b->Y))
676             goto end;
677         /* n3 = X_b */
678         /* n4 = Y_b */
679     } else {
680         if (!field_sqr(group, n0, a->Z, ctx))
681             goto end;
682         if (!field_mul(group, n3, b->X, n0, ctx))
683             goto end;
684         /* n3 = X_b * Z_a^2 */
685
686         if (!field_mul(group, n0, n0, a->Z, ctx))
687             goto end;
688         if (!field_mul(group, n4, b->Y, n0, ctx))
689             goto end;
690         /* n4 = Y_b * Z_a^3 */
691     }
692
693     /* n5, n6 */
694     if (!BN_mod_sub_quick(n5, n1, n3, p))
695         goto end;
696     if (!BN_mod_sub_quick(n6, n2, n4, p))
697         goto end;
698     /* n5 = n1 - n3 */
699     /* n6 = n2 - n4 */
700
701     if (BN_is_zero(n5)) {
702         if (BN_is_zero(n6)) {
703             /* a is the same point as b */
704             BN_CTX_end(ctx);
705             ret = EC_POINT_dbl(group, r, a, ctx);
706             ctx = NULL;
707             goto end;
708         } else {
709             /* a is the inverse of b */
710             BN_zero(r->Z);
711             r->Z_is_one = 0;
712             ret = 1;
713             goto end;
714         }
715     }
716
717     /* 'n7', 'n8' */
718     if (!BN_mod_add_quick(n1, n1, n3, p))
719         goto end;
720     if (!BN_mod_add_quick(n2, n2, n4, p))
721         goto end;
722     /* 'n7' = n1 + n3 */
723     /* 'n8' = n2 + n4 */
724
725     /* Z_r */
726     if (a->Z_is_one && b->Z_is_one) {
727         if (!BN_copy(r->Z, n5))
728             goto end;
729     } else {
730         if (a->Z_is_one) {
731             if (!BN_copy(n0, b->Z))
732                 goto end;
733         } else if (b->Z_is_one) {
734             if (!BN_copy(n0, a->Z))
735                 goto end;
736         } else {
737             if (!field_mul(group, n0, a->Z, b->Z, ctx))
738                 goto end;
739         }
740         if (!field_mul(group, r->Z, n0, n5, ctx))
741             goto end;
742     }
743     r->Z_is_one = 0;
744     /* Z_r = Z_a * Z_b * n5 */
745
746     /* X_r */
747     if (!field_sqr(group, n0, n6, ctx))
748         goto end;
749     if (!field_sqr(group, n4, n5, ctx))
750         goto end;
751     if (!field_mul(group, n3, n1, n4, ctx))
752         goto end;
753     if (!BN_mod_sub_quick(r->X, n0, n3, p))
754         goto end;
755     /* X_r = n6^2 - n5^2 * 'n7' */
756
757     /* 'n9' */
758     if (!BN_mod_lshift1_quick(n0, r->X, p))
759         goto end;
760     if (!BN_mod_sub_quick(n0, n3, n0, p))
761         goto end;
762     /* n9 = n5^2 * 'n7' - 2 * X_r */
763
764     /* Y_r */
765     if (!field_mul(group, n0, n0, n6, ctx))
766         goto end;
767     if (!field_mul(group, n5, n4, n5, ctx))
768         goto end;               /* now n5 is n5^3 */
769     if (!field_mul(group, n1, n2, n5, ctx))
770         goto end;
771     if (!BN_mod_sub_quick(n0, n0, n1, p))
772         goto end;
773     if (BN_is_odd(n0))
774         if (!BN_add(n0, n0, p))
775             goto end;
776     /* now  0 <= n0 < 2*p,  and n0 is even */
777     if (!BN_rshift1(r->Y, n0))
778         goto end;
779     /* Y_r = (n6 * 'n9' - 'n8' * 'n5^3') / 2 */
780
781     ret = 1;
782
783  end:
784     if (ctx)                    /* otherwise we already called BN_CTX_end */
785         BN_CTX_end(ctx);
786     BN_CTX_free(new_ctx);
787     return ret;
788 }
789
790 int ec_GFp_simple_dbl(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a,
791                       BN_CTX *ctx)
792 {
793     int (*field_mul) (const EC_GROUP *, BIGNUM *, const BIGNUM *,
794                       const BIGNUM *, BN_CTX *);
795     int (*field_sqr) (const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
796     const BIGNUM *p;
797     BN_CTX *new_ctx = NULL;
798     BIGNUM *n0, *n1, *n2, *n3;
799     int ret = 0;
800
801     if (EC_POINT_is_at_infinity(group, a)) {
802         BN_zero(r->Z);
803         r->Z_is_one = 0;
804         return 1;
805     }
806
807     field_mul = group->meth->field_mul;
808     field_sqr = group->meth->field_sqr;
809     p = group->field;
810
811     if (ctx == NULL) {
812         ctx = new_ctx = BN_CTX_new();
813         if (ctx == NULL)
814             return 0;
815     }
816
817     BN_CTX_start(ctx);
818     n0 = BN_CTX_get(ctx);
819     n1 = BN_CTX_get(ctx);
820     n2 = BN_CTX_get(ctx);
821     n3 = BN_CTX_get(ctx);
822     if (n3 == NULL)
823         goto err;
824
825     /*
826      * Note that in this function we must not read components of 'a' once we
827      * have written the corresponding components of 'r'. ('r' might the same
828      * as 'a'.)
829      */
830
831     /* n1 */
832     if (a->Z_is_one) {
833         if (!field_sqr(group, n0, a->X, ctx))
834             goto err;
835         if (!BN_mod_lshift1_quick(n1, n0, p))
836             goto err;
837         if (!BN_mod_add_quick(n0, n0, n1, p))
838             goto err;
839         if (!BN_mod_add_quick(n1, n0, group->a, p))
840             goto err;
841         /* n1 = 3 * X_a^2 + a_curve */
842     } else if (group->a_is_minus3) {
843         if (!field_sqr(group, n1, a->Z, ctx))
844             goto err;
845         if (!BN_mod_add_quick(n0, a->X, n1, p))
846             goto err;
847         if (!BN_mod_sub_quick(n2, a->X, n1, p))
848             goto err;
849         if (!field_mul(group, n1, n0, n2, ctx))
850             goto err;
851         if (!BN_mod_lshift1_quick(n0, n1, p))
852             goto err;
853         if (!BN_mod_add_quick(n1, n0, n1, p))
854             goto err;
855         /*-
856          * n1 = 3 * (X_a + Z_a^2) * (X_a - Z_a^2)
857          *    = 3 * X_a^2 - 3 * Z_a^4
858          */
859     } else {
860         if (!field_sqr(group, n0, a->X, ctx))
861             goto err;
862         if (!BN_mod_lshift1_quick(n1, n0, p))
863             goto err;
864         if (!BN_mod_add_quick(n0, n0, n1, p))
865             goto err;
866         if (!field_sqr(group, n1, a->Z, ctx))
867             goto err;
868         if (!field_sqr(group, n1, n1, ctx))
869             goto err;
870         if (!field_mul(group, n1, n1, group->a, ctx))
871             goto err;
872         if (!BN_mod_add_quick(n1, n1, n0, p))
873             goto err;
874         /* n1 = 3 * X_a^2 + a_curve * Z_a^4 */
875     }
876
877     /* Z_r */
878     if (a->Z_is_one) {
879         if (!BN_copy(n0, a->Y))
880             goto err;
881     } else {
882         if (!field_mul(group, n0, a->Y, a->Z, ctx))
883             goto err;
884     }
885     if (!BN_mod_lshift1_quick(r->Z, n0, p))
886         goto err;
887     r->Z_is_one = 0;
888     /* Z_r = 2 * Y_a * Z_a */
889
890     /* n2 */
891     if (!field_sqr(group, n3, a->Y, ctx))
892         goto err;
893     if (!field_mul(group, n2, a->X, n3, ctx))
894         goto err;
895     if (!BN_mod_lshift_quick(n2, n2, 2, p))
896         goto err;
897     /* n2 = 4 * X_a * Y_a^2 */
898
899     /* X_r */
900     if (!BN_mod_lshift1_quick(n0, n2, p))
901         goto err;
902     if (!field_sqr(group, r->X, n1, ctx))
903         goto err;
904     if (!BN_mod_sub_quick(r->X, r->X, n0, p))
905         goto err;
906     /* X_r = n1^2 - 2 * n2 */
907
908     /* n3 */
909     if (!field_sqr(group, n0, n3, ctx))
910         goto err;
911     if (!BN_mod_lshift_quick(n3, n0, 3, p))
912         goto err;
913     /* n3 = 8 * Y_a^4 */
914
915     /* Y_r */
916     if (!BN_mod_sub_quick(n0, n2, r->X, p))
917         goto err;
918     if (!field_mul(group, n0, n1, n0, ctx))
919         goto err;
920     if (!BN_mod_sub_quick(r->Y, n0, n3, p))
921         goto err;
922     /* Y_r = n1 * (n2 - X_r) - n3 */
923
924     ret = 1;
925
926  err:
927     BN_CTX_end(ctx);
928     BN_CTX_free(new_ctx);
929     return ret;
930 }
931
932 int ec_GFp_simple_invert(const EC_GROUP *group, EC_POINT *point, BN_CTX *ctx)
933 {
934     if (EC_POINT_is_at_infinity(group, point) || BN_is_zero(point->Y))
935         /* point is its own inverse */
936         return 1;
937
938     return BN_usub(point->Y, group->field, point->Y);
939 }
940
941 int ec_GFp_simple_is_at_infinity(const EC_GROUP *group, const EC_POINT *point)
942 {
943     return BN_is_zero(point->Z);
944 }
945
946 int ec_GFp_simple_is_on_curve(const EC_GROUP *group, const EC_POINT *point,
947                               BN_CTX *ctx)
948 {
949     int (*field_mul) (const EC_GROUP *, BIGNUM *, const BIGNUM *,
950                       const BIGNUM *, BN_CTX *);
951     int (*field_sqr) (const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
952     const BIGNUM *p;
953     BN_CTX *new_ctx = NULL;
954     BIGNUM *rh, *tmp, *Z4, *Z6;
955     int ret = -1;
956
957     if (EC_POINT_is_at_infinity(group, point))
958         return 1;
959
960     field_mul = group->meth->field_mul;
961     field_sqr = group->meth->field_sqr;
962     p = group->field;
963
964     if (ctx == NULL) {
965         ctx = new_ctx = BN_CTX_new();
966         if (ctx == NULL)
967             return -1;
968     }
969
970     BN_CTX_start(ctx);
971     rh = BN_CTX_get(ctx);
972     tmp = BN_CTX_get(ctx);
973     Z4 = BN_CTX_get(ctx);
974     Z6 = BN_CTX_get(ctx);
975     if (Z6 == NULL)
976         goto err;
977
978     /*-
979      * We have a curve defined by a Weierstrass equation
980      *      y^2 = x^3 + a*x + b.
981      * The point to consider is given in Jacobian projective coordinates
982      * where  (X, Y, Z)  represents  (x, y) = (X/Z^2, Y/Z^3).
983      * Substituting this and multiplying by  Z^6  transforms the above equation into
984      *      Y^2 = X^3 + a*X*Z^4 + b*Z^6.
985      * To test this, we add up the right-hand side in 'rh'.
986      */
987
988     /* rh := X^2 */
989     if (!field_sqr(group, rh, point->X, ctx))
990         goto err;
991
992     if (!point->Z_is_one) {
993         if (!field_sqr(group, tmp, point->Z, ctx))
994             goto err;
995         if (!field_sqr(group, Z4, tmp, ctx))
996             goto err;
997         if (!field_mul(group, Z6, Z4, tmp, ctx))
998             goto err;
999
1000         /* rh := (rh + a*Z^4)*X */
1001         if (group->a_is_minus3) {
1002             if (!BN_mod_lshift1_quick(tmp, Z4, p))
1003                 goto err;
1004             if (!BN_mod_add_quick(tmp, tmp, Z4, p))
1005                 goto err;
1006             if (!BN_mod_sub_quick(rh, rh, tmp, p))
1007                 goto err;
1008             if (!field_mul(group, rh, rh, point->X, ctx))
1009                 goto err;
1010         } else {
1011             if (!field_mul(group, tmp, Z4, group->a, ctx))
1012                 goto err;
1013             if (!BN_mod_add_quick(rh, rh, tmp, p))
1014                 goto err;
1015             if (!field_mul(group, rh, rh, point->X, ctx))
1016                 goto err;
1017         }
1018
1019         /* rh := rh + b*Z^6 */
1020         if (!field_mul(group, tmp, group->b, Z6, ctx))
1021             goto err;
1022         if (!BN_mod_add_quick(rh, rh, tmp, p))
1023             goto err;
1024     } else {
1025         /* point->Z_is_one */
1026
1027         /* rh := (rh + a)*X */
1028         if (!BN_mod_add_quick(rh, rh, group->a, p))
1029             goto err;
1030         if (!field_mul(group, rh, rh, point->X, ctx))
1031             goto err;
1032         /* rh := rh + b */
1033         if (!BN_mod_add_quick(rh, rh, group->b, p))
1034             goto err;
1035     }
1036
1037     /* 'lh' := Y^2 */
1038     if (!field_sqr(group, tmp, point->Y, ctx))
1039         goto err;
1040
1041     ret = (0 == BN_ucmp(tmp, rh));
1042
1043  err:
1044     BN_CTX_end(ctx);
1045     BN_CTX_free(new_ctx);
1046     return ret;
1047 }
1048
1049 int ec_GFp_simple_cmp(const EC_GROUP *group, const EC_POINT *a,
1050                       const EC_POINT *b, BN_CTX *ctx)
1051 {
1052     /*-
1053      * return values:
1054      *  -1   error
1055      *   0   equal (in affine coordinates)
1056      *   1   not equal
1057      */
1058
1059     int (*field_mul) (const EC_GROUP *, BIGNUM *, const BIGNUM *,
1060                       const BIGNUM *, BN_CTX *);
1061     int (*field_sqr) (const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
1062     BN_CTX *new_ctx = NULL;
1063     BIGNUM *tmp1, *tmp2, *Za23, *Zb23;
1064     const BIGNUM *tmp1_, *tmp2_;
1065     int ret = -1;
1066
1067     if (EC_POINT_is_at_infinity(group, a)) {
1068         return EC_POINT_is_at_infinity(group, b) ? 0 : 1;
1069     }
1070
1071     if (EC_POINT_is_at_infinity(group, b))
1072         return 1;
1073
1074     if (a->Z_is_one && b->Z_is_one) {
1075         return ((BN_cmp(a->X, b->X) == 0) && BN_cmp(a->Y, b->Y) == 0) ? 0 : 1;
1076     }
1077
1078     field_mul = group->meth->field_mul;
1079     field_sqr = group->meth->field_sqr;
1080
1081     if (ctx == NULL) {
1082         ctx = new_ctx = BN_CTX_new();
1083         if (ctx == NULL)
1084             return -1;
1085     }
1086
1087     BN_CTX_start(ctx);
1088     tmp1 = BN_CTX_get(ctx);
1089     tmp2 = BN_CTX_get(ctx);
1090     Za23 = BN_CTX_get(ctx);
1091     Zb23 = BN_CTX_get(ctx);
1092     if (Zb23 == NULL)
1093         goto end;
1094
1095     /*-
1096      * We have to decide whether
1097      *     (X_a/Z_a^2, Y_a/Z_a^3) = (X_b/Z_b^2, Y_b/Z_b^3),
1098      * or equivalently, whether
1099      *     (X_a*Z_b^2, Y_a*Z_b^3) = (X_b*Z_a^2, Y_b*Z_a^3).
1100      */
1101
1102     if (!b->Z_is_one) {
1103         if (!field_sqr(group, Zb23, b->Z, ctx))
1104             goto end;
1105         if (!field_mul(group, tmp1, a->X, Zb23, ctx))
1106             goto end;
1107         tmp1_ = tmp1;
1108     } else
1109         tmp1_ = a->X;
1110     if (!a->Z_is_one) {
1111         if (!field_sqr(group, Za23, a->Z, ctx))
1112             goto end;
1113         if (!field_mul(group, tmp2, b->X, Za23, ctx))
1114             goto end;
1115         tmp2_ = tmp2;
1116     } else
1117         tmp2_ = b->X;
1118
1119     /* compare  X_a*Z_b^2  with  X_b*Z_a^2 */
1120     if (BN_cmp(tmp1_, tmp2_) != 0) {
1121         ret = 1;                /* points differ */
1122         goto end;
1123     }
1124
1125     if (!b->Z_is_one) {
1126         if (!field_mul(group, Zb23, Zb23, b->Z, ctx))
1127             goto end;
1128         if (!field_mul(group, tmp1, a->Y, Zb23, ctx))
1129             goto end;
1130         /* tmp1_ = tmp1 */
1131     } else
1132         tmp1_ = a->Y;
1133     if (!a->Z_is_one) {
1134         if (!field_mul(group, Za23, Za23, a->Z, ctx))
1135             goto end;
1136         if (!field_mul(group, tmp2, b->Y, Za23, ctx))
1137             goto end;
1138         /* tmp2_ = tmp2 */
1139     } else
1140         tmp2_ = b->Y;
1141
1142     /* compare  Y_a*Z_b^3  with  Y_b*Z_a^3 */
1143     if (BN_cmp(tmp1_, tmp2_) != 0) {
1144         ret = 1;                /* points differ */
1145         goto end;
1146     }
1147
1148     /* points are equal */
1149     ret = 0;
1150
1151  end:
1152     BN_CTX_end(ctx);
1153     BN_CTX_free(new_ctx);
1154     return ret;
1155 }
1156
1157 int ec_GFp_simple_make_affine(const EC_GROUP *group, EC_POINT *point,
1158                               BN_CTX *ctx)
1159 {
1160     BN_CTX *new_ctx = NULL;
1161     BIGNUM *x, *y;
1162     int ret = 0;
1163
1164     if (point->Z_is_one || EC_POINT_is_at_infinity(group, point))
1165         return 1;
1166
1167     if (ctx == NULL) {
1168         ctx = new_ctx = BN_CTX_new();
1169         if (ctx == NULL)
1170             return 0;
1171     }
1172
1173     BN_CTX_start(ctx);
1174     x = BN_CTX_get(ctx);
1175     y = BN_CTX_get(ctx);
1176     if (y == NULL)
1177         goto err;
1178
1179     if (!EC_POINT_get_affine_coordinates_GFp(group, point, x, y, ctx))
1180         goto err;
1181     if (!EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx))
1182         goto err;
1183     if (!point->Z_is_one) {
1184         ECerr(EC_F_EC_GFP_SIMPLE_MAKE_AFFINE, ERR_R_INTERNAL_ERROR);
1185         goto err;
1186     }
1187
1188     ret = 1;
1189
1190  err:
1191     BN_CTX_end(ctx);
1192     BN_CTX_free(new_ctx);
1193     return ret;
1194 }
1195
1196 int ec_GFp_simple_points_make_affine(const EC_GROUP *group, size_t num,
1197                                      EC_POINT *points[], BN_CTX *ctx)
1198 {
1199     BN_CTX *new_ctx = NULL;
1200     BIGNUM *tmp, *tmp_Z;
1201     BIGNUM **prod_Z = NULL;
1202     size_t i;
1203     int ret = 0;
1204
1205     if (num == 0)
1206         return 1;
1207
1208     if (ctx == NULL) {
1209         ctx = new_ctx = BN_CTX_new();
1210         if (ctx == NULL)
1211             return 0;
1212     }
1213
1214     BN_CTX_start(ctx);
1215     tmp = BN_CTX_get(ctx);
1216     tmp_Z = BN_CTX_get(ctx);
1217     if (tmp_Z == NULL)
1218         goto err;
1219
1220     prod_Z = OPENSSL_malloc(num * sizeof(prod_Z[0]));
1221     if (prod_Z == NULL)
1222         goto err;
1223     for (i = 0; i < num; i++) {
1224         prod_Z[i] = BN_new();
1225         if (prod_Z[i] == NULL)
1226             goto err;
1227     }
1228
1229     /*
1230      * Set each prod_Z[i] to the product of points[0]->Z .. points[i]->Z,
1231      * skipping any zero-valued inputs (pretend that they're 1).
1232      */
1233
1234     if (!BN_is_zero(points[0]->Z)) {
1235         if (!BN_copy(prod_Z[0], points[0]->Z))
1236             goto err;
1237     } else {
1238         if (group->meth->field_set_to_one != 0) {
1239             if (!group->meth->field_set_to_one(group, prod_Z[0], ctx))
1240                 goto err;
1241         } else {
1242             if (!BN_one(prod_Z[0]))
1243                 goto err;
1244         }
1245     }
1246
1247     for (i = 1; i < num; i++) {
1248         if (!BN_is_zero(points[i]->Z)) {
1249             if (!group->
1250                 meth->field_mul(group, prod_Z[i], prod_Z[i - 1], points[i]->Z,
1251                                 ctx))
1252                 goto err;
1253         } else {
1254             if (!BN_copy(prod_Z[i], prod_Z[i - 1]))
1255                 goto err;
1256         }
1257     }
1258
1259     /*
1260      * Now use a single explicit inversion to replace every non-zero
1261      * points[i]->Z by its inverse.
1262      */
1263
1264     if (!BN_mod_inverse(tmp, prod_Z[num - 1], group->field, ctx)) {
1265         ECerr(EC_F_EC_GFP_SIMPLE_POINTS_MAKE_AFFINE, ERR_R_BN_LIB);
1266         goto err;
1267     }
1268     if (group->meth->field_encode != 0) {
1269         /*
1270          * In the Montgomery case, we just turned R*H (representing H) into
1271          * 1/(R*H), but we need R*(1/H) (representing 1/H); i.e. we need to
1272          * multiply by the Montgomery factor twice.
1273          */
1274         if (!group->meth->field_encode(group, tmp, tmp, ctx))
1275             goto err;
1276         if (!group->meth->field_encode(group, tmp, tmp, ctx))
1277             goto err;
1278     }
1279
1280     for (i = num - 1; i > 0; --i) {
1281         /*
1282          * Loop invariant: tmp is the product of the inverses of points[0]->Z
1283          * .. points[i]->Z (zero-valued inputs skipped).
1284          */
1285         if (!BN_is_zero(points[i]->Z)) {
1286             /*
1287              * Set tmp_Z to the inverse of points[i]->Z (as product of Z
1288              * inverses 0 .. i, Z values 0 .. i - 1).
1289              */
1290             if (!group->
1291                 meth->field_mul(group, tmp_Z, prod_Z[i - 1], tmp, ctx))
1292                 goto err;
1293             /*
1294              * Update tmp to satisfy the loop invariant for i - 1.
1295              */
1296             if (!group->meth->field_mul(group, tmp, tmp, points[i]->Z, ctx))
1297                 goto err;
1298             /* Replace points[i]->Z by its inverse. */
1299             if (!BN_copy(points[i]->Z, tmp_Z))
1300                 goto err;
1301         }
1302     }
1303
1304     if (!BN_is_zero(points[0]->Z)) {
1305         /* Replace points[0]->Z by its inverse. */
1306         if (!BN_copy(points[0]->Z, tmp))
1307             goto err;
1308     }
1309
1310     /* Finally, fix up the X and Y coordinates for all points. */
1311
1312     for (i = 0; i < num; i++) {
1313         EC_POINT *p = points[i];
1314
1315         if (!BN_is_zero(p->Z)) {
1316             /* turn  (X, Y, 1/Z)  into  (X/Z^2, Y/Z^3, 1) */
1317
1318             if (!group->meth->field_sqr(group, tmp, p->Z, ctx))
1319                 goto err;
1320             if (!group->meth->field_mul(group, p->X, p->X, tmp, ctx))
1321                 goto err;
1322
1323             if (!group->meth->field_mul(group, tmp, tmp, p->Z, ctx))
1324                 goto err;
1325             if (!group->meth->field_mul(group, p->Y, p->Y, tmp, ctx))
1326                 goto err;
1327
1328             if (group->meth->field_set_to_one != 0) {
1329                 if (!group->meth->field_set_to_one(group, p->Z, ctx))
1330                     goto err;
1331             } else {
1332                 if (!BN_one(p->Z))
1333                     goto err;
1334             }
1335             p->Z_is_one = 1;
1336         }
1337     }
1338
1339     ret = 1;
1340
1341  err:
1342     BN_CTX_end(ctx);
1343     BN_CTX_free(new_ctx);
1344     if (prod_Z != NULL) {
1345         for (i = 0; i < num; i++) {
1346             if (prod_Z[i] == NULL)
1347                 break;
1348             BN_clear_free(prod_Z[i]);
1349         }
1350         OPENSSL_free(prod_Z);
1351     }
1352     return ret;
1353 }
1354
1355 int ec_GFp_simple_field_mul(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a,
1356                             const BIGNUM *b, BN_CTX *ctx)
1357 {
1358     return BN_mod_mul(r, a, b, group->field, ctx);
1359 }
1360
1361 int ec_GFp_simple_field_sqr(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a,
1362                             BN_CTX *ctx)
1363 {
1364     return BN_mod_sqr(r, a, group->field, ctx);
1365 }