OLD | NEW |
1 /* crypto/ec/ec2_smpl.c */ | 1 /* crypto/ec/ec2_smpl.c */ |
2 /* ==================================================================== | 2 /* ==================================================================== |
3 * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED. | 3 * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED. |
4 * | 4 * |
5 * The Elliptic Curve Public-Key Crypto Library (ECC Code) included | 5 * The Elliptic Curve Public-Key Crypto Library (ECC Code) included |
6 * herein is developed by SUN MICROSYSTEMS, INC., and is contributed | 6 * herein is developed by SUN MICROSYSTEMS, INC., and is contributed |
7 * to the OpenSSL project. | 7 * to the OpenSSL project. |
8 * | 8 * |
9 * The ECC Code is licensed pursuant to the OpenSSL open source | 9 * The ECC Code is licensed pursuant to the OpenSSL open source |
10 * license provided below. | 10 * license provided below. |
11 * | 11 * |
12 * The software is originally written by Sheueling Chang Shantz and | 12 * The software is originally written by Sheueling Chang Shantz and |
13 * Douglas Stebila of Sun Microsystems Laboratories. | 13 * Douglas Stebila of Sun Microsystems Laboratories. |
14 * | 14 * |
15 */ | 15 */ |
16 /* ==================================================================== | 16 /* ==================================================================== |
17 * Copyright (c) 1998-2003 The OpenSSL Project. All rights reserved. | 17 * Copyright (c) 1998-2005 The OpenSSL Project. All rights reserved. |
18 * | 18 * |
19 * Redistribution and use in source and binary forms, with or without | 19 * Redistribution and use in source and binary forms, with or without |
20 * modification, are permitted provided that the following conditions | 20 * modification, are permitted provided that the following conditions |
21 * are met: | 21 * are met: |
22 * | 22 * |
23 * 1. Redistributions of source code must retain the above copyright | 23 * 1. Redistributions of source code must retain the above copyright |
24 * notice, this list of conditions and the following disclaimer. | 24 * notice, this list of conditions and the following disclaimer. |
25 * | 25 * |
26 * 2. Redistributions in binary form must reproduce the above copyright | 26 * 2. Redistributions in binary form must reproduce the above copyright |
27 * notice, this list of conditions and the following disclaimer in | 27 * notice, this list of conditions and the following disclaimer in |
(...skipping 122 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
150 void ec_GF2m_simple_group_clear_finish(EC_GROUP *group) | 150 void ec_GF2m_simple_group_clear_finish(EC_GROUP *group) |
151 { | 151 { |
152 BN_clear_free(&group->field); | 152 BN_clear_free(&group->field); |
153 BN_clear_free(&group->a); | 153 BN_clear_free(&group->a); |
154 BN_clear_free(&group->b); | 154 BN_clear_free(&group->b); |
155 group->poly[0] = 0; | 155 group->poly[0] = 0; |
156 group->poly[1] = 0; | 156 group->poly[1] = 0; |
157 group->poly[2] = 0; | 157 group->poly[2] = 0; |
158 group->poly[3] = 0; | 158 group->poly[3] = 0; |
159 group->poly[4] = 0; | 159 group->poly[4] = 0; |
| 160 group->poly[5] = -1; |
160 } | 161 } |
161 | 162 |
162 | 163 |
163 /* Copy a GF(2^m)-based EC_GROUP structure. | 164 /* Copy a GF(2^m)-based EC_GROUP structure. |
164 * Note that all other members are handled by EC_GROUP_copy. | 165 * Note that all other members are handled by EC_GROUP_copy. |
165 */ | 166 */ |
166 int ec_GF2m_simple_group_copy(EC_GROUP *dest, const EC_GROUP *src) | 167 int ec_GF2m_simple_group_copy(EC_GROUP *dest, const EC_GROUP *src) |
167 { | 168 { |
168 int i; | 169 int i; |
169 if (!BN_copy(&dest->field, &src->field)) return 0; | 170 if (!BN_copy(&dest->field, &src->field)) return 0; |
170 if (!BN_copy(&dest->a, &src->a)) return 0; | 171 if (!BN_copy(&dest->a, &src->a)) return 0; |
171 if (!BN_copy(&dest->b, &src->b)) return 0; | 172 if (!BN_copy(&dest->b, &src->b)) return 0; |
172 dest->poly[0] = src->poly[0]; | 173 dest->poly[0] = src->poly[0]; |
173 dest->poly[1] = src->poly[1]; | 174 dest->poly[1] = src->poly[1]; |
174 dest->poly[2] = src->poly[2]; | 175 dest->poly[2] = src->poly[2]; |
175 dest->poly[3] = src->poly[3]; | 176 dest->poly[3] = src->poly[3]; |
176 dest->poly[4] = src->poly[4]; | 177 dest->poly[4] = src->poly[4]; |
177 » if(bn_wexpand(&dest->a, (int)(dest->poly[0] + BN_BITS2 - 1) / BN_BITS2)
== NULL) | 178 » dest->poly[5] = src->poly[5]; |
178 » » return 0; | 179 » if (bn_wexpand(&dest->a, (int)(dest->poly[0] + BN_BITS2 - 1) / BN_BITS2)
== NULL) return 0; |
179 » if(bn_wexpand(&dest->b, (int)(dest->poly[0] + BN_BITS2 - 1) / BN_BITS2)
== NULL) | 180 » if (bn_wexpand(&dest->b, (int)(dest->poly[0] + BN_BITS2 - 1) / BN_BITS2)
== NULL) return 0; |
180 » » return 0; | |
181 for (i = dest->a.top; i < dest->a.dmax; i++) dest->a.d[i] = 0; | 181 for (i = dest->a.top; i < dest->a.dmax; i++) dest->a.d[i] = 0; |
182 for (i = dest->b.top; i < dest->b.dmax; i++) dest->b.d[i] = 0; | 182 for (i = dest->b.top; i < dest->b.dmax; i++) dest->b.d[i] = 0; |
183 return 1; | 183 return 1; |
184 } | 184 } |
185 | 185 |
186 | 186 |
187 /* Set the curve parameters of an EC_GROUP structure. */ | 187 /* Set the curve parameters of an EC_GROUP structure. */ |
188 int ec_GF2m_simple_group_set_curve(EC_GROUP *group, | 188 int ec_GF2m_simple_group_set_curve(EC_GROUP *group, |
189 const BIGNUM *p, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx) | 189 const BIGNUM *p, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx) |
190 { | 190 { |
191 int ret = 0, i; | 191 int ret = 0, i; |
192 | 192 |
193 /* group->field */ | 193 /* group->field */ |
194 if (!BN_copy(&group->field, p)) goto err; | 194 if (!BN_copy(&group->field, p)) goto err; |
195 » i = BN_GF2m_poly2arr(&group->field, group->poly, 5); | 195 » i = BN_GF2m_poly2arr(&group->field, group->poly, 6) - 1; |
196 if ((i != 5) && (i != 3)) | 196 if ((i != 5) && (i != 3)) |
197 { | 197 { |
198 ECerr(EC_F_EC_GF2M_SIMPLE_GROUP_SET_CURVE, EC_R_UNSUPPORTED_FIEL
D); | 198 ECerr(EC_F_EC_GF2M_SIMPLE_GROUP_SET_CURVE, EC_R_UNSUPPORTED_FIEL
D); |
199 goto err; | 199 goto err; |
200 } | 200 } |
201 | 201 |
202 /* group->a */ | 202 /* group->a */ |
203 if (!BN_GF2m_mod_arr(&group->a, a, group->poly)) goto err; | 203 if (!BN_GF2m_mod_arr(&group->a, a, group->poly)) goto err; |
204 if(bn_wexpand(&group->a, (int)(group->poly[0] + BN_BITS2 - 1) / BN_BITS2
) == NULL) goto err; | 204 if(bn_wexpand(&group->a, (int)(group->poly[0] + BN_BITS2 - 1) / BN_BITS2
) == NULL) goto err; |
205 for (i = group->a.top; i < group->a.dmax; i++) group->a.d[i] = 0; | 205 for (i = group->a.top; i < group->a.dmax; i++) group->a.d[i] = 0; |
(...skipping 193 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
399 if (!BN_copy(y, &point->Y)) goto err; | 399 if (!BN_copy(y, &point->Y)) goto err; |
400 BN_set_negative(y, 0); | 400 BN_set_negative(y, 0); |
401 } | 401 } |
402 ret = 1; | 402 ret = 1; |
403 | 403 |
404 err: | 404 err: |
405 return ret; | 405 return ret; |
406 } | 406 } |
407 | 407 |
408 | 408 |
409 /* Include patented algorithms. */ | 409 /* Calculates and sets the affine coordinates of an EC_POINT from the given |
410 #include "ec2_smpt.c" | 410 * compressed coordinates. Uses algorithm 2.3.4 of SEC 1. |
| 411 * Note that the simple implementation only uses affine coordinates. |
| 412 * |
| 413 * The method is from the following publication: |
| 414 * |
| 415 * Harper, Menezes, Vanstone: |
| 416 * "Public-Key Cryptosystems with Very Small Key Lengths", |
| 417 * EUROCRYPT '92, Springer-Verlag LNCS 658, |
| 418 * published February 1993 |
| 419 * |
| 420 * US Patents 6,141,420 and 6,618,483 (Vanstone, Mullin, Agnew) describe |
| 421 * the same method, but claim no priority date earlier than July 29, 1994 |
| 422 * (and additionally fail to cite the EUROCRYPT '92 publication as prior art). |
| 423 */ |
| 424 int ec_GF2m_simple_set_compressed_coordinates(const EC_GROUP *group, EC_POINT *p
oint, |
| 425 » const BIGNUM *x_, int y_bit, BN_CTX *ctx) |
| 426 » { |
| 427 » BN_CTX *new_ctx = NULL; |
| 428 » BIGNUM *tmp, *x, *y, *z; |
| 429 » int ret = 0, z0; |
| 430 |
| 431 » /* clear error queue */ |
| 432 » ERR_clear_error(); |
| 433 |
| 434 » if (ctx == NULL) |
| 435 » » { |
| 436 » » ctx = new_ctx = BN_CTX_new(); |
| 437 » » if (ctx == NULL) |
| 438 » » » return 0; |
| 439 » » } |
| 440 |
| 441 » y_bit = (y_bit != 0) ? 1 : 0; |
| 442 |
| 443 » BN_CTX_start(ctx); |
| 444 » tmp = BN_CTX_get(ctx); |
| 445 » x = BN_CTX_get(ctx); |
| 446 » y = BN_CTX_get(ctx); |
| 447 » z = BN_CTX_get(ctx); |
| 448 » if (z == NULL) goto err; |
| 449 |
| 450 » if (!BN_GF2m_mod_arr(x, x_, group->poly)) goto err; |
| 451 » if (BN_is_zero(x)) |
| 452 » » { |
| 453 » » if (!BN_GF2m_mod_sqrt_arr(y, &group->b, group->poly, ctx)) goto
err; |
| 454 » » } |
| 455 » else |
| 456 » » { |
| 457 » » if (!group->meth->field_sqr(group, tmp, x, ctx)) goto err; |
| 458 » » if (!group->meth->field_div(group, tmp, &group->b, tmp, ctx)) go
to err; |
| 459 » » if (!BN_GF2m_add(tmp, &group->a, tmp)) goto err; |
| 460 » » if (!BN_GF2m_add(tmp, x, tmp)) goto err; |
| 461 » » if (!BN_GF2m_mod_solve_quad_arr(z, tmp, group->poly, ctx)) |
| 462 » » » { |
| 463 » » » unsigned long err = ERR_peek_last_error(); |
| 464 » » » |
| 465 » » » if (ERR_GET_LIB(err) == ERR_LIB_BN && ERR_GET_REASON(err
) == BN_R_NO_SOLUTION) |
| 466 » » » » { |
| 467 » » » » ERR_clear_error(); |
| 468 » » » » ECerr(EC_F_EC_GF2M_SIMPLE_SET_COMPRESSED_COORDIN
ATES, EC_R_INVALID_COMPRESSED_POINT); |
| 469 » » » » } |
| 470 » » » else |
| 471 » » » » ECerr(EC_F_EC_GF2M_SIMPLE_SET_COMPRESSED_COORDIN
ATES, ERR_R_BN_LIB); |
| 472 » » » goto err; |
| 473 » » » } |
| 474 » » z0 = (BN_is_odd(z)) ? 1 : 0; |
| 475 » » if (!group->meth->field_mul(group, y, x, z, ctx)) goto err; |
| 476 » » if (z0 != y_bit) |
| 477 » » » { |
| 478 » » » if (!BN_GF2m_add(y, y, x)) goto err; |
| 479 » » » } |
| 480 » » } |
| 481 |
| 482 » if (!EC_POINT_set_affine_coordinates_GF2m(group, point, x, y, ctx)) goto
err; |
| 483 |
| 484 » ret = 1; |
| 485 |
| 486 err: |
| 487 » BN_CTX_end(ctx); |
| 488 » if (new_ctx != NULL) |
| 489 » » BN_CTX_free(new_ctx); |
| 490 » return ret; |
| 491 » } |
411 | 492 |
412 | 493 |
413 /* Converts an EC_POINT to an octet string. | 494 /* Converts an EC_POINT to an octet string. |
414 * If buf is NULL, the encoded length will be returned. | 495 * If buf is NULL, the encoded length will be returned. |
415 * If the length len of buf is smaller than required an error will be returned. | 496 * If the length len of buf is smaller than required an error will be returned. |
416 * | |
417 * The point compression section of this function is patented by Certicom Corp. | |
418 * under US Patent 6,141,420. Point compression is disabled by default and can | |
419 * be enabled by defining the preprocessor macro OPENSSL_EC_BIN_PT_COMP at | |
420 * Configure-time. | |
421 */ | 497 */ |
422 size_t ec_GF2m_simple_point2oct(const EC_GROUP *group, const EC_POINT *point, po
int_conversion_form_t form, | 498 size_t ec_GF2m_simple_point2oct(const EC_GROUP *group, const EC_POINT *point, po
int_conversion_form_t form, |
423 unsigned char *buf, size_t len, BN_CTX *ctx) | 499 unsigned char *buf, size_t len, BN_CTX *ctx) |
424 { | 500 { |
425 size_t ret; | 501 size_t ret; |
426 BN_CTX *new_ctx = NULL; | 502 BN_CTX *new_ctx = NULL; |
427 int used_ctx = 0; | 503 int used_ctx = 0; |
428 BIGNUM *x, *y, *yxi; | 504 BIGNUM *x, *y, *yxi; |
429 size_t field_len, i, skip; | 505 size_t field_len, i, skip; |
430 | 506 |
431 #ifndef OPENSSL_EC_BIN_PT_COMP | |
432 if ((form == POINT_CONVERSION_COMPRESSED) || (form == POINT_CONVERSION_H
YBRID)) | |
433 { | |
434 ECerr(EC_F_EC_GF2M_SIMPLE_POINT2OCT, ERR_R_DISABLED); | |
435 goto err; | |
436 } | |
437 #endif | |
438 | |
439 if ((form != POINT_CONVERSION_COMPRESSED) | 507 if ((form != POINT_CONVERSION_COMPRESSED) |
440 && (form != POINT_CONVERSION_UNCOMPRESSED) | 508 && (form != POINT_CONVERSION_UNCOMPRESSED) |
441 && (form != POINT_CONVERSION_HYBRID)) | 509 && (form != POINT_CONVERSION_HYBRID)) |
442 { | 510 { |
443 ECerr(EC_F_EC_GF2M_SIMPLE_POINT2OCT, EC_R_INVALID_FORM); | 511 ECerr(EC_F_EC_GF2M_SIMPLE_POINT2OCT, EC_R_INVALID_FORM); |
444 goto err; | 512 goto err; |
445 } | 513 } |
446 | 514 |
447 if (EC_POINT_is_at_infinity(group, point)) | 515 if (EC_POINT_is_at_infinity(group, point)) |
448 { | 516 { |
(...skipping 34 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
483 BN_CTX_start(ctx); | 551 BN_CTX_start(ctx); |
484 used_ctx = 1; | 552 used_ctx = 1; |
485 x = BN_CTX_get(ctx); | 553 x = BN_CTX_get(ctx); |
486 y = BN_CTX_get(ctx); | 554 y = BN_CTX_get(ctx); |
487 yxi = BN_CTX_get(ctx); | 555 yxi = BN_CTX_get(ctx); |
488 if (yxi == NULL) goto err; | 556 if (yxi == NULL) goto err; |
489 | 557 |
490 if (!EC_POINT_get_affine_coordinates_GF2m(group, point, x, y, ct
x)) goto err; | 558 if (!EC_POINT_get_affine_coordinates_GF2m(group, point, x, y, ct
x)) goto err; |
491 | 559 |
492 buf[0] = form; | 560 buf[0] = form; |
493 #ifdef OPENSSL_EC_BIN_PT_COMP | |
494 if ((form != POINT_CONVERSION_UNCOMPRESSED) && !BN_is_zero(x)) | 561 if ((form != POINT_CONVERSION_UNCOMPRESSED) && !BN_is_zero(x)) |
495 { | 562 { |
496 if (!group->meth->field_div(group, yxi, y, x, ctx)) goto
err; | 563 if (!group->meth->field_div(group, yxi, y, x, ctx)) goto
err; |
497 if (BN_is_odd(yxi)) buf[0]++; | 564 if (BN_is_odd(yxi)) buf[0]++; |
498 } | 565 } |
499 #endif | |
500 | 566 |
501 i = 1; | 567 i = 1; |
502 | 568 |
503 skip = field_len - BN_num_bytes(x); | 569 skip = field_len - BN_num_bytes(x); |
504 if (skip > field_len) | 570 if (skip > field_len) |
505 { | 571 { |
506 ECerr(EC_F_EC_GF2M_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERRO
R); | 572 ECerr(EC_F_EC_GF2M_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERRO
R); |
507 goto err; | 573 goto err; |
508 } | 574 } |
509 while (skip > 0) | 575 while (skip > 0) |
(...skipping 304 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
814 int (*field_mul)(const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNU
M *, BN_CTX *); | 880 int (*field_mul)(const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNU
M *, BN_CTX *); |
815 int (*field_sqr)(const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *); | 881 int (*field_sqr)(const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *); |
816 | 882 |
817 if (EC_POINT_is_at_infinity(group, point)) | 883 if (EC_POINT_is_at_infinity(group, point)) |
818 return 1; | 884 return 1; |
819 | 885 |
820 field_mul = group->meth->field_mul; | 886 field_mul = group->meth->field_mul; |
821 field_sqr = group->meth->field_sqr; | 887 field_sqr = group->meth->field_sqr; |
822 | 888 |
823 /* only support affine coordinates */ | 889 /* only support affine coordinates */ |
824 » if (!point->Z_is_one) goto err; | 890 » if (!point->Z_is_one) return -1; |
825 | 891 |
826 if (ctx == NULL) | 892 if (ctx == NULL) |
827 { | 893 { |
828 ctx = new_ctx = BN_CTX_new(); | 894 ctx = new_ctx = BN_CTX_new(); |
829 if (ctx == NULL) | 895 if (ctx == NULL) |
830 return -1; | 896 return -1; |
831 } | 897 } |
832 | 898 |
833 BN_CTX_start(ctx); | 899 BN_CTX_start(ctx); |
834 y2 = BN_CTX_get(ctx); | 900 y2 = BN_CTX_get(ctx); |
(...skipping 29 matching lines...) Expand all Loading... |
864 int ec_GF2m_simple_cmp(const EC_GROUP *group, const EC_POINT *a, const EC_POINT
*b, BN_CTX *ctx) | 930 int ec_GF2m_simple_cmp(const EC_GROUP *group, const EC_POINT *a, const EC_POINT
*b, BN_CTX *ctx) |
865 { | 931 { |
866 BIGNUM *aX, *aY, *bX, *bY; | 932 BIGNUM *aX, *aY, *bX, *bY; |
867 BN_CTX *new_ctx = NULL; | 933 BN_CTX *new_ctx = NULL; |
868 int ret = -1; | 934 int ret = -1; |
869 | 935 |
870 if (EC_POINT_is_at_infinity(group, a)) | 936 if (EC_POINT_is_at_infinity(group, a)) |
871 { | 937 { |
872 return EC_POINT_is_at_infinity(group, b) ? 0 : 1; | 938 return EC_POINT_is_at_infinity(group, b) ? 0 : 1; |
873 } | 939 } |
| 940 |
| 941 if (EC_POINT_is_at_infinity(group, b)) |
| 942 return 1; |
874 | 943 |
875 if (a->Z_is_one && b->Z_is_one) | 944 if (a->Z_is_one && b->Z_is_one) |
876 { | 945 { |
877 return ((BN_cmp(&a->X, &b->X) == 0) && BN_cmp(&a->Y, &b->Y) == 0
) ? 0 : 1; | 946 return ((BN_cmp(&a->X, &b->X) == 0) && BN_cmp(&a->Y, &b->Y) == 0
) ? 0 : 1; |
878 } | 947 } |
879 | 948 |
880 if (ctx == NULL) | 949 if (ctx == NULL) |
881 { | 950 { |
882 ctx = new_ctx = BN_CTX_new(); | 951 ctx = new_ctx = BN_CTX_new(); |
883 if (ctx == NULL) | 952 if (ctx == NULL) |
(...skipping 80 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
964 { | 1033 { |
965 return BN_GF2m_mod_sqr_arr(r, a, group->poly, ctx); | 1034 return BN_GF2m_mod_sqr_arr(r, a, group->poly, ctx); |
966 } | 1035 } |
967 | 1036 |
968 | 1037 |
969 /* Wrapper to simple binary polynomial field division implementation. */ | 1038 /* Wrapper to simple binary polynomial field division implementation. */ |
970 int ec_GF2m_simple_field_div(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a,
const BIGNUM *b, BN_CTX *ctx) | 1039 int ec_GF2m_simple_field_div(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a,
const BIGNUM *b, BN_CTX *ctx) |
971 { | 1040 { |
972 return BN_GF2m_mod_div(r, a, b, &group->field, ctx); | 1041 return BN_GF2m_mod_div(r, a, b, &group->field, ctx); |
973 } | 1042 } |
OLD | NEW |