summaryrefslogtreecommitdiff
path: root/src/lib/libcrypto/bn/bn_gf2m.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/lib/libcrypto/bn/bn_gf2m.c')
-rw-r--r--src/lib/libcrypto/bn/bn_gf2m.c142
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
143static 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
166static 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
193static void bn_GF2m_mul_1x1(BN_ULONG *r1, BN_ULONG *r0, const BN_ULONG a, const BN_ULONG b) 131static 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. */
324int BN_GF2m_mod_arr(BIGNUM *r, const BIGNUM *a, const unsigned int p[]) 262int 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[])
422int BN_GF2m_mod(BIGNUM *r, const BIGNUM *a, const BIGNUM *p) 360int 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 */
447int BN_GF2m_mod_mul_arr(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const unsigned int p[], BN_CTX *ctx) 385int 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:
500int BN_GF2m_mod_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *p, BN_CTX *ctx) 438int 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. */
524int BN_GF2m_mod_sqr_arr(BIGNUM *r, const BIGNUM *a, const unsigned int p[], BN_CTX *ctx) 462int 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:
556int BN_GF2m_mod_sqr(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx) 494int 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 */
646int BN_GF2m_mod_inv_arr(BIGNUM *r, const BIGNUM *xx, const unsigned int p[], BN_CTX *ctx) 584int 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 */
772int BN_GF2m_mod_div_arr(BIGNUM *r, const BIGNUM *yy, const BIGNUM *xx, const unsigned int p[], BN_CTX *ctx) 710int 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 */
797int BN_GF2m_mod_exp_arr(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const unsigned int p[], BN_CTX *ctx) 735int 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:
840int BN_GF2m_mod_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *p, BN_CTX *ctx) 778int 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 */
866int BN_GF2m_mod_sqrt_arr(BIGNUM *r, const BIGNUM *a, const unsigned int p[], BN_CTX *ctx) 804int 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:
899int BN_GF2m_mod_sqrt(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx) 837int 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 */
923int BN_GF2m_mod_solve_quad_arr(BIGNUM *r, const BIGNUM *a_, const unsigned int p[], BN_CTX *ctx) 861int 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:
1018int BN_GF2m_mod_solve_quad(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx) 955int 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 */
1046int BN_GF2m_poly2arr(const BIGNUM *a, unsigned int p[], int max) 983int 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 */
1080int BN_GF2m_arr2poly(const unsigned int p[], BIGNUM *a) 1019int 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;