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