OLD | NEW |
1 /* crypto/bn/bn_gf2m.c */ | 1 /* crypto/bn/bn_gf2m.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. |
(...skipping 103 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
114 SQR_tb[(w) >> 4 & 0xF] << 8 | SQR_tb[(w) & 0xF] | 114 SQR_tb[(w) >> 4 & 0xF] << 8 | SQR_tb[(w) & 0xF] |
115 #endif | 115 #endif |
116 #ifdef THIRTY_TWO_BIT | 116 #ifdef THIRTY_TWO_BIT |
117 #define SQR1(w) \ | 117 #define SQR1(w) \ |
118 SQR_tb[(w) >> 28 & 0xF] << 24 | SQR_tb[(w) >> 24 & 0xF] << 16 | \ | 118 SQR_tb[(w) >> 28 & 0xF] << 24 | SQR_tb[(w) >> 24 & 0xF] << 16 | \ |
119 SQR_tb[(w) >> 20 & 0xF] << 8 | SQR_tb[(w) >> 16 & 0xF] | 119 SQR_tb[(w) >> 20 & 0xF] << 8 | SQR_tb[(w) >> 16 & 0xF] |
120 #define SQR0(w) \ | 120 #define SQR0(w) \ |
121 SQR_tb[(w) >> 12 & 0xF] << 24 | SQR_tb[(w) >> 8 & 0xF] << 16 | \ | 121 SQR_tb[(w) >> 12 & 0xF] << 24 | SQR_tb[(w) >> 8 & 0xF] << 16 | \ |
122 SQR_tb[(w) >> 4 & 0xF] << 8 | SQR_tb[(w) & 0xF] | 122 SQR_tb[(w) >> 4 & 0xF] << 8 | SQR_tb[(w) & 0xF] |
123 #endif | 123 #endif |
124 #ifdef SIXTEEN_BIT | |
125 #define SQR1(w) \ | |
126 SQR_tb[(w) >> 12 & 0xF] << 8 | SQR_tb[(w) >> 8 & 0xF] | |
127 #define SQR0(w) \ | |
128 SQR_tb[(w) >> 4 & 0xF] << 8 | SQR_tb[(w) & 0xF] | |
129 #endif | |
130 #ifdef EIGHT_BIT | |
131 #define SQR1(w) \ | |
132 SQR_tb[(w) >> 4 & 0xF] | |
133 #define SQR0(w) \ | |
134 SQR_tb[(w) & 15] | |
135 #endif | |
136 | 124 |
137 /* Product of two polynomials a, b each with degree < BN_BITS2 - 1, | 125 /* Product of two polynomials a, b each with degree < BN_BITS2 - 1, |
138 * result is a polynomial r with degree < 2 * BN_BITS - 1 | 126 * result is a polynomial r with degree < 2 * BN_BITS - 1 |
139 * The caller MUST ensure that the variables have the right amount | 127 * The caller MUST ensure that the variables have the right amount |
140 * of space allocated. | 128 * of space allocated. |
141 */ | 129 */ |
142 #ifdef EIGHT_BIT | |
143 static void bn_GF2m_mul_1x1(BN_ULONG *r1, BN_ULONG *r0, const BN_ULONG a, const
BN_ULONG b) | |
144 { | |
145 register BN_ULONG h, l, s; | |
146 BN_ULONG tab[4], top1b = a >> 7; | |
147 register BN_ULONG a1, a2; | |
148 | |
149 a1 = a & (0x7F); a2 = a1 << 1; | |
150 | |
151 tab[0] = 0; tab[1] = a1; tab[2] = a2; tab[3] = a1^a2; | |
152 | |
153 s = tab[b & 0x3]; l = s; | |
154 s = tab[b >> 2 & 0x3]; l ^= s << 2; h = s >> 6; | |
155 s = tab[b >> 4 & 0x3]; l ^= s << 4; h ^= s >> 4; | |
156 s = tab[b >> 6 ]; l ^= s << 6; h ^= s >> 2; | |
157 | |
158 /* compensate for the top bit of a */ | |
159 | |
160 if (top1b & 01) { l ^= b << 7; h ^= b >> 1; } | |
161 | |
162 *r1 = h; *r0 = l; | |
163 } | |
164 #endif | |
165 #ifdef SIXTEEN_BIT | |
166 static void bn_GF2m_mul_1x1(BN_ULONG *r1, BN_ULONG *r0, const BN_ULONG a, const
BN_ULONG b) | |
167 { | |
168 register BN_ULONG h, l, s; | |
169 BN_ULONG tab[4], top1b = a >> 15; | |
170 register BN_ULONG a1, a2; | |
171 | |
172 a1 = a & (0x7FFF); a2 = a1 << 1; | |
173 | |
174 tab[0] = 0; tab[1] = a1; tab[2] = a2; tab[3] = a1^a2; | |
175 | |
176 s = tab[b & 0x3]; l = s; | |
177 s = tab[b >> 2 & 0x3]; l ^= s << 2; h = s >> 14; | |
178 s = tab[b >> 4 & 0x3]; l ^= s << 4; h ^= s >> 12; | |
179 s = tab[b >> 6 & 0x3]; l ^= s << 6; h ^= s >> 10; | |
180 s = tab[b >> 8 & 0x3]; l ^= s << 8; h ^= s >> 8; | |
181 s = tab[b >>10 & 0x3]; l ^= s << 10; h ^= s >> 6; | |
182 s = tab[b >>12 & 0x3]; l ^= s << 12; h ^= s >> 4; | |
183 s = tab[b >>14 ]; l ^= s << 14; h ^= s >> 2; | |
184 | |
185 /* compensate for the top bit of a */ | |
186 | |
187 if (top1b & 01) { l ^= b << 15; h ^= b >> 1; } | |
188 | |
189 *r1 = h; *r0 = l; | |
190 } | |
191 #endif | |
192 #ifdef THIRTY_TWO_BIT | 130 #ifdef THIRTY_TWO_BIT |
193 static void bn_GF2m_mul_1x1(BN_ULONG *r1, BN_ULONG *r0, const BN_ULONG a, const
BN_ULONG b) | 131 static void bn_GF2m_mul_1x1(BN_ULONG *r1, BN_ULONG *r0, const BN_ULONG a, const
BN_ULONG b) |
194 { | 132 { |
195 register BN_ULONG h, l, s; | 133 register BN_ULONG h, l, s; |
196 BN_ULONG tab[8], top2b = a >> 30; | 134 BN_ULONG tab[8], top2b = a >> 30; |
197 register BN_ULONG a1, a2, a4; | 135 register BN_ULONG a1, a2, a4; |
198 | 136 |
199 a1 = a & (0x3FFFFFFF); a2 = a1 << 1; a4 = a2 << 1; | 137 a1 = a & (0x3FFFFFFF); a2 = a1 << 1; a4 = a2 << 1; |
200 | 138 |
201 tab[0] = 0; tab[1] = a1; tab[2] = a2; tab[3] = a1^a2; | 139 tab[0] = 0; tab[1] = a1; tab[2] = a2; tab[3] = a1^a2; |
(...skipping 112 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
314 | 252 |
315 | 253 |
316 /* Some functions allow for representation of the irreducible polynomials | 254 /* Some functions allow for representation of the irreducible polynomials |
317 * as an int[], say p. The irreducible f(t) is then of the form: | 255 * as an int[], say p. The irreducible f(t) is then of the form: |
318 * t^p[0] + t^p[1] + ... + t^p[k] | 256 * t^p[0] + t^p[1] + ... + t^p[k] |
319 * where m = p[0] > p[1] > ... > p[k] = 0. | 257 * where m = p[0] > p[1] > ... > p[k] = 0. |
320 */ | 258 */ |
321 | 259 |
322 | 260 |
323 /* Performs modular reduction of a and store result in r. r could be a. */ | 261 /* Performs modular reduction of a and store result in r. r could be a. */ |
324 int BN_GF2m_mod_arr(BIGNUM *r, const BIGNUM *a, const unsigned int p[]) | 262 int BN_GF2m_mod_arr(BIGNUM *r, const BIGNUM *a, const int p[]) |
325 { | 263 { |
326 int j, k; | 264 int j, k; |
327 int n, dN, d0, d1; | 265 int n, dN, d0, d1; |
328 BN_ULONG zz, *z; | 266 BN_ULONG zz, *z; |
329 | 267 |
330 bn_check_top(a); | 268 bn_check_top(a); |
331 | 269 |
332 if (!p[0]) | 270 if (!p[0]) |
333 { | 271 { |
334 /* reduction mod 1 => return 0 */ | 272 /* reduction mod 1 => return 0 */ |
(...skipping 80 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
415 | 353 |
416 /* Performs modular reduction of a by p and store result in r. r could be a. | 354 /* Performs modular reduction of a by p and store result in r. r could be a. |
417 * | 355 * |
418 * This function calls down to the BN_GF2m_mod_arr implementation; this wrapper | 356 * This function calls down to the BN_GF2m_mod_arr implementation; this wrapper |
419 * function is only provided for convenience; for best performance, use the | 357 * function is only provided for convenience; for best performance, use the |
420 * BN_GF2m_mod_arr function. | 358 * BN_GF2m_mod_arr function. |
421 */ | 359 */ |
422 int BN_GF2m_mod(BIGNUM *r, const BIGNUM *a, const BIGNUM *p) | 360 int BN_GF2m_mod(BIGNUM *r, const BIGNUM *a, const BIGNUM *p) |
423 { | 361 { |
424 int ret = 0; | 362 int ret = 0; |
425 » const int max = BN_num_bits(p); | 363 » const int max = BN_num_bits(p) + 1; |
426 » unsigned int *arr=NULL; | 364 » int *arr=NULL; |
427 bn_check_top(a); | 365 bn_check_top(a); |
428 bn_check_top(p); | 366 bn_check_top(p); |
429 » if ((arr = (unsigned int *)OPENSSL_malloc(sizeof(unsigned int) * max)) =
= NULL) goto err; | 367 » if ((arr = (int *)OPENSSL_malloc(sizeof(int) * max)) == NULL) goto err; |
430 ret = BN_GF2m_poly2arr(p, arr, max); | 368 ret = BN_GF2m_poly2arr(p, arr, max); |
431 if (!ret || ret > max) | 369 if (!ret || ret > max) |
432 { | 370 { |
433 BNerr(BN_F_BN_GF2M_MOD,BN_R_INVALID_LENGTH); | 371 BNerr(BN_F_BN_GF2M_MOD,BN_R_INVALID_LENGTH); |
434 goto err; | 372 goto err; |
435 } | 373 } |
436 ret = BN_GF2m_mod_arr(r, a, arr); | 374 ret = BN_GF2m_mod_arr(r, a, arr); |
437 bn_check_top(r); | 375 bn_check_top(r); |
438 err: | 376 err: |
439 if (arr) OPENSSL_free(arr); | 377 if (arr) OPENSSL_free(arr); |
440 return ret; | 378 return ret; |
441 } | 379 } |
442 | 380 |
443 | 381 |
444 /* Compute the product of two polynomials a and b, reduce modulo p, and store | 382 /* Compute the product of two polynomials a and b, reduce modulo p, and store |
445 * the result in r. r could be a or b; a could be b. | 383 * the result in r. r could be a or b; a could be b. |
446 */ | 384 */ |
447 int» BN_GF2m_mod_mul_arr(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const u
nsigned int p[], BN_CTX *ctx) | 385 int» BN_GF2m_mod_mul_arr(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const i
nt p[], BN_CTX *ctx) |
448 { | 386 { |
449 int zlen, i, j, k, ret = 0; | 387 int zlen, i, j, k, ret = 0; |
450 BIGNUM *s; | 388 BIGNUM *s; |
451 BN_ULONG x1, x0, y1, y0, zz[4]; | 389 BN_ULONG x1, x0, y1, y0, zz[4]; |
452 | 390 |
453 bn_check_top(a); | 391 bn_check_top(a); |
454 bn_check_top(b); | 392 bn_check_top(b); |
455 | 393 |
456 if (a == b) | 394 if (a == b) |
457 { | 395 { |
(...skipping 35 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
493 /* Compute the product of two polynomials a and b, reduce modulo p, and store | 431 /* Compute the product of two polynomials a and b, reduce modulo p, and store |
494 * the result in r. r could be a or b; a could equal b. | 432 * the result in r. r could be a or b; a could equal b. |
495 * | 433 * |
496 * This function calls down to the BN_GF2m_mod_mul_arr implementation; this wrap
per | 434 * This function calls down to the BN_GF2m_mod_mul_arr implementation; this wrap
per |
497 * function is only provided for convenience; for best performance, use the | 435 * function is only provided for convenience; for best performance, use the |
498 * BN_GF2m_mod_mul_arr function. | 436 * BN_GF2m_mod_mul_arr function. |
499 */ | 437 */ |
500 int BN_GF2m_mod_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNU
M *p, BN_CTX *ctx) | 438 int BN_GF2m_mod_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNU
M *p, BN_CTX *ctx) |
501 { | 439 { |
502 int ret = 0; | 440 int ret = 0; |
503 » const int max = BN_num_bits(p); | 441 » const int max = BN_num_bits(p) + 1; |
504 » unsigned int *arr=NULL; | 442 » int *arr=NULL; |
505 bn_check_top(a); | 443 bn_check_top(a); |
506 bn_check_top(b); | 444 bn_check_top(b); |
507 bn_check_top(p); | 445 bn_check_top(p); |
508 » if ((arr = (unsigned int *)OPENSSL_malloc(sizeof(unsigned int) * max)) =
= NULL) goto err; | 446 » if ((arr = (int *)OPENSSL_malloc(sizeof(int) * max)) == NULL) goto err; |
509 ret = BN_GF2m_poly2arr(p, arr, max); | 447 ret = BN_GF2m_poly2arr(p, arr, max); |
510 if (!ret || ret > max) | 448 if (!ret || ret > max) |
511 { | 449 { |
512 BNerr(BN_F_BN_GF2M_MOD_MUL,BN_R_INVALID_LENGTH); | 450 BNerr(BN_F_BN_GF2M_MOD_MUL,BN_R_INVALID_LENGTH); |
513 goto err; | 451 goto err; |
514 } | 452 } |
515 ret = BN_GF2m_mod_mul_arr(r, a, b, arr, ctx); | 453 ret = BN_GF2m_mod_mul_arr(r, a, b, arr, ctx); |
516 bn_check_top(r); | 454 bn_check_top(r); |
517 err: | 455 err: |
518 if (arr) OPENSSL_free(arr); | 456 if (arr) OPENSSL_free(arr); |
519 return ret; | 457 return ret; |
520 } | 458 } |
521 | 459 |
522 | 460 |
523 /* Square a, reduce the result mod p, and store it in a. r could be a. */ | 461 /* Square a, reduce the result mod p, and store it in a. r could be a. */ |
524 int» BN_GF2m_mod_sqr_arr(BIGNUM *r, const BIGNUM *a, const unsigned int p[],
BN_CTX *ctx) | 462 int» BN_GF2m_mod_sqr_arr(BIGNUM *r, const BIGNUM *a, const int p[], BN_CTX *c
tx) |
525 { | 463 { |
526 int i, ret = 0; | 464 int i, ret = 0; |
527 BIGNUM *s; | 465 BIGNUM *s; |
528 | 466 |
529 bn_check_top(a); | 467 bn_check_top(a); |
530 BN_CTX_start(ctx); | 468 BN_CTX_start(ctx); |
531 if ((s = BN_CTX_get(ctx)) == NULL) return 0; | 469 if ((s = BN_CTX_get(ctx)) == NULL) return 0; |
532 if (!bn_wexpand(s, 2 * a->top)) goto err; | 470 if (!bn_wexpand(s, 2 * a->top)) goto err; |
533 | 471 |
534 for (i = a->top - 1; i >= 0; i--) | 472 for (i = a->top - 1; i >= 0; i--) |
(...skipping 14 matching lines...) Expand all Loading... |
549 | 487 |
550 /* Square a, reduce the result mod p, and store it in a. r could be a. | 488 /* Square a, reduce the result mod p, and store it in a. r could be a. |
551 * | 489 * |
552 * This function calls down to the BN_GF2m_mod_sqr_arr implementation; this wrap
per | 490 * This function calls down to the BN_GF2m_mod_sqr_arr implementation; this wrap
per |
553 * function is only provided for convenience; for best performance, use the | 491 * function is only provided for convenience; for best performance, use the |
554 * BN_GF2m_mod_sqr_arr function. | 492 * BN_GF2m_mod_sqr_arr function. |
555 */ | 493 */ |
556 int BN_GF2m_mod_sqr(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx
) | 494 int BN_GF2m_mod_sqr(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx
) |
557 { | 495 { |
558 int ret = 0; | 496 int ret = 0; |
559 » const int max = BN_num_bits(p); | 497 » const int max = BN_num_bits(p) + 1; |
560 » unsigned int *arr=NULL; | 498 » int *arr=NULL; |
561 | 499 |
562 bn_check_top(a); | 500 bn_check_top(a); |
563 bn_check_top(p); | 501 bn_check_top(p); |
564 » if ((arr = (unsigned int *)OPENSSL_malloc(sizeof(unsigned int) * max)) =
= NULL) goto err; | 502 » if ((arr = (int *)OPENSSL_malloc(sizeof(int) * max)) == NULL) goto err; |
565 ret = BN_GF2m_poly2arr(p, arr, max); | 503 ret = BN_GF2m_poly2arr(p, arr, max); |
566 if (!ret || ret > max) | 504 if (!ret || ret > max) |
567 { | 505 { |
568 BNerr(BN_F_BN_GF2M_MOD_SQR,BN_R_INVALID_LENGTH); | 506 BNerr(BN_F_BN_GF2M_MOD_SQR,BN_R_INVALID_LENGTH); |
569 goto err; | 507 goto err; |
570 } | 508 } |
571 ret = BN_GF2m_mod_sqr_arr(r, a, arr, ctx); | 509 ret = BN_GF2m_mod_sqr_arr(r, a, arr, ctx); |
572 bn_check_top(r); | 510 bn_check_top(r); |
573 err: | 511 err: |
574 if (arr) OPENSSL_free(arr); | 512 if (arr) OPENSSL_free(arr); |
(...skipping 25 matching lines...) Expand all Loading... |
600 if (!BN_one(b)) goto err; | 538 if (!BN_one(b)) goto err; |
601 if (!BN_GF2m_mod(u, a, p)) goto err; | 539 if (!BN_GF2m_mod(u, a, p)) goto err; |
602 if (!BN_copy(v, p)) goto err; | 540 if (!BN_copy(v, p)) goto err; |
603 | 541 |
604 if (BN_is_zero(u)) goto err; | 542 if (BN_is_zero(u)) goto err; |
605 | 543 |
606 while (1) | 544 while (1) |
607 { | 545 { |
608 while (!BN_is_odd(u)) | 546 while (!BN_is_odd(u)) |
609 { | 547 { |
| 548 if (BN_is_zero(u)) goto err; |
610 if (!BN_rshift1(u, u)) goto err; | 549 if (!BN_rshift1(u, u)) goto err; |
611 if (BN_is_odd(b)) | 550 if (BN_is_odd(b)) |
612 { | 551 { |
613 if (!BN_GF2m_add(b, b, p)) goto err; | 552 if (!BN_GF2m_add(b, b, p)) goto err; |
614 } | 553 } |
615 if (!BN_rshift1(b, b)) goto err; | 554 if (!BN_rshift1(b, b)) goto err; |
616 } | 555 } |
617 | 556 |
618 if (BN_abs_is_word(u, 1)) break; | 557 if (BN_abs_is_word(u, 1)) break; |
619 | 558 |
(...skipping 16 matching lines...) Expand all Loading... |
636 BN_CTX_end(ctx); | 575 BN_CTX_end(ctx); |
637 return ret; | 576 return ret; |
638 } | 577 } |
639 | 578 |
640 /* Invert xx, reduce modulo p, and store the result in r. r could be xx. | 579 /* Invert xx, reduce modulo p, and store the result in r. r could be xx. |
641 * | 580 * |
642 * This function calls down to the BN_GF2m_mod_inv implementation; this wrapper | 581 * This function calls down to the BN_GF2m_mod_inv implementation; this wrapper |
643 * function is only provided for convenience; for best performance, use the | 582 * function is only provided for convenience; for best performance, use the |
644 * BN_GF2m_mod_inv function. | 583 * BN_GF2m_mod_inv function. |
645 */ | 584 */ |
646 int BN_GF2m_mod_inv_arr(BIGNUM *r, const BIGNUM *xx, const unsigned int p[], BN_
CTX *ctx) | 585 int BN_GF2m_mod_inv_arr(BIGNUM *r, const BIGNUM *xx, const int p[], BN_CTX *ctx) |
647 { | 586 { |
648 BIGNUM *field; | 587 BIGNUM *field; |
649 int ret = 0; | 588 int ret = 0; |
650 | 589 |
651 bn_check_top(xx); | 590 bn_check_top(xx); |
652 BN_CTX_start(ctx); | 591 BN_CTX_start(ctx); |
653 if ((field = BN_CTX_get(ctx)) == NULL) goto err; | 592 if ((field = BN_CTX_get(ctx)) == NULL) goto err; |
654 if (!BN_GF2m_arr2poly(p, field)) goto err; | 593 if (!BN_GF2m_arr2poly(p, field)) goto err; |
655 | 594 |
656 ret = BN_GF2m_mod_inv(r, xx, field, ctx); | 595 ret = BN_GF2m_mod_inv(r, xx, field, ctx); |
(...skipping 105 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
762 } | 701 } |
763 #endif | 702 #endif |
764 | 703 |
765 /* Divide yy by xx, reduce modulo p, and store the result in r. r could be xx | 704 /* Divide yy by xx, reduce modulo p, and store the result in r. r could be xx |
766 * or yy, xx could equal yy. | 705 * or yy, xx could equal yy. |
767 * | 706 * |
768 * This function calls down to the BN_GF2m_mod_div implementation; this wrapper | 707 * This function calls down to the BN_GF2m_mod_div implementation; this wrapper |
769 * function is only provided for convenience; for best performance, use the | 708 * function is only provided for convenience; for best performance, use the |
770 * BN_GF2m_mod_div function. | 709 * BN_GF2m_mod_div function. |
771 */ | 710 */ |
772 int BN_GF2m_mod_div_arr(BIGNUM *r, const BIGNUM *yy, const BIGNUM *xx, const uns
igned int p[], BN_CTX *ctx) | 711 int BN_GF2m_mod_div_arr(BIGNUM *r, const BIGNUM *yy, const BIGNUM *xx, const int
p[], BN_CTX *ctx) |
773 { | 712 { |
774 BIGNUM *field; | 713 BIGNUM *field; |
775 int ret = 0; | 714 int ret = 0; |
776 | 715 |
777 bn_check_top(yy); | 716 bn_check_top(yy); |
778 bn_check_top(xx); | 717 bn_check_top(xx); |
779 | 718 |
780 BN_CTX_start(ctx); | 719 BN_CTX_start(ctx); |
781 if ((field = BN_CTX_get(ctx)) == NULL) goto err; | 720 if ((field = BN_CTX_get(ctx)) == NULL) goto err; |
782 if (!BN_GF2m_arr2poly(p, field)) goto err; | 721 if (!BN_GF2m_arr2poly(p, field)) goto err; |
783 | 722 |
784 ret = BN_GF2m_mod_div(r, yy, xx, field, ctx); | 723 ret = BN_GF2m_mod_div(r, yy, xx, field, ctx); |
785 bn_check_top(r); | 724 bn_check_top(r); |
786 | 725 |
787 err: | 726 err: |
788 BN_CTX_end(ctx); | 727 BN_CTX_end(ctx); |
789 return ret; | 728 return ret; |
790 } | 729 } |
791 | 730 |
792 | 731 |
793 /* Compute the bth power of a, reduce modulo p, and store | 732 /* Compute the bth power of a, reduce modulo p, and store |
794 * the result in r. r could be a. | 733 * the result in r. r could be a. |
795 * Uses simple square-and-multiply algorithm A.5.1 from IEEE P1363. | 734 * Uses simple square-and-multiply algorithm A.5.1 from IEEE P1363. |
796 */ | 735 */ |
797 int» BN_GF2m_mod_exp_arr(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const u
nsigned int p[], BN_CTX *ctx) | 736 int» BN_GF2m_mod_exp_arr(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const i
nt p[], BN_CTX *ctx) |
798 { | 737 { |
799 int ret = 0, i, n; | 738 int ret = 0, i, n; |
800 BIGNUM *u; | 739 BIGNUM *u; |
801 | 740 |
802 bn_check_top(a); | 741 bn_check_top(a); |
803 bn_check_top(b); | 742 bn_check_top(b); |
804 | 743 |
805 if (BN_is_zero(b)) | 744 if (BN_is_zero(b)) |
806 return(BN_one(r)); | 745 return(BN_one(r)); |
807 | 746 |
(...skipping 25 matching lines...) Expand all Loading... |
833 /* Compute the bth power of a, reduce modulo p, and store | 772 /* Compute the bth power of a, reduce modulo p, and store |
834 * the result in r. r could be a. | 773 * the result in r. r could be a. |
835 * | 774 * |
836 * This function calls down to the BN_GF2m_mod_exp_arr implementation; this wrap
per | 775 * This function calls down to the BN_GF2m_mod_exp_arr implementation; this wrap
per |
837 * function is only provided for convenience; for best performance, use the | 776 * function is only provided for convenience; for best performance, use the |
838 * BN_GF2m_mod_exp_arr function. | 777 * BN_GF2m_mod_exp_arr function. |
839 */ | 778 */ |
840 int BN_GF2m_mod_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *p
, BN_CTX *ctx) | 779 int BN_GF2m_mod_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *p
, BN_CTX *ctx) |
841 { | 780 { |
842 int ret = 0; | 781 int ret = 0; |
843 » const int max = BN_num_bits(p); | 782 » const int max = BN_num_bits(p) + 1; |
844 » unsigned int *arr=NULL; | 783 » int *arr=NULL; |
845 bn_check_top(a); | 784 bn_check_top(a); |
846 bn_check_top(b); | 785 bn_check_top(b); |
847 bn_check_top(p); | 786 bn_check_top(p); |
848 » if ((arr = (unsigned int *)OPENSSL_malloc(sizeof(unsigned int) * max)) =
= NULL) goto err; | 787 » if ((arr = (int *)OPENSSL_malloc(sizeof(int) * max)) == NULL) goto err; |
849 ret = BN_GF2m_poly2arr(p, arr, max); | 788 ret = BN_GF2m_poly2arr(p, arr, max); |
850 if (!ret || ret > max) | 789 if (!ret || ret > max) |
851 { | 790 { |
852 BNerr(BN_F_BN_GF2M_MOD_EXP,BN_R_INVALID_LENGTH); | 791 BNerr(BN_F_BN_GF2M_MOD_EXP,BN_R_INVALID_LENGTH); |
853 goto err; | 792 goto err; |
854 } | 793 } |
855 ret = BN_GF2m_mod_exp_arr(r, a, b, arr, ctx); | 794 ret = BN_GF2m_mod_exp_arr(r, a, b, arr, ctx); |
856 bn_check_top(r); | 795 bn_check_top(r); |
857 err: | 796 err: |
858 if (arr) OPENSSL_free(arr); | 797 if (arr) OPENSSL_free(arr); |
859 return ret; | 798 return ret; |
860 } | 799 } |
861 | 800 |
862 /* Compute the square root of a, reduce modulo p, and store | 801 /* Compute the square root of a, reduce modulo p, and store |
863 * the result in r. r could be a. | 802 * the result in r. r could be a. |
864 * Uses exponentiation as in algorithm A.4.1 from IEEE P1363. | 803 * Uses exponentiation as in algorithm A.4.1 from IEEE P1363. |
865 */ | 804 */ |
866 int» BN_GF2m_mod_sqrt_arr(BIGNUM *r, const BIGNUM *a, const unsigned int p[],
BN_CTX *ctx) | 805 int» BN_GF2m_mod_sqrt_arr(BIGNUM *r, const BIGNUM *a, const int p[], BN_CTX *
ctx) |
867 { | 806 { |
868 int ret = 0; | 807 int ret = 0; |
869 BIGNUM *u; | 808 BIGNUM *u; |
870 | 809 |
871 bn_check_top(a); | 810 bn_check_top(a); |
872 | 811 |
873 if (!p[0]) | 812 if (!p[0]) |
874 { | 813 { |
875 /* reduction mod 1 => return 0 */ | 814 /* reduction mod 1 => return 0 */ |
876 BN_zero(r); | 815 BN_zero(r); |
(...skipping 15 matching lines...) Expand all Loading... |
892 /* Compute the square root of a, reduce modulo p, and store | 831 /* Compute the square root of a, reduce modulo p, and store |
893 * the result in r. r could be a. | 832 * the result in r. r could be a. |
894 * | 833 * |
895 * This function calls down to the BN_GF2m_mod_sqrt_arr implementation; this wra
pper | 834 * This function calls down to the BN_GF2m_mod_sqrt_arr implementation; this wra
pper |
896 * function is only provided for convenience; for best performance, use the | 835 * function is only provided for convenience; for best performance, use the |
897 * BN_GF2m_mod_sqrt_arr function. | 836 * BN_GF2m_mod_sqrt_arr function. |
898 */ | 837 */ |
899 int BN_GF2m_mod_sqrt(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx) | 838 int BN_GF2m_mod_sqrt(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx) |
900 { | 839 { |
901 int ret = 0; | 840 int ret = 0; |
902 » const int max = BN_num_bits(p); | 841 » const int max = BN_num_bits(p) + 1; |
903 » unsigned int *arr=NULL; | 842 » int *arr=NULL; |
904 bn_check_top(a); | 843 bn_check_top(a); |
905 bn_check_top(p); | 844 bn_check_top(p); |
906 » if ((arr = (unsigned int *)OPENSSL_malloc(sizeof(unsigned int) * max)) =
= NULL) goto err; | 845 » if ((arr = (int *)OPENSSL_malloc(sizeof(int) * max)) == NULL) goto err; |
907 ret = BN_GF2m_poly2arr(p, arr, max); | 846 ret = BN_GF2m_poly2arr(p, arr, max); |
908 if (!ret || ret > max) | 847 if (!ret || ret > max) |
909 { | 848 { |
910 BNerr(BN_F_BN_GF2M_MOD_SQRT,BN_R_INVALID_LENGTH); | 849 BNerr(BN_F_BN_GF2M_MOD_SQRT,BN_R_INVALID_LENGTH); |
911 goto err; | 850 goto err; |
912 } | 851 } |
913 ret = BN_GF2m_mod_sqrt_arr(r, a, arr, ctx); | 852 ret = BN_GF2m_mod_sqrt_arr(r, a, arr, ctx); |
914 bn_check_top(r); | 853 bn_check_top(r); |
915 err: | 854 err: |
916 if (arr) OPENSSL_free(arr); | 855 if (arr) OPENSSL_free(arr); |
917 return ret; | 856 return ret; |
918 } | 857 } |
919 | 858 |
920 /* Find r such that r^2 + r = a mod p. r could be a. If no r exists returns 0. | 859 /* Find r such that r^2 + r = a mod p. r could be a. If no r exists returns 0. |
921 * Uses algorithms A.4.7 and A.4.6 from IEEE P1363. | 860 * Uses algorithms A.4.7 and A.4.6 from IEEE P1363. |
922 */ | 861 */ |
923 int BN_GF2m_mod_solve_quad_arr(BIGNUM *r, const BIGNUM *a_, const unsigned int p
[], BN_CTX *ctx) | 862 int BN_GF2m_mod_solve_quad_arr(BIGNUM *r, const BIGNUM *a_, const int p[], BN_CT
X *ctx) |
924 { | 863 { |
925 » int ret = 0, count = 0; | 864 » int ret = 0, count = 0, j; |
926 » unsigned int j; | |
927 BIGNUM *a, *z, *rho, *w, *w2, *tmp; | 865 BIGNUM *a, *z, *rho, *w, *w2, *tmp; |
928 | 866 |
929 bn_check_top(a_); | 867 bn_check_top(a_); |
930 | 868 |
931 if (!p[0]) | 869 if (!p[0]) |
932 { | 870 { |
933 /* reduction mod 1 => return 0 */ | 871 /* reduction mod 1 => return 0 */ |
934 BN_zero(r); | 872 BN_zero(r); |
935 return 1; | 873 return 1; |
936 } | 874 } |
(...skipping 74 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1011 | 949 |
1012 /* Find r such that r^2 + r = a mod p. r could be a. If no r exists returns 0. | 950 /* Find r such that r^2 + r = a mod p. r could be a. If no r exists returns 0. |
1013 * | 951 * |
1014 * This function calls down to the BN_GF2m_mod_solve_quad_arr implementation; th
is wrapper | 952 * This function calls down to the BN_GF2m_mod_solve_quad_arr implementation; th
is wrapper |
1015 * function is only provided for convenience; for best performance, use the | 953 * function is only provided for convenience; for best performance, use the |
1016 * BN_GF2m_mod_solve_quad_arr function. | 954 * BN_GF2m_mod_solve_quad_arr function. |
1017 */ | 955 */ |
1018 int BN_GF2m_mod_solve_quad(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *
ctx) | 956 int BN_GF2m_mod_solve_quad(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *
ctx) |
1019 { | 957 { |
1020 int ret = 0; | 958 int ret = 0; |
1021 » const int max = BN_num_bits(p); | 959 » const int max = BN_num_bits(p) + 1; |
1022 » unsigned int *arr=NULL; | 960 » int *arr=NULL; |
1023 bn_check_top(a); | 961 bn_check_top(a); |
1024 bn_check_top(p); | 962 bn_check_top(p); |
1025 » if ((arr = (unsigned int *)OPENSSL_malloc(sizeof(unsigned int) * | 963 » if ((arr = (int *)OPENSSL_malloc(sizeof(int) * |
1026 max)) == NULL) goto err; | 964 max)) == NULL) goto err; |
1027 ret = BN_GF2m_poly2arr(p, arr, max); | 965 ret = BN_GF2m_poly2arr(p, arr, max); |
1028 if (!ret || ret > max) | 966 if (!ret || ret > max) |
1029 { | 967 { |
1030 BNerr(BN_F_BN_GF2M_MOD_SOLVE_QUAD,BN_R_INVALID_LENGTH); | 968 BNerr(BN_F_BN_GF2M_MOD_SOLVE_QUAD,BN_R_INVALID_LENGTH); |
1031 goto err; | 969 goto err; |
1032 } | 970 } |
1033 ret = BN_GF2m_mod_solve_quad_arr(r, a, arr, ctx); | 971 ret = BN_GF2m_mod_solve_quad_arr(r, a, arr, ctx); |
1034 bn_check_top(r); | 972 bn_check_top(r); |
1035 err: | 973 err: |
1036 if (arr) OPENSSL_free(arr); | 974 if (arr) OPENSSL_free(arr); |
1037 return ret; | 975 return ret; |
1038 } | 976 } |
1039 | 977 |
1040 /* Convert the bit-string representation of a polynomial | 978 /* Convert the bit-string representation of a polynomial |
1041 * ( \sum_{i=0}^n a_i * x^i , where a_0 is *not* zero) into an array | 979 * ( \sum_{i=0}^n a_i * x^i) into an array of integers corresponding |
1042 * of integers corresponding to the bits with non-zero coefficient. | 980 * to the bits with non-zero coefficient. Array is terminated with -1. |
1043 * Up to max elements of the array will be filled. Return value is total | 981 * Up to max elements of the array will be filled. Return value is total |
1044 * number of coefficients that would be extracted if array was large enough. | 982 * number of array elements that would be filled if array was large enough. |
1045 */ | 983 */ |
1046 int BN_GF2m_poly2arr(const BIGNUM *a, unsigned int p[], int max) | 984 int BN_GF2m_poly2arr(const BIGNUM *a, int p[], int max) |
1047 { | 985 { |
1048 int i, j, k = 0; | 986 int i, j, k = 0; |
1049 BN_ULONG mask; | 987 BN_ULONG mask; |
1050 | 988 |
1051 » if (BN_is_zero(a) || !BN_is_bit_set(a, 0)) | 989 » if (BN_is_zero(a)) |
1052 » » /* a_0 == 0 => return error (the unsigned int array | |
1053 » » * must be terminated by 0) | |
1054 » » */ | |
1055 return 0; | 990 return 0; |
1056 | 991 |
1057 for (i = a->top - 1; i >= 0; i--) | 992 for (i = a->top - 1; i >= 0; i--) |
1058 { | 993 { |
1059 if (!a->d[i]) | 994 if (!a->d[i]) |
1060 /* skip word if a->d[i] == 0 */ | 995 /* skip word if a->d[i] == 0 */ |
1061 continue; | 996 continue; |
1062 mask = BN_TBIT; | 997 mask = BN_TBIT; |
1063 for (j = BN_BITS2 - 1; j >= 0; j--) | 998 for (j = BN_BITS2 - 1; j >= 0; j--) |
1064 { | 999 { |
1065 if (a->d[i] & mask) | 1000 if (a->d[i] & mask) |
1066 { | 1001 { |
1067 if (k < max) p[k] = BN_BITS2 * i + j; | 1002 if (k < max) p[k] = BN_BITS2 * i + j; |
1068 k++; | 1003 k++; |
1069 } | 1004 } |
1070 mask >>= 1; | 1005 mask >>= 1; |
1071 } | 1006 } |
1072 } | 1007 } |
1073 | 1008 |
| 1009 if (k < max) { |
| 1010 p[k] = -1; |
| 1011 k++; |
| 1012 } |
| 1013 |
1074 return k; | 1014 return k; |
1075 } | 1015 } |
1076 | 1016 |
1077 /* Convert the coefficient array representation of a polynomial to a | 1017 /* Convert the coefficient array representation of a polynomial to a |
1078 * bit-string. The array must be terminated by 0. | 1018 * bit-string. The array must be terminated by -1. |
1079 */ | 1019 */ |
1080 int BN_GF2m_arr2poly(const unsigned int p[], BIGNUM *a) | 1020 int BN_GF2m_arr2poly(const int p[], BIGNUM *a) |
1081 { | 1021 { |
1082 int i; | 1022 int i; |
1083 | 1023 |
1084 bn_check_top(a); | 1024 bn_check_top(a); |
1085 BN_zero(a); | 1025 BN_zero(a); |
1086 » for (i = 0; p[i] != 0; i++) | 1026 » for (i = 0; p[i] != -1; i++) |
1087 { | 1027 { |
1088 if (BN_set_bit(a, p[i]) == 0) | 1028 if (BN_set_bit(a, p[i]) == 0) |
1089 return 0; | 1029 return 0; |
1090 } | 1030 } |
1091 BN_set_bit(a, 0); | |
1092 bn_check_top(a); | 1031 bn_check_top(a); |
1093 | 1032 |
1094 return 1; | 1033 return 1; |
1095 } | 1034 } |
1096 | 1035 |
OLD | NEW |