]>
Commit | Line | Data |
---|---|---|
7793f30e BM |
1 | /* crypto/ec/ec2_smpl.c */ |
2 | /* ==================================================================== | |
3 | * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED. | |
4 | * | |
5 | * The Elliptic Curve Public-Key Crypto Library (ECC Code) included | |
6 | * herein is developed by SUN MICROSYSTEMS, INC., and is contributed | |
7 | * to the OpenSSL project. | |
8 | * | |
9 | * The ECC Code is licensed pursuant to the OpenSSL open source | |
10 | * license provided below. | |
11 | * | |
7793f30e BM |
12 | * The software is originally written by Sheueling Chang Shantz and |
13 | * Douglas Stebila of Sun Microsystems Laboratories. | |
14 | * | |
15 | */ | |
16 | /* ==================================================================== | |
8dee9f84 | 17 | * Copyright (c) 1998-2005 The OpenSSL Project. All rights reserved. |
7793f30e BM |
18 | * |
19 | * Redistribution and use in source and binary forms, with or without | |
20 | * modification, are permitted provided that the following conditions | |
21 | * are met: | |
22 | * | |
23 | * 1. Redistributions of source code must retain the above copyright | |
0f113f3e | 24 | * notice, this list of conditions and the following disclaimer. |
7793f30e BM |
25 | * |
26 | * 2. Redistributions in binary form must reproduce the above copyright | |
27 | * notice, this list of conditions and the following disclaimer in | |
28 | * the documentation and/or other materials provided with the | |
29 | * distribution. | |
30 | * | |
31 | * 3. All advertising materials mentioning features or use of this | |
32 | * software must display the following acknowledgment: | |
33 | * "This product includes software developed by the OpenSSL Project | |
34 | * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" | |
35 | * | |
36 | * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to | |
37 | * endorse or promote products derived from this software without | |
38 | * prior written permission. For written permission, please contact | |
39 | * openssl-core@openssl.org. | |
40 | * | |
41 | * 5. Products derived from this software may not be called "OpenSSL" | |
42 | * nor may "OpenSSL" appear in their names without prior written | |
43 | * permission of the OpenSSL Project. | |
44 | * | |
45 | * 6. Redistributions of any form whatsoever must retain the following | |
46 | * acknowledgment: | |
47 | * "This product includes software developed by the OpenSSL Project | |
48 | * for use in the OpenSSL Toolkit (http://www.openssl.org/)" | |
49 | * | |
50 | * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY | |
51 | * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | |
52 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR | |
53 | * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR | |
54 | * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, | |
55 | * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT | |
56 | * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; | |
57 | * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) | |
58 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, | |
59 | * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) | |
60 | * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED | |
61 | * OF THE POSSIBILITY OF SUCH DAMAGE. | |
62 | * ==================================================================== | |
63 | * | |
64 | * This product includes cryptographic software written by Eric Young | |
65 | * (eay@cryptsoft.com). This product includes software written by Tim | |
66 | * Hudson (tjh@cryptsoft.com). | |
67 | * | |
68 | */ | |
69 | ||
70 | #include <openssl/err.h> | |
71 | ||
5784a521 | 72 | #include "internal/bn_int.h" |
7793f30e BM |
73 | #include "ec_lcl.h" |
74 | ||
b3310161 DSH |
75 | #ifndef OPENSSL_NO_EC2M |
76 | ||
7793f30e | 77 | const EC_METHOD *EC_GF2m_simple_method(void) |
0f113f3e MC |
78 | { |
79 | static const EC_METHOD ret = { | |
80 | EC_FLAGS_DEFAULT_OCT, | |
81 | NID_X9_62_characteristic_two_field, | |
82 | ec_GF2m_simple_group_init, | |
83 | ec_GF2m_simple_group_finish, | |
84 | ec_GF2m_simple_group_clear_finish, | |
85 | ec_GF2m_simple_group_copy, | |
86 | ec_GF2m_simple_group_set_curve, | |
87 | ec_GF2m_simple_group_get_curve, | |
88 | ec_GF2m_simple_group_get_degree, | |
89 | ec_GF2m_simple_group_check_discriminant, | |
90 | ec_GF2m_simple_point_init, | |
91 | ec_GF2m_simple_point_finish, | |
92 | ec_GF2m_simple_point_clear_finish, | |
93 | ec_GF2m_simple_point_copy, | |
94 | ec_GF2m_simple_point_set_to_infinity, | |
95 | 0 /* set_Jprojective_coordinates_GFp */ , | |
96 | 0 /* get_Jprojective_coordinates_GFp */ , | |
97 | ec_GF2m_simple_point_set_affine_coordinates, | |
98 | ec_GF2m_simple_point_get_affine_coordinates, | |
99 | 0, 0, 0, | |
100 | ec_GF2m_simple_add, | |
101 | ec_GF2m_simple_dbl, | |
102 | ec_GF2m_simple_invert, | |
103 | ec_GF2m_simple_is_at_infinity, | |
104 | ec_GF2m_simple_is_on_curve, | |
105 | ec_GF2m_simple_cmp, | |
106 | ec_GF2m_simple_make_affine, | |
107 | ec_GF2m_simple_points_make_affine, | |
108 | ||
109 | /* | |
110 | * the following three method functions are defined in ec2_mult.c | |
111 | */ | |
112 | ec_GF2m_simple_mul, | |
113 | ec_GF2m_precompute_mult, | |
114 | ec_GF2m_have_precompute_mult, | |
115 | ||
116 | ec_GF2m_simple_field_mul, | |
117 | ec_GF2m_simple_field_sqr, | |
118 | ec_GF2m_simple_field_div, | |
119 | 0 /* field_encode */ , | |
120 | 0 /* field_decode */ , | |
121 | 0 /* field_set_to_one */ | |
122 | }; | |
123 | ||
124 | return &ret; | |
125 | } | |
126 | ||
127 | /* | |
128 | * Initialize a GF(2^m)-based EC_GROUP structure. Note that all other members | |
129 | * are handled by EC_GROUP_new. | |
7793f30e BM |
130 | */ |
131 | int ec_GF2m_simple_group_init(EC_GROUP *group) | |
0f113f3e MC |
132 | { |
133 | group->field = BN_new(); | |
134 | group->a = BN_new(); | |
135 | group->b = BN_new(); | |
136 | ||
137 | if (!group->field || !group->a || !group->b) { | |
138 | if (group->field) | |
139 | BN_free(group->field); | |
140 | if (group->a) | |
141 | BN_free(group->a); | |
142 | if (group->b) | |
143 | BN_free(group->b); | |
144 | return 0; | |
145 | } | |
146 | return 1; | |
147 | } | |
148 | ||
149 | /* | |
150 | * Free a GF(2^m)-based EC_GROUP structure. Note that all other members are | |
151 | * handled by EC_GROUP_free. | |
7793f30e BM |
152 | */ |
153 | void ec_GF2m_simple_group_finish(EC_GROUP *group) | |
0f113f3e MC |
154 | { |
155 | BN_free(group->field); | |
156 | BN_free(group->a); | |
157 | BN_free(group->b); | |
158 | } | |
159 | ||
160 | /* | |
161 | * Clear and free a GF(2^m)-based EC_GROUP structure. Note that all other | |
162 | * members are handled by EC_GROUP_clear_free. | |
7793f30e BM |
163 | */ |
164 | void ec_GF2m_simple_group_clear_finish(EC_GROUP *group) | |
0f113f3e MC |
165 | { |
166 | BN_clear_free(group->field); | |
167 | BN_clear_free(group->a); | |
168 | BN_clear_free(group->b); | |
169 | group->poly[0] = 0; | |
170 | group->poly[1] = 0; | |
171 | group->poly[2] = 0; | |
172 | group->poly[3] = 0; | |
173 | group->poly[4] = 0; | |
174 | group->poly[5] = -1; | |
175 | } | |
176 | ||
177 | /* | |
178 | * Copy a GF(2^m)-based EC_GROUP structure. Note that all other members are | |
179 | * handled by EC_GROUP_copy. | |
7793f30e BM |
180 | */ |
181 | int ec_GF2m_simple_group_copy(EC_GROUP *dest, const EC_GROUP *src) | |
0f113f3e MC |
182 | { |
183 | if (!BN_copy(dest->field, src->field)) | |
184 | return 0; | |
185 | if (!BN_copy(dest->a, src->a)) | |
186 | return 0; | |
187 | if (!BN_copy(dest->b, src->b)) | |
188 | return 0; | |
189 | dest->poly[0] = src->poly[0]; | |
190 | dest->poly[1] = src->poly[1]; | |
191 | dest->poly[2] = src->poly[2]; | |
192 | dest->poly[3] = src->poly[3]; | |
193 | dest->poly[4] = src->poly[4]; | |
194 | dest->poly[5] = src->poly[5]; | |
195 | if (bn_wexpand(dest->a, (int)(dest->poly[0] + BN_BITS2 - 1) / BN_BITS2) == | |
196 | NULL) | |
197 | return 0; | |
198 | if (bn_wexpand(dest->b, (int)(dest->poly[0] + BN_BITS2 - 1) / BN_BITS2) == | |
199 | NULL) | |
200 | return 0; | |
201 | bn_set_all_zero(dest->a); | |
202 | bn_set_all_zero(dest->b); | |
203 | return 1; | |
204 | } | |
7793f30e BM |
205 | |
206 | /* Set the curve parameters of an EC_GROUP structure. */ | |
35b73a1f | 207 | int ec_GF2m_simple_group_set_curve(EC_GROUP *group, |
0f113f3e MC |
208 | const BIGNUM *p, const BIGNUM *a, |
209 | const BIGNUM *b, BN_CTX *ctx) | |
210 | { | |
211 | int ret = 0, i; | |
212 | ||
213 | /* group->field */ | |
214 | if (!BN_copy(group->field, p)) | |
215 | goto err; | |
216 | i = BN_GF2m_poly2arr(group->field, group->poly, 6) - 1; | |
217 | if ((i != 5) && (i != 3)) { | |
218 | ECerr(EC_F_EC_GF2M_SIMPLE_GROUP_SET_CURVE, EC_R_UNSUPPORTED_FIELD); | |
219 | goto err; | |
220 | } | |
221 | ||
222 | /* group->a */ | |
223 | if (!BN_GF2m_mod_arr(group->a, a, group->poly)) | |
224 | goto err; | |
225 | if (bn_wexpand(group->a, (int)(group->poly[0] + BN_BITS2 - 1) / BN_BITS2) | |
226 | == NULL) | |
227 | goto err; | |
228 | bn_set_all_zero(group->a); | |
229 | ||
230 | /* group->b */ | |
231 | if (!BN_GF2m_mod_arr(group->b, b, group->poly)) | |
232 | goto err; | |
233 | if (bn_wexpand(group->b, (int)(group->poly[0] + BN_BITS2 - 1) / BN_BITS2) | |
234 | == NULL) | |
235 | goto err; | |
236 | bn_set_all_zero(group->b); | |
237 | ||
238 | ret = 1; | |
239 | err: | |
240 | return ret; | |
241 | } | |
242 | ||
243 | /* | |
244 | * Get the curve parameters of an EC_GROUP structure. If p, a, or b are NULL | |
245 | * then there values will not be set but the method will return with success. | |
7793f30e | 246 | */ |
0f113f3e MC |
247 | int ec_GF2m_simple_group_get_curve(const EC_GROUP *group, BIGNUM *p, |
248 | BIGNUM *a, BIGNUM *b, BN_CTX *ctx) | |
249 | { | |
250 | int ret = 0; | |
251 | ||
252 | if (p != NULL) { | |
253 | if (!BN_copy(p, group->field)) | |
254 | return 0; | |
255 | } | |
256 | ||
257 | if (a != NULL) { | |
258 | if (!BN_copy(a, group->a)) | |
259 | goto err; | |
260 | } | |
7793f30e | 261 | |
0f113f3e MC |
262 | if (b != NULL) { |
263 | if (!BN_copy(b, group->b)) | |
264 | goto err; | |
265 | } | |
7793f30e | 266 | |
0f113f3e MC |
267 | ret = 1; |
268 | ||
269 | err: | |
270 | return ret; | |
271 | } | |
272 | ||
273 | /* | |
274 | * Gets the degree of the field. For a curve over GF(2^m) this is the value | |
275 | * m. | |
276 | */ | |
277 | int ec_GF2m_simple_group_get_degree(const EC_GROUP *group) | |
278 | { | |
279 | return BN_num_bits(group->field) - 1; | |
280 | } | |
281 | ||
282 | /* | |
283 | * Checks the discriminant of the curve. y^2 + x*y = x^3 + a*x^2 + b is an | |
284 | * elliptic curve <=> b != 0 (mod p) | |
7793f30e | 285 | */ |
0f113f3e MC |
286 | int ec_GF2m_simple_group_check_discriminant(const EC_GROUP *group, |
287 | BN_CTX *ctx) | |
288 | { | |
289 | int ret = 0; | |
290 | BIGNUM *b; | |
291 | BN_CTX *new_ctx = NULL; | |
292 | ||
293 | if (ctx == NULL) { | |
294 | ctx = new_ctx = BN_CTX_new(); | |
295 | if (ctx == NULL) { | |
296 | ECerr(EC_F_EC_GF2M_SIMPLE_GROUP_CHECK_DISCRIMINANT, | |
297 | ERR_R_MALLOC_FAILURE); | |
298 | goto err; | |
299 | } | |
300 | } | |
301 | BN_CTX_start(ctx); | |
302 | b = BN_CTX_get(ctx); | |
303 | if (b == NULL) | |
304 | goto err; | |
305 | ||
306 | if (!BN_GF2m_mod_arr(b, group->b, group->poly)) | |
307 | goto err; | |
308 | ||
309 | /* | |
310 | * check the discriminant: y^2 + x*y = x^3 + a*x^2 + b is an elliptic | |
311 | * curve <=> b != 0 (mod p) | |
312 | */ | |
313 | if (BN_is_zero(b)) | |
314 | goto err; | |
315 | ||
316 | ret = 1; | |
7793f30e | 317 | |
0f113f3e MC |
318 | err: |
319 | if (ctx != NULL) | |
320 | BN_CTX_end(ctx); | |
321 | if (new_ctx != NULL) | |
322 | BN_CTX_free(new_ctx); | |
323 | return ret; | |
324 | } | |
7793f30e BM |
325 | |
326 | /* Initializes an EC_POINT. */ | |
327 | int ec_GF2m_simple_point_init(EC_POINT *point) | |
0f113f3e MC |
328 | { |
329 | point->X = BN_new(); | |
330 | point->Y = BN_new(); | |
331 | point->Z = BN_new(); | |
332 | ||
333 | if (!point->X || !point->Y || !point->Z) { | |
334 | if (point->X) | |
335 | BN_free(point->X); | |
336 | if (point->Y) | |
337 | BN_free(point->Y); | |
338 | if (point->Z) | |
339 | BN_free(point->Z); | |
340 | return 0; | |
341 | } | |
342 | return 1; | |
343 | } | |
7793f30e BM |
344 | |
345 | /* Frees an EC_POINT. */ | |
346 | void ec_GF2m_simple_point_finish(EC_POINT *point) | |
0f113f3e MC |
347 | { |
348 | BN_free(point->X); | |
349 | BN_free(point->Y); | |
350 | BN_free(point->Z); | |
351 | } | |
7793f30e BM |
352 | |
353 | /* Clears and frees an EC_POINT. */ | |
354 | void ec_GF2m_simple_point_clear_finish(EC_POINT *point) | |
0f113f3e MC |
355 | { |
356 | BN_clear_free(point->X); | |
357 | BN_clear_free(point->Y); | |
358 | BN_clear_free(point->Z); | |
359 | point->Z_is_one = 0; | |
360 | } | |
361 | ||
362 | /* | |
363 | * Copy the contents of one EC_POINT into another. Assumes dest is | |
364 | * initialized. | |
7793f30e | 365 | */ |
0f113f3e MC |
366 | int ec_GF2m_simple_point_copy(EC_POINT *dest, const EC_POINT *src) |
367 | { | |
368 | if (!BN_copy(dest->X, src->X)) | |
369 | return 0; | |
370 | if (!BN_copy(dest->Y, src->Y)) | |
371 | return 0; | |
372 | if (!BN_copy(dest->Z, src->Z)) | |
373 | return 0; | |
374 | dest->Z_is_one = src->Z_is_one; | |
375 | ||
376 | return 1; | |
377 | } | |
378 | ||
379 | /* | |
380 | * Set an EC_POINT to the point at infinity. A point at infinity is | |
381 | * represented by having Z=0. | |
7793f30e | 382 | */ |
0f113f3e MC |
383 | int ec_GF2m_simple_point_set_to_infinity(const EC_GROUP *group, |
384 | EC_POINT *point) | |
385 | { | |
386 | point->Z_is_one = 0; | |
387 | BN_zero(point->Z); | |
388 | return 1; | |
389 | } | |
390 | ||
391 | /* | |
392 | * Set the coordinates of an EC_POINT using affine coordinates. Note that | |
393 | * the simple implementation only uses affine coordinates. | |
7793f30e | 394 | */ |
0f113f3e MC |
395 | int ec_GF2m_simple_point_set_affine_coordinates(const EC_GROUP *group, |
396 | EC_POINT *point, | |
397 | const BIGNUM *x, | |
398 | const BIGNUM *y, BN_CTX *ctx) | |
399 | { | |
400 | int ret = 0; | |
401 | if (x == NULL || y == NULL) { | |
402 | ECerr(EC_F_EC_GF2M_SIMPLE_POINT_SET_AFFINE_COORDINATES, | |
403 | ERR_R_PASSED_NULL_PARAMETER); | |
404 | return 0; | |
405 | } | |
406 | ||
407 | if (!BN_copy(point->X, x)) | |
408 | goto err; | |
409 | BN_set_negative(point->X, 0); | |
410 | if (!BN_copy(point->Y, y)) | |
411 | goto err; | |
412 | BN_set_negative(point->Y, 0); | |
413 | if (!BN_copy(point->Z, BN_value_one())) | |
414 | goto err; | |
415 | BN_set_negative(point->Z, 0); | |
416 | point->Z_is_one = 1; | |
417 | ret = 1; | |
418 | ||
7793f30e | 419 | err: |
0f113f3e MC |
420 | return ret; |
421 | } | |
7793f30e | 422 | |
0f113f3e MC |
423 | /* |
424 | * Gets the affine coordinates of an EC_POINT. Note that the simple | |
425 | * implementation only uses affine coordinates. | |
7793f30e | 426 | */ |
0f113f3e MC |
427 | int ec_GF2m_simple_point_get_affine_coordinates(const EC_GROUP *group, |
428 | const EC_POINT *point, | |
429 | BIGNUM *x, BIGNUM *y, | |
430 | BN_CTX *ctx) | |
431 | { | |
432 | int ret = 0; | |
433 | ||
434 | if (EC_POINT_is_at_infinity(group, point)) { | |
435 | ECerr(EC_F_EC_GF2M_SIMPLE_POINT_GET_AFFINE_COORDINATES, | |
436 | EC_R_POINT_AT_INFINITY); | |
437 | return 0; | |
438 | } | |
439 | ||
440 | if (BN_cmp(point->Z, BN_value_one())) { | |
441 | ECerr(EC_F_EC_GF2M_SIMPLE_POINT_GET_AFFINE_COORDINATES, | |
442 | ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); | |
443 | return 0; | |
444 | } | |
445 | if (x != NULL) { | |
446 | if (!BN_copy(x, point->X)) | |
447 | goto err; | |
448 | BN_set_negative(x, 0); | |
449 | } | |
450 | if (y != NULL) { | |
451 | if (!BN_copy(y, point->Y)) | |
452 | goto err; | |
453 | BN_set_negative(y, 0); | |
454 | } | |
455 | ret = 1; | |
7793f30e BM |
456 | |
457 | err: | |
0f113f3e MC |
458 | return ret; |
459 | } | |
7793f30e | 460 | |
0f113f3e MC |
461 | /* |
462 | * Computes a + b and stores the result in r. r could be a or b, a could be | |
463 | * b. Uses algorithm A.10.2 of IEEE P1363. | |
7793f30e | 464 | */ |
0f113f3e MC |
465 | int ec_GF2m_simple_add(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a, |
466 | const EC_POINT *b, BN_CTX *ctx) | |
467 | { | |
468 | BN_CTX *new_ctx = NULL; | |
469 | BIGNUM *x0, *y0, *x1, *y1, *x2, *y2, *s, *t; | |
470 | int ret = 0; | |
471 | ||
472 | if (EC_POINT_is_at_infinity(group, a)) { | |
473 | if (!EC_POINT_copy(r, b)) | |
474 | return 0; | |
475 | return 1; | |
476 | } | |
477 | ||
478 | if (EC_POINT_is_at_infinity(group, b)) { | |
479 | if (!EC_POINT_copy(r, a)) | |
480 | return 0; | |
481 | return 1; | |
482 | } | |
483 | ||
484 | if (ctx == NULL) { | |
485 | ctx = new_ctx = BN_CTX_new(); | |
486 | if (ctx == NULL) | |
487 | return 0; | |
488 | } | |
489 | ||
490 | BN_CTX_start(ctx); | |
491 | x0 = BN_CTX_get(ctx); | |
492 | y0 = BN_CTX_get(ctx); | |
493 | x1 = BN_CTX_get(ctx); | |
494 | y1 = BN_CTX_get(ctx); | |
495 | x2 = BN_CTX_get(ctx); | |
496 | y2 = BN_CTX_get(ctx); | |
497 | s = BN_CTX_get(ctx); | |
498 | t = BN_CTX_get(ctx); | |
499 | if (t == NULL) | |
500 | goto err; | |
501 | ||
502 | if (a->Z_is_one) { | |
503 | if (!BN_copy(x0, a->X)) | |
504 | goto err; | |
505 | if (!BN_copy(y0, a->Y)) | |
506 | goto err; | |
507 | } else { | |
508 | if (!EC_POINT_get_affine_coordinates_GF2m(group, a, x0, y0, ctx)) | |
509 | goto err; | |
510 | } | |
511 | if (b->Z_is_one) { | |
512 | if (!BN_copy(x1, b->X)) | |
513 | goto err; | |
514 | if (!BN_copy(y1, b->Y)) | |
515 | goto err; | |
516 | } else { | |
517 | if (!EC_POINT_get_affine_coordinates_GF2m(group, b, x1, y1, ctx)) | |
518 | goto err; | |
519 | } | |
520 | ||
521 | if (BN_GF2m_cmp(x0, x1)) { | |
522 | if (!BN_GF2m_add(t, x0, x1)) | |
523 | goto err; | |
524 | if (!BN_GF2m_add(s, y0, y1)) | |
525 | goto err; | |
526 | if (!group->meth->field_div(group, s, s, t, ctx)) | |
527 | goto err; | |
528 | if (!group->meth->field_sqr(group, x2, s, ctx)) | |
529 | goto err; | |
530 | if (!BN_GF2m_add(x2, x2, group->a)) | |
531 | goto err; | |
532 | if (!BN_GF2m_add(x2, x2, s)) | |
533 | goto err; | |
534 | if (!BN_GF2m_add(x2, x2, t)) | |
535 | goto err; | |
536 | } else { | |
537 | if (BN_GF2m_cmp(y0, y1) || BN_is_zero(x1)) { | |
538 | if (!EC_POINT_set_to_infinity(group, r)) | |
539 | goto err; | |
540 | ret = 1; | |
541 | goto err; | |
542 | } | |
543 | if (!group->meth->field_div(group, s, y1, x1, ctx)) | |
544 | goto err; | |
545 | if (!BN_GF2m_add(s, s, x1)) | |
546 | goto err; | |
547 | ||
548 | if (!group->meth->field_sqr(group, x2, s, ctx)) | |
549 | goto err; | |
550 | if (!BN_GF2m_add(x2, x2, s)) | |
551 | goto err; | |
552 | if (!BN_GF2m_add(x2, x2, group->a)) | |
553 | goto err; | |
554 | } | |
555 | ||
556 | if (!BN_GF2m_add(y2, x1, x2)) | |
557 | goto err; | |
558 | if (!group->meth->field_mul(group, y2, y2, s, ctx)) | |
559 | goto err; | |
560 | if (!BN_GF2m_add(y2, y2, x2)) | |
561 | goto err; | |
562 | if (!BN_GF2m_add(y2, y2, y1)) | |
563 | goto err; | |
564 | ||
565 | if (!EC_POINT_set_affine_coordinates_GF2m(group, r, x2, y2, ctx)) | |
566 | goto err; | |
567 | ||
568 | ret = 1; | |
7793f30e | 569 | |
0f113f3e MC |
570 | err: |
571 | BN_CTX_end(ctx); | |
572 | if (new_ctx != NULL) | |
573 | BN_CTX_free(new_ctx); | |
574 | return ret; | |
575 | } | |
576 | ||
577 | /* | |
578 | * Computes 2 * a and stores the result in r. r could be a. Uses algorithm | |
579 | * A.10.2 of IEEE P1363. | |
580 | */ | |
581 | int ec_GF2m_simple_dbl(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a, | |
582 | BN_CTX *ctx) | |
583 | { | |
584 | return ec_GF2m_simple_add(group, r, a, a, ctx); | |
585 | } | |
7793f30e BM |
586 | |
587 | int ec_GF2m_simple_invert(const EC_GROUP *group, EC_POINT *point, BN_CTX *ctx) | |
0f113f3e MC |
588 | { |
589 | if (EC_POINT_is_at_infinity(group, point) || BN_is_zero(point->Y)) | |
590 | /* point is its own inverse */ | |
591 | return 1; | |
7793f30e | 592 | |
0f113f3e MC |
593 | if (!EC_POINT_make_affine(group, point, ctx)) |
594 | return 0; | |
595 | return BN_GF2m_add(point->Y, point->X, point->Y); | |
596 | } | |
7793f30e BM |
597 | |
598 | /* Indicates whether the given point is the point at infinity. */ | |
0f113f3e MC |
599 | int ec_GF2m_simple_is_at_infinity(const EC_GROUP *group, |
600 | const EC_POINT *point) | |
601 | { | |
602 | return BN_is_zero(point->Z); | |
603 | } | |
7793f30e | 604 | |
23a22b4c MC |
605 | /*- |
606 | * Determines whether the given EC_POINT is an actual point on the curve defined | |
7793f30e BM |
607 | * in the EC_GROUP. A point is valid if it satisfies the Weierstrass equation: |
608 | * y^2 + x*y = x^3 + a*x^2 + b. | |
609 | */ | |
0f113f3e MC |
610 | int ec_GF2m_simple_is_on_curve(const EC_GROUP *group, const EC_POINT *point, |
611 | BN_CTX *ctx) | |
612 | { | |
613 | int ret = -1; | |
614 | BN_CTX *new_ctx = NULL; | |
615 | BIGNUM *lh, *y2; | |
616 | int (*field_mul) (const EC_GROUP *, BIGNUM *, const BIGNUM *, | |
617 | const BIGNUM *, BN_CTX *); | |
618 | int (*field_sqr) (const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *); | |
619 | ||
620 | if (EC_POINT_is_at_infinity(group, point)) | |
621 | return 1; | |
622 | ||
623 | field_mul = group->meth->field_mul; | |
624 | field_sqr = group->meth->field_sqr; | |
625 | ||
626 | /* only support affine coordinates */ | |
627 | if (!point->Z_is_one) | |
628 | return -1; | |
629 | ||
630 | if (ctx == NULL) { | |
631 | ctx = new_ctx = BN_CTX_new(); | |
632 | if (ctx == NULL) | |
633 | return -1; | |
634 | } | |
635 | ||
636 | BN_CTX_start(ctx); | |
637 | y2 = BN_CTX_get(ctx); | |
638 | lh = BN_CTX_get(ctx); | |
639 | if (lh == NULL) | |
640 | goto err; | |
641 | ||
50e735f9 MC |
642 | /*- |
643 | * We have a curve defined by a Weierstrass equation | |
644 | * y^2 + x*y = x^3 + a*x^2 + b. | |
645 | * <=> x^3 + a*x^2 + x*y + b + y^2 = 0 | |
646 | * <=> ((x + a) * x + y ) * x + b + y^2 = 0 | |
647 | */ | |
0f113f3e MC |
648 | if (!BN_GF2m_add(lh, point->X, group->a)) |
649 | goto err; | |
650 | if (!field_mul(group, lh, lh, point->X, ctx)) | |
651 | goto err; | |
652 | if (!BN_GF2m_add(lh, lh, point->Y)) | |
653 | goto err; | |
654 | if (!field_mul(group, lh, lh, point->X, ctx)) | |
655 | goto err; | |
656 | if (!BN_GF2m_add(lh, lh, group->b)) | |
657 | goto err; | |
658 | if (!field_sqr(group, y2, point->Y, ctx)) | |
659 | goto err; | |
660 | if (!BN_GF2m_add(lh, lh, y2)) | |
661 | goto err; | |
662 | ret = BN_is_zero(lh); | |
7793f30e | 663 | err: |
0f113f3e MC |
664 | if (ctx) |
665 | BN_CTX_end(ctx); | |
666 | if (new_ctx) | |
667 | BN_CTX_free(new_ctx); | |
668 | return ret; | |
669 | } | |
7793f30e | 670 | |
1d97c843 TH |
671 | /*- |
672 | * Indicates whether two points are equal. | |
7793f30e BM |
673 | * Return values: |
674 | * -1 error | |
675 | * 0 equal (in affine coordinates) | |
676 | * 1 not equal | |
677 | */ | |
0f113f3e MC |
678 | int ec_GF2m_simple_cmp(const EC_GROUP *group, const EC_POINT *a, |
679 | const EC_POINT *b, BN_CTX *ctx) | |
680 | { | |
681 | BIGNUM *aX, *aY, *bX, *bY; | |
682 | BN_CTX *new_ctx = NULL; | |
683 | int ret = -1; | |
684 | ||
685 | if (EC_POINT_is_at_infinity(group, a)) { | |
686 | return EC_POINT_is_at_infinity(group, b) ? 0 : 1; | |
687 | } | |
688 | ||
689 | if (EC_POINT_is_at_infinity(group, b)) | |
690 | return 1; | |
691 | ||
692 | if (a->Z_is_one && b->Z_is_one) { | |
693 | return ((BN_cmp(a->X, b->X) == 0) && BN_cmp(a->Y, b->Y) == 0) ? 0 : 1; | |
694 | } | |
695 | ||
696 | if (ctx == NULL) { | |
697 | ctx = new_ctx = BN_CTX_new(); | |
698 | if (ctx == NULL) | |
699 | return -1; | |
700 | } | |
701 | ||
702 | BN_CTX_start(ctx); | |
703 | aX = BN_CTX_get(ctx); | |
704 | aY = BN_CTX_get(ctx); | |
705 | bX = BN_CTX_get(ctx); | |
706 | bY = BN_CTX_get(ctx); | |
707 | if (bY == NULL) | |
708 | goto err; | |
709 | ||
710 | if (!EC_POINT_get_affine_coordinates_GF2m(group, a, aX, aY, ctx)) | |
711 | goto err; | |
712 | if (!EC_POINT_get_affine_coordinates_GF2m(group, b, bX, bY, ctx)) | |
713 | goto err; | |
714 | ret = ((BN_cmp(aX, bX) == 0) && BN_cmp(aY, bY) == 0) ? 0 : 1; | |
7793f30e | 715 | |
0f113f3e MC |
716 | err: |
717 | if (ctx) | |
718 | BN_CTX_end(ctx); | |
719 | if (new_ctx) | |
720 | BN_CTX_free(new_ctx); | |
721 | return ret; | |
722 | } | |
7793f30e BM |
723 | |
724 | /* Forces the given EC_POINT to internally use affine coordinates. */ | |
0f113f3e MC |
725 | int ec_GF2m_simple_make_affine(const EC_GROUP *group, EC_POINT *point, |
726 | BN_CTX *ctx) | |
727 | { | |
728 | BN_CTX *new_ctx = NULL; | |
729 | BIGNUM *x, *y; | |
730 | int ret = 0; | |
731 | ||
732 | if (point->Z_is_one || EC_POINT_is_at_infinity(group, point)) | |
733 | return 1; | |
734 | ||
735 | if (ctx == NULL) { | |
736 | ctx = new_ctx = BN_CTX_new(); | |
737 | if (ctx == NULL) | |
738 | return 0; | |
739 | } | |
740 | ||
741 | BN_CTX_start(ctx); | |
742 | x = BN_CTX_get(ctx); | |
743 | y = BN_CTX_get(ctx); | |
744 | if (y == NULL) | |
745 | goto err; | |
746 | ||
747 | if (!EC_POINT_get_affine_coordinates_GF2m(group, point, x, y, ctx)) | |
748 | goto err; | |
749 | if (!BN_copy(point->X, x)) | |
750 | goto err; | |
751 | if (!BN_copy(point->Y, y)) | |
752 | goto err; | |
753 | if (!BN_one(point->Z)) | |
754 | goto err; | |
755 | ||
756 | ret = 1; | |
757 | ||
758 | err: | |
759 | if (ctx) | |
760 | BN_CTX_end(ctx); | |
761 | if (new_ctx) | |
762 | BN_CTX_free(new_ctx); | |
763 | return ret; | |
764 | } | |
765 | ||
766 | /* | |
767 | * Forces each of the EC_POINTs in the given array to use affine coordinates. | |
768 | */ | |
769 | int ec_GF2m_simple_points_make_affine(const EC_GROUP *group, size_t num, | |
770 | EC_POINT *points[], BN_CTX *ctx) | |
771 | { | |
772 | size_t i; | |
7793f30e | 773 | |
0f113f3e MC |
774 | for (i = 0; i < num; i++) { |
775 | if (!group->meth->make_affine(group, points[i], ctx)) | |
776 | return 0; | |
777 | } | |
7793f30e | 778 | |
0f113f3e MC |
779 | return 1; |
780 | } | |
7793f30e | 781 | |
0f113f3e MC |
782 | /* Wrapper to simple binary polynomial field multiplication implementation. */ |
783 | int ec_GF2m_simple_field_mul(const EC_GROUP *group, BIGNUM *r, | |
784 | const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx) | |
785 | { | |
786 | return BN_GF2m_mod_mul_arr(r, a, b, group->poly, ctx); | |
787 | } | |
7793f30e BM |
788 | |
789 | /* Wrapper to simple binary polynomial field squaring implementation. */ | |
0f113f3e MC |
790 | int ec_GF2m_simple_field_sqr(const EC_GROUP *group, BIGNUM *r, |
791 | const BIGNUM *a, BN_CTX *ctx) | |
792 | { | |
793 | return BN_GF2m_mod_sqr_arr(r, a, group->poly, ctx); | |
794 | } | |
7793f30e BM |
795 | |
796 | /* Wrapper to simple binary polynomial field division implementation. */ | |
0f113f3e MC |
797 | int ec_GF2m_simple_field_div(const EC_GROUP *group, BIGNUM *r, |
798 | const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx) | |
799 | { | |
800 | return BN_GF2m_mod_div(r, a, b, group->field, ctx); | |
801 | } | |
b3310161 DSH |
802 | |
803 | #endif |