1 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
4 * This package is an SSL implementation written
5 * by Eric Young (eay@cryptsoft.com).
6 * The implementation was written so as to conform with Netscapes SSL.
8 * This library is free for commercial and non-commercial use as long as
9 * the following conditions are aheared to. The following conditions
10 * apply to all code found in this distribution, be it the RC4, RSA,
11 * lhash, DES, etc., code; not just the SSL code. The SSL documentation
12 * included with this distribution is covered by the same copyright terms
13 * except that the holder is Tim Hudson (tjh@cryptsoft.com).
15 * Copyright remains Eric Young's, and as such any Copyright notices in
16 * the code are not to be removed.
17 * If this package is used in a product, Eric Young should be given attribution
18 * as the author of the parts of the library used.
19 * This can be in the form of a textual message at program startup or
20 * in documentation (online or textual) provided with the package.
22 * Redistribution and use in source and binary forms, with or without
23 * modification, are permitted provided that the following conditions
25 * 1. Redistributions of source code must retain the copyright
26 * notice, this list of conditions and the following disclaimer.
27 * 2. Redistributions in binary form must reproduce the above copyright
28 * notice, this list of conditions and the following disclaimer in the
29 * documentation and/or other materials provided with the distribution.
30 * 3. All advertising materials mentioning features or use of this software
31 * must display the following acknowledgement:
32 * "This product includes cryptographic software written by
33 * Eric Young (eay@cryptsoft.com)"
34 * The word 'cryptographic' can be left out if the rouines from the library
35 * being used are not cryptographic related :-).
36 * 4. If you include any Windows specific code (or a derivative thereof) from
37 * the apps directory (application code) you must include an acknowledgement:
38 * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
40 * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
41 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
42 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
43 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
44 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
45 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
46 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
47 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
48 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
49 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
52 * The licence and distribution terms for any publically available version or
53 * derivative of this code cannot be changed. i.e. this code cannot simply be
54 * copied and put under another distribution licence
55 * [including the GNU Public Licence.]
57 /* ====================================================================
58 * Copyright (c) 1998-2001 The OpenSSL Project. All rights reserved.
60 * Redistribution and use in source and binary forms, with or without
61 * modification, are permitted provided that the following conditions
64 * 1. Redistributions of source code must retain the above copyright
65 * notice, this list of conditions and the following disclaimer.
67 * 2. Redistributions in binary form must reproduce the above copyright
68 * notice, this list of conditions and the following disclaimer in
69 * the documentation and/or other materials provided with the
72 * 3. All advertising materials mentioning features or use of this
73 * software must display the following acknowledgment:
74 * "This product includes software developed by the OpenSSL Project
75 * for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
77 * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
78 * endorse or promote products derived from this software without
79 * prior written permission. For written permission, please contact
80 * openssl-core@openssl.org.
82 * 5. Products derived from this software may not be called "OpenSSL"
83 * nor may "OpenSSL" appear in their names without prior written
84 * permission of the OpenSSL Project.
86 * 6. Redistributions of any form whatsoever must retain the following
88 * "This product includes software developed by the OpenSSL Project
89 * for use in the OpenSSL Toolkit (http://www.openssl.org/)"
91 * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
92 * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
93 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
94 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR
95 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
96 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
97 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
98 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
99 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
100 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
101 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
102 * OF THE POSSIBILITY OF SUCH DAMAGE.
103 * ====================================================================
105 * This product includes cryptographic software written by Eric Young
106 * (eay@cryptsoft.com). This product includes software written by Tim
107 * Hudson (tjh@cryptsoft.com).
113 #include "internal/cryptlib.h"
115 #include <openssl/rand.h>
118 * The quick sieve algorithm approach to weeding out primes is Philip
119 * Zimmermann's, as implemented in PGP. I have had a read of his comments
120 * and implemented my own version.
122 #include "bn_prime.h"
124 static int witness(BIGNUM *w, const BIGNUM *a, const BIGNUM *a1,
125 const BIGNUM *a1_odd, int k, BN_CTX *ctx,
127 static int probable_prime(BIGNUM *rnd, int bits, prime_t *mods);
128 static int probable_prime_dh_safe(BIGNUM *rnd, int bits,
129 const BIGNUM *add, const BIGNUM *rem,
132 static const int prime_offsets[480] = {
133 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83,
134 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163,
135 167, 169, 173, 179, 181, 191, 193, 197, 199, 211, 221, 223, 227, 229,
136 233, 239, 241, 247, 251, 257, 263, 269, 271, 277, 281, 283, 289, 293,
137 299, 307, 311, 313, 317, 323, 331, 337, 347, 349, 353, 359, 361, 367,
138 373, 377, 379, 383, 389, 391, 397, 401, 403, 409, 419, 421, 431, 433,
139 437, 439, 443, 449, 457, 461, 463, 467, 479, 481, 487, 491, 493, 499,
140 503, 509, 521, 523, 527, 529, 533, 541, 547, 551, 557, 559, 563, 569,
141 571, 577, 587, 589, 593, 599, 601, 607, 611, 613, 617, 619, 629, 631,
142 641, 643, 647, 653, 659, 661, 667, 673, 677, 683, 689, 691, 697, 701,
143 703, 709, 713, 719, 727, 731, 733, 739, 743, 751, 757, 761, 767, 769,
144 773, 779, 787, 793, 797, 799, 809, 811, 817, 821, 823, 827, 829, 839,
145 841, 851, 853, 857, 859, 863, 871, 877, 881, 883, 887, 893, 899, 901,
146 907, 911, 919, 923, 929, 937, 941, 943, 947, 949, 953, 961, 967, 971,
147 977, 983, 989, 991, 997, 1003, 1007, 1009, 1013, 1019, 1021, 1027, 1031,
148 1033, 1037, 1039, 1049, 1051, 1061, 1063, 1069, 1073, 1079, 1081, 1087,
149 1091, 1093, 1097, 1103, 1109, 1117, 1121, 1123, 1129, 1139, 1147, 1151,
150 1153, 1157, 1159, 1163, 1171, 1181, 1187, 1189, 1193, 1201, 1207, 1213,
151 1217, 1219, 1223, 1229, 1231, 1237, 1241, 1247, 1249, 1259, 1261, 1271,
152 1273, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1313, 1319,
153 1321, 1327, 1333, 1339, 1343, 1349, 1357, 1361, 1363, 1367, 1369, 1373,
154 1381, 1387, 1391, 1399, 1403, 1409, 1411, 1417, 1423, 1427, 1429, 1433,
155 1439, 1447, 1451, 1453, 1457, 1459, 1469, 1471, 1481, 1483, 1487, 1489,
156 1493, 1499, 1501, 1511, 1513, 1517, 1523, 1531, 1537, 1541, 1543, 1549,
157 1553, 1559, 1567, 1571, 1577, 1579, 1583, 1591, 1597, 1601, 1607, 1609,
158 1613, 1619, 1621, 1627, 1633, 1637, 1643, 1649, 1651, 1657, 1663, 1667,
159 1669, 1679, 1681, 1691, 1693, 1697, 1699, 1703, 1709, 1711, 1717, 1721,
160 1723, 1733, 1739, 1741, 1747, 1751, 1753, 1759, 1763, 1769, 1777, 1781,
161 1783, 1787, 1789, 1801, 1807, 1811, 1817, 1819, 1823, 1829, 1831, 1843,
162 1847, 1849, 1853, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1891, 1901,
163 1907, 1909, 1913, 1919, 1921, 1927, 1931, 1933, 1937, 1943, 1949, 1951,
164 1957, 1961, 1963, 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017,
165 2021, 2027, 2029, 2033, 2039, 2041, 2047, 2053, 2059, 2063, 2069, 2071,
166 2077, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2117, 2119, 2129, 2131,
167 2137, 2141, 2143, 2147, 2153, 2159, 2161, 2171, 2173, 2179, 2183, 2197,
168 2201, 2203, 2207, 2209, 2213, 2221, 2227, 2231, 2237, 2239, 2243, 2249,
169 2251, 2257, 2263, 2267, 2269, 2273, 2279, 2281, 2287, 2291, 2293, 2297,
173 static const int prime_offset_count = 480;
174 static const int prime_multiplier = 2310;
175 static const int prime_multiplier_bits = 11; /* 2^|prime_multiplier_bits| <=
176 * |prime_multiplier| */
177 static const int first_prime_index = 5;
179 int BN_GENCB_call(BN_GENCB *cb, int a, int b)
181 /* No callback means continue */
186 /* Deprecated-style callbacks */
189 cb->cb.cb_1(a, b, cb->arg);
192 /* New-style callbacks */
193 return cb->cb.cb_2(a, b, cb);
197 /* Unrecognised callback type */
201 int BN_generate_prime_ex(BIGNUM *ret, int bits, int safe,
202 const BIGNUM *add, const BIGNUM *rem, BN_GENCB *cb)
208 prime_t *mods = NULL;
209 int checks = BN_prime_checks_for_size(bits);
212 /* There are no prime numbers this small. */
213 BNerr(BN_F_BN_GENERATE_PRIME_EX, BN_R_BITS_TOO_SMALL);
215 } else if (bits == 2 && safe) {
216 /* The smallest safe prime (7) is three bits. */
217 BNerr(BN_F_BN_GENERATE_PRIME_EX, BN_R_BITS_TOO_SMALL);
221 mods = OPENSSL_zalloc(sizeof(*mods) * NUMPRIMES);
233 /* make a random number and set the top and bottom bits */
235 if (!probable_prime(ret, bits, mods))
239 if (!probable_prime_dh_safe(ret, bits, add, rem, ctx))
242 if (!bn_probable_prime_dh(ret, bits, add, rem, ctx))
246 /* if (BN_mod_word(ret,(BN_ULONG)3) == 1) goto loop; */
247 if (!BN_GENCB_call(cb, 0, c1++))
252 i = BN_is_prime_fasttest_ex(ret, checks, ctx, 0, cb);
259 * for "safe prime" generation, check that (p-1)/2 is prime. Since a
260 * prime is odd, We just need to divide by 2
262 if (!BN_rshift1(t, ret))
265 for (i = 0; i < checks; i++) {
266 j = BN_is_prime_fasttest_ex(ret, 1, ctx, 0, cb);
272 j = BN_is_prime_fasttest_ex(t, 1, ctx, 0, cb);
278 if (!BN_GENCB_call(cb, 2, c1 - 1))
280 /* We have a safe prime test pass */
283 /* we have a prime :-) */
294 int BN_is_prime_ex(const BIGNUM *a, int checks, BN_CTX *ctx_passed,
297 return BN_is_prime_fasttest_ex(a, checks, ctx_passed, 0, cb);
300 int BN_is_prime_fasttest_ex(const BIGNUM *a, int checks, BN_CTX *ctx_passed,
301 int do_trial_division, BN_GENCB *cb)
306 BIGNUM *A1, *A1_odd, *check; /* taken from ctx */
307 BN_MONT_CTX *mont = NULL;
308 const BIGNUM *A = NULL;
310 if (BN_cmp(a, BN_value_one()) <= 0)
313 if (checks == BN_prime_checks)
314 checks = BN_prime_checks_for_size(BN_num_bits(a));
316 /* first look for small factors */
318 /* a is even => a is prime if and only if a == 2 */
319 return BN_is_word(a, 2);
320 if (do_trial_division) {
321 for (i = 1; i < NUMPRIMES; i++)
322 if (BN_mod_word(a, primes[i]) == 0)
324 if (!BN_GENCB_call(cb, 1, -1))
328 if (ctx_passed != NULL)
330 else if ((ctx = BN_CTX_new()) == NULL)
337 if ((t = BN_CTX_get(ctx)) == NULL)
344 A1 = BN_CTX_get(ctx);
345 A1_odd = BN_CTX_get(ctx);
346 check = BN_CTX_get(ctx);
350 /* compute A1 := A - 1 */
353 if (!BN_sub_word(A1, 1))
355 if (BN_is_zero(A1)) {
360 /* write A1 as A1_odd * 2^k */
362 while (!BN_is_bit_set(A1, k))
364 if (!BN_rshift(A1_odd, A1, k))
367 /* Montgomery setup for computations mod A */
368 mont = BN_MONT_CTX_new();
371 if (!BN_MONT_CTX_set(mont, A, ctx))
374 for (i = 0; i < checks; i++) {
375 if (!BN_pseudo_rand_range(check, A1))
377 if (!BN_add_word(check, 1))
379 /* now 1 <= check < A */
381 j = witness(check, A, A1, A1_odd, k, ctx, mont);
388 if (!BN_GENCB_call(cb, 1, i))
395 if (ctx_passed == NULL)
398 BN_MONT_CTX_free(mont);
403 int bn_probable_prime_dh_retry(BIGNUM *rnd, int bits, BN_CTX *ctx)
409 if (!BN_rand(rnd, bits, 0, 1))
412 /* we now have a random number 'rand' to test. */
414 for (i = 1; i < NUMPRIMES; i++) {
415 /* check that rnd is a prime */
416 if (BN_mod_word(rnd, (BN_ULONG)primes[i]) <= 1) {
427 int bn_probable_prime_dh_coprime(BIGNUM *rnd, int bits, BN_CTX *ctx)
430 BIGNUM *offset_index;
431 BIGNUM *offset_count;
434 OPENSSL_assert(bits > prime_multiplier_bits);
437 if ((offset_index = BN_CTX_get(ctx)) == NULL)
439 if ((offset_count = BN_CTX_get(ctx)) == NULL)
442 BN_add_word(offset_count, prime_offset_count);
445 if (!BN_rand(rnd, bits - prime_multiplier_bits, 0, 1))
447 if (BN_is_bit_set(rnd, bits))
449 if (!BN_rand_range(offset_index, offset_count))
452 BN_mul_word(rnd, prime_multiplier);
453 BN_add_word(rnd, prime_offsets[BN_get_word(offset_index)]);
455 /* we now have a random number 'rand' to test. */
458 for (i = first_prime_index; i < NUMPRIMES; i++) {
459 /* check that rnd is a prime */
460 if (BN_mod_word(rnd, (BN_ULONG)primes[i]) <= 1) {
472 static int witness(BIGNUM *w, const BIGNUM *a, const BIGNUM *a1,
473 const BIGNUM *a1_odd, int k, BN_CTX *ctx,
476 if (!BN_mod_exp_mont(w, w, a1_odd, a, ctx, mont)) /* w := w^a1_odd mod a */
479 return 0; /* probably prime */
480 if (BN_cmp(w, a1) == 0)
481 return 0; /* w == -1 (mod a), 'a' is probably prime */
483 if (!BN_mod_mul(w, w, w, a, ctx)) /* w := w^2 mod a */
486 return 1; /* 'a' is composite, otherwise a previous 'w'
487 * would have been == -1 (mod 'a') */
488 if (BN_cmp(w, a1) == 0)
489 return 0; /* w == -1 (mod a), 'a' is probably prime */
492 * If we get here, 'w' is the (a-1)/2-th power of the original 'w', and
493 * it is neither -1 nor +1 -- so 'a' cannot be prime
499 static int probable_prime(BIGNUM *rnd, int bits, prime_t *mods)
503 BN_ULONG maxdelta = BN_MASK2 - primes[NUMPRIMES - 1];
504 char is_single_word = bits <= BN_BITS2;
507 if (!BN_rand(rnd, bits, 1, 1))
509 /* we now have a random number 'rnd' to test. */
510 for (i = 1; i < NUMPRIMES; i++)
511 mods[i] = (prime_t) BN_mod_word(rnd, (BN_ULONG)primes[i]);
513 * If bits is so small that it fits into a single word then we
514 * additionally don't want to exceed that many bits.
516 if (is_single_word) {
519 if (bits == BN_BITS2) {
521 * Shifting by this much has undefined behaviour so we do it a
524 size_limit = ~((BN_ULONG)0) - BN_get_word(rnd);
526 size_limit = (((BN_ULONG)1) << bits) - BN_get_word(rnd) - 1;
528 if (size_limit < maxdelta)
529 maxdelta = size_limit;
533 if (is_single_word) {
534 BN_ULONG rnd_word = BN_get_word(rnd);
537 * In the case that the candidate prime is a single word then
539 * 1) It's greater than primes[i] because we shouldn't reject
540 * 3 as being a prime number because it's a multiple of
542 * 2) That it's not a multiple of a known prime. We don't
543 * check that rnd-1 is also coprime to all the known
544 * primes because there aren't many small primes where
547 for (i = 1; i < NUMPRIMES && primes[i] < rnd_word; i++) {
548 if ((mods[i] + delta) % primes[i] == 0) {
550 if (delta > maxdelta)
556 for (i = 1; i < NUMPRIMES; i++) {
558 * check that rnd is not a prime and also that gcd(rnd-1,primes)
559 * == 1 (except for 2)
561 if (((mods[i] + delta) % primes[i]) <= 1) {
563 if (delta > maxdelta)
569 if (!BN_add_word(rnd, delta))
571 if (BN_num_bits(rnd) != bits)
577 int bn_probable_prime_dh(BIGNUM *rnd, int bits,
578 const BIGNUM *add, const BIGNUM *rem, BN_CTX *ctx)
584 if ((t1 = BN_CTX_get(ctx)) == NULL)
587 if (!BN_rand(rnd, bits, 0, 1))
590 /* we need ((rnd-rem) % add) == 0 */
592 if (!BN_mod(t1, rnd, add, ctx))
594 if (!BN_sub(rnd, rnd, t1))
597 if (!BN_add_word(rnd, 1))
600 if (!BN_add(rnd, rnd, rem))
604 /* we now have a random number 'rand' to test. */
607 for (i = 1; i < NUMPRIMES; i++) {
608 /* check that rnd is a prime */
609 if (BN_mod_word(rnd, (BN_ULONG)primes[i]) <= 1) {
610 if (!BN_add(rnd, rnd, add))
623 static int probable_prime_dh_safe(BIGNUM *p, int bits, const BIGNUM *padd,
624 const BIGNUM *rem, BN_CTX *ctx)
627 BIGNUM *t1, *qadd, *q;
631 t1 = BN_CTX_get(ctx);
633 qadd = BN_CTX_get(ctx);
637 if (!BN_rshift1(qadd, padd))
640 if (!BN_rand(q, bits, 0, 1))
643 /* we need ((rnd-rem) % add) == 0 */
644 if (!BN_mod(t1, q, qadd, ctx))
646 if (!BN_sub(q, q, t1))
649 if (!BN_add_word(q, 1))
652 if (!BN_rshift1(t1, rem))
654 if (!BN_add(q, q, t1))
658 /* we now have a random number 'rand' to test. */
659 if (!BN_lshift1(p, q))
661 if (!BN_add_word(p, 1))
665 for (i = 1; i < NUMPRIMES; i++) {
666 /* check that p and q are prime */
668 * check that for p and q gcd(p-1,primes) == 1 (except for 2)
670 if ((BN_mod_word(p, (BN_ULONG)primes[i]) == 0) ||
671 (BN_mod_word(q, (BN_ULONG)primes[i]) == 0)) {
672 if (!BN_add(p, p, padd))
674 if (!BN_add(q, q, qadd))