diff options
Diffstat (limited to 'src/lib/libcrypto/bn/bn_gf2m.c')
-rw-r--r-- | src/lib/libcrypto/bn/bn_gf2m.c | 142 |
1 files changed, 40 insertions, 102 deletions
diff --git a/src/lib/libcrypto/bn/bn_gf2m.c b/src/lib/libcrypto/bn/bn_gf2m.c index ae642ccb39..527b0fa15b 100644 --- a/src/lib/libcrypto/bn/bn_gf2m.c +++ b/src/lib/libcrypto/bn/bn_gf2m.c | |||
@@ -121,74 +121,12 @@ static const BN_ULONG SQR_tb[16] = | |||
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 | { |
@@ -321,7 +259,7 @@ int BN_GF2m_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b) | |||
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; |
@@ -422,11 +360,11 @@ int BN_GF2m_mod_arr(BIGNUM *r, const BIGNUM *a, const unsigned int p[]) | |||
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 | { |
@@ -444,7 +382,7 @@ err: | |||
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 unsigned int p[], BN_CTX *ctx) | 385 | int BN_GF2m_mod_mul_arr(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const int 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; |
@@ -500,12 +438,12 @@ err: | |||
500 | int BN_GF2m_mod_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *p, BN_CTX *ctx) | 438 | int BN_GF2m_mod_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *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 | { |
@@ -521,7 +459,7 @@ err: | |||
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 *ctx) |
525 | { | 463 | { |
526 | int i, ret = 0; | 464 | int i, ret = 0; |
527 | BIGNUM *s; | 465 | BIGNUM *s; |
@@ -556,12 +494,12 @@ err: | |||
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 | { |
@@ -643,7 +581,7 @@ err: | |||
643 | * function is only provided for convenience; for best performance, use the | 581 | * function is only provided for convenience; for best performance, use the |
644 | * BN_GF2m_mod_inv function. | 582 | * BN_GF2m_mod_inv function. |
645 | */ | 583 | */ |
646 | int BN_GF2m_mod_inv_arr(BIGNUM *r, const BIGNUM *xx, const unsigned int p[], BN_CTX *ctx) | 584 | int BN_GF2m_mod_inv_arr(BIGNUM *r, const BIGNUM *xx, const int p[], BN_CTX *ctx) |
647 | { | 585 | { |
648 | BIGNUM *field; | 586 | BIGNUM *field; |
649 | int ret = 0; | 587 | int ret = 0; |
@@ -769,7 +707,7 @@ err: | |||
769 | * function is only provided for convenience; for best performance, use the | 707 | * function is only provided for convenience; for best performance, use the |
770 | * BN_GF2m_mod_div function. | 708 | * BN_GF2m_mod_div function. |
771 | */ | 709 | */ |
772 | int BN_GF2m_mod_div_arr(BIGNUM *r, const BIGNUM *yy, const BIGNUM *xx, const unsigned int p[], BN_CTX *ctx) | 710 | int BN_GF2m_mod_div_arr(BIGNUM *r, const BIGNUM *yy, const BIGNUM *xx, const int p[], BN_CTX *ctx) |
773 | { | 711 | { |
774 | BIGNUM *field; | 712 | BIGNUM *field; |
775 | int ret = 0; | 713 | int ret = 0; |
@@ -794,7 +732,7 @@ err: | |||
794 | * the result in r. r could be a. | 732 | * the result in r. r could be a. |
795 | * Uses simple square-and-multiply algorithm A.5.1 from IEEE P1363. | 733 | * Uses simple square-and-multiply algorithm A.5.1 from IEEE P1363. |
796 | */ | 734 | */ |
797 | int BN_GF2m_mod_exp_arr(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const unsigned int p[], BN_CTX *ctx) | 735 | int BN_GF2m_mod_exp_arr(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const int p[], BN_CTX *ctx) |
798 | { | 736 | { |
799 | int ret = 0, i, n; | 737 | int ret = 0, i, n; |
800 | BIGNUM *u; | 738 | BIGNUM *u; |
@@ -840,12 +778,12 @@ err: | |||
840 | int BN_GF2m_mod_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *p, BN_CTX *ctx) | 778 | int BN_GF2m_mod_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *p, BN_CTX *ctx) |
841 | { | 779 | { |
842 | int ret = 0; | 780 | int ret = 0; |
843 | const int max = BN_num_bits(p); | 781 | const int max = BN_num_bits(p) + 1; |
844 | unsigned int *arr=NULL; | 782 | int *arr=NULL; |
845 | bn_check_top(a); | 783 | bn_check_top(a); |
846 | bn_check_top(b); | 784 | bn_check_top(b); |
847 | bn_check_top(p); | 785 | bn_check_top(p); |
848 | if ((arr = (unsigned int *)OPENSSL_malloc(sizeof(unsigned int) * max)) == NULL) goto err; | 786 | if ((arr = (int *)OPENSSL_malloc(sizeof(int) * max)) == NULL) goto err; |
849 | ret = BN_GF2m_poly2arr(p, arr, max); | 787 | ret = BN_GF2m_poly2arr(p, arr, max); |
850 | if (!ret || ret > max) | 788 | if (!ret || ret > max) |
851 | { | 789 | { |
@@ -863,7 +801,7 @@ err: | |||
863 | * the result in r. r could be a. | 801 | * the result in r. r could be a. |
864 | * Uses exponentiation as in algorithm A.4.1 from IEEE P1363. | 802 | * Uses exponentiation as in algorithm A.4.1 from IEEE P1363. |
865 | */ | 803 | */ |
866 | int BN_GF2m_mod_sqrt_arr(BIGNUM *r, const BIGNUM *a, const unsigned int p[], BN_CTX *ctx) | 804 | int BN_GF2m_mod_sqrt_arr(BIGNUM *r, const BIGNUM *a, const int p[], BN_CTX *ctx) |
867 | { | 805 | { |
868 | int ret = 0; | 806 | int ret = 0; |
869 | BIGNUM *u; | 807 | BIGNUM *u; |
@@ -899,11 +837,11 @@ err: | |||
899 | int BN_GF2m_mod_sqrt(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx) | 837 | int BN_GF2m_mod_sqrt(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx) |
900 | { | 838 | { |
901 | int ret = 0; | 839 | int ret = 0; |
902 | const int max = BN_num_bits(p); | 840 | const int max = BN_num_bits(p) + 1; |
903 | unsigned int *arr=NULL; | 841 | int *arr=NULL; |
904 | bn_check_top(a); | 842 | bn_check_top(a); |
905 | bn_check_top(p); | 843 | bn_check_top(p); |
906 | if ((arr = (unsigned int *)OPENSSL_malloc(sizeof(unsigned int) * max)) == NULL) goto err; | 844 | if ((arr = (int *)OPENSSL_malloc(sizeof(int) * max)) == NULL) goto err; |
907 | ret = BN_GF2m_poly2arr(p, arr, max); | 845 | ret = BN_GF2m_poly2arr(p, arr, max); |
908 | if (!ret || ret > max) | 846 | if (!ret || ret > max) |
909 | { | 847 | { |
@@ -920,10 +858,9 @@ err: | |||
920 | /* Find r such that r^2 + r = a mod p. r could be a. If no r exists returns 0. | 858 | /* 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. | 859 | * Uses algorithms A.4.7 and A.4.6 from IEEE P1363. |
922 | */ | 860 | */ |
923 | int BN_GF2m_mod_solve_quad_arr(BIGNUM *r, const BIGNUM *a_, const unsigned int p[], BN_CTX *ctx) | 861 | int BN_GF2m_mod_solve_quad_arr(BIGNUM *r, const BIGNUM *a_, const int p[], BN_CTX *ctx) |
924 | { | 862 | { |
925 | int ret = 0, count = 0; | 863 | int ret = 0, count = 0, j; |
926 | unsigned int j; | ||
927 | BIGNUM *a, *z, *rho, *w, *w2, *tmp; | 864 | BIGNUM *a, *z, *rho, *w, *w2, *tmp; |
928 | 865 | ||
929 | bn_check_top(a_); | 866 | bn_check_top(a_); |
@@ -1018,11 +955,11 @@ err: | |||
1018 | int BN_GF2m_mod_solve_quad(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx) | 955 | int BN_GF2m_mod_solve_quad(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx) |
1019 | { | 956 | { |
1020 | int ret = 0; | 957 | int ret = 0; |
1021 | const int max = BN_num_bits(p); | 958 | const int max = BN_num_bits(p) + 1; |
1022 | unsigned int *arr=NULL; | 959 | int *arr=NULL; |
1023 | bn_check_top(a); | 960 | bn_check_top(a); |
1024 | bn_check_top(p); | 961 | bn_check_top(p); |
1025 | if ((arr = (unsigned int *)OPENSSL_malloc(sizeof(unsigned int) * | 962 | if ((arr = (int *)OPENSSL_malloc(sizeof(int) * |
1026 | max)) == NULL) goto err; | 963 | max)) == NULL) goto err; |
1027 | ret = BN_GF2m_poly2arr(p, arr, max); | 964 | ret = BN_GF2m_poly2arr(p, arr, max); |
1028 | if (!ret || ret > max) | 965 | if (!ret || ret > max) |
@@ -1038,20 +975,17 @@ err: | |||
1038 | } | 975 | } |
1039 | 976 | ||
1040 | /* Convert the bit-string representation of a polynomial | 977 | /* 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 | 978 | * ( \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. | 979 | * 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 | 980 | * 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. | 981 | * number of array elements that would be filled if array was large enough. |
1045 | */ | 982 | */ |
1046 | int BN_GF2m_poly2arr(const BIGNUM *a, unsigned int p[], int max) | 983 | int BN_GF2m_poly2arr(const BIGNUM *a, int p[], int max) |
1047 | { | 984 | { |
1048 | int i, j, k = 0; | 985 | int i, j, k = 0; |
1049 | BN_ULONG mask; | 986 | BN_ULONG mask; |
1050 | 987 | ||
1051 | if (BN_is_zero(a) || !BN_is_bit_set(a, 0)) | 988 | 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; | 989 | return 0; |
1056 | 990 | ||
1057 | for (i = a->top - 1; i >= 0; i--) | 991 | for (i = a->top - 1; i >= 0; i--) |
@@ -1071,24 +1005,28 @@ int BN_GF2m_poly2arr(const BIGNUM *a, unsigned int p[], int max) | |||
1071 | } | 1005 | } |
1072 | } | 1006 | } |
1073 | 1007 | ||
1008 | if (k < max) { | ||
1009 | p[k] = -1; | ||
1010 | k++; | ||
1011 | } | ||
1012 | |||
1074 | return k; | 1013 | return k; |
1075 | } | 1014 | } |
1076 | 1015 | ||
1077 | /* Convert the coefficient array representation of a polynomial to a | 1016 | /* Convert the coefficient array representation of a polynomial to a |
1078 | * bit-string. The array must be terminated by 0. | 1017 | * bit-string. The array must be terminated by -1. |
1079 | */ | 1018 | */ |
1080 | int BN_GF2m_arr2poly(const unsigned int p[], BIGNUM *a) | 1019 | int BN_GF2m_arr2poly(const int p[], BIGNUM *a) |
1081 | { | 1020 | { |
1082 | int i; | 1021 | int i; |
1083 | 1022 | ||
1084 | bn_check_top(a); | 1023 | bn_check_top(a); |
1085 | BN_zero(a); | 1024 | BN_zero(a); |
1086 | for (i = 0; p[i] != 0; i++) | 1025 | for (i = 0; p[i] != -1; i++) |
1087 | { | 1026 | { |
1088 | if (BN_set_bit(a, p[i]) == 0) | 1027 | if (BN_set_bit(a, p[i]) == 0) |
1089 | return 0; | 1028 | return 0; |
1090 | } | 1029 | } |
1091 | BN_set_bit(a, 0); | ||
1092 | bn_check_top(a); | 1030 | bn_check_top(a); |
1093 | 1031 | ||
1094 | return 1; | 1032 | return 1; |