deprecate EC_POINT_make_affine and EC_POINTs_make_affine
[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_MODULE
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_MODULE
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_MODULE
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_MODULE
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_MODULE
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 (group->meth->make_affine == NULL
493         || !group->meth->make_affine(group, point, ctx))
494         return 0;
495     return BN_GF2m_add(point->Y, point->X, point->Y);
496 }
497
498 /* Indicates whether the given point is the point at infinity. */
499 int ec_GF2m_simple_is_at_infinity(const EC_GROUP *group,
500                                   const EC_POINT *point)
501 {
502     return BN_is_zero(point->Z);
503 }
504
505 /*-
506  * Determines whether the given EC_POINT is an actual point on the curve defined
507  * in the EC_GROUP.  A point is valid if it satisfies the Weierstrass equation:
508  *      y^2 + x*y = x^3 + a*x^2 + b.
509  */
510 int ec_GF2m_simple_is_on_curve(const EC_GROUP *group, const EC_POINT *point,
511                                BN_CTX *ctx)
512 {
513     int ret = -1;
514     BIGNUM *lh, *y2;
515     int (*field_mul) (const EC_GROUP *, BIGNUM *, const BIGNUM *,
516                       const BIGNUM *, BN_CTX *);
517     int (*field_sqr) (const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
518 #ifndef FIPS_MODULE
519     BN_CTX *new_ctx = NULL;
520 #endif
521
522     if (EC_POINT_is_at_infinity(group, point))
523         return 1;
524
525     field_mul = group->meth->field_mul;
526     field_sqr = group->meth->field_sqr;
527
528     /* only support affine coordinates */
529     if (!point->Z_is_one)
530         return -1;
531
532 #ifndef FIPS_MODULE
533     if (ctx == NULL) {
534         ctx = new_ctx = BN_CTX_new();
535         if (ctx == NULL)
536             return -1;
537     }
538 #endif
539
540     BN_CTX_start(ctx);
541     y2 = BN_CTX_get(ctx);
542     lh = BN_CTX_get(ctx);
543     if (lh == NULL)
544         goto err;
545
546     /*-
547      * We have a curve defined by a Weierstrass equation
548      *      y^2 + x*y = x^3 + a*x^2 + b.
549      *  <=> x^3 + a*x^2 + x*y + b + y^2 = 0
550      *  <=> ((x + a) * x + y ) * x + b + y^2 = 0
551      */
552     if (!BN_GF2m_add(lh, point->X, group->a))
553         goto err;
554     if (!field_mul(group, lh, lh, point->X, ctx))
555         goto err;
556     if (!BN_GF2m_add(lh, lh, point->Y))
557         goto err;
558     if (!field_mul(group, lh, lh, point->X, ctx))
559         goto err;
560     if (!BN_GF2m_add(lh, lh, group->b))
561         goto err;
562     if (!field_sqr(group, y2, point->Y, ctx))
563         goto err;
564     if (!BN_GF2m_add(lh, lh, y2))
565         goto err;
566     ret = BN_is_zero(lh);
567
568  err:
569     BN_CTX_end(ctx);
570 #ifndef FIPS_MODULE
571     BN_CTX_free(new_ctx);
572 #endif
573     return ret;
574 }
575
576 /*-
577  * Indicates whether two points are equal.
578  * Return values:
579  *  -1   error
580  *   0   equal (in affine coordinates)
581  *   1   not equal
582  */
583 int ec_GF2m_simple_cmp(const EC_GROUP *group, const EC_POINT *a,
584                        const EC_POINT *b, BN_CTX *ctx)
585 {
586     BIGNUM *aX, *aY, *bX, *bY;
587     int ret = -1;
588 #ifndef FIPS_MODULE
589     BN_CTX *new_ctx = NULL;
590 #endif
591
592     if (EC_POINT_is_at_infinity(group, a)) {
593         return EC_POINT_is_at_infinity(group, b) ? 0 : 1;
594     }
595
596     if (EC_POINT_is_at_infinity(group, b))
597         return 1;
598
599     if (a->Z_is_one && b->Z_is_one) {
600         return ((BN_cmp(a->X, b->X) == 0) && BN_cmp(a->Y, b->Y) == 0) ? 0 : 1;
601     }
602
603 #ifndef FIPS_MODULE
604     if (ctx == NULL) {
605         ctx = new_ctx = BN_CTX_new();
606         if (ctx == NULL)
607             return -1;
608     }
609 #endif
610
611     BN_CTX_start(ctx);
612     aX = BN_CTX_get(ctx);
613     aY = BN_CTX_get(ctx);
614     bX = BN_CTX_get(ctx);
615     bY = BN_CTX_get(ctx);
616     if (bY == NULL)
617         goto err;
618
619     if (!EC_POINT_get_affine_coordinates(group, a, aX, aY, ctx))
620         goto err;
621     if (!EC_POINT_get_affine_coordinates(group, b, bX, bY, ctx))
622         goto err;
623     ret = ((BN_cmp(aX, bX) == 0) && BN_cmp(aY, bY) == 0) ? 0 : 1;
624
625  err:
626     BN_CTX_end(ctx);
627 #ifndef FIPS_MODULE
628     BN_CTX_free(new_ctx);
629 #endif
630     return ret;
631 }
632
633 /* Forces the given EC_POINT to internally use affine coordinates. */
634 int ec_GF2m_simple_make_affine(const EC_GROUP *group, EC_POINT *point,
635                                BN_CTX *ctx)
636 {
637     BIGNUM *x, *y;
638     int ret = 0;
639 #ifndef FIPS_MODULE
640     BN_CTX *new_ctx = NULL;
641 #endif
642
643     if (point->Z_is_one || EC_POINT_is_at_infinity(group, point))
644         return 1;
645
646 #ifndef FIPS_MODULE
647     if (ctx == NULL) {
648         ctx = new_ctx = BN_CTX_new();
649         if (ctx == NULL)
650             return 0;
651     }
652 #endif
653
654     BN_CTX_start(ctx);
655     x = BN_CTX_get(ctx);
656     y = BN_CTX_get(ctx);
657     if (y == NULL)
658         goto err;
659
660     if (!EC_POINT_get_affine_coordinates(group, point, x, y, ctx))
661         goto err;
662     if (!BN_copy(point->X, x))
663         goto err;
664     if (!BN_copy(point->Y, y))
665         goto err;
666     if (!BN_one(point->Z))
667         goto err;
668     point->Z_is_one = 1;
669
670     ret = 1;
671
672  err:
673     BN_CTX_end(ctx);
674 #ifndef FIPS_MODULE
675     BN_CTX_free(new_ctx);
676 #endif
677     return ret;
678 }
679
680 /*
681  * Forces each of the EC_POINTs in the given array to use affine coordinates.
682  */
683 int ec_GF2m_simple_points_make_affine(const EC_GROUP *group, size_t num,
684                                       EC_POINT *points[], BN_CTX *ctx)
685 {
686     size_t i;
687
688     for (i = 0; i < num; i++) {
689         if (!group->meth->make_affine(group, points[i], ctx))
690             return 0;
691     }
692
693     return 1;
694 }
695
696 /* Wrapper to simple binary polynomial field multiplication implementation. */
697 int ec_GF2m_simple_field_mul(const EC_GROUP *group, BIGNUM *r,
698                              const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
699 {
700     return BN_GF2m_mod_mul_arr(r, a, b, group->poly, ctx);
701 }
702
703 /* Wrapper to simple binary polynomial field squaring implementation. */
704 int ec_GF2m_simple_field_sqr(const EC_GROUP *group, BIGNUM *r,
705                              const BIGNUM *a, BN_CTX *ctx)
706 {
707     return BN_GF2m_mod_sqr_arr(r, a, group->poly, ctx);
708 }
709
710 /* Wrapper to simple binary polynomial field division implementation. */
711 int ec_GF2m_simple_field_div(const EC_GROUP *group, BIGNUM *r,
712                              const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
713 {
714     return BN_GF2m_mod_div(r, a, b, group->field, ctx);
715 }
716
717 /*-
718  * Lopez-Dahab ladder, pre step.
719  * See e.g. "Guide to ECC" Alg 3.40.
720  * Modified to blind s and r independently.
721  * s:= p, r := 2p
722  */
723 static
724 int ec_GF2m_simple_ladder_pre(const EC_GROUP *group,
725                               EC_POINT *r, EC_POINT *s,
726                               EC_POINT *p, BN_CTX *ctx)
727 {
728     /* if p is not affine, something is wrong */
729     if (p->Z_is_one == 0)
730         return 0;
731
732     /* s blinding: make sure lambda (s->Z here) is not zero */
733     do {
734         if (!BN_priv_rand_ex(s->Z, BN_num_bits(group->field) - 1,
735                              BN_RAND_TOP_ANY, BN_RAND_BOTTOM_ANY, ctx)) {
736             ECerr(EC_F_EC_GF2M_SIMPLE_LADDER_PRE, ERR_R_BN_LIB);
737             return 0;
738         }
739     } while (BN_is_zero(s->Z));
740
741     /* if field_encode defined convert between representations */
742     if ((group->meth->field_encode != NULL
743          && !group->meth->field_encode(group, s->Z, s->Z, ctx))
744         || !group->meth->field_mul(group, s->X, p->X, s->Z, ctx))
745         return 0;
746
747     /* r blinding: make sure lambda (r->Y here for storage) is not zero */
748     do {
749         if (!BN_priv_rand_ex(r->Y, BN_num_bits(group->field) - 1,
750                              BN_RAND_TOP_ANY, BN_RAND_BOTTOM_ANY, ctx)) {
751             ECerr(EC_F_EC_GF2M_SIMPLE_LADDER_PRE, ERR_R_BN_LIB);
752             return 0;
753         }
754     } while (BN_is_zero(r->Y));
755
756     if ((group->meth->field_encode != NULL
757          && !group->meth->field_encode(group, r->Y, r->Y, ctx))
758         || !group->meth->field_sqr(group, r->Z, p->X, ctx)
759         || !group->meth->field_sqr(group, r->X, r->Z, ctx)
760         || !BN_GF2m_add(r->X, r->X, group->b)
761         || !group->meth->field_mul(group, r->Z, r->Z, r->Y, ctx)
762         || !group->meth->field_mul(group, r->X, r->X, r->Y, ctx))
763         return 0;
764
765     s->Z_is_one = 0;
766     r->Z_is_one = 0;
767
768     return 1;
769 }
770
771 /*-
772  * Ladder step: differential addition-and-doubling, mixed Lopez-Dahab coords.
773  * http://www.hyperelliptic.org/EFD/g12o/auto-code/shortw/xz/ladder/mladd-2003-s.op3
774  * s := r + s, r := 2r
775  */
776 static
777 int ec_GF2m_simple_ladder_step(const EC_GROUP *group,
778                                EC_POINT *r, EC_POINT *s,
779                                EC_POINT *p, BN_CTX *ctx)
780 {
781     if (!group->meth->field_mul(group, r->Y, r->Z, s->X, ctx)
782         || !group->meth->field_mul(group, s->X, r->X, s->Z, ctx)
783         || !group->meth->field_sqr(group, s->Y, r->Z, ctx)
784         || !group->meth->field_sqr(group, r->Z, r->X, ctx)
785         || !BN_GF2m_add(s->Z, r->Y, s->X)
786         || !group->meth->field_sqr(group, s->Z, s->Z, ctx)
787         || !group->meth->field_mul(group, s->X, r->Y, s->X, ctx)
788         || !group->meth->field_mul(group, r->Y, s->Z, p->X, ctx)
789         || !BN_GF2m_add(s->X, s->X, r->Y)
790         || !group->meth->field_sqr(group, r->Y, r->Z, ctx)
791         || !group->meth->field_mul(group, r->Z, r->Z, s->Y, ctx)
792         || !group->meth->field_sqr(group, s->Y, s->Y, ctx)
793         || !group->meth->field_mul(group, s->Y, s->Y, group->b, ctx)
794         || !BN_GF2m_add(r->X, r->Y, s->Y))
795         return 0;
796
797     return 1;
798 }
799
800 /*-
801  * Recover affine (x,y) result from Lopez-Dahab r and s, affine p.
802  * See e.g. "Fast Multiplication on Elliptic Curves over GF(2**m)
803  * without Precomputation" (Lopez and Dahab, CHES 1999),
804  * Appendix Alg Mxy.
805  */
806 static
807 int ec_GF2m_simple_ladder_post(const EC_GROUP *group,
808                                EC_POINT *r, EC_POINT *s,
809                                EC_POINT *p, BN_CTX *ctx)
810 {
811     int ret = 0;
812     BIGNUM *t0, *t1, *t2 = NULL;
813
814     if (BN_is_zero(r->Z))
815         return EC_POINT_set_to_infinity(group, r);
816
817     if (BN_is_zero(s->Z)) {
818         if (!EC_POINT_copy(r, p)
819             || !EC_POINT_invert(group, r, ctx)) {
820             ECerr(EC_F_EC_GF2M_SIMPLE_LADDER_POST, ERR_R_EC_LIB);
821             return 0;
822         }
823         return 1;
824     }
825
826     BN_CTX_start(ctx);
827     t0 = BN_CTX_get(ctx);
828     t1 = BN_CTX_get(ctx);
829     t2 = BN_CTX_get(ctx);
830     if (t2 == NULL) {
831         ECerr(EC_F_EC_GF2M_SIMPLE_LADDER_POST, ERR_R_MALLOC_FAILURE);
832         goto err;
833     }
834
835     if (!group->meth->field_mul(group, t0, r->Z, s->Z, ctx)
836         || !group->meth->field_mul(group, t1, p->X, r->Z, ctx)
837         || !BN_GF2m_add(t1, r->X, t1)
838         || !group->meth->field_mul(group, t2, p->X, s->Z, ctx)
839         || !group->meth->field_mul(group, r->Z, r->X, t2, ctx)
840         || !BN_GF2m_add(t2, t2, s->X)
841         || !group->meth->field_mul(group, t1, t1, t2, ctx)
842         || !group->meth->field_sqr(group, t2, p->X, ctx)
843         || !BN_GF2m_add(t2, p->Y, t2)
844         || !group->meth->field_mul(group, t2, t2, t0, ctx)
845         || !BN_GF2m_add(t1, t2, t1)
846         || !group->meth->field_mul(group, t2, p->X, t0, ctx)
847         || !group->meth->field_inv(group, t2, t2, ctx)
848         || !group->meth->field_mul(group, t1, t1, t2, ctx)
849         || !group->meth->field_mul(group, r->X, r->Z, t2, ctx)
850         || !BN_GF2m_add(t2, p->X, r->X)
851         || !group->meth->field_mul(group, t2, t2, t1, ctx)
852         || !BN_GF2m_add(r->Y, p->Y, t2)
853         || !BN_one(r->Z))
854         goto err;
855
856     r->Z_is_one = 1;
857
858     /* GF(2^m) field elements should always have BIGNUM::neg = 0 */
859     BN_set_negative(r->X, 0);
860     BN_set_negative(r->Y, 0);
861
862     ret = 1;
863
864  err:
865     BN_CTX_end(ctx);
866     return ret;
867 }
868
869 static
870 int ec_GF2m_simple_points_mul(const EC_GROUP *group, EC_POINT *r,
871                               const BIGNUM *scalar, size_t num,
872                               const EC_POINT *points[],
873                               const BIGNUM *scalars[],
874                               BN_CTX *ctx)
875 {
876     int ret = 0;
877     EC_POINT *t = NULL;
878
879     /*-
880      * We limit use of the ladder only to the following cases:
881      * - r := scalar * G
882      *   Fixed point mul: scalar != NULL && num == 0;
883      * - r := scalars[0] * points[0]
884      *   Variable point mul: scalar == NULL && num == 1;
885      * - r := scalar * G + scalars[0] * points[0]
886      *   used, e.g., in ECDSA verification: scalar != NULL && num == 1
887      *
888      * In any other case (num > 1) we use the default wNAF implementation.
889      *
890      * We also let the default implementation handle degenerate cases like group
891      * order or cofactor set to 0.
892      */
893     if (num > 1 || BN_is_zero(group->order) || BN_is_zero(group->cofactor))
894         return ec_wNAF_mul(group, r, scalar, num, points, scalars, ctx);
895
896     if (scalar != NULL && num == 0)
897         /* Fixed point multiplication */
898         return ec_scalar_mul_ladder(group, r, scalar, NULL, ctx);
899
900     if (scalar == NULL && num == 1)
901         /* Variable point multiplication */
902         return ec_scalar_mul_ladder(group, r, scalars[0], points[0], ctx);
903
904     /*-
905      * Double point multiplication:
906      *  r := scalar * G + scalars[0] * points[0]
907      */
908
909     if ((t = EC_POINT_new(group)) == NULL) {
910         ECerr(EC_F_EC_GF2M_SIMPLE_POINTS_MUL, ERR_R_MALLOC_FAILURE);
911         return 0;
912     }
913
914     if (!ec_scalar_mul_ladder(group, t, scalar, NULL, ctx)
915         || !ec_scalar_mul_ladder(group, r, scalars[0], points[0], ctx)
916         || !EC_POINT_add(group, r, t, r, ctx))
917         goto err;
918
919     ret = 1;
920
921  err:
922     EC_POINT_free(t);
923     return ret;
924 }
925
926 /*-
927  * Computes the multiplicative inverse of a in GF(2^m), storing the result in r.
928  * If a is zero (or equivalent), you'll get a EC_R_CANNOT_INVERT error.
929  * SCA hardening is with blinding: BN_GF2m_mod_inv does that.
930  */
931 static int ec_GF2m_simple_field_inv(const EC_GROUP *group, BIGNUM *r,
932                                     const BIGNUM *a, BN_CTX *ctx)
933 {
934     int ret;
935
936     if (!(ret = BN_GF2m_mod_inv(r, a, group->field, ctx)))
937         ECerr(EC_F_EC_GF2M_SIMPLE_FIELD_INV, EC_R_CANNOT_INVERT);
938     return ret;
939 }
940
941 const EC_METHOD *EC_GF2m_simple_method(void)
942 {
943     static const EC_METHOD ret = {
944         EC_FLAGS_DEFAULT_OCT,
945         NID_X9_62_characteristic_two_field,
946         ec_GF2m_simple_group_init,
947         ec_GF2m_simple_group_finish,
948         ec_GF2m_simple_group_clear_finish,
949         ec_GF2m_simple_group_copy,
950         ec_GF2m_simple_group_set_curve,
951         ec_GF2m_simple_group_get_curve,
952         ec_GF2m_simple_group_get_degree,
953         ec_group_simple_order_bits,
954         ec_GF2m_simple_group_check_discriminant,
955         ec_GF2m_simple_point_init,
956         ec_GF2m_simple_point_finish,
957         ec_GF2m_simple_point_clear_finish,
958         ec_GF2m_simple_point_copy,
959         ec_GF2m_simple_point_set_to_infinity,
960         ec_GF2m_simple_point_set_affine_coordinates,
961         ec_GF2m_simple_point_get_affine_coordinates,
962         0, /* point_set_compressed_coordinates */
963         0, /* point2oct */
964         0, /* oct2point */
965         ec_GF2m_simple_add,
966         ec_GF2m_simple_dbl,
967         ec_GF2m_simple_invert,
968         ec_GF2m_simple_is_at_infinity,
969         ec_GF2m_simple_is_on_curve,
970         ec_GF2m_simple_cmp,
971         ec_GF2m_simple_make_affine,
972         ec_GF2m_simple_points_make_affine,
973         ec_GF2m_simple_points_mul,
974         0, /* precompute_mult */
975         0, /* have_precompute_mult */
976         ec_GF2m_simple_field_mul,
977         ec_GF2m_simple_field_sqr,
978         ec_GF2m_simple_field_div,
979         ec_GF2m_simple_field_inv,
980         0, /* field_encode */
981         0, /* field_decode */
982         0, /* field_set_to_one */
983         ec_key_simple_priv2oct,
984         ec_key_simple_oct2priv,
985         0, /* set private */
986         ec_key_simple_generate_key,
987         ec_key_simple_check_key,
988         ec_key_simple_generate_public_key,
989         0, /* keycopy */
990         0, /* keyfinish */
991         ecdh_simple_compute_key,
992         ecdsa_simple_sign_setup,
993         ecdsa_simple_sign_sig,
994         ecdsa_simple_verify_sig,
995         0, /* field_inverse_mod_ord */
996         0, /* blind_coordinates */
997         ec_GF2m_simple_ladder_pre,
998         ec_GF2m_simple_ladder_step,
999         ec_GF2m_simple_ladder_post
1000     };
1001
1002     return &ret;
1003 }
1004
1005 #endif