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