OLD | NEW |
| (Empty) |
1 /* crypto/ec/ecp_smpl.c */ | |
2 /* Includes code written by Lenka Fibikova <fibikova@exp-math.uni-essen.de> | |
3 * for the OpenSSL project. | |
4 * Includes code written by Bodo Moeller for the OpenSSL project. | |
5 */ | |
6 /* ==================================================================== | |
7 * Copyright (c) 1998-2002 The OpenSSL Project. All rights reserved. | |
8 * | |
9 * Redistribution and use in source and binary forms, with or without | |
10 * modification, are permitted provided that the following conditions | |
11 * are met: | |
12 * | |
13 * 1. Redistributions of source code must retain the above copyright | |
14 * notice, this list of conditions and the following disclaimer. | |
15 * | |
16 * 2. Redistributions in binary form must reproduce the above copyright | |
17 * notice, this list of conditions and the following disclaimer in | |
18 * the documentation and/or other materials provided with the | |
19 * distribution. | |
20 * | |
21 * 3. All advertising materials mentioning features or use of this | |
22 * software must display the following acknowledgment: | |
23 * "This product includes software developed by the OpenSSL Project | |
24 * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" | |
25 * | |
26 * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to | |
27 * endorse or promote products derived from this software without | |
28 * prior written permission. For written permission, please contact | |
29 * openssl-core@openssl.org. | |
30 * | |
31 * 5. Products derived from this software may not be called "OpenSSL" | |
32 * nor may "OpenSSL" appear in their names without prior written | |
33 * permission of the OpenSSL Project. | |
34 * | |
35 * 6. Redistributions of any form whatsoever must retain the following | |
36 * acknowledgment: | |
37 * "This product includes software developed by the OpenSSL Project | |
38 * for use in the OpenSSL Toolkit (http://www.openssl.org/)" | |
39 * | |
40 * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY | |
41 * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | |
42 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR | |
43 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR | |
44 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, | |
45 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT | |
46 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; | |
47 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) | |
48 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, | |
49 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) | |
50 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED | |
51 * OF THE POSSIBILITY OF SUCH DAMAGE. | |
52 * ==================================================================== | |
53 * | |
54 * This product includes cryptographic software written by Eric Young | |
55 * (eay@cryptsoft.com). This product includes software written by Tim | |
56 * Hudson (tjh@cryptsoft.com). | |
57 * | |
58 */ | |
59 /* ==================================================================== | |
60 * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED. | |
61 * Portions of this software developed by SUN MICROSYSTEMS, INC., | |
62 * and contributed to the OpenSSL project. | |
63 */ | |
64 | |
65 #include <openssl/err.h> | |
66 #include <openssl/symhacks.h> | |
67 | |
68 #ifdef OPENSSL_FIPS | |
69 #include <openssl/fips.h> | |
70 #endif | |
71 | |
72 #include "ec_lcl.h" | |
73 | |
74 const EC_METHOD *EC_GFp_simple_method(void) | |
75 { | |
76 #ifdef OPENSSL_FIPS | |
77 return fips_ec_gfp_simple_method(); | |
78 #else | |
79 static const EC_METHOD ret = { | |
80 EC_FLAGS_DEFAULT_OCT, | |
81 NID_X9_62_prime_field, | |
82 ec_GFp_simple_group_init, | |
83 ec_GFp_simple_group_finish, | |
84 ec_GFp_simple_group_clear_finish, | |
85 ec_GFp_simple_group_copy, | |
86 ec_GFp_simple_group_set_curve, | |
87 ec_GFp_simple_group_get_curve, | |
88 ec_GFp_simple_group_get_degree, | |
89 ec_GFp_simple_group_check_discriminant, | |
90 ec_GFp_simple_point_init, | |
91 ec_GFp_simple_point_finish, | |
92 ec_GFp_simple_point_clear_finish, | |
93 ec_GFp_simple_point_copy, | |
94 ec_GFp_simple_point_set_to_infinity, | |
95 ec_GFp_simple_set_Jprojective_coordinates_GFp, | |
96 ec_GFp_simple_get_Jprojective_coordinates_GFp, | |
97 ec_GFp_simple_point_set_affine_coordinates, | |
98 ec_GFp_simple_point_get_affine_coordinates, | |
99 0,0,0, | |
100 ec_GFp_simple_add, | |
101 ec_GFp_simple_dbl, | |
102 ec_GFp_simple_invert, | |
103 ec_GFp_simple_is_at_infinity, | |
104 ec_GFp_simple_is_on_curve, | |
105 ec_GFp_simple_cmp, | |
106 ec_GFp_simple_make_affine, | |
107 ec_GFp_simple_points_make_affine, | |
108 0 /* mul */, | |
109 0 /* precompute_mult */, | |
110 0 /* have_precompute_mult */, | |
111 ec_GFp_simple_field_mul, | |
112 ec_GFp_simple_field_sqr, | |
113 0 /* field_div */, | |
114 0 /* field_encode */, | |
115 0 /* field_decode */, | |
116 0 /* field_set_to_one */ }; | |
117 | |
118 return &ret; | |
119 #endif | |
120 } | |
121 | |
122 | |
123 /* Most method functions in this file are designed to work with | |
124 * non-trivial representations of field elements if necessary | |
125 * (see ecp_mont.c): while standard modular addition and subtraction | |
126 * are used, the field_mul and field_sqr methods will be used for | |
127 * multiplication, and field_encode and field_decode (if defined) | |
128 * will be used for converting between representations. | |
129 | |
130 * Functions ec_GFp_simple_points_make_affine() and | |
131 * ec_GFp_simple_point_get_affine_coordinates() specifically assume | |
132 * that if a non-trivial representation is used, it is a Montgomery | |
133 * representation (i.e. 'encoding' means multiplying by some factor R). | |
134 */ | |
135 | |
136 | |
137 int ec_GFp_simple_group_init(EC_GROUP *group) | |
138 { | |
139 BN_init(&group->field); | |
140 BN_init(&group->a); | |
141 BN_init(&group->b); | |
142 group->a_is_minus3 = 0; | |
143 return 1; | |
144 } | |
145 | |
146 | |
147 void ec_GFp_simple_group_finish(EC_GROUP *group) | |
148 { | |
149 BN_free(&group->field); | |
150 BN_free(&group->a); | |
151 BN_free(&group->b); | |
152 } | |
153 | |
154 | |
155 void ec_GFp_simple_group_clear_finish(EC_GROUP *group) | |
156 { | |
157 BN_clear_free(&group->field); | |
158 BN_clear_free(&group->a); | |
159 BN_clear_free(&group->b); | |
160 } | |
161 | |
162 | |
163 int ec_GFp_simple_group_copy(EC_GROUP *dest, const EC_GROUP *src) | |
164 { | |
165 if (!BN_copy(&dest->field, &src->field)) return 0; | |
166 if (!BN_copy(&dest->a, &src->a)) return 0; | |
167 if (!BN_copy(&dest->b, &src->b)) return 0; | |
168 | |
169 dest->a_is_minus3 = src->a_is_minus3; | |
170 | |
171 return 1; | |
172 } | |
173 | |
174 | |
175 int ec_GFp_simple_group_set_curve(EC_GROUP *group, | |
176 const BIGNUM *p, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx) | |
177 { | |
178 int ret = 0; | |
179 BN_CTX *new_ctx = NULL; | |
180 BIGNUM *tmp_a; | |
181 | |
182 /* p must be a prime > 3 */ | |
183 if (BN_num_bits(p) <= 2 || !BN_is_odd(p)) | |
184 { | |
185 ECerr(EC_F_EC_GFP_SIMPLE_GROUP_SET_CURVE, EC_R_INVALID_FIELD); | |
186 return 0; | |
187 } | |
188 | |
189 if (ctx == NULL) | |
190 { | |
191 ctx = new_ctx = BN_CTX_new(); | |
192 if (ctx == NULL) | |
193 return 0; | |
194 } | |
195 | |
196 BN_CTX_start(ctx); | |
197 tmp_a = BN_CTX_get(ctx); | |
198 if (tmp_a == NULL) goto err; | |
199 | |
200 /* group->field */ | |
201 if (!BN_copy(&group->field, p)) goto err; | |
202 BN_set_negative(&group->field, 0); | |
203 | |
204 /* group->a */ | |
205 if (!BN_nnmod(tmp_a, a, p, ctx)) goto err; | |
206 if (group->meth->field_encode) | |
207 { if (!group->meth->field_encode(group, &group->a, tmp_a, ctx))
goto err; } | |
208 else | |
209 if (!BN_copy(&group->a, tmp_a)) goto err; | |
210 | |
211 /* group->b */ | |
212 if (!BN_nnmod(&group->b, b, p, ctx)) goto err; | |
213 if (group->meth->field_encode) | |
214 if (!group->meth->field_encode(group, &group->b, &group->b, ctx)
) goto err; | |
215 | |
216 /* group->a_is_minus3 */ | |
217 if (!BN_add_word(tmp_a, 3)) goto err; | |
218 group->a_is_minus3 = (0 == BN_cmp(tmp_a, &group->field)); | |
219 | |
220 ret = 1; | |
221 | |
222 err: | |
223 BN_CTX_end(ctx); | |
224 if (new_ctx != NULL) | |
225 BN_CTX_free(new_ctx); | |
226 return ret; | |
227 } | |
228 | |
229 | |
230 int ec_GFp_simple_group_get_curve(const EC_GROUP *group, BIGNUM *p, BIGNUM *a, B
IGNUM *b, BN_CTX *ctx) | |
231 { | |
232 int ret = 0; | |
233 BN_CTX *new_ctx = NULL; | |
234 | |
235 if (p != NULL) | |
236 { | |
237 if (!BN_copy(p, &group->field)) return 0; | |
238 } | |
239 | |
240 if (a != NULL || b != NULL) | |
241 { | |
242 if (group->meth->field_decode) | |
243 { | |
244 if (ctx == NULL) | |
245 { | |
246 ctx = new_ctx = BN_CTX_new(); | |
247 if (ctx == NULL) | |
248 return 0; | |
249 } | |
250 if (a != NULL) | |
251 { | |
252 if (!group->meth->field_decode(group, a, &group-
>a, ctx)) goto err; | |
253 } | |
254 if (b != NULL) | |
255 { | |
256 if (!group->meth->field_decode(group, b, &group-
>b, ctx)) goto err; | |
257 } | |
258 } | |
259 else | |
260 { | |
261 if (a != NULL) | |
262 { | |
263 if (!BN_copy(a, &group->a)) goto err; | |
264 } | |
265 if (b != NULL) | |
266 { | |
267 if (!BN_copy(b, &group->b)) goto err; | |
268 } | |
269 } | |
270 } | |
271 | |
272 ret = 1; | |
273 | |
274 err: | |
275 if (new_ctx) | |
276 BN_CTX_free(new_ctx); | |
277 return ret; | |
278 } | |
279 | |
280 | |
281 int ec_GFp_simple_group_get_degree(const EC_GROUP *group) | |
282 { | |
283 return BN_num_bits(&group->field); | |
284 } | |
285 | |
286 | |
287 int ec_GFp_simple_group_check_discriminant(const EC_GROUP *group, BN_CTX *ctx) | |
288 { | |
289 int ret = 0; | |
290 BIGNUM *a,*b,*order,*tmp_1,*tmp_2; | |
291 const BIGNUM *p = &group->field; | |
292 BN_CTX *new_ctx = NULL; | |
293 | |
294 if (ctx == NULL) | |
295 { | |
296 ctx = new_ctx = BN_CTX_new(); | |
297 if (ctx == NULL) | |
298 { | |
299 ECerr(EC_F_EC_GFP_SIMPLE_GROUP_CHECK_DISCRIMINANT, ERR_R
_MALLOC_FAILURE); | |
300 goto err; | |
301 } | |
302 } | |
303 BN_CTX_start(ctx); | |
304 a = BN_CTX_get(ctx); | |
305 b = BN_CTX_get(ctx); | |
306 tmp_1 = BN_CTX_get(ctx); | |
307 tmp_2 = BN_CTX_get(ctx); | |
308 order = BN_CTX_get(ctx); | |
309 if (order == NULL) goto err; | |
310 | |
311 if (group->meth->field_decode) | |
312 { | |
313 if (!group->meth->field_decode(group, a, &group->a, ctx)) goto e
rr; | |
314 if (!group->meth->field_decode(group, b, &group->b, ctx)) goto e
rr; | |
315 } | |
316 else | |
317 { | |
318 if (!BN_copy(a, &group->a)) goto err; | |
319 if (!BN_copy(b, &group->b)) goto err; | |
320 } | |
321 | |
322 /* check the discriminant: | |
323 * y^2 = x^3 + a*x + b is an elliptic curve <=> 4*a^3 + 27*b^2 != 0 (mod
p) | |
324 * 0 =< a, b < p */ | |
325 if (BN_is_zero(a)) | |
326 { | |
327 if (BN_is_zero(b)) goto err; | |
328 } | |
329 else if (!BN_is_zero(b)) | |
330 { | |
331 if (!BN_mod_sqr(tmp_1, a, p, ctx)) goto err; | |
332 if (!BN_mod_mul(tmp_2, tmp_1, a, p, ctx)) goto err; | |
333 if (!BN_lshift(tmp_1, tmp_2, 2)) goto err; | |
334 /* tmp_1 = 4*a^3 */ | |
335 | |
336 if (!BN_mod_sqr(tmp_2, b, p, ctx)) goto err; | |
337 if (!BN_mul_word(tmp_2, 27)) goto err; | |
338 /* tmp_2 = 27*b^2 */ | |
339 | |
340 if (!BN_mod_add(a, tmp_1, tmp_2, p, ctx)) goto err; | |
341 if (BN_is_zero(a)) goto err; | |
342 } | |
343 ret = 1; | |
344 | |
345 err: | |
346 if (ctx != NULL) | |
347 BN_CTX_end(ctx); | |
348 if (new_ctx != NULL) | |
349 BN_CTX_free(new_ctx); | |
350 return ret; | |
351 } | |
352 | |
353 | |
354 int ec_GFp_simple_point_init(EC_POINT *point) | |
355 { | |
356 BN_init(&point->X); | |
357 BN_init(&point->Y); | |
358 BN_init(&point->Z); | |
359 point->Z_is_one = 0; | |
360 | |
361 return 1; | |
362 } | |
363 | |
364 | |
365 void ec_GFp_simple_point_finish(EC_POINT *point) | |
366 { | |
367 BN_free(&point->X); | |
368 BN_free(&point->Y); | |
369 BN_free(&point->Z); | |
370 } | |
371 | |
372 | |
373 void ec_GFp_simple_point_clear_finish(EC_POINT *point) | |
374 { | |
375 BN_clear_free(&point->X); | |
376 BN_clear_free(&point->Y); | |
377 BN_clear_free(&point->Z); | |
378 point->Z_is_one = 0; | |
379 } | |
380 | |
381 | |
382 int ec_GFp_simple_point_copy(EC_POINT *dest, const EC_POINT *src) | |
383 { | |
384 if (!BN_copy(&dest->X, &src->X)) return 0; | |
385 if (!BN_copy(&dest->Y, &src->Y)) return 0; | |
386 if (!BN_copy(&dest->Z, &src->Z)) return 0; | |
387 dest->Z_is_one = src->Z_is_one; | |
388 | |
389 return 1; | |
390 } | |
391 | |
392 | |
393 int ec_GFp_simple_point_set_to_infinity(const EC_GROUP *group, EC_POINT *point) | |
394 { | |
395 point->Z_is_one = 0; | |
396 BN_zero(&point->Z); | |
397 return 1; | |
398 } | |
399 | |
400 | |
401 int ec_GFp_simple_set_Jprojective_coordinates_GFp(const EC_GROUP *group, EC_POIN
T *point, | |
402 const BIGNUM *x, const BIGNUM *y, const BIGNUM *z, BN_CTX *ctx) | |
403 { | |
404 BN_CTX *new_ctx = NULL; | |
405 int ret = 0; | |
406 | |
407 if (ctx == NULL) | |
408 { | |
409 ctx = new_ctx = BN_CTX_new(); | |
410 if (ctx == NULL) | |
411 return 0; | |
412 } | |
413 | |
414 if (x != NULL) | |
415 { | |
416 if (!BN_nnmod(&point->X, x, &group->field, ctx)) goto err; | |
417 if (group->meth->field_encode) | |
418 { | |
419 if (!group->meth->field_encode(group, &point->X, &point-
>X, ctx)) goto err; | |
420 } | |
421 } | |
422 | |
423 if (y != NULL) | |
424 { | |
425 if (!BN_nnmod(&point->Y, y, &group->field, ctx)) goto err; | |
426 if (group->meth->field_encode) | |
427 { | |
428 if (!group->meth->field_encode(group, &point->Y, &point-
>Y, ctx)) goto err; | |
429 } | |
430 } | |
431 | |
432 if (z != NULL) | |
433 { | |
434 int Z_is_one; | |
435 | |
436 if (!BN_nnmod(&point->Z, z, &group->field, ctx)) goto err; | |
437 Z_is_one = BN_is_one(&point->Z); | |
438 if (group->meth->field_encode) | |
439 { | |
440 if (Z_is_one && (group->meth->field_set_to_one != 0)) | |
441 { | |
442 if (!group->meth->field_set_to_one(group, &point
->Z, ctx)) goto err; | |
443 } | |
444 else | |
445 { | |
446 if (!group->meth->field_encode(group, &point->Z,
&point->Z, ctx)) goto err; | |
447 } | |
448 } | |
449 point->Z_is_one = Z_is_one; | |
450 } | |
451 | |
452 ret = 1; | |
453 | |
454 err: | |
455 if (new_ctx != NULL) | |
456 BN_CTX_free(new_ctx); | |
457 return ret; | |
458 } | |
459 | |
460 | |
461 int ec_GFp_simple_get_Jprojective_coordinates_GFp(const EC_GROUP *group, const E
C_POINT *point, | |
462 BIGNUM *x, BIGNUM *y, BIGNUM *z, BN_CTX *ctx) | |
463 { | |
464 BN_CTX *new_ctx = NULL; | |
465 int ret = 0; | |
466 | |
467 if (group->meth->field_decode != 0) | |
468 { | |
469 if (ctx == NULL) | |
470 { | |
471 ctx = new_ctx = BN_CTX_new(); | |
472 if (ctx == NULL) | |
473 return 0; | |
474 } | |
475 | |
476 if (x != NULL) | |
477 { | |
478 if (!group->meth->field_decode(group, x, &point->X, ctx)
) goto err; | |
479 } | |
480 if (y != NULL) | |
481 { | |
482 if (!group->meth->field_decode(group, y, &point->Y, ctx)
) goto err; | |
483 } | |
484 if (z != NULL) | |
485 { | |
486 if (!group->meth->field_decode(group, z, &point->Z, ctx)
) goto err; | |
487 } | |
488 } | |
489 else | |
490 { | |
491 if (x != NULL) | |
492 { | |
493 if (!BN_copy(x, &point->X)) goto err; | |
494 } | |
495 if (y != NULL) | |
496 { | |
497 if (!BN_copy(y, &point->Y)) goto err; | |
498 } | |
499 if (z != NULL) | |
500 { | |
501 if (!BN_copy(z, &point->Z)) goto err; | |
502 } | |
503 } | |
504 | |
505 ret = 1; | |
506 | |
507 err: | |
508 if (new_ctx != NULL) | |
509 BN_CTX_free(new_ctx); | |
510 return ret; | |
511 } | |
512 | |
513 | |
514 int ec_GFp_simple_point_set_affine_coordinates(const EC_GROUP *group, EC_POINT *
point, | |
515 const BIGNUM *x, const BIGNUM *y, BN_CTX *ctx) | |
516 { | |
517 if (x == NULL || y == NULL) | |
518 { | |
519 /* unlike for projective coordinates, we do not tolerate this */ | |
520 ECerr(EC_F_EC_GFP_SIMPLE_POINT_SET_AFFINE_COORDINATES, ERR_R_PAS
SED_NULL_PARAMETER); | |
521 return 0; | |
522 } | |
523 | |
524 return EC_POINT_set_Jprojective_coordinates_GFp(group, point, x, y, BN_v
alue_one(), ctx); | |
525 } | |
526 | |
527 | |
528 int ec_GFp_simple_point_get_affine_coordinates(const EC_GROUP *group, const EC_P
OINT *point, | |
529 BIGNUM *x, BIGNUM *y, BN_CTX *ctx) | |
530 { | |
531 BN_CTX *new_ctx = NULL; | |
532 BIGNUM *Z, *Z_1, *Z_2, *Z_3; | |
533 const BIGNUM *Z_; | |
534 int ret = 0; | |
535 | |
536 if (EC_POINT_is_at_infinity(group, point)) | |
537 { | |
538 ECerr(EC_F_EC_GFP_SIMPLE_POINT_GET_AFFINE_COORDINATES, EC_R_POIN
T_AT_INFINITY); | |
539 return 0; | |
540 } | |
541 | |
542 if (ctx == NULL) | |
543 { | |
544 ctx = new_ctx = BN_CTX_new(); | |
545 if (ctx == NULL) | |
546 return 0; | |
547 } | |
548 | |
549 BN_CTX_start(ctx); | |
550 Z = BN_CTX_get(ctx); | |
551 Z_1 = BN_CTX_get(ctx); | |
552 Z_2 = BN_CTX_get(ctx); | |
553 Z_3 = BN_CTX_get(ctx); | |
554 if (Z_3 == NULL) goto err; | |
555 | |
556 /* transform (X, Y, Z) into (x, y) := (X/Z^2, Y/Z^3) */ | |
557 | |
558 if (group->meth->field_decode) | |
559 { | |
560 if (!group->meth->field_decode(group, Z, &point->Z, ctx)) goto e
rr; | |
561 Z_ = Z; | |
562 } | |
563 else | |
564 { | |
565 Z_ = &point->Z; | |
566 } | |
567 | |
568 if (BN_is_one(Z_)) | |
569 { | |
570 if (group->meth->field_decode) | |
571 { | |
572 if (x != NULL) | |
573 { | |
574 if (!group->meth->field_decode(group, x, &point-
>X, ctx)) goto err; | |
575 } | |
576 if (y != NULL) | |
577 { | |
578 if (!group->meth->field_decode(group, y, &point-
>Y, ctx)) goto err; | |
579 } | |
580 } | |
581 else | |
582 { | |
583 if (x != NULL) | |
584 { | |
585 if (!BN_copy(x, &point->X)) goto err; | |
586 } | |
587 if (y != NULL) | |
588 { | |
589 if (!BN_copy(y, &point->Y)) goto err; | |
590 } | |
591 } | |
592 } | |
593 else | |
594 { | |
595 if (!BN_mod_inverse(Z_1, Z_, &group->field, ctx)) | |
596 { | |
597 ECerr(EC_F_EC_GFP_SIMPLE_POINT_GET_AFFINE_COORDINATES, E
RR_R_BN_LIB); | |
598 goto err; | |
599 } | |
600 | |
601 if (group->meth->field_encode == 0) | |
602 { | |
603 /* field_sqr works on standard representation */ | |
604 if (!group->meth->field_sqr(group, Z_2, Z_1, ctx)) goto
err; | |
605 } | |
606 else | |
607 { | |
608 if (!BN_mod_sqr(Z_2, Z_1, &group->field, ctx)) goto err; | |
609 } | |
610 | |
611 if (x != NULL) | |
612 { | |
613 /* in the Montgomery case, field_mul will cancel out Mon
tgomery factor in X: */ | |
614 if (!group->meth->field_mul(group, x, &point->X, Z_2, ct
x)) goto err; | |
615 } | |
616 | |
617 if (y != NULL) | |
618 { | |
619 if (group->meth->field_encode == 0) | |
620 { | |
621 /* field_mul works on standard representation */ | |
622 if (!group->meth->field_mul(group, Z_3, Z_2, Z_1
, ctx)) goto err; | |
623 } | |
624 else | |
625 { | |
626 if (!BN_mod_mul(Z_3, Z_2, Z_1, &group->field, ct
x)) goto err; | |
627 } | |
628 | |
629 /* in the Montgomery case, field_mul will cancel out Mon
tgomery factor in Y: */ | |
630 if (!group->meth->field_mul(group, y, &point->Y, Z_3, ct
x)) goto err; | |
631 } | |
632 } | |
633 | |
634 ret = 1; | |
635 | |
636 err: | |
637 BN_CTX_end(ctx); | |
638 if (new_ctx != NULL) | |
639 BN_CTX_free(new_ctx); | |
640 return ret; | |
641 } | |
642 | |
643 int ec_GFp_simple_add(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a, con
st EC_POINT *b, BN_CTX *ctx) | |
644 { | |
645 int (*field_mul)(const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNU
M *, BN_CTX *); | |
646 int (*field_sqr)(const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *); | |
647 const BIGNUM *p; | |
648 BN_CTX *new_ctx = NULL; | |
649 BIGNUM *n0, *n1, *n2, *n3, *n4, *n5, *n6; | |
650 int ret = 0; | |
651 | |
652 if (a == b) | |
653 return EC_POINT_dbl(group, r, a, ctx); | |
654 if (EC_POINT_is_at_infinity(group, a)) | |
655 return EC_POINT_copy(r, b); | |
656 if (EC_POINT_is_at_infinity(group, b)) | |
657 return EC_POINT_copy(r, a); | |
658 | |
659 field_mul = group->meth->field_mul; | |
660 field_sqr = group->meth->field_sqr; | |
661 p = &group->field; | |
662 | |
663 if (ctx == NULL) | |
664 { | |
665 ctx = new_ctx = BN_CTX_new(); | |
666 if (ctx == NULL) | |
667 return 0; | |
668 } | |
669 | |
670 BN_CTX_start(ctx); | |
671 n0 = BN_CTX_get(ctx); | |
672 n1 = BN_CTX_get(ctx); | |
673 n2 = BN_CTX_get(ctx); | |
674 n3 = BN_CTX_get(ctx); | |
675 n4 = BN_CTX_get(ctx); | |
676 n5 = BN_CTX_get(ctx); | |
677 n6 = BN_CTX_get(ctx); | |
678 if (n6 == NULL) goto end; | |
679 | |
680 /* Note that in this function we must not read components of 'a' or 'b' | |
681 * once we have written the corresponding components of 'r'. | |
682 * ('r' might be one of 'a' or 'b'.) | |
683 */ | |
684 | |
685 /* n1, n2 */ | |
686 if (b->Z_is_one) | |
687 { | |
688 if (!BN_copy(n1, &a->X)) goto end; | |
689 if (!BN_copy(n2, &a->Y)) goto end; | |
690 /* n1 = X_a */ | |
691 /* n2 = Y_a */ | |
692 } | |
693 else | |
694 { | |
695 if (!field_sqr(group, n0, &b->Z, ctx)) goto end; | |
696 if (!field_mul(group, n1, &a->X, n0, ctx)) goto end; | |
697 /* n1 = X_a * Z_b^2 */ | |
698 | |
699 if (!field_mul(group, n0, n0, &b->Z, ctx)) goto end; | |
700 if (!field_mul(group, n2, &a->Y, n0, ctx)) goto end; | |
701 /* n2 = Y_a * Z_b^3 */ | |
702 } | |
703 | |
704 /* n3, n4 */ | |
705 if (a->Z_is_one) | |
706 { | |
707 if (!BN_copy(n3, &b->X)) goto end; | |
708 if (!BN_copy(n4, &b->Y)) goto end; | |
709 /* n3 = X_b */ | |
710 /* n4 = Y_b */ | |
711 } | |
712 else | |
713 { | |
714 if (!field_sqr(group, n0, &a->Z, ctx)) goto end; | |
715 if (!field_mul(group, n3, &b->X, n0, ctx)) goto end; | |
716 /* n3 = X_b * Z_a^2 */ | |
717 | |
718 if (!field_mul(group, n0, n0, &a->Z, ctx)) goto end; | |
719 if (!field_mul(group, n4, &b->Y, n0, ctx)) goto end; | |
720 /* n4 = Y_b * Z_a^3 */ | |
721 } | |
722 | |
723 /* n5, n6 */ | |
724 if (!BN_mod_sub_quick(n5, n1, n3, p)) goto end; | |
725 if (!BN_mod_sub_quick(n6, n2, n4, p)) goto end; | |
726 /* n5 = n1 - n3 */ | |
727 /* n6 = n2 - n4 */ | |
728 | |
729 if (BN_is_zero(n5)) | |
730 { | |
731 if (BN_is_zero(n6)) | |
732 { | |
733 /* a is the same point as b */ | |
734 BN_CTX_end(ctx); | |
735 ret = EC_POINT_dbl(group, r, a, ctx); | |
736 ctx = NULL; | |
737 goto end; | |
738 } | |
739 else | |
740 { | |
741 /* a is the inverse of b */ | |
742 BN_zero(&r->Z); | |
743 r->Z_is_one = 0; | |
744 ret = 1; | |
745 goto end; | |
746 } | |
747 } | |
748 | |
749 /* 'n7', 'n8' */ | |
750 if (!BN_mod_add_quick(n1, n1, n3, p)) goto end; | |
751 if (!BN_mod_add_quick(n2, n2, n4, p)) goto end; | |
752 /* 'n7' = n1 + n3 */ | |
753 /* 'n8' = n2 + n4 */ | |
754 | |
755 /* Z_r */ | |
756 if (a->Z_is_one && b->Z_is_one) | |
757 { | |
758 if (!BN_copy(&r->Z, n5)) goto end; | |
759 } | |
760 else | |
761 { | |
762 if (a->Z_is_one) | |
763 { if (!BN_copy(n0, &b->Z)) goto end; } | |
764 else if (b->Z_is_one) | |
765 { if (!BN_copy(n0, &a->Z)) goto end; } | |
766 else | |
767 { if (!field_mul(group, n0, &a->Z, &b->Z, ctx)) goto end
; } | |
768 if (!field_mul(group, &r->Z, n0, n5, ctx)) goto end; | |
769 } | |
770 r->Z_is_one = 0; | |
771 /* Z_r = Z_a * Z_b * n5 */ | |
772 | |
773 /* X_r */ | |
774 if (!field_sqr(group, n0, n6, ctx)) goto end; | |
775 if (!field_sqr(group, n4, n5, ctx)) goto end; | |
776 if (!field_mul(group, n3, n1, n4, ctx)) goto end; | |
777 if (!BN_mod_sub_quick(&r->X, n0, n3, p)) goto end; | |
778 /* X_r = n6^2 - n5^2 * 'n7' */ | |
779 | |
780 /* 'n9' */ | |
781 if (!BN_mod_lshift1_quick(n0, &r->X, p)) goto end; | |
782 if (!BN_mod_sub_quick(n0, n3, n0, p)) goto end; | |
783 /* n9 = n5^2 * 'n7' - 2 * X_r */ | |
784 | |
785 /* Y_r */ | |
786 if (!field_mul(group, n0, n0, n6, ctx)) goto end; | |
787 if (!field_mul(group, n5, n4, n5, ctx)) goto end; /* now n5 is n5^3 */ | |
788 if (!field_mul(group, n1, n2, n5, ctx)) goto end; | |
789 if (!BN_mod_sub_quick(n0, n0, n1, p)) goto end; | |
790 if (BN_is_odd(n0)) | |
791 if (!BN_add(n0, n0, p)) goto end; | |
792 /* now 0 <= n0 < 2*p, and n0 is even */ | |
793 if (!BN_rshift1(&r->Y, n0)) goto end; | |
794 /* Y_r = (n6 * 'n9' - 'n8' * 'n5^3') / 2 */ | |
795 | |
796 ret = 1; | |
797 | |
798 end: | |
799 if (ctx) /* otherwise we already called BN_CTX_end */ | |
800 BN_CTX_end(ctx); | |
801 if (new_ctx != NULL) | |
802 BN_CTX_free(new_ctx); | |
803 return ret; | |
804 } | |
805 | |
806 | |
807 int ec_GFp_simple_dbl(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a, BN_
CTX *ctx) | |
808 { | |
809 int (*field_mul)(const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNU
M *, BN_CTX *); | |
810 int (*field_sqr)(const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *); | |
811 const BIGNUM *p; | |
812 BN_CTX *new_ctx = NULL; | |
813 BIGNUM *n0, *n1, *n2, *n3; | |
814 int ret = 0; | |
815 | |
816 if (EC_POINT_is_at_infinity(group, a)) | |
817 { | |
818 BN_zero(&r->Z); | |
819 r->Z_is_one = 0; | |
820 return 1; | |
821 } | |
822 | |
823 field_mul = group->meth->field_mul; | |
824 field_sqr = group->meth->field_sqr; | |
825 p = &group->field; | |
826 | |
827 if (ctx == NULL) | |
828 { | |
829 ctx = new_ctx = BN_CTX_new(); | |
830 if (ctx == NULL) | |
831 return 0; | |
832 } | |
833 | |
834 BN_CTX_start(ctx); | |
835 n0 = BN_CTX_get(ctx); | |
836 n1 = BN_CTX_get(ctx); | |
837 n2 = BN_CTX_get(ctx); | |
838 n3 = BN_CTX_get(ctx); | |
839 if (n3 == NULL) goto err; | |
840 | |
841 /* Note that in this function we must not read components of 'a' | |
842 * once we have written the corresponding components of 'r'. | |
843 * ('r' might the same as 'a'.) | |
844 */ | |
845 | |
846 /* n1 */ | |
847 if (a->Z_is_one) | |
848 { | |
849 if (!field_sqr(group, n0, &a->X, ctx)) goto err; | |
850 if (!BN_mod_lshift1_quick(n1, n0, p)) goto err; | |
851 if (!BN_mod_add_quick(n0, n0, n1, p)) goto err; | |
852 if (!BN_mod_add_quick(n1, n0, &group->a, p)) goto err; | |
853 /* n1 = 3 * X_a^2 + a_curve */ | |
854 } | |
855 else if (group->a_is_minus3) | |
856 { | |
857 if (!field_sqr(group, n1, &a->Z, ctx)) goto err; | |
858 if (!BN_mod_add_quick(n0, &a->X, n1, p)) goto err; | |
859 if (!BN_mod_sub_quick(n2, &a->X, n1, p)) goto err; | |
860 if (!field_mul(group, n1, n0, n2, ctx)) goto err; | |
861 if (!BN_mod_lshift1_quick(n0, n1, p)) goto err; | |
862 if (!BN_mod_add_quick(n1, n0, n1, p)) goto err; | |
863 /* n1 = 3 * (X_a + Z_a^2) * (X_a - Z_a^2) | |
864 * = 3 * X_a^2 - 3 * Z_a^4 */ | |
865 } | |
866 else | |
867 { | |
868 if (!field_sqr(group, n0, &a->X, ctx)) goto err; | |
869 if (!BN_mod_lshift1_quick(n1, n0, p)) goto err; | |
870 if (!BN_mod_add_quick(n0, n0, n1, p)) goto err; | |
871 if (!field_sqr(group, n1, &a->Z, ctx)) goto err; | |
872 if (!field_sqr(group, n1, n1, ctx)) goto err; | |
873 if (!field_mul(group, n1, n1, &group->a, ctx)) goto err; | |
874 if (!BN_mod_add_quick(n1, n1, n0, p)) goto err; | |
875 /* n1 = 3 * X_a^2 + a_curve * Z_a^4 */ | |
876 } | |
877 | |
878 /* Z_r */ | |
879 if (a->Z_is_one) | |
880 { | |
881 if (!BN_copy(n0, &a->Y)) goto err; | |
882 } | |
883 else | |
884 { | |
885 if (!field_mul(group, n0, &a->Y, &a->Z, ctx)) goto err; | |
886 } | |
887 if (!BN_mod_lshift1_quick(&r->Z, n0, p)) goto err; | |
888 r->Z_is_one = 0; | |
889 /* Z_r = 2 * Y_a * Z_a */ | |
890 | |
891 /* n2 */ | |
892 if (!field_sqr(group, n3, &a->Y, ctx)) goto err; | |
893 if (!field_mul(group, n2, &a->X, n3, ctx)) goto err; | |
894 if (!BN_mod_lshift_quick(n2, n2, 2, p)) goto err; | |
895 /* n2 = 4 * X_a * Y_a^2 */ | |
896 | |
897 /* X_r */ | |
898 if (!BN_mod_lshift1_quick(n0, n2, p)) goto err; | |
899 if (!field_sqr(group, &r->X, n1, ctx)) goto err; | |
900 if (!BN_mod_sub_quick(&r->X, &r->X, n0, p)) goto err; | |
901 /* X_r = n1^2 - 2 * n2 */ | |
902 | |
903 /* n3 */ | |
904 if (!field_sqr(group, n0, n3, ctx)) goto err; | |
905 if (!BN_mod_lshift_quick(n3, n0, 3, p)) goto err; | |
906 /* n3 = 8 * Y_a^4 */ | |
907 | |
908 /* Y_r */ | |
909 if (!BN_mod_sub_quick(n0, n2, &r->X, p)) goto err; | |
910 if (!field_mul(group, n0, n1, n0, ctx)) goto err; | |
911 if (!BN_mod_sub_quick(&r->Y, n0, n3, p)) goto err; | |
912 /* Y_r = n1 * (n2 - X_r) - n3 */ | |
913 | |
914 ret = 1; | |
915 | |
916 err: | |
917 BN_CTX_end(ctx); | |
918 if (new_ctx != NULL) | |
919 BN_CTX_free(new_ctx); | |
920 return ret; | |
921 } | |
922 | |
923 | |
924 int ec_GFp_simple_invert(const EC_GROUP *group, EC_POINT *point, BN_CTX *ctx) | |
925 { | |
926 if (EC_POINT_is_at_infinity(group, point) || BN_is_zero(&point->Y)) | |
927 /* point is its own inverse */ | |
928 return 1; | |
929 | |
930 return BN_usub(&point->Y, &group->field, &point->Y); | |
931 } | |
932 | |
933 | |
934 int ec_GFp_simple_is_at_infinity(const EC_GROUP *group, const EC_POINT *point) | |
935 { | |
936 return BN_is_zero(&point->Z); | |
937 } | |
938 | |
939 | |
940 int ec_GFp_simple_is_on_curve(const EC_GROUP *group, const EC_POINT *point, BN_C
TX *ctx) | |
941 { | |
942 int (*field_mul)(const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNU
M *, BN_CTX *); | |
943 int (*field_sqr)(const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *); | |
944 const BIGNUM *p; | |
945 BN_CTX *new_ctx = NULL; | |
946 BIGNUM *rh, *tmp, *Z4, *Z6; | |
947 int ret = -1; | |
948 | |
949 if (EC_POINT_is_at_infinity(group, point)) | |
950 return 1; | |
951 | |
952 field_mul = group->meth->field_mul; | |
953 field_sqr = group->meth->field_sqr; | |
954 p = &group->field; | |
955 | |
956 if (ctx == NULL) | |
957 { | |
958 ctx = new_ctx = BN_CTX_new(); | |
959 if (ctx == NULL) | |
960 return -1; | |
961 } | |
962 | |
963 BN_CTX_start(ctx); | |
964 rh = BN_CTX_get(ctx); | |
965 tmp = BN_CTX_get(ctx); | |
966 Z4 = BN_CTX_get(ctx); | |
967 Z6 = BN_CTX_get(ctx); | |
968 if (Z6 == NULL) goto err; | |
969 | |
970 /* We have a curve defined by a Weierstrass equation | |
971 * y^2 = x^3 + a*x + b. | |
972 * The point to consider is given in Jacobian projective coordinates | |
973 * where (X, Y, Z) represents (x, y) = (X/Z^2, Y/Z^3). | |
974 * Substituting this and multiplying by Z^6 transforms the above equat
ion into | |
975 * Y^2 = X^3 + a*X*Z^4 + b*Z^6. | |
976 * To test this, we add up the right-hand side in 'rh'. | |
977 */ | |
978 | |
979 /* rh := X^2 */ | |
980 if (!field_sqr(group, rh, &point->X, ctx)) goto err; | |
981 | |
982 if (!point->Z_is_one) | |
983 { | |
984 if (!field_sqr(group, tmp, &point->Z, ctx)) goto err; | |
985 if (!field_sqr(group, Z4, tmp, ctx)) goto err; | |
986 if (!field_mul(group, Z6, Z4, tmp, ctx)) goto err; | |
987 | |
988 /* rh := (rh + a*Z^4)*X */ | |
989 if (group->a_is_minus3) | |
990 { | |
991 if (!BN_mod_lshift1_quick(tmp, Z4, p)) goto err; | |
992 if (!BN_mod_add_quick(tmp, tmp, Z4, p)) goto err; | |
993 if (!BN_mod_sub_quick(rh, rh, tmp, p)) goto err; | |
994 if (!field_mul(group, rh, rh, &point->X, ctx)) goto err; | |
995 } | |
996 else | |
997 { | |
998 if (!field_mul(group, tmp, Z4, &group->a, ctx)) goto err
; | |
999 if (!BN_mod_add_quick(rh, rh, tmp, p)) goto err; | |
1000 if (!field_mul(group, rh, rh, &point->X, ctx)) goto err; | |
1001 } | |
1002 | |
1003 /* rh := rh + b*Z^6 */ | |
1004 if (!field_mul(group, tmp, &group->b, Z6, ctx)) goto err; | |
1005 if (!BN_mod_add_quick(rh, rh, tmp, p)) goto err; | |
1006 } | |
1007 else | |
1008 { | |
1009 /* point->Z_is_one */ | |
1010 | |
1011 /* rh := (rh + a)*X */ | |
1012 if (!BN_mod_add_quick(rh, rh, &group->a, p)) goto err; | |
1013 if (!field_mul(group, rh, rh, &point->X, ctx)) goto err; | |
1014 /* rh := rh + b */ | |
1015 if (!BN_mod_add_quick(rh, rh, &group->b, p)) goto err; | |
1016 } | |
1017 | |
1018 /* 'lh' := Y^2 */ | |
1019 if (!field_sqr(group, tmp, &point->Y, ctx)) goto err; | |
1020 | |
1021 ret = (0 == BN_ucmp(tmp, rh)); | |
1022 | |
1023 err: | |
1024 BN_CTX_end(ctx); | |
1025 if (new_ctx != NULL) | |
1026 BN_CTX_free(new_ctx); | |
1027 return ret; | |
1028 } | |
1029 | |
1030 | |
1031 int ec_GFp_simple_cmp(const EC_GROUP *group, const EC_POINT *a, const EC_POINT *
b, BN_CTX *ctx) | |
1032 { | |
1033 /* return values: | |
1034 * -1 error | |
1035 * 0 equal (in affine coordinates) | |
1036 * 1 not equal | |
1037 */ | |
1038 | |
1039 int (*field_mul)(const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNU
M *, BN_CTX *); | |
1040 int (*field_sqr)(const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *); | |
1041 BN_CTX *new_ctx = NULL; | |
1042 BIGNUM *tmp1, *tmp2, *Za23, *Zb23; | |
1043 const BIGNUM *tmp1_, *tmp2_; | |
1044 int ret = -1; | |
1045 | |
1046 if (EC_POINT_is_at_infinity(group, a)) | |
1047 { | |
1048 return EC_POINT_is_at_infinity(group, b) ? 0 : 1; | |
1049 } | |
1050 | |
1051 if (EC_POINT_is_at_infinity(group, b)) | |
1052 return 1; | |
1053 | |
1054 if (a->Z_is_one && b->Z_is_one) | |
1055 { | |
1056 return ((BN_cmp(&a->X, &b->X) == 0) && BN_cmp(&a->Y, &b->Y) == 0
) ? 0 : 1; | |
1057 } | |
1058 | |
1059 field_mul = group->meth->field_mul; | |
1060 field_sqr = group->meth->field_sqr; | |
1061 | |
1062 if (ctx == NULL) | |
1063 { | |
1064 ctx = new_ctx = BN_CTX_new(); | |
1065 if (ctx == NULL) | |
1066 return -1; | |
1067 } | |
1068 | |
1069 BN_CTX_start(ctx); | |
1070 tmp1 = BN_CTX_get(ctx); | |
1071 tmp2 = BN_CTX_get(ctx); | |
1072 Za23 = BN_CTX_get(ctx); | |
1073 Zb23 = BN_CTX_get(ctx); | |
1074 if (Zb23 == NULL) goto end; | |
1075 | |
1076 /* We have to decide whether | |
1077 * (X_a/Z_a^2, Y_a/Z_a^3) = (X_b/Z_b^2, Y_b/Z_b^3), | |
1078 * or equivalently, whether | |
1079 * (X_a*Z_b^2, Y_a*Z_b^3) = (X_b*Z_a^2, Y_b*Z_a^3). | |
1080 */ | |
1081 | |
1082 if (!b->Z_is_one) | |
1083 { | |
1084 if (!field_sqr(group, Zb23, &b->Z, ctx)) goto end; | |
1085 if (!field_mul(group, tmp1, &a->X, Zb23, ctx)) goto end; | |
1086 tmp1_ = tmp1; | |
1087 } | |
1088 else | |
1089 tmp1_ = &a->X; | |
1090 if (!a->Z_is_one) | |
1091 { | |
1092 if (!field_sqr(group, Za23, &a->Z, ctx)) goto end; | |
1093 if (!field_mul(group, tmp2, &b->X, Za23, ctx)) goto end; | |
1094 tmp2_ = tmp2; | |
1095 } | |
1096 else | |
1097 tmp2_ = &b->X; | |
1098 | |
1099 /* compare X_a*Z_b^2 with X_b*Z_a^2 */ | |
1100 if (BN_cmp(tmp1_, tmp2_) != 0) | |
1101 { | |
1102 ret = 1; /* points differ */ | |
1103 goto end; | |
1104 } | |
1105 | |
1106 | |
1107 if (!b->Z_is_one) | |
1108 { | |
1109 if (!field_mul(group, Zb23, Zb23, &b->Z, ctx)) goto end; | |
1110 if (!field_mul(group, tmp1, &a->Y, Zb23, ctx)) goto end; | |
1111 /* tmp1_ = tmp1 */ | |
1112 } | |
1113 else | |
1114 tmp1_ = &a->Y; | |
1115 if (!a->Z_is_one) | |
1116 { | |
1117 if (!field_mul(group, Za23, Za23, &a->Z, ctx)) goto end; | |
1118 if (!field_mul(group, tmp2, &b->Y, Za23, ctx)) goto end; | |
1119 /* tmp2_ = tmp2 */ | |
1120 } | |
1121 else | |
1122 tmp2_ = &b->Y; | |
1123 | |
1124 /* compare Y_a*Z_b^3 with Y_b*Z_a^3 */ | |
1125 if (BN_cmp(tmp1_, tmp2_) != 0) | |
1126 { | |
1127 ret = 1; /* points differ */ | |
1128 goto end; | |
1129 } | |
1130 | |
1131 /* points are equal */ | |
1132 ret = 0; | |
1133 | |
1134 end: | |
1135 BN_CTX_end(ctx); | |
1136 if (new_ctx != NULL) | |
1137 BN_CTX_free(new_ctx); | |
1138 return ret; | |
1139 } | |
1140 | |
1141 | |
1142 int ec_GFp_simple_make_affine(const EC_GROUP *group, EC_POINT *point, BN_CTX *ct
x) | |
1143 { | |
1144 BN_CTX *new_ctx = NULL; | |
1145 BIGNUM *x, *y; | |
1146 int ret = 0; | |
1147 | |
1148 if (point->Z_is_one || EC_POINT_is_at_infinity(group, point)) | |
1149 return 1; | |
1150 | |
1151 if (ctx == NULL) | |
1152 { | |
1153 ctx = new_ctx = BN_CTX_new(); | |
1154 if (ctx == NULL) | |
1155 return 0; | |
1156 } | |
1157 | |
1158 BN_CTX_start(ctx); | |
1159 x = BN_CTX_get(ctx); | |
1160 y = BN_CTX_get(ctx); | |
1161 if (y == NULL) goto err; | |
1162 | |
1163 if (!EC_POINT_get_affine_coordinates_GFp(group, point, x, y, ctx)) goto
err; | |
1164 if (!EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx)) goto
err; | |
1165 if (!point->Z_is_one) | |
1166 { | |
1167 ECerr(EC_F_EC_GFP_SIMPLE_MAKE_AFFINE, ERR_R_INTERNAL_ERROR); | |
1168 goto err; | |
1169 } | |
1170 | |
1171 ret = 1; | |
1172 | |
1173 err: | |
1174 BN_CTX_end(ctx); | |
1175 if (new_ctx != NULL) | |
1176 BN_CTX_free(new_ctx); | |
1177 return ret; | |
1178 } | |
1179 | |
1180 | |
1181 int ec_GFp_simple_points_make_affine(const EC_GROUP *group, size_t num, EC_POINT
*points[], BN_CTX *ctx) | |
1182 { | |
1183 BN_CTX *new_ctx = NULL; | |
1184 BIGNUM *tmp0, *tmp1; | |
1185 size_t pow2 = 0; | |
1186 BIGNUM **heap = NULL; | |
1187 size_t i; | |
1188 int ret = 0; | |
1189 | |
1190 if (num == 0) | |
1191 return 1; | |
1192 | |
1193 if (ctx == NULL) | |
1194 { | |
1195 ctx = new_ctx = BN_CTX_new(); | |
1196 if (ctx == NULL) | |
1197 return 0; | |
1198 } | |
1199 | |
1200 BN_CTX_start(ctx); | |
1201 tmp0 = BN_CTX_get(ctx); | |
1202 tmp1 = BN_CTX_get(ctx); | |
1203 if (tmp0 == NULL || tmp1 == NULL) goto err; | |
1204 | |
1205 /* Before converting the individual points, compute inverses of all Z va
lues. | |
1206 * Modular inversion is rather slow, but luckily we can do with a single | |
1207 * explicit inversion, plus about 3 multiplications per input value. | |
1208 */ | |
1209 | |
1210 pow2 = 1; | |
1211 while (num > pow2) | |
1212 pow2 <<= 1; | |
1213 /* Now pow2 is the smallest power of 2 satifsying pow2 >= num. | |
1214 * We need twice that. */ | |
1215 pow2 <<= 1; | |
1216 | |
1217 heap = OPENSSL_malloc(pow2 * sizeof heap[0]); | |
1218 if (heap == NULL) goto err; | |
1219 | |
1220 /* The array is used as a binary tree, exactly as in heapsort: | |
1221 * | |
1222 * heap[1] | |
1223 * heap[2] heap[3] | |
1224 * heap[4] heap[5] heap[6] heap[7] | |
1225 * heap[8]heap[9] heap[10]heap[11] heap[12]heap[13] heap[14] heap[15] | |
1226 * | |
1227 * We put the Z's in the last line; | |
1228 * then we set each other node to the product of its two child-nodes (wh
ere | |
1229 * empty or 0 entries are treated as ones); | |
1230 * then we invert heap[1]; | |
1231 * then we invert each other node by replacing it by the product of its | |
1232 * parent (after inversion) and its sibling (before inversion). | |
1233 */ | |
1234 heap[0] = NULL; | |
1235 for (i = pow2/2 - 1; i > 0; i--) | |
1236 heap[i] = NULL; | |
1237 for (i = 0; i < num; i++) | |
1238 heap[pow2/2 + i] = &points[i]->Z; | |
1239 for (i = pow2/2 + num; i < pow2; i++) | |
1240 heap[i] = NULL; | |
1241 | |
1242 /* set each node to the product of its children */ | |
1243 for (i = pow2/2 - 1; i > 0; i--) | |
1244 { | |
1245 heap[i] = BN_new(); | |
1246 if (heap[i] == NULL) goto err; | |
1247 | |
1248 if (heap[2*i] != NULL) | |
1249 { | |
1250 if ((heap[2*i + 1] == NULL) || BN_is_zero(heap[2*i + 1])
) | |
1251 { | |
1252 if (!BN_copy(heap[i], heap[2*i])) goto err; | |
1253 } | |
1254 else | |
1255 { | |
1256 if (BN_is_zero(heap[2*i])) | |
1257 { | |
1258 if (!BN_copy(heap[i], heap[2*i + 1])) go
to err; | |
1259 } | |
1260 else | |
1261 { | |
1262 if (!group->meth->field_mul(group, heap[
i], | |
1263 heap[2*i], heap[2*i + 1], ctx))
goto err; | |
1264 } | |
1265 } | |
1266 } | |
1267 } | |
1268 | |
1269 /* invert heap[1] */ | |
1270 if (!BN_is_zero(heap[1])) | |
1271 { | |
1272 if (!BN_mod_inverse(heap[1], heap[1], &group->field, ctx)) | |
1273 { | |
1274 ECerr(EC_F_EC_GFP_SIMPLE_POINTS_MAKE_AFFINE, ERR_R_BN_LI
B); | |
1275 goto err; | |
1276 } | |
1277 } | |
1278 if (group->meth->field_encode != 0) | |
1279 { | |
1280 /* in the Montgomery case, we just turned R*H (representing H) | |
1281 * into 1/(R*H), but we need R*(1/H) (representing 1/H); | |
1282 * i.e. we have need to multiply by the Montgomery factor twice
*/ | |
1283 if (!group->meth->field_encode(group, heap[1], heap[1], ctx)) go
to err; | |
1284 if (!group->meth->field_encode(group, heap[1], heap[1], ctx)) go
to err; | |
1285 } | |
1286 | |
1287 /* set other heap[i]'s to their inverses */ | |
1288 for (i = 2; i < pow2/2 + num; i += 2) | |
1289 { | |
1290 /* i is even */ | |
1291 if ((heap[i + 1] != NULL) && !BN_is_zero(heap[i + 1])) | |
1292 { | |
1293 if (!group->meth->field_mul(group, tmp0, heap[i/2], heap
[i + 1], ctx)) goto err; | |
1294 if (!group->meth->field_mul(group, tmp1, heap[i/2], heap
[i], ctx)) goto err; | |
1295 if (!BN_copy(heap[i], tmp0)) goto err; | |
1296 if (!BN_copy(heap[i + 1], tmp1)) goto err; | |
1297 } | |
1298 else | |
1299 { | |
1300 if (!BN_copy(heap[i], heap[i/2])) goto err; | |
1301 } | |
1302 } | |
1303 | |
1304 /* we have replaced all non-zero Z's by their inverses, now fix up all t
he points */ | |
1305 for (i = 0; i < num; i++) | |
1306 { | |
1307 EC_POINT *p = points[i]; | |
1308 | |
1309 if (!BN_is_zero(&p->Z)) | |
1310 { | |
1311 /* turn (X, Y, 1/Z) into (X/Z^2, Y/Z^3, 1) */ | |
1312 | |
1313 if (!group->meth->field_sqr(group, tmp1, &p->Z, ctx)) go
to err; | |
1314 if (!group->meth->field_mul(group, &p->X, &p->X, tmp1, c
tx)) goto err; | |
1315 | |
1316 if (!group->meth->field_mul(group, tmp1, tmp1, &p->Z, ct
x)) goto err; | |
1317 if (!group->meth->field_mul(group, &p->Y, &p->Y, tmp1, c
tx)) goto err; | |
1318 | |
1319 if (group->meth->field_set_to_one != 0) | |
1320 { | |
1321 if (!group->meth->field_set_to_one(group, &p->Z,
ctx)) goto err; | |
1322 } | |
1323 else | |
1324 { | |
1325 if (!BN_one(&p->Z)) goto err; | |
1326 } | |
1327 p->Z_is_one = 1; | |
1328 } | |
1329 } | |
1330 | |
1331 ret = 1; | |
1332 | |
1333 err: | |
1334 BN_CTX_end(ctx); | |
1335 if (new_ctx != NULL) | |
1336 BN_CTX_free(new_ctx); | |
1337 if (heap != NULL) | |
1338 { | |
1339 /* heap[pow2/2] .. heap[pow2-1] have not been allocated locally!
*/ | |
1340 for (i = pow2/2 - 1; i > 0; i--) | |
1341 { | |
1342 if (heap[i] != NULL) | |
1343 BN_clear_free(heap[i]); | |
1344 } | |
1345 OPENSSL_free(heap); | |
1346 } | |
1347 return ret; | |
1348 } | |
1349 | |
1350 | |
1351 int ec_GFp_simple_field_mul(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, c
onst BIGNUM *b, BN_CTX *ctx) | |
1352 { | |
1353 return BN_mod_mul(r, a, b, &group->field, ctx); | |
1354 } | |
1355 | |
1356 | |
1357 int ec_GFp_simple_field_sqr(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, B
N_CTX *ctx) | |
1358 { | |
1359 return BN_mod_sqr(r, a, &group->field, ctx); | |
1360 } | |
OLD | NEW |