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