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