ebd6f21eeca12a4d2227b334b61d76e9085bde6a
[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 Apache License 2.0 (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     BN_CTX_end(ctx);
208     BN_CTX_free(new_ctx);
209     return ret;
210 }
211
212 /* Initializes an EC_POINT. */
213 int ec_GF2m_simple_point_init(EC_POINT *point)
214 {
215     point->X = BN_new();
216     point->Y = BN_new();
217     point->Z = BN_new();
218
219     if (point->X == NULL || point->Y == NULL || point->Z == NULL) {
220         BN_free(point->X);
221         BN_free(point->Y);
222         BN_free(point->Z);
223         return 0;
224     }
225     return 1;
226 }
227
228 /* Frees an EC_POINT. */
229 void ec_GF2m_simple_point_finish(EC_POINT *point)
230 {
231     BN_free(point->X);
232     BN_free(point->Y);
233     BN_free(point->Z);
234 }
235
236 /* Clears and frees an EC_POINT. */
237 void ec_GF2m_simple_point_clear_finish(EC_POINT *point)
238 {
239     BN_clear_free(point->X);
240     BN_clear_free(point->Y);
241     BN_clear_free(point->Z);
242     point->Z_is_one = 0;
243 }
244
245 /*
246  * Copy the contents of one EC_POINT into another.  Assumes dest is
247  * initialized.
248  */
249 int ec_GF2m_simple_point_copy(EC_POINT *dest, const EC_POINT *src)
250 {
251     if (!BN_copy(dest->X, src->X))
252         return 0;
253     if (!BN_copy(dest->Y, src->Y))
254         return 0;
255     if (!BN_copy(dest->Z, src->Z))
256         return 0;
257     dest->Z_is_one = src->Z_is_one;
258     dest->curve_name = src->curve_name;
259
260     return 1;
261 }
262
263 /*
264  * Set an EC_POINT to the point at infinity. A point at infinity is
265  * represented by having Z=0.
266  */
267 int ec_GF2m_simple_point_set_to_infinity(const EC_GROUP *group,
268                                          EC_POINT *point)
269 {
270     point->Z_is_one = 0;
271     BN_zero(point->Z);
272     return 1;
273 }
274
275 /*
276  * Set the coordinates of an EC_POINT using affine coordinates. Note that
277  * the simple implementation only uses affine coordinates.
278  */
279 int ec_GF2m_simple_point_set_affine_coordinates(const EC_GROUP *group,
280                                                 EC_POINT *point,
281                                                 const BIGNUM *x,
282                                                 const BIGNUM *y, BN_CTX *ctx)
283 {
284     int ret = 0;
285     if (x == NULL || y == NULL) {
286         ECerr(EC_F_EC_GF2M_SIMPLE_POINT_SET_AFFINE_COORDINATES,
287               ERR_R_PASSED_NULL_PARAMETER);
288         return 0;
289     }
290
291     if (!BN_copy(point->X, x))
292         goto err;
293     BN_set_negative(point->X, 0);
294     if (!BN_copy(point->Y, y))
295         goto err;
296     BN_set_negative(point->Y, 0);
297     if (!BN_copy(point->Z, BN_value_one()))
298         goto err;
299     BN_set_negative(point->Z, 0);
300     point->Z_is_one = 1;
301     ret = 1;
302
303  err:
304     return ret;
305 }
306
307 /*
308  * Gets the affine coordinates of an EC_POINT. Note that the simple
309  * implementation only uses affine coordinates.
310  */
311 int ec_GF2m_simple_point_get_affine_coordinates(const EC_GROUP *group,
312                                                 const EC_POINT *point,
313                                                 BIGNUM *x, BIGNUM *y,
314                                                 BN_CTX *ctx)
315 {
316     int ret = 0;
317
318     if (EC_POINT_is_at_infinity(group, point)) {
319         ECerr(EC_F_EC_GF2M_SIMPLE_POINT_GET_AFFINE_COORDINATES,
320               EC_R_POINT_AT_INFINITY);
321         return 0;
322     }
323
324     if (BN_cmp(point->Z, BN_value_one())) {
325         ECerr(EC_F_EC_GF2M_SIMPLE_POINT_GET_AFFINE_COORDINATES,
326               ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
327         return 0;
328     }
329     if (x != NULL) {
330         if (!BN_copy(x, point->X))
331             goto err;
332         BN_set_negative(x, 0);
333     }
334     if (y != NULL) {
335         if (!BN_copy(y, point->Y))
336             goto err;
337         BN_set_negative(y, 0);
338     }
339     ret = 1;
340
341  err:
342     return ret;
343 }
344
345 /*
346  * Computes a + b and stores the result in r.  r could be a or b, a could be
347  * b. Uses algorithm A.10.2 of IEEE P1363.
348  */
349 int ec_GF2m_simple_add(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a,
350                        const EC_POINT *b, BN_CTX *ctx)
351 {
352     BN_CTX *new_ctx = NULL;
353     BIGNUM *x0, *y0, *x1, *y1, *x2, *y2, *s, *t;
354     int ret = 0;
355
356     if (EC_POINT_is_at_infinity(group, a)) {
357         if (!EC_POINT_copy(r, b))
358             return 0;
359         return 1;
360     }
361
362     if (EC_POINT_is_at_infinity(group, b)) {
363         if (!EC_POINT_copy(r, a))
364             return 0;
365         return 1;
366     }
367
368     if (ctx == NULL) {
369         ctx = new_ctx = BN_CTX_new();
370         if (ctx == NULL)
371             return 0;
372     }
373
374     BN_CTX_start(ctx);
375     x0 = BN_CTX_get(ctx);
376     y0 = BN_CTX_get(ctx);
377     x1 = BN_CTX_get(ctx);
378     y1 = BN_CTX_get(ctx);
379     x2 = BN_CTX_get(ctx);
380     y2 = BN_CTX_get(ctx);
381     s = BN_CTX_get(ctx);
382     t = BN_CTX_get(ctx);
383     if (t == NULL)
384         goto err;
385
386     if (a->Z_is_one) {
387         if (!BN_copy(x0, a->X))
388             goto err;
389         if (!BN_copy(y0, a->Y))
390             goto err;
391     } else {
392         if (!EC_POINT_get_affine_coordinates(group, a, x0, y0, ctx))
393             goto err;
394     }
395     if (b->Z_is_one) {
396         if (!BN_copy(x1, b->X))
397             goto err;
398         if (!BN_copy(y1, b->Y))
399             goto err;
400     } else {
401         if (!EC_POINT_get_affine_coordinates(group, b, x1, y1, ctx))
402             goto err;
403     }
404
405     if (BN_GF2m_cmp(x0, x1)) {
406         if (!BN_GF2m_add(t, x0, x1))
407             goto err;
408         if (!BN_GF2m_add(s, y0, y1))
409             goto err;
410         if (!group->meth->field_div(group, s, s, t, ctx))
411             goto err;
412         if (!group->meth->field_sqr(group, x2, s, ctx))
413             goto err;
414         if (!BN_GF2m_add(x2, x2, group->a))
415             goto err;
416         if (!BN_GF2m_add(x2, x2, s))
417             goto err;
418         if (!BN_GF2m_add(x2, x2, t))
419             goto err;
420     } else {
421         if (BN_GF2m_cmp(y0, y1) || BN_is_zero(x1)) {
422             if (!EC_POINT_set_to_infinity(group, r))
423                 goto err;
424             ret = 1;
425             goto err;
426         }
427         if (!group->meth->field_div(group, s, y1, x1, ctx))
428             goto err;
429         if (!BN_GF2m_add(s, s, x1))
430             goto err;
431
432         if (!group->meth->field_sqr(group, x2, s, ctx))
433             goto err;
434         if (!BN_GF2m_add(x2, x2, s))
435             goto err;
436         if (!BN_GF2m_add(x2, x2, group->a))
437             goto err;
438     }
439
440     if (!BN_GF2m_add(y2, x1, x2))
441         goto err;
442     if (!group->meth->field_mul(group, y2, y2, s, ctx))
443         goto err;
444     if (!BN_GF2m_add(y2, y2, x2))
445         goto err;
446     if (!BN_GF2m_add(y2, y2, y1))
447         goto err;
448
449     if (!EC_POINT_set_affine_coordinates(group, r, x2, y2, ctx))
450         goto err;
451
452     ret = 1;
453
454  err:
455     BN_CTX_end(ctx);
456     BN_CTX_free(new_ctx);
457     return ret;
458 }
459
460 /*
461  * Computes 2 * a and stores the result in r.  r could be a. Uses algorithm
462  * A.10.2 of IEEE P1363.
463  */
464 int ec_GF2m_simple_dbl(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a,
465                        BN_CTX *ctx)
466 {
467     return ec_GF2m_simple_add(group, r, a, a, ctx);
468 }
469
470 int ec_GF2m_simple_invert(const EC_GROUP *group, EC_POINT *point, BN_CTX *ctx)
471 {
472     if (EC_POINT_is_at_infinity(group, point) || BN_is_zero(point->Y))
473         /* point is its own inverse */
474         return 1;
475
476     if (!EC_POINT_make_affine(group, point, ctx))
477         return 0;
478     return BN_GF2m_add(point->Y, point->X, point->Y);
479 }
480
481 /* Indicates whether the given point is the point at infinity. */
482 int ec_GF2m_simple_is_at_infinity(const EC_GROUP *group,
483                                   const EC_POINT *point)
484 {
485     return BN_is_zero(point->Z);
486 }
487
488 /*-
489  * Determines whether the given EC_POINT is an actual point on the curve defined
490  * in the EC_GROUP.  A point is valid if it satisfies the Weierstrass equation:
491  *      y^2 + x*y = x^3 + a*x^2 + b.
492  */
493 int ec_GF2m_simple_is_on_curve(const EC_GROUP *group, const EC_POINT *point,
494                                BN_CTX *ctx)
495 {
496     int ret = -1;
497     BN_CTX *new_ctx = NULL;
498     BIGNUM *lh, *y2;
499     int (*field_mul) (const EC_GROUP *, BIGNUM *, const BIGNUM *,
500                       const BIGNUM *, BN_CTX *);
501     int (*field_sqr) (const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
502
503     if (EC_POINT_is_at_infinity(group, point))
504         return 1;
505
506     field_mul = group->meth->field_mul;
507     field_sqr = group->meth->field_sqr;
508
509     /* only support affine coordinates */
510     if (!point->Z_is_one)
511         return -1;
512
513     if (ctx == NULL) {
514         ctx = new_ctx = BN_CTX_new();
515         if (ctx == NULL)
516             return -1;
517     }
518
519     BN_CTX_start(ctx);
520     y2 = BN_CTX_get(ctx);
521     lh = BN_CTX_get(ctx);
522     if (lh == NULL)
523         goto err;
524
525     /*-
526      * We have a curve defined by a Weierstrass equation
527      *      y^2 + x*y = x^3 + a*x^2 + b.
528      *  <=> x^3 + a*x^2 + x*y + b + y^2 = 0
529      *  <=> ((x + a) * x + y ) * x + b + y^2 = 0
530      */
531     if (!BN_GF2m_add(lh, point->X, group->a))
532         goto err;
533     if (!field_mul(group, lh, lh, point->X, ctx))
534         goto err;
535     if (!BN_GF2m_add(lh, lh, point->Y))
536         goto err;
537     if (!field_mul(group, lh, lh, point->X, ctx))
538         goto err;
539     if (!BN_GF2m_add(lh, lh, group->b))
540         goto err;
541     if (!field_sqr(group, y2, point->Y, ctx))
542         goto err;
543     if (!BN_GF2m_add(lh, lh, y2))
544         goto err;
545     ret = BN_is_zero(lh);
546
547  err:
548     BN_CTX_end(ctx);
549     BN_CTX_free(new_ctx);
550     return ret;
551 }
552
553 /*-
554  * Indicates whether two points are equal.
555  * Return values:
556  *  -1   error
557  *   0   equal (in affine coordinates)
558  *   1   not equal
559  */
560 int ec_GF2m_simple_cmp(const EC_GROUP *group, const EC_POINT *a,
561                        const EC_POINT *b, BN_CTX *ctx)
562 {
563     BIGNUM *aX, *aY, *bX, *bY;
564     BN_CTX *new_ctx = NULL;
565     int ret = -1;
566
567     if (EC_POINT_is_at_infinity(group, a)) {
568         return EC_POINT_is_at_infinity(group, b) ? 0 : 1;
569     }
570
571     if (EC_POINT_is_at_infinity(group, b))
572         return 1;
573
574     if (a->Z_is_one && b->Z_is_one) {
575         return ((BN_cmp(a->X, b->X) == 0) && BN_cmp(a->Y, b->Y) == 0) ? 0 : 1;
576     }
577
578     if (ctx == NULL) {
579         ctx = new_ctx = BN_CTX_new();
580         if (ctx == NULL)
581             return -1;
582     }
583
584     BN_CTX_start(ctx);
585     aX = BN_CTX_get(ctx);
586     aY = BN_CTX_get(ctx);
587     bX = BN_CTX_get(ctx);
588     bY = BN_CTX_get(ctx);
589     if (bY == NULL)
590         goto err;
591
592     if (!EC_POINT_get_affine_coordinates(group, a, aX, aY, ctx))
593         goto err;
594     if (!EC_POINT_get_affine_coordinates(group, b, bX, bY, ctx))
595         goto err;
596     ret = ((BN_cmp(aX, bX) == 0) && BN_cmp(aY, bY) == 0) ? 0 : 1;
597
598  err:
599     BN_CTX_end(ctx);
600     BN_CTX_free(new_ctx);
601     return ret;
602 }
603
604 /* Forces the given EC_POINT to internally use affine coordinates. */
605 int ec_GF2m_simple_make_affine(const EC_GROUP *group, EC_POINT *point,
606                                BN_CTX *ctx)
607 {
608     BN_CTX *new_ctx = NULL;
609     BIGNUM *x, *y;
610     int ret = 0;
611
612     if (point->Z_is_one || EC_POINT_is_at_infinity(group, point))
613         return 1;
614
615     if (ctx == NULL) {
616         ctx = new_ctx = BN_CTX_new();
617         if (ctx == NULL)
618             return 0;
619     }
620
621     BN_CTX_start(ctx);
622     x = BN_CTX_get(ctx);
623     y = BN_CTX_get(ctx);
624     if (y == NULL)
625         goto err;
626
627     if (!EC_POINT_get_affine_coordinates(group, point, x, y, ctx))
628         goto err;
629     if (!BN_copy(point->X, x))
630         goto err;
631     if (!BN_copy(point->Y, y))
632         goto err;
633     if (!BN_one(point->Z))
634         goto err;
635     point->Z_is_one = 1;
636
637     ret = 1;
638
639  err:
640     BN_CTX_end(ctx);
641     BN_CTX_free(new_ctx);
642     return ret;
643 }
644
645 /*
646  * Forces each of the EC_POINTs in the given array to use affine coordinates.
647  */
648 int ec_GF2m_simple_points_make_affine(const EC_GROUP *group, size_t num,
649                                       EC_POINT *points[], BN_CTX *ctx)
650 {
651     size_t i;
652
653     for (i = 0; i < num; i++) {
654         if (!group->meth->make_affine(group, points[i], ctx))
655             return 0;
656     }
657
658     return 1;
659 }
660
661 /* Wrapper to simple binary polynomial field multiplication implementation. */
662 int ec_GF2m_simple_field_mul(const EC_GROUP *group, BIGNUM *r,
663                              const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
664 {
665     return BN_GF2m_mod_mul_arr(r, a, b, group->poly, ctx);
666 }
667
668 /* Wrapper to simple binary polynomial field squaring implementation. */
669 int ec_GF2m_simple_field_sqr(const EC_GROUP *group, BIGNUM *r,
670                              const BIGNUM *a, BN_CTX *ctx)
671 {
672     return BN_GF2m_mod_sqr_arr(r, a, group->poly, ctx);
673 }
674
675 /* Wrapper to simple binary polynomial field division implementation. */
676 int ec_GF2m_simple_field_div(const EC_GROUP *group, BIGNUM *r,
677                              const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
678 {
679     return BN_GF2m_mod_div(r, a, b, group->field, ctx);
680 }
681
682 /*-
683  * Lopez-Dahab ladder, pre step.
684  * See e.g. "Guide to ECC" Alg 3.40.
685  * Modified to blind s and r independently.
686  * s:= p, r := 2p
687  */
688 static
689 int ec_GF2m_simple_ladder_pre(const EC_GROUP *group,
690                               EC_POINT *r, EC_POINT *s,
691                               EC_POINT *p, BN_CTX *ctx)
692 {
693     /* if p is not affine, something is wrong */
694     if (p->Z_is_one == 0)
695         return 0;
696
697     /* s blinding: make sure lambda (s->Z here) is not zero */
698     do {
699         if (!BN_priv_rand(s->Z, BN_num_bits(group->field) - 1,
700                           BN_RAND_TOP_ANY, BN_RAND_BOTTOM_ANY)) {
701             ECerr(EC_F_EC_GF2M_SIMPLE_LADDER_PRE, ERR_R_BN_LIB);
702             return 0;
703         }
704     } while (BN_is_zero(s->Z));
705
706     /* if field_encode defined convert between representations */
707     if ((group->meth->field_encode != NULL
708          && !group->meth->field_encode(group, s->Z, s->Z, ctx))
709         || !group->meth->field_mul(group, s->X, p->X, s->Z, ctx))
710         return 0;
711
712     /* r blinding: make sure lambda (r->Y here for storage) is not zero */
713     do {
714         if (!BN_priv_rand(r->Y, BN_num_bits(group->field) - 1,
715                           BN_RAND_TOP_ANY, BN_RAND_BOTTOM_ANY)) {
716             ECerr(EC_F_EC_GF2M_SIMPLE_LADDER_PRE, ERR_R_BN_LIB);
717             return 0;
718         }
719     } while (BN_is_zero(r->Y));
720
721     if ((group->meth->field_encode != NULL
722          && !group->meth->field_encode(group, r->Y, r->Y, ctx))
723         || !group->meth->field_sqr(group, r->Z, p->X, ctx)
724         || !group->meth->field_sqr(group, r->X, r->Z, ctx)
725         || !BN_GF2m_add(r->X, r->X, group->b)
726         || !group->meth->field_mul(group, r->Z, r->Z, r->Y, ctx)
727         || !group->meth->field_mul(group, r->X, r->X, r->Y, ctx))
728         return 0;
729
730     s->Z_is_one = 0;
731     r->Z_is_one = 0;
732
733     return 1;
734 }
735
736 /*-
737  * Ladder step: differential addition-and-doubling, mixed Lopez-Dahab coords.
738  * http://www.hyperelliptic.org/EFD/g12o/auto-code/shortw/xz/ladder/mladd-2003-s.op3
739  * s := r + s, r := 2r
740  */
741 static
742 int ec_GF2m_simple_ladder_step(const EC_GROUP *group,
743                                EC_POINT *r, EC_POINT *s,
744                                EC_POINT *p, BN_CTX *ctx)
745 {
746     if (!group->meth->field_mul(group, r->Y, r->Z, s->X, ctx)
747         || !group->meth->field_mul(group, s->X, r->X, s->Z, ctx)
748         || !group->meth->field_sqr(group, s->Y, r->Z, ctx)
749         || !group->meth->field_sqr(group, r->Z, r->X, ctx)
750         || !BN_GF2m_add(s->Z, r->Y, s->X)
751         || !group->meth->field_sqr(group, s->Z, s->Z, ctx)
752         || !group->meth->field_mul(group, s->X, r->Y, s->X, ctx)
753         || !group->meth->field_mul(group, r->Y, s->Z, p->X, ctx)
754         || !BN_GF2m_add(s->X, s->X, r->Y)
755         || !group->meth->field_sqr(group, r->Y, r->Z, ctx)
756         || !group->meth->field_mul(group, r->Z, r->Z, s->Y, ctx)
757         || !group->meth->field_sqr(group, s->Y, s->Y, ctx)
758         || !group->meth->field_mul(group, s->Y, s->Y, group->b, ctx)
759         || !BN_GF2m_add(r->X, r->Y, s->Y))
760         return 0;
761
762     return 1;
763 }
764
765 /*-
766  * Recover affine (x,y) result from Lopez-Dahab r and s, affine p.
767  * See e.g. "Fast Multiplication on Elliptic Curves over GF(2**m)
768  * without Precomputation" (Lopez and Dahab, CHES 1999),
769  * Appendix Alg Mxy.
770  */
771 static
772 int ec_GF2m_simple_ladder_post(const EC_GROUP *group,
773                                EC_POINT *r, EC_POINT *s,
774                                EC_POINT *p, BN_CTX *ctx)
775 {
776     int ret = 0;
777     BIGNUM *t0, *t1, *t2 = NULL;
778
779     if (BN_is_zero(r->Z))
780         return EC_POINT_set_to_infinity(group, r);
781
782     if (BN_is_zero(s->Z)) {
783         if (!EC_POINT_copy(r, p)
784             || !EC_POINT_invert(group, r, ctx)) {
785             ECerr(EC_F_EC_GF2M_SIMPLE_LADDER_POST, ERR_R_EC_LIB);
786             return 0;
787         }
788         return 1;
789     }
790
791     BN_CTX_start(ctx);
792     t0 = BN_CTX_get(ctx);
793     t1 = BN_CTX_get(ctx);
794     t2 = BN_CTX_get(ctx);
795     if (t2 == NULL) {
796         ECerr(EC_F_EC_GF2M_SIMPLE_LADDER_POST, ERR_R_MALLOC_FAILURE);
797         goto err;
798     }
799
800     if (!group->meth->field_mul(group, t0, r->Z, s->Z, ctx)
801         || !group->meth->field_mul(group, t1, p->X, r->Z, ctx)
802         || !BN_GF2m_add(t1, r->X, t1)
803         || !group->meth->field_mul(group, t2, p->X, s->Z, ctx)
804         || !group->meth->field_mul(group, r->Z, r->X, t2, ctx)
805         || !BN_GF2m_add(t2, t2, s->X)
806         || !group->meth->field_mul(group, t1, t1, t2, ctx)
807         || !group->meth->field_sqr(group, t2, p->X, ctx)
808         || !BN_GF2m_add(t2, p->Y, t2)
809         || !group->meth->field_mul(group, t2, t2, t0, ctx)
810         || !BN_GF2m_add(t1, t2, t1)
811         || !group->meth->field_mul(group, t2, p->X, t0, ctx)
812         || !group->meth->field_inv(group, t2, t2, ctx)
813         || !group->meth->field_mul(group, t1, t1, t2, ctx)
814         || !group->meth->field_mul(group, r->X, r->Z, t2, ctx)
815         || !BN_GF2m_add(t2, p->X, r->X)
816         || !group->meth->field_mul(group, t2, t2, t1, ctx)
817         || !BN_GF2m_add(r->Y, p->Y, t2)
818         || !BN_one(r->Z))
819         goto err;
820
821     r->Z_is_one = 1;
822
823     /* GF(2^m) field elements should always have BIGNUM::neg = 0 */
824     BN_set_negative(r->X, 0);
825     BN_set_negative(r->Y, 0);
826
827     ret = 1;
828
829  err:
830     BN_CTX_end(ctx);
831     return ret;
832 }
833
834 static
835 int ec_GF2m_simple_points_mul(const EC_GROUP *group, EC_POINT *r,
836                               const BIGNUM *scalar, size_t num,
837                               const EC_POINT *points[],
838                               const BIGNUM *scalars[],
839                               BN_CTX *ctx)
840 {
841     int ret = 0;
842     EC_POINT *t = NULL;
843
844     /*-
845      * We limit use of the ladder only to the following cases:
846      * - r := scalar * G
847      *   Fixed point mul: scalar != NULL && num == 0;
848      * - r := scalars[0] * points[0]
849      *   Variable point mul: scalar == NULL && num == 1;
850      * - r := scalar * G + scalars[0] * points[0]
851      *   used, e.g., in ECDSA verification: scalar != NULL && num == 1
852      *
853      * In any other case (num > 1) we use the default wNAF implementation.
854      *
855      * We also let the default implementation handle degenerate cases like group
856      * order or cofactor set to 0.
857      */
858     if (num > 1 || BN_is_zero(group->order) || BN_is_zero(group->cofactor))
859         return ec_wNAF_mul(group, r, scalar, num, points, scalars, ctx);
860
861     if (scalar != NULL && num == 0)
862         /* Fixed point multiplication */
863         return ec_scalar_mul_ladder(group, r, scalar, NULL, ctx);
864
865     if (scalar == NULL && num == 1)
866         /* Variable point multiplication */
867         return ec_scalar_mul_ladder(group, r, scalars[0], points[0], ctx);
868
869     /*-
870      * Double point multiplication:
871      *  r := scalar * G + scalars[0] * points[0]
872      */
873
874     if ((t = EC_POINT_new(group)) == NULL) {
875         ECerr(EC_F_EC_GF2M_SIMPLE_POINTS_MUL, ERR_R_MALLOC_FAILURE);
876         return 0;
877     }
878
879     if (!ec_scalar_mul_ladder(group, t, scalar, NULL, ctx)
880         || !ec_scalar_mul_ladder(group, r, scalars[0], points[0], ctx)
881         || !EC_POINT_add(group, r, t, r, ctx))
882         goto err;
883
884     ret = 1;
885
886  err:
887     EC_POINT_free(t);
888     return ret;
889 }
890
891 /*-
892  * Computes the multiplicative inverse of a in GF(2^m), storing the result in r.
893  * If a is zero (or equivalent), you'll get a EC_R_CANNOT_INVERT error.
894  * SCA hardening is with blinding: BN_GF2m_mod_inv does that.
895  */
896 static int ec_GF2m_simple_field_inv(const EC_GROUP *group, BIGNUM *r,
897                                     const BIGNUM *a, BN_CTX *ctx)
898 {
899     int ret;
900
901     if (!(ret = BN_GF2m_mod_inv(r, a, group->field, ctx)))
902         ECerr(EC_F_EC_GF2M_SIMPLE_FIELD_INV, EC_R_CANNOT_INVERT);
903     return ret;
904 }
905
906 const EC_METHOD *EC_GF2m_simple_method(void)
907 {
908     static const EC_METHOD ret = {
909         EC_FLAGS_DEFAULT_OCT,
910         NID_X9_62_characteristic_two_field,
911         ec_GF2m_simple_group_init,
912         ec_GF2m_simple_group_finish,
913         ec_GF2m_simple_group_clear_finish,
914         ec_GF2m_simple_group_copy,
915         ec_GF2m_simple_group_set_curve,
916         ec_GF2m_simple_group_get_curve,
917         ec_GF2m_simple_group_get_degree,
918         ec_group_simple_order_bits,
919         ec_GF2m_simple_group_check_discriminant,
920         ec_GF2m_simple_point_init,
921         ec_GF2m_simple_point_finish,
922         ec_GF2m_simple_point_clear_finish,
923         ec_GF2m_simple_point_copy,
924         ec_GF2m_simple_point_set_to_infinity,
925         0, /* set_Jprojective_coordinates_GFp */
926         0, /* get_Jprojective_coordinates_GFp */
927         ec_GF2m_simple_point_set_affine_coordinates,
928         ec_GF2m_simple_point_get_affine_coordinates,
929         0, /* point_set_compressed_coordinates */
930         0, /* point2oct */
931         0, /* oct2point */
932         ec_GF2m_simple_add,
933         ec_GF2m_simple_dbl,
934         ec_GF2m_simple_invert,
935         ec_GF2m_simple_is_at_infinity,
936         ec_GF2m_simple_is_on_curve,
937         ec_GF2m_simple_cmp,
938         ec_GF2m_simple_make_affine,
939         ec_GF2m_simple_points_make_affine,
940         ec_GF2m_simple_points_mul,
941         0, /* precompute_mult */
942         0, /* have_precompute_mult */
943         ec_GF2m_simple_field_mul,
944         ec_GF2m_simple_field_sqr,
945         ec_GF2m_simple_field_div,
946         ec_GF2m_simple_field_inv,
947         0, /* field_encode */
948         0, /* field_decode */
949         0, /* field_set_to_one */
950         ec_key_simple_priv2oct,
951         ec_key_simple_oct2priv,
952         0, /* set private */
953         ec_key_simple_generate_key,
954         ec_key_simple_check_key,
955         ec_key_simple_generate_public_key,
956         0, /* keycopy */
957         0, /* keyfinish */
958         ecdh_simple_compute_key,
959         0, /* field_inverse_mod_ord */
960         0, /* blind_coordinates */
961         ec_GF2m_simple_ladder_pre,
962         ec_GF2m_simple_ladder_step,
963         ec_GF2m_simple_ladder_post
964     };
965
966     return &ret;
967 }
968
969 #endif