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 :-) */
296 int BN_is_prime_ex(const BIGNUM *a, int checks, BN_CTX *ctx_passed,
299 return BN_is_prime_fasttest_ex(a, checks, ctx_passed, 0, cb);
302 int BN_is_prime_fasttest_ex(const BIGNUM *a, int checks, BN_CTX *ctx_passed,
303 int do_trial_division, BN_GENCB *cb)
308 BIGNUM *A1, *A1_odd, *check; /* taken from ctx */
309 BN_MONT_CTX *mont = NULL;
310 const BIGNUM *A = NULL;
312 if (BN_cmp(a, BN_value_one()) <= 0)
315 if (checks == BN_prime_checks)
316 checks = BN_prime_checks_for_size(BN_num_bits(a));
318 /* first look for small factors */
320 /* a is even => a is prime if and only if a == 2 */
321 return BN_is_word(a, 2);
322 if (do_trial_division) {
323 for (i = 1; i < NUMPRIMES; i++)
324 if (BN_mod_word(a, primes[i]) == 0)
326 if (!BN_GENCB_call(cb, 1, -1))
330 if (ctx_passed != NULL)
332 else if ((ctx = BN_CTX_new()) == NULL)
339 if ((t = BN_CTX_get(ctx)) == NULL)
346 A1 = BN_CTX_get(ctx);
347 A1_odd = BN_CTX_get(ctx);
348 check = BN_CTX_get(ctx);
352 /* compute A1 := A - 1 */
355 if (!BN_sub_word(A1, 1))
357 if (BN_is_zero(A1)) {
362 /* write A1 as A1_odd * 2^k */
364 while (!BN_is_bit_set(A1, k))
366 if (!BN_rshift(A1_odd, A1, k))
369 /* Montgomery setup for computations mod A */
370 mont = BN_MONT_CTX_new();
373 if (!BN_MONT_CTX_set(mont, A, ctx))
376 for (i = 0; i < checks; i++) {
377 if (!BN_pseudo_rand_range(check, A1))
379 if (!BN_add_word(check, 1))
381 /* now 1 <= check < A */
383 j = witness(check, A, A1, A1_odd, k, ctx, mont);
390 if (!BN_GENCB_call(cb, 1, i))
397 if (ctx_passed == NULL)
401 BN_MONT_CTX_free(mont);
406 int bn_probable_prime_dh_retry(BIGNUM *rnd, int bits, BN_CTX *ctx)
412 if (!BN_rand(rnd, bits, 0, 1))
415 /* we now have a random number 'rand' to test. */
417 for (i = 1; i < NUMPRIMES; i++) {
418 /* check that rnd is a prime */
419 if (BN_mod_word(rnd, (BN_ULONG)primes[i]) <= 1) {
430 int bn_probable_prime_dh_coprime(BIGNUM *rnd, int bits, BN_CTX *ctx)
433 BIGNUM *offset_index;
434 BIGNUM *offset_count;
437 OPENSSL_assert(bits > prime_multiplier_bits);
440 if ((offset_index = BN_CTX_get(ctx)) == NULL)
442 if ((offset_count = BN_CTX_get(ctx)) == NULL)
445 BN_add_word(offset_count, prime_offset_count);
448 if (!BN_rand(rnd, bits - prime_multiplier_bits, 0, 1))
450 if (BN_is_bit_set(rnd, bits))
452 if (!BN_rand_range(offset_index, offset_count))
455 BN_mul_word(rnd, prime_multiplier);
456 BN_add_word(rnd, prime_offsets[BN_get_word(offset_index)]);
458 /* we now have a random number 'rand' to test. */
461 for (i = first_prime_index; i < NUMPRIMES; i++) {
462 /* check that rnd is a prime */
463 if (BN_mod_word(rnd, (BN_ULONG)primes[i]) <= 1) {
475 static int witness(BIGNUM *w, const BIGNUM *a, const BIGNUM *a1,
476 const BIGNUM *a1_odd, int k, BN_CTX *ctx,
479 if (!BN_mod_exp_mont(w, w, a1_odd, a, ctx, mont)) /* w := w^a1_odd mod a */
482 return 0; /* probably prime */
483 if (BN_cmp(w, a1) == 0)
484 return 0; /* w == -1 (mod a), 'a' is probably prime */
486 if (!BN_mod_mul(w, w, w, a, ctx)) /* w := w^2 mod a */
489 return 1; /* 'a' is composite, otherwise a previous 'w'
490 * would have been == -1 (mod 'a') */
491 if (BN_cmp(w, a1) == 0)
492 return 0; /* w == -1 (mod a), 'a' is probably prime */
495 * If we get here, 'w' is the (a-1)/2-th power of the original 'w', and
496 * it is neither -1 nor +1 -- so 'a' cannot be prime
502 static int probable_prime(BIGNUM *rnd, int bits)
505 prime_t mods[NUMPRIMES];
507 BN_ULONG maxdelta = BN_MASK2 - primes[NUMPRIMES - 1];
508 char is_single_word = bits <= BN_BITS2;
511 if (!BN_rand(rnd, bits, 1, 1))
513 /* we now have a random number 'rnd' to test. */
514 for (i = 1; i < NUMPRIMES; i++)
515 mods[i] = (prime_t) BN_mod_word(rnd, (BN_ULONG)primes[i]);
517 * If bits is so small that it fits into a single word then we
518 * additionally don't want to exceed that many bits.
520 if (is_single_word) {
523 if (bits == BN_BITS2) {
525 * Shifting by this much has undefined behaviour so we do it a
528 size_limit = ~((BN_ULONG)0) - BN_get_word(rnd);
530 size_limit = (((BN_ULONG)1) << bits) - BN_get_word(rnd) - 1;
532 if (size_limit < maxdelta)
533 maxdelta = size_limit;
537 if (is_single_word) {
538 BN_ULONG rnd_word = BN_get_word(rnd);
541 * In the case that the candidate prime is a single word then
543 * 1) It's greater than primes[i] because we shouldn't reject
544 * 3 as being a prime number because it's a multiple of
546 * 2) That it's not a multiple of a known prime. We don't
547 * check that rnd-1 is also coprime to all the known
548 * primes because there aren't many small primes where
551 for (i = 1; i < NUMPRIMES && primes[i] < rnd_word; i++) {
552 if ((mods[i] + delta) % primes[i] == 0) {
554 if (delta > maxdelta)
560 for (i = 1; i < NUMPRIMES; i++) {
562 * check that rnd is not a prime and also that gcd(rnd-1,primes)
563 * == 1 (except for 2)
565 if (((mods[i] + delta) % primes[i]) <= 1) {
567 if (delta > maxdelta)
573 if (!BN_add_word(rnd, delta))
575 if (BN_num_bits(rnd) != bits)
581 int bn_probable_prime_dh(BIGNUM *rnd, int bits,
582 const BIGNUM *add, const BIGNUM *rem, BN_CTX *ctx)
588 if ((t1 = BN_CTX_get(ctx)) == NULL)
591 if (!BN_rand(rnd, bits, 0, 1))
594 /* we need ((rnd-rem) % add) == 0 */
596 if (!BN_mod(t1, rnd, add, ctx))
598 if (!BN_sub(rnd, rnd, t1))
601 if (!BN_add_word(rnd, 1))
604 if (!BN_add(rnd, rnd, rem))
608 /* we now have a random number 'rand' to test. */
611 for (i = 1; i < NUMPRIMES; i++) {
612 /* check that rnd is a prime */
613 if (BN_mod_word(rnd, (BN_ULONG)primes[i]) <= 1) {
614 if (!BN_add(rnd, rnd, add))
627 static int probable_prime_dh_safe(BIGNUM *p, int bits, const BIGNUM *padd,
628 const BIGNUM *rem, BN_CTX *ctx)
631 BIGNUM *t1, *qadd, *q;
635 t1 = BN_CTX_get(ctx);
637 qadd = BN_CTX_get(ctx);
641 if (!BN_rshift1(qadd, padd))
644 if (!BN_rand(q, bits, 0, 1))
647 /* we need ((rnd-rem) % add) == 0 */
648 if (!BN_mod(t1, q, qadd, ctx))
650 if (!BN_sub(q, q, t1))
653 if (!BN_add_word(q, 1))
656 if (!BN_rshift1(t1, rem))
658 if (!BN_add(q, q, t1))
662 /* we now have a random number 'rand' to test. */
663 if (!BN_lshift1(p, q))
665 if (!BN_add_word(p, 1))
669 for (i = 1; i < NUMPRIMES; i++) {
670 /* check that p and q are prime */
672 * check that for p and q gcd(p-1,primes) == 1 (except for 2)
674 if ((BN_mod_word(p, (BN_ULONG)primes[i]) == 0) ||
675 (BN_mod_word(q, (BN_ULONG)primes[i]) == 0)) {
676 if (!BN_add(p, p, padd))
678 if (!BN_add(q, q, qadd))