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);
211 mods = OPENSSL_zalloc(sizeof(*mods) * NUMPRIMES);
215 /* There are no prime numbers this small. */
216 BNerr(BN_F_BN_GENERATE_PRIME_EX, BN_R_BITS_TOO_SMALL);
218 } else if (bits == 2 && safe) {
219 /* The smallest safe prime (7) is three bits. */
220 BNerr(BN_F_BN_GENERATE_PRIME_EX, BN_R_BITS_TOO_SMALL);
232 /* make a random number and set the top and bottom bits */
234 if (!probable_prime(ret, bits, mods))
238 if (!probable_prime_dh_safe(ret, bits, add, rem, ctx))
241 if (!bn_probable_prime_dh(ret, bits, add, rem, ctx))
245 /* if (BN_mod_word(ret,(BN_ULONG)3) == 1) goto loop; */
246 if (!BN_GENCB_call(cb, 0, c1++))
251 i = BN_is_prime_fasttest_ex(ret, checks, ctx, 0, cb);
258 * for "safe prime" generation, check that (p-1)/2 is prime. Since a
259 * prime is odd, We just need to divide by 2
261 if (!BN_rshift1(t, ret))
264 for (i = 0; i < checks; i++) {
265 j = BN_is_prime_fasttest_ex(ret, 1, ctx, 0, cb);
271 j = BN_is_prime_fasttest_ex(t, 1, ctx, 0, cb);
277 if (!BN_GENCB_call(cb, 2, c1 - 1))
279 /* We have a safe prime test pass */
282 /* we have a prime :-) */
293 int BN_is_prime_ex(const BIGNUM *a, int checks, BN_CTX *ctx_passed,
296 return BN_is_prime_fasttest_ex(a, checks, ctx_passed, 0, cb);
299 int BN_is_prime_fasttest_ex(const BIGNUM *a, int checks, BN_CTX *ctx_passed,
300 int do_trial_division, BN_GENCB *cb)
305 BIGNUM *A1, *A1_odd, *check; /* taken from ctx */
306 BN_MONT_CTX *mont = NULL;
307 const BIGNUM *A = NULL;
309 if (BN_cmp(a, BN_value_one()) <= 0)
312 if (checks == BN_prime_checks)
313 checks = BN_prime_checks_for_size(BN_num_bits(a));
315 /* first look for small factors */
317 /* a is even => a is prime if and only if a == 2 */
318 return BN_is_word(a, 2);
319 if (do_trial_division) {
320 for (i = 1; i < NUMPRIMES; i++)
321 if (BN_mod_word(a, primes[i]) == 0)
323 if (!BN_GENCB_call(cb, 1, -1))
327 if (ctx_passed != NULL)
329 else if ((ctx = BN_CTX_new()) == NULL)
336 if ((t = BN_CTX_get(ctx)) == NULL)
343 A1 = BN_CTX_get(ctx);
344 A1_odd = BN_CTX_get(ctx);
345 check = BN_CTX_get(ctx);
349 /* compute A1 := A - 1 */
352 if (!BN_sub_word(A1, 1))
354 if (BN_is_zero(A1)) {
359 /* write A1 as A1_odd * 2^k */
361 while (!BN_is_bit_set(A1, k))
363 if (!BN_rshift(A1_odd, A1, k))
366 /* Montgomery setup for computations mod A */
367 mont = BN_MONT_CTX_new();
370 if (!BN_MONT_CTX_set(mont, A, ctx))
373 for (i = 0; i < checks; i++) {
374 if (!BN_pseudo_rand_range(check, A1))
376 if (!BN_add_word(check, 1))
378 /* now 1 <= check < A */
380 j = witness(check, A, A1, A1_odd, k, ctx, mont);
387 if (!BN_GENCB_call(cb, 1, i))
394 if (ctx_passed == NULL)
397 BN_MONT_CTX_free(mont);
402 int bn_probable_prime_dh_retry(BIGNUM *rnd, int bits, BN_CTX *ctx)
408 if (!BN_rand(rnd, bits, 0, 1))
411 /* we now have a random number 'rand' to test. */
413 for (i = 1; i < NUMPRIMES; i++) {
414 /* check that rnd is a prime */
415 if (BN_mod_word(rnd, (BN_ULONG)primes[i]) <= 1) {
426 int bn_probable_prime_dh_coprime(BIGNUM *rnd, int bits, BN_CTX *ctx)
429 BIGNUM *offset_index;
430 BIGNUM *offset_count;
433 OPENSSL_assert(bits > prime_multiplier_bits);
436 if ((offset_index = BN_CTX_get(ctx)) == NULL)
438 if ((offset_count = BN_CTX_get(ctx)) == NULL)
441 BN_add_word(offset_count, prime_offset_count);
444 if (!BN_rand(rnd, bits - prime_multiplier_bits, 0, 1))
446 if (BN_is_bit_set(rnd, bits))
448 if (!BN_rand_range(offset_index, offset_count))
451 BN_mul_word(rnd, prime_multiplier);
452 BN_add_word(rnd, prime_offsets[BN_get_word(offset_index)]);
454 /* we now have a random number 'rand' to test. */
457 for (i = first_prime_index; i < NUMPRIMES; i++) {
458 /* check that rnd is a prime */
459 if (BN_mod_word(rnd, (BN_ULONG)primes[i]) <= 1) {
471 static int witness(BIGNUM *w, const BIGNUM *a, const BIGNUM *a1,
472 const BIGNUM *a1_odd, int k, BN_CTX *ctx,
475 if (!BN_mod_exp_mont(w, w, a1_odd, a, ctx, mont)) /* w := w^a1_odd mod a */
478 return 0; /* probably prime */
479 if (BN_cmp(w, a1) == 0)
480 return 0; /* w == -1 (mod a), 'a' is probably prime */
482 if (!BN_mod_mul(w, w, w, a, ctx)) /* w := w^2 mod a */
485 return 1; /* 'a' is composite, otherwise a previous 'w'
486 * would have been == -1 (mod 'a') */
487 if (BN_cmp(w, a1) == 0)
488 return 0; /* w == -1 (mod a), 'a' is probably prime */
491 * If we get here, 'w' is the (a-1)/2-th power of the original 'w', and
492 * it is neither -1 nor +1 -- so 'a' cannot be prime
498 static int probable_prime(BIGNUM *rnd, int bits, prime_t *mods)
502 BN_ULONG maxdelta = BN_MASK2 - primes[NUMPRIMES - 1];
503 char is_single_word = bits <= BN_BITS2;
506 if (!BN_rand(rnd, bits, 1, 1))
508 /* we now have a random number 'rnd' to test. */
509 for (i = 1; i < NUMPRIMES; i++)
510 mods[i] = (prime_t) BN_mod_word(rnd, (BN_ULONG)primes[i]);
512 * If bits is so small that it fits into a single word then we
513 * additionally don't want to exceed that many bits.
515 if (is_single_word) {
518 if (bits == BN_BITS2) {
520 * Shifting by this much has undefined behaviour so we do it a
523 size_limit = ~((BN_ULONG)0) - BN_get_word(rnd);
525 size_limit = (((BN_ULONG)1) << bits) - BN_get_word(rnd) - 1;
527 if (size_limit < maxdelta)
528 maxdelta = size_limit;
532 if (is_single_word) {
533 BN_ULONG rnd_word = BN_get_word(rnd);
536 * In the case that the candidate prime is a single word then
538 * 1) It's greater than primes[i] because we shouldn't reject
539 * 3 as being a prime number because it's a multiple of
541 * 2) That it's not a multiple of a known prime. We don't
542 * check that rnd-1 is also coprime to all the known
543 * primes because there aren't many small primes where
546 for (i = 1; i < NUMPRIMES && primes[i] < rnd_word; i++) {
547 if ((mods[i] + delta) % primes[i] == 0) {
549 if (delta > maxdelta)
555 for (i = 1; i < NUMPRIMES; i++) {
557 * check that rnd is not a prime and also that gcd(rnd-1,primes)
558 * == 1 (except for 2)
560 if (((mods[i] + delta) % primes[i]) <= 1) {
562 if (delta > maxdelta)
568 if (!BN_add_word(rnd, delta))
570 if (BN_num_bits(rnd) != bits)
576 int bn_probable_prime_dh(BIGNUM *rnd, int bits,
577 const BIGNUM *add, const BIGNUM *rem, BN_CTX *ctx)
583 if ((t1 = BN_CTX_get(ctx)) == NULL)
586 if (!BN_rand(rnd, bits, 0, 1))
589 /* we need ((rnd-rem) % add) == 0 */
591 if (!BN_mod(t1, rnd, add, ctx))
593 if (!BN_sub(rnd, rnd, t1))
596 if (!BN_add_word(rnd, 1))
599 if (!BN_add(rnd, rnd, rem))
603 /* we now have a random number 'rand' to test. */
606 for (i = 1; i < NUMPRIMES; i++) {
607 /* check that rnd is a prime */
608 if (BN_mod_word(rnd, (BN_ULONG)primes[i]) <= 1) {
609 if (!BN_add(rnd, rnd, add))
622 static int probable_prime_dh_safe(BIGNUM *p, int bits, const BIGNUM *padd,
623 const BIGNUM *rem, BN_CTX *ctx)
626 BIGNUM *t1, *qadd, *q;
630 t1 = BN_CTX_get(ctx);
632 qadd = BN_CTX_get(ctx);
636 if (!BN_rshift1(qadd, padd))
639 if (!BN_rand(q, bits, 0, 1))
642 /* we need ((rnd-rem) % add) == 0 */
643 if (!BN_mod(t1, q, qadd, ctx))
645 if (!BN_sub(q, q, t1))
648 if (!BN_add_word(q, 1))
651 if (!BN_rshift1(t1, rem))
653 if (!BN_add(q, q, t1))
657 /* we now have a random number 'rand' to test. */
658 if (!BN_lshift1(p, q))
660 if (!BN_add_word(p, 1))
664 for (i = 1; i < NUMPRIMES; i++) {
665 /* check that p and q are prime */
667 * check that for p and q gcd(p-1,primes) == 1 (except for 2)
669 if ((BN_mod_word(p, (BN_ULONG)primes[i]) == 0) ||
670 (BN_mod_word(q, (BN_ULONG)primes[i]) == 0)) {
671 if (!BN_add(p, p, padd))
673 if (!BN_add(q, q, qadd))