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 "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);
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 int checks = BN_prime_checks_for_size(bits);
218 /* There are no prime numbers this small. */
219 BNerr(BN_F_BN_GENERATE_PRIME_EX, BN_R_BITS_TOO_SMALL);
221 } else if (bits == 2 && safe) {
222 /* The smallest safe prime (7) is three bits. */
223 BNerr(BN_F_BN_GENERATE_PRIME_EX, BN_R_BITS_TOO_SMALL);
235 /* make a random number and set the top and bottom bits */
237 if (!probable_prime(ret, bits))
241 if (!probable_prime_dh_safe(ret, bits, add, rem, ctx))
244 if (!bn_probable_prime_dh(ret, bits, add, rem, ctx))
248 /* if (BN_mod_word(ret,(BN_ULONG)3) == 1) goto loop; */
249 if (!BN_GENCB_call(cb, 0, c1++))
254 i = BN_is_prime_fasttest_ex(ret, checks, ctx, 0, cb);
261 * for "safe prime" generation, check that (p-1)/2 is prime. Since a
262 * prime is odd, We just need to divide by 2
264 if (!BN_rshift1(t, ret))
267 for (i = 0; i < checks; i++) {
268 j = BN_is_prime_fasttest_ex(ret, 1, ctx, 0, cb);
274 j = BN_is_prime_fasttest_ex(t, 1, ctx, 0, cb);
280 if (!BN_GENCB_call(cb, 2, c1 - 1))
282 /* We have a safe prime test pass */
285 /* we have a prime :-) */
295 int BN_is_prime_ex(const BIGNUM *a, int checks, BN_CTX *ctx_passed,
298 return BN_is_prime_fasttest_ex(a, checks, ctx_passed, 0, cb);
301 int BN_is_prime_fasttest_ex(const BIGNUM *a, int checks, BN_CTX *ctx_passed,
302 int do_trial_division, BN_GENCB *cb)
307 BIGNUM *A1, *A1_odd, *check; /* taken from ctx */
308 BN_MONT_CTX *mont = NULL;
309 const BIGNUM *A = NULL;
311 if (BN_cmp(a, BN_value_one()) <= 0)
314 if (checks == BN_prime_checks)
315 checks = BN_prime_checks_for_size(BN_num_bits(a));
317 /* first look for small factors */
319 /* a is even => a is prime if and only if a == 2 */
320 return BN_is_word(a, 2);
321 if (do_trial_division) {
322 for (i = 1; i < NUMPRIMES; i++)
323 if (BN_mod_word(a, primes[i]) == 0)
325 if (!BN_GENCB_call(cb, 1, -1))
329 if (ctx_passed != NULL)
331 else if ((ctx = BN_CTX_new()) == NULL)
338 if ((t = BN_CTX_get(ctx)) == NULL)
345 A1 = BN_CTX_get(ctx);
346 A1_odd = BN_CTX_get(ctx);
347 check = BN_CTX_get(ctx);
351 /* compute A1 := A - 1 */
354 if (!BN_sub_word(A1, 1))
356 if (BN_is_zero(A1)) {
361 /* write A1 as A1_odd * 2^k */
363 while (!BN_is_bit_set(A1, k))
365 if (!BN_rshift(A1_odd, A1, k))
368 /* Montgomery setup for computations mod A */
369 mont = BN_MONT_CTX_new();
372 if (!BN_MONT_CTX_set(mont, A, ctx))
375 for (i = 0; i < checks; i++) {
376 if (!BN_pseudo_rand_range(check, A1))
378 if (!BN_add_word(check, 1))
380 /* now 1 <= check < A */
382 j = witness(check, A, A1, A1_odd, k, ctx, mont);
389 if (!BN_GENCB_call(cb, 1, i))
396 if (ctx_passed == NULL)
399 BN_MONT_CTX_free(mont);
404 int bn_probable_prime_dh_retry(BIGNUM *rnd, int bits, BN_CTX *ctx)
410 if (!BN_rand(rnd, bits, 0, 1))
413 /* we now have a random number 'rand' to test. */
415 for (i = 1; i < NUMPRIMES; i++) {
416 /* check that rnd is a prime */
417 if (BN_mod_word(rnd, (BN_ULONG)primes[i]) <= 1) {
428 int bn_probable_prime_dh_coprime(BIGNUM *rnd, int bits, BN_CTX *ctx)
431 BIGNUM *offset_index;
432 BIGNUM *offset_count;
435 OPENSSL_assert(bits > prime_multiplier_bits);
438 if ((offset_index = BN_CTX_get(ctx)) == NULL)
440 if ((offset_count = BN_CTX_get(ctx)) == NULL)
443 BN_add_word(offset_count, prime_offset_count);
446 if (!BN_rand(rnd, bits - prime_multiplier_bits, 0, 1))
448 if (BN_is_bit_set(rnd, bits))
450 if (!BN_rand_range(offset_index, offset_count))
453 BN_mul_word(rnd, prime_multiplier);
454 BN_add_word(rnd, prime_offsets[BN_get_word(offset_index)]);
456 /* we now have a random number 'rand' to test. */
459 for (i = first_prime_index; i < NUMPRIMES; i++) {
460 /* check that rnd is a prime */
461 if (BN_mod_word(rnd, (BN_ULONG)primes[i]) <= 1) {
473 static int witness(BIGNUM *w, const BIGNUM *a, const BIGNUM *a1,
474 const BIGNUM *a1_odd, int k, BN_CTX *ctx,
477 if (!BN_mod_exp_mont(w, w, a1_odd, a, ctx, mont)) /* w := w^a1_odd mod a */
480 return 0; /* probably prime */
481 if (BN_cmp(w, a1) == 0)
482 return 0; /* w == -1 (mod a), 'a' is probably prime */
484 if (!BN_mod_mul(w, w, w, a, ctx)) /* w := w^2 mod a */
487 return 1; /* 'a' is composite, otherwise a previous 'w'
488 * would have been == -1 (mod 'a') */
489 if (BN_cmp(w, a1) == 0)
490 return 0; /* w == -1 (mod a), 'a' is probably prime */
493 * If we get here, 'w' is the (a-1)/2-th power of the original 'w', and
494 * it is neither -1 nor +1 -- so 'a' cannot be prime
500 static int probable_prime(BIGNUM *rnd, int bits)
503 prime_t mods[NUMPRIMES];
505 BN_ULONG maxdelta = BN_MASK2 - primes[NUMPRIMES - 1];
506 char is_single_word = bits <= BN_BITS2;
509 if (!BN_rand(rnd, bits, 1, 1))
511 /* we now have a random number 'rnd' to test. */
512 for (i = 1; i < NUMPRIMES; i++)
513 mods[i] = (prime_t) BN_mod_word(rnd, (BN_ULONG)primes[i]);
515 * If bits is so small that it fits into a single word then we
516 * additionally don't want to exceed that many bits.
518 if (is_single_word) {
521 if (bits == BN_BITS2) {
523 * Shifting by this much has undefined behaviour so we do it a
526 size_limit = ~((BN_ULONG)0) - BN_get_word(rnd);
528 size_limit = (((BN_ULONG)1) << bits) - BN_get_word(rnd) - 1;
530 if (size_limit < maxdelta)
531 maxdelta = size_limit;
535 if (is_single_word) {
536 BN_ULONG rnd_word = BN_get_word(rnd);
539 * In the case that the candidate prime is a single word then
541 * 1) It's greater than primes[i] because we shouldn't reject
542 * 3 as being a prime number because it's a multiple of
544 * 2) That it's not a multiple of a known prime. We don't
545 * check that rnd-1 is also coprime to all the known
546 * primes because there aren't many small primes where
549 for (i = 1; i < NUMPRIMES && primes[i] < rnd_word; i++) {
550 if ((mods[i] + delta) % primes[i] == 0) {
552 if (delta > maxdelta)
558 for (i = 1; i < NUMPRIMES; i++) {
560 * check that rnd is not a prime and also that gcd(rnd-1,primes)
561 * == 1 (except for 2)
563 if (((mods[i] + delta) % primes[i]) <= 1) {
565 if (delta > maxdelta)
571 if (!BN_add_word(rnd, delta))
573 if (BN_num_bits(rnd) != bits)
579 int bn_probable_prime_dh(BIGNUM *rnd, int bits,
580 const BIGNUM *add, const BIGNUM *rem, BN_CTX *ctx)
586 if ((t1 = BN_CTX_get(ctx)) == NULL)
589 if (!BN_rand(rnd, bits, 0, 1))
592 /* we need ((rnd-rem) % add) == 0 */
594 if (!BN_mod(t1, rnd, add, ctx))
596 if (!BN_sub(rnd, rnd, t1))
599 if (!BN_add_word(rnd, 1))
602 if (!BN_add(rnd, rnd, rem))
606 /* we now have a random number 'rand' to test. */
609 for (i = 1; i < NUMPRIMES; i++) {
610 /* check that rnd is a prime */
611 if (BN_mod_word(rnd, (BN_ULONG)primes[i]) <= 1) {
612 if (!BN_add(rnd, rnd, add))
625 static int probable_prime_dh_safe(BIGNUM *p, int bits, const BIGNUM *padd,
626 const BIGNUM *rem, BN_CTX *ctx)
629 BIGNUM *t1, *qadd, *q;
633 t1 = BN_CTX_get(ctx);
635 qadd = BN_CTX_get(ctx);
639 if (!BN_rshift1(qadd, padd))
642 if (!BN_rand(q, bits, 0, 1))
645 /* we need ((rnd-rem) % add) == 0 */
646 if (!BN_mod(t1, q, qadd, ctx))
648 if (!BN_sub(q, q, t1))
651 if (!BN_add_word(q, 1))
654 if (!BN_rshift1(t1, rem))
656 if (!BN_add(q, q, t1))
660 /* we now have a random number 'rand' to test. */
661 if (!BN_lshift1(p, q))
663 if (!BN_add_word(p, 1))
667 for (i = 1; i < NUMPRIMES; i++) {
668 /* check that p and q are prime */
670 * check that for p and q gcd(p-1,primes) == 1 (except for 2)
672 if ((BN_mod_word(p, (BN_ULONG)primes[i]) == 0) ||
673 (BN_mod_word(q, (BN_ULONG)primes[i]) == 0)) {
674 if (!BN_add(p, p, padd))
676 if (!BN_add(q, q, qadd))