Use the new non-curve type specific EC functions internally
[openssl.git] / crypto / ec / ec2_smpl.c
1 /*
2  * Copyright 2002-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
13 #include "internal/bn_int.h"
14 #include "ec_lcl.h"
15
16 #ifndef OPENSSL_NO_EC2M
17
18 /*
19  * Initialize a GF(2^m)-based EC_GROUP structure. Note that all other members
20  * are handled by EC_GROUP_new.
21  */
22 int ec_GF2m_simple_group_init(EC_GROUP *group)
23 {
24     group->field = BN_new();
25     group->a = BN_new();
26     group->b = BN_new();
27
28     if (group->field == NULL || group->a == NULL || group->b == NULL) {
29         BN_free(group->field);
30         BN_free(group->a);
31         BN_free(group->b);
32         return 0;
33     }
34     return 1;
35 }
36
37 /*
38  * Free a GF(2^m)-based EC_GROUP structure. Note that all other members are
39  * handled by EC_GROUP_free.
40  */
41 void ec_GF2m_simple_group_finish(EC_GROUP *group)
42 {
43     BN_free(group->field);
44     BN_free(group->a);
45     BN_free(group->b);
46 }
47
48 /*
49  * Clear and free a GF(2^m)-based EC_GROUP structure. Note that all other
50  * members are handled by EC_GROUP_clear_free.
51  */
52 void ec_GF2m_simple_group_clear_finish(EC_GROUP *group)
53 {
54     BN_clear_free(group->field);
55     BN_clear_free(group->a);
56     BN_clear_free(group->b);
57     group->poly[0] = 0;
58     group->poly[1] = 0;
59     group->poly[2] = 0;
60     group->poly[3] = 0;
61     group->poly[4] = 0;
62     group->poly[5] = -1;
63 }
64
65 /*
66  * Copy a GF(2^m)-based EC_GROUP structure. Note that all other members are
67  * handled by EC_GROUP_copy.
68  */
69 int ec_GF2m_simple_group_copy(EC_GROUP *dest, const EC_GROUP *src)
70 {
71     if (!BN_copy(dest->field, src->field))
72         return 0;
73     if (!BN_copy(dest->a, src->a))
74         return 0;
75     if (!BN_copy(dest->b, src->b))
76         return 0;
77     dest->poly[0] = src->poly[0];
78     dest->poly[1] = src->poly[1];
79     dest->poly[2] = src->poly[2];
80     dest->poly[3] = src->poly[3];
81     dest->poly[4] = src->poly[4];
82     dest->poly[5] = src->poly[5];
83     if (bn_wexpand(dest->a, (int)(dest->poly[0] + BN_BITS2 - 1) / BN_BITS2) ==
84         NULL)
85         return 0;
86     if (bn_wexpand(dest->b, (int)(dest->poly[0] + BN_BITS2 - 1) / BN_BITS2) ==
87         NULL)
88         return 0;
89     bn_set_all_zero(dest->a);
90     bn_set_all_zero(dest->b);
91     return 1;
92 }
93
94 /* Set the curve parameters of an EC_GROUP structure. */
95 int ec_GF2m_simple_group_set_curve(EC_GROUP *group,
96                                    const BIGNUM *p, const BIGNUM *a,
97                                    const BIGNUM *b, BN_CTX *ctx)
98 {
99     int ret = 0, i;
100
101     /* group->field */
102     if (!BN_copy(group->field, p))
103         goto err;
104     i = BN_GF2m_poly2arr(group->field, group->poly, 6) - 1;
105     if ((i != 5) && (i != 3)) {
106         ECerr(EC_F_EC_GF2M_SIMPLE_GROUP_SET_CURVE, EC_R_UNSUPPORTED_FIELD);
107         goto err;
108     }
109
110     /* group->a */
111     if (!BN_GF2m_mod_arr(group->a, a, group->poly))
112         goto err;
113     if (bn_wexpand(group->a, (int)(group->poly[0] + BN_BITS2 - 1) / BN_BITS2)
114         == NULL)
115         goto err;
116     bn_set_all_zero(group->a);
117
118     /* group->b */
119     if (!BN_GF2m_mod_arr(group->b, b, group->poly))
120         goto err;
121     if (bn_wexpand(group->b, (int)(group->poly[0] + BN_BITS2 - 1) / BN_BITS2)
122         == NULL)
123         goto err;
124     bn_set_all_zero(group->b);
125
126     ret = 1;
127  err:
128     return ret;
129 }
130
131 /*
132  * Get the curve parameters of an EC_GROUP structure. If p, a, or b are NULL
133  * then there values will not be set but the method will return with success.
134  */
135 int ec_GF2m_simple_group_get_curve(const EC_GROUP *group, BIGNUM *p,
136                                    BIGNUM *a, BIGNUM *b, BN_CTX *ctx)
137 {
138     int ret = 0;
139
140     if (p != NULL) {
141         if (!BN_copy(p, group->field))
142             return 0;
143     }
144
145     if (a != NULL) {
146         if (!BN_copy(a, group->a))
147             goto err;
148     }
149
150     if (b != NULL) {
151         if (!BN_copy(b, group->b))
152             goto err;
153     }
154
155     ret = 1;
156
157  err:
158     return ret;
159 }
160
161 /*
162  * Gets the degree of the field.  For a curve over GF(2^m) this is the value
163  * m.
164  */
165 int ec_GF2m_simple_group_get_degree(const EC_GROUP *group)
166 {
167     return BN_num_bits(group->field) - 1;
168 }
169
170 /*
171  * Checks the discriminant of the curve. y^2 + x*y = x^3 + a*x^2 + b is an
172  * elliptic curve <=> b != 0 (mod p)
173  */
174 int ec_GF2m_simple_group_check_discriminant(const EC_GROUP *group,
175                                             BN_CTX *ctx)
176 {
177     int ret = 0;
178     BIGNUM *b;
179     BN_CTX *new_ctx = NULL;
180
181     if (ctx == NULL) {
182         ctx = new_ctx = BN_CTX_new();
183         if (ctx == NULL) {
184             ECerr(EC_F_EC_GF2M_SIMPLE_GROUP_CHECK_DISCRIMINANT,
185                   ERR_R_MALLOC_FAILURE);
186             goto err;
187         }
188     }
189     BN_CTX_start(ctx);
190     b = BN_CTX_get(ctx);
191     if (b == NULL)
192         goto err;
193
194     if (!BN_GF2m_mod_arr(b, group->b, group->poly))
195         goto err;
196
197     /*
198      * check the discriminant: y^2 + x*y = x^3 + a*x^2 + b is an elliptic
199      * curve <=> b != 0 (mod p)
200      */
201     if (BN_is_zero(b))
202         goto err;
203
204     ret = 1;
205
206  err:
207     if (ctx != NULL)
208         BN_CTX_end(ctx);
209     BN_CTX_free(new_ctx);
210     return ret;
211 }
212
213 /* Initializes an EC_POINT. */
214 int ec_GF2m_simple_point_init(EC_POINT *point)
215 {
216     point->X = BN_new();
217     point->Y = BN_new();
218     point->Z = BN_new();
219
220     if (point->X == NULL || point->Y == NULL || point->Z == NULL) {
221         BN_free(point->X);
222         BN_free(point->Y);
223         BN_free(point->Z);
224         return 0;
225     }
226     return 1;
227 }
228
229 /* Frees an EC_POINT. */
230 void ec_GF2m_simple_point_finish(EC_POINT *point)
231 {
232     BN_free(point->X);
233     BN_free(point->Y);
234     BN_free(point->Z);
235 }
236
237 /* Clears and frees an EC_POINT. */
238 void ec_GF2m_simple_point_clear_finish(EC_POINT *point)
239 {
240     BN_clear_free(point->X);
241     BN_clear_free(point->Y);
242     BN_clear_free(point->Z);
243     point->Z_is_one = 0;
244 }
245
246 /*
247  * Copy the contents of one EC_POINT into another.  Assumes dest is
248  * initialized.
249  */
250 int ec_GF2m_simple_point_copy(EC_POINT *dest, const EC_POINT *src)
251 {
252     if (!BN_copy(dest->X, src->X))
253         return 0;
254     if (!BN_copy(dest->Y, src->Y))
255         return 0;
256     if (!BN_copy(dest->Z, src->Z))
257         return 0;
258     dest->Z_is_one = src->Z_is_one;
259     dest->curve_name = src->curve_name;
260
261     return 1;
262 }
263
264 /*
265  * Set an EC_POINT to the point at infinity. A point at infinity is
266  * represented by having Z=0.
267  */
268 int ec_GF2m_simple_point_set_to_infinity(const EC_GROUP *group,
269                                          EC_POINT *point)
270 {
271     point->Z_is_one = 0;
272     BN_zero(point->Z);
273     return 1;
274 }
275
276 /*
277  * Set the coordinates of an EC_POINT using affine coordinates. Note that
278  * the simple implementation only uses affine coordinates.
279  */
280 int ec_GF2m_simple_point_set_affine_coordinates(const EC_GROUP *group,
281                                                 EC_POINT *point,
282                                                 const BIGNUM *x,
283                                                 const BIGNUM *y, BN_CTX *ctx)
284 {
285     int ret = 0;
286     if (x == NULL || y == NULL) {
287         ECerr(EC_F_EC_GF2M_SIMPLE_POINT_SET_AFFINE_COORDINATES,
288               ERR_R_PASSED_NULL_PARAMETER);
289         return 0;
290     }
291
292     if (!BN_copy(point->X, x))
293         goto err;
294     BN_set_negative(point->X, 0);
295     if (!BN_copy(point->Y, y))
296         goto err;
297     BN_set_negative(point->Y, 0);
298     if (!BN_copy(point->Z, BN_value_one()))
299         goto err;
300     BN_set_negative(point->Z, 0);
301     point->Z_is_one = 1;
302     ret = 1;
303
304  err:
305     return ret;
306 }
307
308 /*
309  * Gets the affine coordinates of an EC_POINT. Note that the simple
310  * implementation only uses affine coordinates.
311  */
312 int ec_GF2m_simple_point_get_affine_coordinates(const EC_GROUP *group,
313                                                 const EC_POINT *point,
314                                                 BIGNUM *x, BIGNUM *y,
315                                                 BN_CTX *ctx)
316 {
317     int ret = 0;
318
319     if (EC_POINT_is_at_infinity(group, point)) {
320         ECerr(EC_F_EC_GF2M_SIMPLE_POINT_GET_AFFINE_COORDINATES,
321               EC_R_POINT_AT_INFINITY);
322         return 0;
323     }
324
325     if (BN_cmp(point->Z, BN_value_one())) {
326         ECerr(EC_F_EC_GF2M_SIMPLE_POINT_GET_AFFINE_COORDINATES,
327               ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
328         return 0;
329     }
330     if (x != NULL) {
331         if (!BN_copy(x, point->X))
332             goto err;
333         BN_set_negative(x, 0);
334     }
335     if (y != NULL) {
336         if (!BN_copy(y, point->Y))
337             goto err;
338         BN_set_negative(y, 0);
339     }
340     ret = 1;
341
342  err:
343     return ret;
344 }
345
346 /*
347  * Computes a + b and stores the result in r.  r could be a or b, a could be
348  * b. Uses algorithm A.10.2 of IEEE P1363.
349  */
350 int ec_GF2m_simple_add(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a,
351                        const EC_POINT *b, BN_CTX *ctx)
352 {
353     BN_CTX *new_ctx = NULL;
354     BIGNUM *x0, *y0, *x1, *y1, *x2, *y2, *s, *t;
355     int ret = 0;
356
357     if (EC_POINT_is_at_infinity(group, a)) {
358         if (!EC_POINT_copy(r, b))
359             return 0;
360         return 1;
361     }
362
363     if (EC_POINT_is_at_infinity(group, b)) {
364         if (!EC_POINT_copy(r, a))
365             return 0;
366         return 1;
367     }
368
369     if (ctx == NULL) {
370         ctx = new_ctx = BN_CTX_new();
371         if (ctx == NULL)
372             return 0;
373     }
374
375     BN_CTX_start(ctx);
376     x0 = BN_CTX_get(ctx);
377     y0 = BN_CTX_get(ctx);
378     x1 = BN_CTX_get(ctx);
379     y1 = BN_CTX_get(ctx);
380     x2 = BN_CTX_get(ctx);
381     y2 = BN_CTX_get(ctx);
382     s = BN_CTX_get(ctx);
383     t = BN_CTX_get(ctx);
384     if (t == NULL)
385         goto err;
386
387     if (a->Z_is_one) {
388         if (!BN_copy(x0, a->X))
389             goto err;
390         if (!BN_copy(y0, a->Y))
391             goto err;
392     } else {
393         if (!EC_POINT_get_affine_coordinates(group, a, x0, y0, ctx))
394             goto err;
395     }
396     if (b->Z_is_one) {
397         if (!BN_copy(x1, b->X))
398             goto err;
399         if (!BN_copy(y1, b->Y))
400             goto err;
401     } else {
402         if (!EC_POINT_get_affine_coordinates(group, b, x1, y1, ctx))
403             goto err;
404     }
405
406     if (BN_GF2m_cmp(x0, x1)) {
407         if (!BN_GF2m_add(t, x0, x1))
408             goto err;
409         if (!BN_GF2m_add(s, y0, y1))
410             goto err;
411         if (!group->meth->field_div(group, s, s, t, ctx))
412             goto err;
413         if (!group->meth->field_sqr(group, x2, s, ctx))
414             goto err;
415         if (!BN_GF2m_add(x2, x2, group->a))
416             goto err;
417         if (!BN_GF2m_add(x2, x2, s))
418             goto err;
419         if (!BN_GF2m_add(x2, x2, t))
420             goto err;
421     } else {
422         if (BN_GF2m_cmp(y0, y1) || BN_is_zero(x1)) {
423             if (!EC_POINT_set_to_infinity(group, r))
424                 goto err;
425             ret = 1;
426             goto err;
427         }
428         if (!group->meth->field_div(group, s, y1, x1, ctx))
429             goto err;
430         if (!BN_GF2m_add(s, s, x1))
431             goto err;
432
433         if (!group->meth->field_sqr(group, x2, s, ctx))
434             goto err;
435         if (!BN_GF2m_add(x2, x2, s))
436             goto err;
437         if (!BN_GF2m_add(x2, x2, group->a))
438             goto err;
439     }
440
441     if (!BN_GF2m_add(y2, x1, x2))
442         goto err;
443     if (!group->meth->field_mul(group, y2, y2, s, ctx))
444         goto err;
445     if (!BN_GF2m_add(y2, y2, x2))
446         goto err;
447     if (!BN_GF2m_add(y2, y2, y1))
448         goto err;
449
450     if (!EC_POINT_set_affine_coordinates(group, r, x2, y2, ctx))
451         goto err;
452
453     ret = 1;
454
455  err:
456     BN_CTX_end(ctx);
457     BN_CTX_free(new_ctx);
458     return ret;
459 }
460
461 /*
462  * Computes 2 * a and stores the result in r.  r could be a. Uses algorithm
463  * A.10.2 of IEEE P1363.
464  */
465 int ec_GF2m_simple_dbl(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a,
466                        BN_CTX *ctx)
467 {
468     return ec_GF2m_simple_add(group, r, a, a, ctx);
469 }
470
471 int ec_GF2m_simple_invert(const EC_GROUP *group, EC_POINT *point, BN_CTX *ctx)
472 {
473     if (EC_POINT_is_at_infinity(group, point) || BN_is_zero(point->Y))
474         /* point is its own inverse */
475         return 1;
476
477     if (!EC_POINT_make_affine(group, point, ctx))
478         return 0;
479     return BN_GF2m_add(point->Y, point->X, point->Y);
480 }
481
482 /* Indicates whether the given point is the point at infinity. */
483 int ec_GF2m_simple_is_at_infinity(const EC_GROUP *group,
484                                   const EC_POINT *point)
485 {
486     return BN_is_zero(point->Z);
487 }
488
489 /*-
490  * Determines whether the given EC_POINT is an actual point on the curve defined
491  * in the EC_GROUP.  A point is valid if it satisfies the Weierstrass equation:
492  *      y^2 + x*y = x^3 + a*x^2 + b.
493  */
494 int ec_GF2m_simple_is_on_curve(const EC_GROUP *group, const EC_POINT *point,
495                                BN_CTX *ctx)
496 {
497     int ret = -1;
498     BN_CTX *new_ctx = NULL;
499     BIGNUM *lh, *y2;
500     int (*field_mul) (const EC_GROUP *, BIGNUM *, const BIGNUM *,
501                       const BIGNUM *, BN_CTX *);
502     int (*field_sqr) (const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
503
504     if (EC_POINT_is_at_infinity(group, point))
505         return 1;
506
507     field_mul = group->meth->field_mul;
508     field_sqr = group->meth->field_sqr;
509
510     /* only support affine coordinates */
511     if (!point->Z_is_one)
512         return -1;
513
514     if (ctx == NULL) {
515         ctx = new_ctx = BN_CTX_new();
516         if (ctx == NULL)
517             return -1;
518     }
519
520     BN_CTX_start(ctx);
521     y2 = BN_CTX_get(ctx);
522     lh = BN_CTX_get(ctx);
523     if (lh == NULL)
524         goto err;
525
526     /*-
527      * We have a curve defined by a Weierstrass equation
528      *      y^2 + x*y = x^3 + a*x^2 + b.
529      *  <=> x^3 + a*x^2 + x*y + b + y^2 = 0
530      *  <=> ((x + a) * x + y ) * x + b + y^2 = 0
531      */
532     if (!BN_GF2m_add(lh, point->X, group->a))
533         goto err;
534     if (!field_mul(group, lh, lh, point->X, ctx))
535         goto err;
536     if (!BN_GF2m_add(lh, lh, point->Y))
537         goto err;
538     if (!field_mul(group, lh, lh, point->X, ctx))
539         goto err;
540     if (!BN_GF2m_add(lh, lh, group->b))
541         goto err;
542     if (!field_sqr(group, y2, point->Y, ctx))
543         goto err;
544     if (!BN_GF2m_add(lh, lh, y2))
545         goto err;
546     ret = BN_is_zero(lh);
547
548  err:
549     BN_CTX_end(ctx);
550     BN_CTX_free(new_ctx);
551     return ret;
552 }
553
554 /*-
555  * Indicates whether two points are equal.
556  * Return values:
557  *  -1   error
558  *   0   equal (in affine coordinates)
559  *   1   not equal
560  */
561 int ec_GF2m_simple_cmp(const EC_GROUP *group, const EC_POINT *a,
562                        const EC_POINT *b, BN_CTX *ctx)
563 {
564     BIGNUM *aX, *aY, *bX, *bY;
565     BN_CTX *new_ctx = NULL;
566     int ret = -1;
567
568     if (EC_POINT_is_at_infinity(group, a)) {
569         return EC_POINT_is_at_infinity(group, b) ? 0 : 1;
570     }
571
572     if (EC_POINT_is_at_infinity(group, b))
573         return 1;
574
575     if (a->Z_is_one && b->Z_is_one) {
576         return ((BN_cmp(a->X, b->X) == 0) && BN_cmp(a->Y, b->Y) == 0) ? 0 : 1;
577     }
578
579     if (ctx == NULL) {
580         ctx = new_ctx = BN_CTX_new();
581         if (ctx == NULL)
582             return -1;
583     }
584
585     BN_CTX_start(ctx);
586     aX = BN_CTX_get(ctx);
587     aY = BN_CTX_get(ctx);
588     bX = BN_CTX_get(ctx);
589     bY = BN_CTX_get(ctx);
590     if (bY == NULL)
591         goto err;
592
593     if (!EC_POINT_get_affine_coordinates(group, a, aX, aY, ctx))
594         goto err;
595     if (!EC_POINT_get_affine_coordinates(group, b, bX, bY, ctx))
596         goto err;
597     ret = ((BN_cmp(aX, bX) == 0) && BN_cmp(aY, bY) == 0) ? 0 : 1;
598
599  err:
600     BN_CTX_end(ctx);
601     BN_CTX_free(new_ctx);
602     return ret;
603 }
604
605 /* Forces the given EC_POINT to internally use affine coordinates. */
606 int ec_GF2m_simple_make_affine(const EC_GROUP *group, EC_POINT *point,
607                                BN_CTX *ctx)
608 {
609     BN_CTX *new_ctx = NULL;
610     BIGNUM *x, *y;
611     int ret = 0;
612
613     if (point->Z_is_one || EC_POINT_is_at_infinity(group, point))
614         return 1;
615
616     if (ctx == NULL) {
617         ctx = new_ctx = BN_CTX_new();
618         if (ctx == NULL)
619             return 0;
620     }
621
622     BN_CTX_start(ctx);
623     x = BN_CTX_get(ctx);
624     y = BN_CTX_get(ctx);
625     if (y == NULL)
626         goto err;
627
628     if (!EC_POINT_get_affine_coordinates(group, point, x, y, ctx))
629         goto err;
630     if (!BN_copy(point->X, x))
631         goto err;
632     if (!BN_copy(point->Y, y))
633         goto err;
634     if (!BN_one(point->Z))
635         goto err;
636     point->Z_is_one = 1;
637
638     ret = 1;
639
640  err:
641     BN_CTX_end(ctx);
642     BN_CTX_free(new_ctx);
643     return ret;
644 }
645
646 /*
647  * Forces each of the EC_POINTs in the given array to use affine coordinates.
648  */
649 int ec_GF2m_simple_points_make_affine(const EC_GROUP *group, size_t num,
650                                       EC_POINT *points[], BN_CTX *ctx)
651 {
652     size_t i;
653
654     for (i = 0; i < num; i++) {
655         if (!group->meth->make_affine(group, points[i], ctx))
656             return 0;
657     }
658
659     return 1;
660 }
661
662 /* Wrapper to simple binary polynomial field multiplication implementation. */
663 int ec_GF2m_simple_field_mul(const EC_GROUP *group, BIGNUM *r,
664                              const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
665 {
666     return BN_GF2m_mod_mul_arr(r, a, b, group->poly, ctx);
667 }
668
669 /* Wrapper to simple binary polynomial field squaring implementation. */
670 int ec_GF2m_simple_field_sqr(const EC_GROUP *group, BIGNUM *r,
671                              const BIGNUM *a, BN_CTX *ctx)
672 {
673     return BN_GF2m_mod_sqr_arr(r, a, group->poly, ctx);
674 }
675
676 /* Wrapper to simple binary polynomial field division implementation. */
677 int ec_GF2m_simple_field_div(const EC_GROUP *group, BIGNUM *r,
678                              const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
679 {
680     return BN_GF2m_mod_div(r, a, b, group->field, ctx);
681 }
682
683 /*-
684  * Lopez-Dahab ladder, pre step.
685  * See e.g. "Guide to ECC" Alg 3.40.
686  * Modified to blind s and r independently.
687  * s:= p, r := 2p
688  */
689 static
690 int ec_GF2m_simple_ladder_pre(const EC_GROUP *group,
691                               EC_POINT *r, EC_POINT *s,
692                               EC_POINT *p, BN_CTX *ctx)
693 {
694     /* if p is not affine, something is wrong */
695     if (p->Z_is_one == 0)
696         return 0;
697
698     /* s blinding: make sure lambda (s->Z here) is not zero */
699     do {
700         if (!BN_priv_rand(s->Z, BN_num_bits(group->field) - 1,
701                           BN_RAND_TOP_ANY, BN_RAND_BOTTOM_ANY)) {
702             ECerr(EC_F_EC_GF2M_SIMPLE_LADDER_PRE, ERR_R_BN_LIB);
703             return 0;
704         }
705     } while (BN_is_zero(s->Z));
706
707     /* if field_encode defined convert between representations */
708     if ((group->meth->field_encode != NULL
709          && !group->meth->field_encode(group, s->Z, s->Z, ctx))
710         || !group->meth->field_mul(group, s->X, p->X, s->Z, ctx))
711         return 0;
712
713     /* r blinding: make sure lambda (r->Y here for storage) is not zero */
714     do {
715         if (!BN_priv_rand(r->Y, BN_num_bits(group->field) - 1,
716                           BN_RAND_TOP_ANY, BN_RAND_BOTTOM_ANY)) {
717             ECerr(EC_F_EC_GF2M_SIMPLE_LADDER_PRE, ERR_R_BN_LIB);
718             return 0;
719         }
720     } while (BN_is_zero(r->Y));
721
722     if ((group->meth->field_encode != NULL
723          && !group->meth->field_encode(group, r->Y, r->Y, ctx))
724         || !group->meth->field_sqr(group, r->Z, p->X, ctx)
725         || !group->meth->field_sqr(group, r->X, r->Z, ctx)
726         || !BN_GF2m_add(r->X, r->X, group->b)
727         || !group->meth->field_mul(group, r->Z, r->Z, r->Y, ctx)
728         || !group->meth->field_mul(group, r->X, r->X, r->Y, ctx))
729         return 0;
730
731     s->Z_is_one = 0;
732     r->Z_is_one = 0;
733
734     return 1;
735 }
736
737 /*-
738  * Ladder step: differential addition-and-doubling, mixed Lopez-Dahab coords.
739  * http://www.hyperelliptic.org/EFD/g12o/auto-code/shortw/xz/ladder/mladd-2003-s.op3
740  * s := r + s, r := 2r
741  */
742 static
743 int ec_GF2m_simple_ladder_step(const EC_GROUP *group,
744                                EC_POINT *r, EC_POINT *s,
745                                EC_POINT *p, BN_CTX *ctx)
746 {
747     if (!group->meth->field_mul(group, r->Y, r->Z, s->X, ctx)
748         || !group->meth->field_mul(group, s->X, r->X, s->Z, ctx)
749         || !group->meth->field_sqr(group, s->Y, r->Z, ctx)
750         || !group->meth->field_sqr(group, r->Z, r->X, ctx)
751         || !BN_GF2m_add(s->Z, r->Y, s->X)
752         || !group->meth->field_sqr(group, s->Z, s->Z, ctx)
753         || !group->meth->field_mul(group, s->X, r->Y, s->X, ctx)
754         || !group->meth->field_mul(group, r->Y, s->Z, p->X, ctx)
755         || !BN_GF2m_add(s->X, s->X, r->Y)
756         || !group->meth->field_sqr(group, r->Y, r->Z, ctx)
757         || !group->meth->field_mul(group, r->Z, r->Z, s->Y, ctx)
758         || !group->meth->field_sqr(group, s->Y, s->Y, ctx)
759         || !group->meth->field_mul(group, s->Y, s->Y, group->b, ctx)
760         || !BN_GF2m_add(r->X, r->Y, s->Y))
761         return 0;
762
763     return 1;
764 }
765
766 /*-
767  * Recover affine (x,y) result from Lopez-Dahab r and s, affine p.
768  * See e.g. "Fast Multiplication on Elliptic Curves over GF(2**m)
769  * without Precomputation" (Lopez and Dahab, CHES 1999),
770  * Appendix Alg Mxy.
771  */
772 static
773 int ec_GF2m_simple_ladder_post(const EC_GROUP *group,
774                                EC_POINT *r, EC_POINT *s,
775                                EC_POINT *p, BN_CTX *ctx)
776 {
777     int ret = 0;
778     BIGNUM *t0, *t1, *t2 = NULL;
779
780     if (BN_is_zero(r->Z))
781         return EC_POINT_set_to_infinity(group, r);
782
783     if (BN_is_zero(s->Z)) {
784         if (!EC_POINT_copy(r, p)
785             || !EC_POINT_invert(group, r, ctx)) {
786             ECerr(EC_F_EC_GF2M_SIMPLE_LADDER_POST, ERR_R_EC_LIB);
787             return 0;
788         }
789         return 1;
790     }
791
792     BN_CTX_start(ctx);
793     t0 = BN_CTX_get(ctx);
794     t1 = BN_CTX_get(ctx);
795     t2 = BN_CTX_get(ctx);
796     if (t2 == NULL) {
797         ECerr(EC_F_EC_GF2M_SIMPLE_LADDER_POST, ERR_R_MALLOC_FAILURE);
798         goto err;
799     }
800
801     if (!group->meth->field_mul(group, t0, r->Z, s->Z, ctx)
802         || !group->meth->field_mul(group, t1, p->X, r->Z, ctx)
803         || !BN_GF2m_add(t1, r->X, t1)
804         || !group->meth->field_mul(group, t2, p->X, s->Z, ctx)
805         || !group->meth->field_mul(group, r->Z, r->X, t2, ctx)
806         || !BN_GF2m_add(t2, t2, s->X)
807         || !group->meth->field_mul(group, t1, t1, t2, ctx)
808         || !group->meth->field_sqr(group, t2, p->X, ctx)
809         || !BN_GF2m_add(t2, p->Y, t2)
810         || !group->meth->field_mul(group, t2, t2, t0, ctx)
811         || !BN_GF2m_add(t1, t2, t1)
812         || !group->meth->field_mul(group, t2, p->X, t0, ctx)
813         || !BN_GF2m_mod_inv(t2, t2, group->field, ctx)
814         || !group->meth->field_mul(group, t1, t1, t2, ctx)
815         || !group->meth->field_mul(group, r->X, r->Z, t2, ctx)
816         || !BN_GF2m_add(t2, p->X, r->X)
817         || !group->meth->field_mul(group, t2, t2, t1, ctx)
818         || !BN_GF2m_add(r->Y, p->Y, t2)
819         || !BN_one(r->Z))
820         goto err;
821
822     r->Z_is_one = 1;
823
824     /* GF(2^m) field elements should always have BIGNUM::neg = 0 */
825     BN_set_negative(r->X, 0);
826     BN_set_negative(r->Y, 0);
827
828     ret = 1;
829
830  err:
831     BN_CTX_end(ctx);
832     return ret;
833 }
834
835 static
836 int ec_GF2m_simple_points_mul(const EC_GROUP *group, EC_POINT *r,
837                               const BIGNUM *scalar, size_t num,
838                               const EC_POINT *points[],
839                               const BIGNUM *scalars[],
840                               BN_CTX *ctx)
841 {
842     int ret = 0;
843     EC_POINT *t = NULL;
844
845     /*-
846      * We limit use of the ladder only to the following cases:
847      * - r := scalar * G
848      *   Fixed point mul: scalar != NULL && num == 0;
849      * - r := scalars[0] * points[0]
850      *   Variable point mul: scalar == NULL && num == 1;
851      * - r := scalar * G + scalars[0] * points[0]
852      *   used, e.g., in ECDSA verification: scalar != NULL && num == 1
853      *
854      * In any other case (num > 1) we use the default wNAF implementation.
855      *
856      * We also let the default implementation handle degenerate cases like group
857      * order or cofactor set to 0.
858      */
859     if (num > 1 || BN_is_zero(group->order) || BN_is_zero(group->cofactor))
860         return ec_wNAF_mul(group, r, scalar, num, points, scalars, ctx);
861
862     if (scalar != NULL && num == 0)
863         /* Fixed point multiplication */
864         return ec_scalar_mul_ladder(group, r, scalar, NULL, ctx);
865
866     if (scalar == NULL && num == 1)
867         /* Variable point multiplication */
868         return ec_scalar_mul_ladder(group, r, scalars[0], points[0], ctx);
869
870     /*-
871      * Double point multiplication:
872      *  r := scalar * G + scalars[0] * points[0]
873      */
874
875     if ((t = EC_POINT_new(group)) == NULL) {
876         ECerr(EC_F_EC_GF2M_SIMPLE_POINTS_MUL, ERR_R_MALLOC_FAILURE);
877         return 0;
878     }
879
880     if (!ec_scalar_mul_ladder(group, t, scalar, NULL, ctx)
881         || !ec_scalar_mul_ladder(group, r, scalars[0], points[0], ctx)
882         || !EC_POINT_add(group, r, t, r, ctx))
883         goto err;
884
885     ret = 1;
886
887  err:
888     EC_POINT_free(t);
889     return ret;
890 }
891
892 const EC_METHOD *EC_GF2m_simple_method(void)
893 {
894     static const EC_METHOD ret = {
895         EC_FLAGS_DEFAULT_OCT,
896         NID_X9_62_characteristic_two_field,
897         ec_GF2m_simple_group_init,
898         ec_GF2m_simple_group_finish,
899         ec_GF2m_simple_group_clear_finish,
900         ec_GF2m_simple_group_copy,
901         ec_GF2m_simple_group_set_curve,
902         ec_GF2m_simple_group_get_curve,
903         ec_GF2m_simple_group_get_degree,
904         ec_group_simple_order_bits,
905         ec_GF2m_simple_group_check_discriminant,
906         ec_GF2m_simple_point_init,
907         ec_GF2m_simple_point_finish,
908         ec_GF2m_simple_point_clear_finish,
909         ec_GF2m_simple_point_copy,
910         ec_GF2m_simple_point_set_to_infinity,
911         0, /* set_Jprojective_coordinates_GFp */
912         0, /* get_Jprojective_coordinates_GFp */
913         ec_GF2m_simple_point_set_affine_coordinates,
914         ec_GF2m_simple_point_get_affine_coordinates,
915         0, /* point_set_compressed_coordinates */
916         0, /* point2oct */
917         0, /* oct2point */
918         ec_GF2m_simple_add,
919         ec_GF2m_simple_dbl,
920         ec_GF2m_simple_invert,
921         ec_GF2m_simple_is_at_infinity,
922         ec_GF2m_simple_is_on_curve,
923         ec_GF2m_simple_cmp,
924         ec_GF2m_simple_make_affine,
925         ec_GF2m_simple_points_make_affine,
926         ec_GF2m_simple_points_mul,
927         0, /* precompute_mult */
928         0, /* have_precompute_mult */
929         ec_GF2m_simple_field_mul,
930         ec_GF2m_simple_field_sqr,
931         ec_GF2m_simple_field_div,
932         0, /* field_encode */
933         0, /* field_decode */
934         0, /* field_set_to_one */
935         ec_key_simple_priv2oct,
936         ec_key_simple_oct2priv,
937         0, /* set private */
938         ec_key_simple_generate_key,
939         ec_key_simple_check_key,
940         ec_key_simple_generate_public_key,
941         0, /* keycopy */
942         0, /* keyfinish */
943         ecdh_simple_compute_key,
944         0, /* field_inverse_mod_ord */
945         0, /* blind_coordinates */
946         ec_GF2m_simple_ladder_pre,
947         ec_GF2m_simple_ladder_step,
948         ec_GF2m_simple_ladder_post
949     };
950
951     return &ret;
952 }
953
954 #endif