diff options
-rw-r--r-- | crypto/bn/README.pod | 8 | ||||
-rw-r--r-- | crypto/bn/bn_intern.c | 15 | ||||
-rw-r--r-- | crypto/bn/bn_lcl.h | 6 | ||||
-rw-r--r-- | crypto/bn/bn_mul.c | 330 | ||||
-rw-r--r-- | crypto/bn/bn_prime.c | 124 | ||||
-rw-r--r-- | crypto/include/internal/bn_int.h | 11 |
6 files changed, 1 insertions, 493 deletions
diff --git a/crypto/bn/README.pod b/crypto/bn/README.pod index 109ab0d914..706a140342 100644 --- a/crypto/bn/README.pod +++ b/crypto/bn/README.pod @@ -6,7 +6,7 @@ bn_mul_words, bn_mul_add_words, bn_sqr_words, bn_div_words, bn_add_words, bn_sub_words, bn_mul_comba4, bn_mul_comba8, bn_sqr_comba4, bn_sqr_comba8, bn_cmp_words, bn_mul_normal, bn_mul_low_normal, bn_mul_recursive, bn_mul_part_recursive, -bn_mul_low_recursive, bn_mul_high, bn_sqr_normal, bn_sqr_recursive, +bn_mul_low_recursive, bn_sqr_normal, bn_sqr_recursive, bn_expand, bn_wexpand, bn_expand2, bn_fix_top, bn_check_top, bn_print, bn_dump, bn_set_max, bn_set_high, bn_set_low - BIGNUM library internal functions @@ -41,8 +41,6 @@ library internal functions int n, int tna, int tnb, BN_ULONG *tmp); void bn_mul_low_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2, BN_ULONG *tmp); - void bn_mul_high(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, BN_ULONG *l, - int n2, BN_ULONG *tmp); void bn_sqr_normal(BN_ULONG *r, BN_ULONG *a, int n, BN_ULONG *tmp); void bn_sqr_recursive(BN_ULONG *r, BN_ULONG *a, int n2, BN_ULONG *tmp); @@ -178,10 +176,6 @@ bn_mul_low_recursive(B<r>, B<a>, B<b>, B<n2>, B<tmp>) operates on the B<n2> word arrays B<r> and B<tmp> and the B<n2>/2 word arrays B<a> and B<b>. -bn_mul_high(B<r>, B<a>, B<b>, B<l>, B<n2>, B<tmp>) operates on the -B<n2> word arrays B<r>, B<a>, B<b> and B<l> (?) and the 3*B<n2> word -array B<tmp>. - BN_mul() calls bn_mul_normal(), or an optimized implementation if the factors have the same size: bn_mul_comba8() is used if they are 8 words long, bn_mul_recursive() if they are larger than diff --git a/crypto/bn/bn_intern.c b/crypto/bn/bn_intern.c index 2c970647de..2524eb2acf 100644 --- a/crypto/bn/bn_intern.c +++ b/crypto/bn/bn_intern.c @@ -143,11 +143,6 @@ int bn_get_top(const BIGNUM *a) return a->top; } -void bn_set_top(BIGNUM *a, int top) -{ - a->top = top; -} - int bn_get_dmax(const BIGNUM *a) { return a->dmax; @@ -198,13 +193,3 @@ int bn_set_words(BIGNUM *a, BN_ULONG *words, int num_words) bn_correct_top(a); return 1; } - -size_t bn_sizeof_BIGNUM(void) -{ - return sizeof(BIGNUM); -} - -BIGNUM *bn_array_el(BIGNUM *base, int el) -{ - return &base[el]; -} diff --git a/crypto/bn/bn_lcl.h b/crypto/bn/bn_lcl.h index eba8dd924e..5121c907ff 100644 --- a/crypto/bn/bn_lcl.h +++ b/crypto/bn/bn_lcl.h @@ -645,10 +645,6 @@ void bn_sqr_recursive(BN_ULONG *r, const BN_ULONG *a, int n2, BN_ULONG *t); void bn_mul_low_normal(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n); void bn_mul_low_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2, BN_ULONG *t); -void bn_mul_high(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, BN_ULONG *l, int n2, - BN_ULONG *t); -BN_ULONG bn_add_part_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b, - int cl, int dl); BN_ULONG bn_sub_part_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b, int cl, int dl); int bn_mul_mont(BN_ULONG *rp, const BN_ULONG *ap, const BN_ULONG *bp, @@ -660,8 +656,6 @@ BIGNUM *int_bn_mod_inverse(BIGNUM *in, int bn_probable_prime_dh(BIGNUM *rnd, int bits, const BIGNUM *add, const BIGNUM *rem, BN_CTX *ctx); -int bn_probable_prime_dh_retry(BIGNUM *rnd, int bits, BN_CTX *ctx); -int bn_probable_prime_dh_coprime(BIGNUM *rnd, int bits, BN_CTX *ctx); static ossl_inline BIGNUM *bn_expand(BIGNUM *a, int bits) { diff --git a/crypto/bn/bn_mul.c b/crypto/bn/bn_mul.c index 4a0a9505b7..1f28f64abb 100644 --- a/crypto/bn/bn_mul.c +++ b/crypto/bn/bn_mul.c @@ -152,166 +152,6 @@ BN_ULONG bn_sub_part_words(BN_ULONG *r, } #endif -BN_ULONG bn_add_part_words(BN_ULONG *r, - const BN_ULONG *a, const BN_ULONG *b, - int cl, int dl) -{ - BN_ULONG c, l, t; - - assert(cl >= 0); - c = bn_add_words(r, a, b, cl); - - if (dl == 0) - return c; - - r += cl; - a += cl; - b += cl; - - if (dl < 0) { - int save_dl = dl; - while (c) { - l = (c + b[0]) & BN_MASK2; - c = (l < c); - r[0] = l; - if (++dl >= 0) - break; - - l = (c + b[1]) & BN_MASK2; - c = (l < c); - r[1] = l; - if (++dl >= 0) - break; - - l = (c + b[2]) & BN_MASK2; - c = (l < c); - r[2] = l; - if (++dl >= 0) - break; - - l = (c + b[3]) & BN_MASK2; - c = (l < c); - r[3] = l; - if (++dl >= 0) - break; - - save_dl = dl; - b += 4; - r += 4; - } - if (dl < 0) { - if (save_dl < dl) { - switch (dl - save_dl) { - case 1: - r[1] = b[1]; - if (++dl >= 0) - break; - case 2: - r[2] = b[2]; - if (++dl >= 0) - break; - case 3: - r[3] = b[3]; - if (++dl >= 0) - break; - } - b += 4; - r += 4; - } - } - if (dl < 0) { - for (;;) { - r[0] = b[0]; - if (++dl >= 0) - break; - r[1] = b[1]; - if (++dl >= 0) - break; - r[2] = b[2]; - if (++dl >= 0) - break; - r[3] = b[3]; - if (++dl >= 0) - break; - - b += 4; - r += 4; - } - } - } else { - int save_dl = dl; - while (c) { - t = (a[0] + c) & BN_MASK2; - c = (t < c); - r[0] = t; - if (--dl <= 0) - break; - - t = (a[1] + c) & BN_MASK2; - c = (t < c); - r[1] = t; - if (--dl <= 0) - break; - - t = (a[2] + c) & BN_MASK2; - c = (t < c); - r[2] = t; - if (--dl <= 0) - break; - - t = (a[3] + c) & BN_MASK2; - c = (t < c); - r[3] = t; - if (--dl <= 0) - break; - - save_dl = dl; - a += 4; - r += 4; - } - if (dl > 0) { - if (save_dl > dl) { - switch (save_dl - dl) { - case 1: - r[1] = a[1]; - if (--dl <= 0) - break; - case 2: - r[2] = a[2]; - if (--dl <= 0) - break; - case 3: - r[3] = a[3]; - if (--dl <= 0) - break; - } - a += 4; - r += 4; - } - } - if (dl > 0) { - for (;;) { - r[0] = a[0]; - if (--dl <= 0) - break; - r[1] = a[1]; - if (--dl <= 0) - break; - r[2] = a[2]; - if (--dl <= 0) - break; - r[3] = a[3]; - if (--dl <= 0) - break; - - a += 4; - r += 4; - } - } - } - return c; -} - #ifdef BN_RECURSION /* * Karatsuba recursive multiplication algorithm (cf. Knuth, The Art of @@ -653,176 +493,6 @@ void bn_mul_low_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2, bn_add_words(&(r[n]), &(r[n]), &(t[n]), n); } } - -/*- - * a and b must be the same size, which is n2. - * r needs to be n2 words and t needs to be n2*2 - * l is the low words of the output. - * t needs to be n2*3 - */ -void bn_mul_high(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, BN_ULONG *l, int n2, - BN_ULONG *t) -{ - int i, n; - int c1, c2; - int neg, oneg, zero; - BN_ULONG ll, lc, *lp, *mp; - - n = n2 / 2; - - /* Calculate (al-ah)*(bh-bl) */ - neg = zero = 0; - c1 = bn_cmp_words(&(a[0]), &(a[n]), n); - c2 = bn_cmp_words(&(b[n]), &(b[0]), n); - switch (c1 * 3 + c2) { - case -4: - bn_sub_words(&(r[0]), &(a[n]), &(a[0]), n); - bn_sub_words(&(r[n]), &(b[0]), &(b[n]), n); - break; - case -3: - zero = 1; - break; - case -2: - bn_sub_words(&(r[0]), &(a[n]), &(a[0]), n); - bn_sub_words(&(r[n]), &(b[n]), &(b[0]), n); - neg = 1; - break; - case -1: - case 0: - case 1: - zero = 1; - break; - case 2: - bn_sub_words(&(r[0]), &(a[0]), &(a[n]), n); - bn_sub_words(&(r[n]), &(b[0]), &(b[n]), n); - neg = 1; - break; - case 3: - zero = 1; - break; - case 4: - bn_sub_words(&(r[0]), &(a[0]), &(a[n]), n); - bn_sub_words(&(r[n]), &(b[n]), &(b[0]), n); - break; - } - - oneg = neg; - /* t[10] = (a[0]-a[1])*(b[1]-b[0]) */ - /* r[10] = (a[1]*b[1]) */ -# ifdef BN_MUL_COMBA - if (n == 8) { - bn_mul_comba8(&(t[0]), &(r[0]), &(r[n])); - bn_mul_comba8(r, &(a[n]), &(b[n])); - } else -# endif - { - bn_mul_recursive(&(t[0]), &(r[0]), &(r[n]), n, 0, 0, &(t[n2])); - bn_mul_recursive(r, &(a[n]), &(b[n]), n, 0, 0, &(t[n2])); - } - - /*- - * s0 == low(al*bl) - * s1 == low(ah*bh)+low((al-ah)*(bh-bl))+low(al*bl)+high(al*bl) - * We know s0 and s1 so the only unknown is high(al*bl) - * high(al*bl) == s1 - low(ah*bh+s0+(al-ah)*(bh-bl)) - * high(al*bl) == s1 - (r[0]+l[0]+t[0]) - */ - if (l != NULL) { - lp = &(t[n2 + n]); - bn_add_words(lp, &(r[0]), &(l[0]), n); - } else { - lp = &(r[0]); - } - - if (neg) - neg = (int)(bn_sub_words(&(t[n2]), lp, &(t[0]), n)); - else { - bn_add_words(&(t[n2]), lp, &(t[0]), n); - neg = 0; - } - - if (l != NULL) { - bn_sub_words(&(t[n2 + n]), &(l[n]), &(t[n2]), n); - } else { - lp = &(t[n2 + n]); - mp = &(t[n2]); - for (i = 0; i < n; i++) - lp[i] = ((~mp[i]) + 1) & BN_MASK2; - } - - /*- - * s[0] = low(al*bl) - * t[3] = high(al*bl) - * t[10] = (a[0]-a[1])*(b[1]-b[0]) neg is the sign - * r[10] = (a[1]*b[1]) - */ - /*- - * R[10] = al*bl - * R[21] = al*bl + ah*bh + (a[0]-a[1])*(b[1]-b[0]) - * R[32] = ah*bh - */ - /*- - * R[1]=t[3]+l[0]+r[0](+-)t[0] (have carry/borrow) - * R[2]=r[0]+t[3]+r[1](+-)t[1] (have carry/borrow) - * R[3]=r[1]+(carry/borrow) - */ - if (l != NULL) { - lp = &(t[n2]); - c1 = (int)(bn_add_words(lp, &(t[n2 + n]), &(l[0]), n)); - } else { - lp = &(t[n2 + n]); - c1 = 0; - } - c1 += (int)(bn_add_words(&(t[n2]), lp, &(r[0]), n)); - if (oneg) - c1 -= (int)(bn_sub_words(&(t[n2]), &(t[n2]), &(t[0]), n)); - else - c1 += (int)(bn_add_words(&(t[n2]), &(t[n2]), &(t[0]), n)); - - c2 = (int)(bn_add_words(&(r[0]), &(r[0]), &(t[n2 + n]), n)); - c2 += (int)(bn_add_words(&(r[0]), &(r[0]), &(r[n]), n)); - if (oneg) - c2 -= (int)(bn_sub_words(&(r[0]), &(r[0]), &(t[n]), n)); - else - c2 += (int)(bn_add_words(&(r[0]), &(r[0]), &(t[n]), n)); - - if (c1 != 0) { /* Add starting at r[0], could be +ve or -ve */ - i = 0; - if (c1 > 0) { - lc = c1; - do { - ll = (r[i] + lc) & BN_MASK2; - r[i++] = ll; - lc = (lc > ll); - } while (lc); - } else { - lc = -c1; - do { - ll = r[i]; - r[i++] = (ll - lc) & BN_MASK2; - lc = (lc > ll); - } while (lc); - } - } - if (c2 != 0) { /* Add starting at r[1] */ - i = n; - if (c2 > 0) { - lc = c2; - do { - ll = (r[i] + lc) & BN_MASK2; - r[i++] = ll; - lc = (lc > ll); - } while (lc); - } else { - lc = -c2; - do { - ll = r[i]; - r[i++] = (ll - lc) & BN_MASK2; - lc = (lc > ll); - } while (lc); - } - } -} #endif /* BN_RECURSION */ int BN_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx) diff --git a/crypto/bn/bn_prime.c b/crypto/bn/bn_prime.c index 7103acfe0b..bbb124fb61 100644 --- a/crypto/bn/bn_prime.c +++ b/crypto/bn/bn_prime.c @@ -29,53 +29,6 @@ static int probable_prime_dh_safe(BIGNUM *rnd, int bits, const BIGNUM *add, const BIGNUM *rem, BN_CTX *ctx); -static const int prime_offsets[480] = { - 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, - 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, - 167, 169, 173, 179, 181, 191, 193, 197, 199, 211, 221, 223, 227, 229, - 233, 239, 241, 247, 251, 257, 263, 269, 271, 277, 281, 283, 289, 293, - 299, 307, 311, 313, 317, 323, 331, 337, 347, 349, 353, 359, 361, 367, - 373, 377, 379, 383, 389, 391, 397, 401, 403, 409, 419, 421, 431, 433, - 437, 439, 443, 449, 457, 461, 463, 467, 479, 481, 487, 491, 493, 499, - 503, 509, 521, 523, 527, 529, 533, 541, 547, 551, 557, 559, 563, 569, - 571, 577, 587, 589, 593, 599, 601, 607, 611, 613, 617, 619, 629, 631, - 641, 643, 647, 653, 659, 661, 667, 673, 677, 683, 689, 691, 697, 701, - 703, 709, 713, 719, 727, 731, 733, 739, 743, 751, 757, 761, 767, 769, - 773, 779, 787, 793, 797, 799, 809, 811, 817, 821, 823, 827, 829, 839, - 841, 851, 853, 857, 859, 863, 871, 877, 881, 883, 887, 893, 899, 901, - 907, 911, 919, 923, 929, 937, 941, 943, 947, 949, 953, 961, 967, 971, - 977, 983, 989, 991, 997, 1003, 1007, 1009, 1013, 1019, 1021, 1027, 1031, - 1033, 1037, 1039, 1049, 1051, 1061, 1063, 1069, 1073, 1079, 1081, 1087, - 1091, 1093, 1097, 1103, 1109, 1117, 1121, 1123, 1129, 1139, 1147, 1151, - 1153, 1157, 1159, 1163, 1171, 1181, 1187, 1189, 1193, 1201, 1207, 1213, - 1217, 1219, 1223, 1229, 1231, 1237, 1241, 1247, 1249, 1259, 1261, 1271, - 1273, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1313, 1319, - 1321, 1327, 1333, 1339, 1343, 1349, 1357, 1361, 1363, 1367, 1369, 1373, - 1381, 1387, 1391, 1399, 1403, 1409, 1411, 1417, 1423, 1427, 1429, 1433, - 1439, 1447, 1451, 1453, 1457, 1459, 1469, 1471, 1481, 1483, 1487, 1489, - 1493, 1499, 1501, 1511, 1513, 1517, 1523, 1531, 1537, 1541, 1543, 1549, - 1553, 1559, 1567, 1571, 1577, 1579, 1583, 1591, 1597, 1601, 1607, 1609, - 1613, 1619, 1621, 1627, 1633, 1637, 1643, 1649, 1651, 1657, 1663, 1667, - 1669, 1679, 1681, 1691, 1693, 1697, 1699, 1703, 1709, 1711, 1717, 1721, - 1723, 1733, 1739, 1741, 1747, 1751, 1753, 1759, 1763, 1769, 1777, 1781, - 1783, 1787, 1789, 1801, 1807, 1811, 1817, 1819, 1823, 1829, 1831, 1843, - 1847, 1849, 1853, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1891, 1901, - 1907, 1909, 1913, 1919, 1921, 1927, 1931, 1933, 1937, 1943, 1949, 1951, - 1957, 1961, 1963, 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017, - 2021, 2027, 2029, 2033, 2039, 2041, 2047, 2053, 2059, 2063, 2069, 2071, - 2077, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2117, 2119, 2129, 2131, - 2137, 2141, 2143, 2147, 2153, 2159, 2161, 2171, 2173, 2179, 2183, 2197, - 2201, 2203, 2207, 2209, 2213, 2221, 2227, 2231, 2237, 2239, 2243, 2249, - 2251, 2257, 2263, 2267, 2269, 2273, 2279, 2281, 2287, 2291, 2293, 2297, - 2309, 2311 -}; - -static const int prime_offset_count = 480; -static const int prime_multiplier = 2310; -static const int prime_multiplier_bits = 11; /* 2^|prime_multiplier_bits| <= - * |prime_multiplier| */ -static const int first_prime_index = 5; - int BN_GENCB_call(BN_GENCB *cb, int a, int b) { /* No callback means continue */ @@ -305,83 +258,6 @@ int BN_is_prime_fasttest_ex(const BIGNUM *a, int checks, BN_CTX *ctx_passed, return (ret); } -int bn_probable_prime_dh_retry(BIGNUM *rnd, int bits, BN_CTX *ctx) -{ - int i; - int ret = 0; - - loop: - if (!BN_rand(rnd, bits, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ODD)) - goto err; - - /* we now have a random number 'rand' to test. */ - - for (i = 1; i < NUMPRIMES; i++) { - /* check that rnd is a prime */ - BN_ULONG mod = BN_mod_word(rnd, (BN_ULONG)primes[i]); - if (mod == (BN_ULONG)-1) - goto err; - if (mod <= 1) { - goto loop; - } - } - ret = 1; - - err: - bn_check_top(rnd); - return (ret); -} - -int bn_probable_prime_dh_coprime(BIGNUM *rnd, int bits, BN_CTX *ctx) -{ - int i; - BIGNUM *offset_index; - BIGNUM *offset_count; - int ret = 0; - - OPENSSL_assert(bits > prime_multiplier_bits); - - BN_CTX_start(ctx); - if ((offset_index = BN_CTX_get(ctx)) == NULL) - goto err; - if ((offset_count = BN_CTX_get(ctx)) == NULL) - goto err; - - if (!BN_add_word(offset_count, prime_offset_count)) - goto err; - - loop: - if (!BN_rand(rnd, bits - prime_multiplier_bits, - BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ODD)) - goto err; - if (BN_is_bit_set(rnd, bits)) - goto loop; - if (!BN_rand_range(offset_index, offset_count)) - goto err; - - if (!BN_mul_word(rnd, prime_multiplier) - || !BN_add_word(rnd, prime_offsets[BN_get_word(offset_index)])) - goto err; - - /* we now have a random number 'rand' to test. */ - - /* skip coprimes */ - for (i = first_prime_index; i < NUMPRIMES; i++) { - /* check that rnd is a prime */ - BN_ULONG mod = BN_mod_word(rnd, (BN_ULONG)primes[i]); - if (mod == (BN_ULONG)-1) - goto err; - if (mod <= 1) - goto loop; - } - ret = 1; - - err: - BN_CTX_end(ctx); - bn_check_top(rnd); - return ret; -} - static int witness(BIGNUM *w, const BIGNUM *a, const BIGNUM *a1, const BIGNUM *a1_odd, int k, BN_CTX *ctx, BN_MONT_CTX *mont) diff --git a/crypto/include/internal/bn_int.h b/crypto/include/internal/bn_int.h index 9c984ba781..ac49d1eab3 100644 --- a/crypto/include/internal/bn_int.h +++ b/crypto/include/internal/bn_int.h @@ -34,8 +34,6 @@ signed char *bn_compute_wNAF(const BIGNUM *scalar, int w, size_t *ret_len); int bn_get_top(const BIGNUM *a); -void bn_set_top(BIGNUM *a, int top); - int bn_get_dmax(const BIGNUM *a); /* Set all words to zero */ @@ -66,15 +64,6 @@ void bn_set_static_words(BIGNUM *a, BN_ULONG *words, int size); */ int bn_set_words(BIGNUM *a, BN_ULONG *words, int num_words); -size_t bn_sizeof_BIGNUM(void); - -/* - * Return element el from an array of BIGNUMs starting at base (required - * because callers do not know the size of BIGNUM at compilation time) - */ -BIGNUM *bn_array_el(BIGNUM *base, int el); - - #ifdef __cplusplus } #endif |