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>
118 /* NB: these functions have been "upgraded", the deprecated versions (which are
119 * compatibility wrappers using these functions) are in bn_depr.c.
123 /* The quick sieve algorithm approach to weeding out primes is
124 * Philip Zimmermann's, as implemented in PGP. I have had a read of
125 * his comments and implemented my own version.
127 #include "bn_prime.h"
129 static int witness(BIGNUM *w, const BIGNUM *a, const BIGNUM *a1,
130 const BIGNUM *a1_odd, int k, BN_CTX *ctx, BN_MONT_CTX *mont);
131 static int probable_prime(BIGNUM *rnd, int bits);
132 static int probable_prime_dh_safe(BIGNUM *rnd, int bits,
133 const BIGNUM *add, const BIGNUM *rem, BN_CTX *ctx);
135 static const int prime_offsets[480] = {
136 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83,
137 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163,
138 167, 169, 173, 179, 181, 191, 193, 197, 199, 211, 221, 223, 227, 229,
139 233, 239, 241, 247, 251, 257, 263, 269, 271, 277, 281, 283, 289, 293,
140 299, 307, 311, 313, 317, 323, 331, 337, 347, 349, 353, 359, 361, 367,
141 373, 377, 379, 383, 389, 391, 397, 401, 403, 409, 419, 421, 431, 433,
142 437, 439, 443, 449, 457, 461, 463, 467, 479, 481, 487, 491, 493, 499,
143 503, 509, 521, 523, 527, 529, 533, 541, 547, 551, 557, 559, 563, 569,
144 571, 577, 587, 589, 593, 599, 601, 607, 611, 613, 617, 619, 629, 631,
145 641, 643, 647, 653, 659, 661, 667, 673, 677, 683, 689, 691, 697, 701,
146 703, 709, 713, 719, 727, 731, 733, 739, 743, 751, 757, 761, 767, 769,
147 773, 779, 787, 793, 797, 799, 809, 811, 817, 821, 823, 827, 829, 839,
148 841, 851, 853, 857, 859, 863, 871, 877, 881, 883, 887, 893, 899, 901,
149 907, 911, 919, 923, 929, 937, 941, 943, 947, 949, 953, 961, 967, 971,
150 977, 983, 989, 991, 997, 1003, 1007, 1009, 1013, 1019, 1021, 1027, 1031,
151 1033, 1037, 1039, 1049, 1051, 1061, 1063, 1069, 1073, 1079, 1081, 1087,
152 1091, 1093, 1097, 1103, 1109, 1117, 1121, 1123, 1129, 1139, 1147, 1151,
153 1153, 1157, 1159, 1163, 1171, 1181, 1187, 1189, 1193, 1201, 1207, 1213,
154 1217, 1219, 1223, 1229, 1231, 1237, 1241, 1247, 1249, 1259, 1261, 1271,
155 1273, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1313, 1319,
156 1321, 1327, 1333, 1339, 1343, 1349, 1357, 1361, 1363, 1367, 1369, 1373,
157 1381, 1387, 1391, 1399, 1403, 1409, 1411, 1417, 1423, 1427, 1429, 1433,
158 1439, 1447, 1451, 1453, 1457, 1459, 1469, 1471, 1481, 1483, 1487, 1489,
159 1493, 1499, 1501, 1511, 1513, 1517, 1523, 1531, 1537, 1541, 1543, 1549,
160 1553, 1559, 1567, 1571, 1577, 1579, 1583, 1591, 1597, 1601, 1607, 1609,
161 1613, 1619, 1621, 1627, 1633, 1637, 1643, 1649, 1651, 1657, 1663, 1667,
162 1669, 1679, 1681, 1691, 1693, 1697, 1699, 1703, 1709, 1711, 1717, 1721,
163 1723, 1733, 1739, 1741, 1747, 1751, 1753, 1759, 1763, 1769, 1777, 1781,
164 1783, 1787, 1789, 1801, 1807, 1811, 1817, 1819, 1823, 1829, 1831, 1843,
165 1847, 1849, 1853, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1891, 1901,
166 1907, 1909, 1913, 1919, 1921, 1927, 1931, 1933, 1937, 1943, 1949, 1951,
167 1957, 1961, 1963, 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017,
168 2021, 2027, 2029, 2033, 2039, 2041, 2047, 2053, 2059, 2063, 2069, 2071,
169 2077, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2117, 2119, 2129, 2131,
170 2137, 2141, 2143, 2147, 2153, 2159, 2161, 2171, 2173, 2179, 2183, 2197,
171 2201, 2203, 2207, 2209, 2213, 2221, 2227, 2231, 2237, 2239, 2243, 2249,
172 2251, 2257, 2263, 2267, 2269, 2273, 2279, 2281, 2287, 2291, 2293, 2297,
174 static const int prime_offset_count = 480;
175 static const int prime_multiplier = 2310;
176 static const int prime_multiplier_bits = 11; /* 2^|prime_multiplier_bits|
177 <= |prime_multiplier| */
178 static const int first_prime_index = 5;
180 int BN_GENCB_call(BN_GENCB *cb, int a, int b)
182 /* No callback means continue */
187 /* Deprecated-style callbacks */
190 cb->cb.cb_1(a, b, cb->arg);
193 /* New-style callbacks */
194 return cb->cb.cb_2(a, b, cb);
198 /* Unrecognised callback type */
202 int BN_generate_prime_ex(BIGNUM *ret, int bits, int safe,
203 const BIGNUM *add, const BIGNUM *rem, BN_GENCB *cb)
209 int checks = BN_prime_checks_for_size(bits);
213 /* There are no prime numbers this small. */
214 BNerr(BN_F_BN_GENERATE_PRIME_EX, BN_R_BITS_TOO_SMALL);
217 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);
225 if (ctx == NULL) goto err;
230 /* make a random number and set the top and bottom bits */
233 if (!probable_prime(ret,bits)) goto err;
239 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++))
255 i=BN_is_prime_fasttest_ex(ret,checks,ctx,0,cb);
256 if (i == -1) goto err;
257 if (i == 0) goto loop;
261 /* for "safe prime" generation,
262 * check that (p-1)/2 is prime.
263 * Since a prime is odd, We just
264 * need to divide by 2 */
265 if (!BN_rshift1(t,ret)) goto err;
267 for (i=0; i<checks; i++)
269 j=BN_is_prime_fasttest_ex(ret,1,ctx,0,cb);
270 if (j == -1) goto err;
271 if (j == 0) goto loop;
273 j=BN_is_prime_fasttest_ex(t,1,ctx,0,cb);
274 if (j == -1) goto err;
275 if (j == 0) goto loop;
277 if(!BN_GENCB_call(cb, 2, c1-1))
279 /* We have a safe prime test pass */
282 /* we have a prime :-) */
294 int BN_is_prime_ex(const BIGNUM *a, int checks, BN_CTX *ctx_passed, BN_GENCB *cb)
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)
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)
331 if ((ctx=BN_CTX_new()) == NULL)
339 if ((t = BN_CTX_get(ctx)) == NULL) goto err;
346 A1 = BN_CTX_get(ctx);
347 A1_odd = BN_CTX_get(ctx);
348 check = BN_CTX_get(ctx);
349 if (check == NULL) goto err;
351 /* compute A1 := A - 1 */
354 if (!BN_sub_word(A1, 1))
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++)
378 if (!BN_pseudo_rand_range(check, A1))
380 if (!BN_add_word(check, 1))
382 /* now 1 <= check < A */
384 j = witness(check, A, A1, A1_odd, k, ctx, mont);
385 if (j == -1) goto err;
391 if(!BN_GENCB_call(cb, 1, i))
399 if (ctx_passed == NULL)
403 BN_MONT_CTX_free(mont);
408 int bn_probable_prime_dh_retry(BIGNUM *rnd, int bits, BN_CTX *ctx)
414 if (!BN_rand(rnd, bits, 0, 1)) goto err;
416 /* we now have a random number 'rand' to test. */
418 for (i = 1; i < NUMPRIMES; i++)
420 /* check that rnd is a prime */
421 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) goto err;
444 if ((offset_count = BN_CTX_get(ctx)) == NULL) goto err;
446 BN_add_word(offset_count, prime_offset_count);
449 if (!BN_rand(rnd, bits - prime_multiplier_bits, 0, 1)) goto err;
450 if (BN_is_bit_set(rnd, bits)) goto loop;
451 if (!BN_rand_range(offset_index, offset_count)) goto err;
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++)
461 /* check that rnd is a prime */
462 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, BN_MONT_CTX *mont)
478 if (!BN_mod_exp_mont(w, w, a1_odd, a, ctx, mont)) /* w := w^a1_odd mod a */
481 return 0; /* probably prime */
482 if (BN_cmp(w, a1) == 0)
483 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' would
490 * have been == -1 (mod 'a') */
491 if (BN_cmp(w, a1) == 0)
492 return 0; /* w == -1 (mod a), 'a' is probably prime */
494 /* If we get here, 'w' is the (a-1)/2-th power of the original 'w',
495 * and 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)) return(0);
510 /* we now have a random number 'rnd' to test. */
511 for (i=1; i<NUMPRIMES; i++)
512 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. */
517 BN_ULONG size_limit = (((BN_ULONG) 1) << bits) - BN_get_word(rnd) - 1;
518 if (size_limit < maxdelta)
519 maxdelta = size_limit;
525 BN_ULONG rnd_word = BN_get_word(rnd);
527 /* In the case that the candidate prime is a single word then
529 * 1) It's greater than primes[i] because we shouldn't reject
530 * 3 as being a prime number because it's a multiple of
532 * 2) That it's not a multiple of a known prime. We don't
533 * check that rnd-1 is also coprime to all the known
534 * primes because there aren't many small primes where
536 for (i=1; i<NUMPRIMES && primes[i]<rnd_word; i++)
538 if ((mods[i]+delta)%primes[i] == 0)
541 if (delta > maxdelta) goto again;
548 for (i=1; i<NUMPRIMES; i++)
550 /* check that rnd is not a prime and also
551 * that gcd(rnd-1,primes) == 1 (except for 2) */
552 if (((mods[i]+delta)%primes[i]) <= 1)
555 if (delta > maxdelta) goto again;
560 if (!BN_add_word(rnd,delta)) return(0);
561 if (BN_num_bits(rnd) != bits)
567 int bn_probable_prime_dh(BIGNUM *rnd, int bits,
568 const BIGNUM *add, const BIGNUM *rem, BN_CTX *ctx)
574 if ((t1 = BN_CTX_get(ctx)) == NULL) goto err;
576 if (!BN_rand(rnd,bits,0,1)) goto err;
578 /* we need ((rnd-rem) % add) == 0 */
580 if (!BN_mod(t1,rnd,add,ctx)) goto err;
581 if (!BN_sub(rnd,rnd,t1)) goto err;
583 { if (!BN_add_word(rnd,1)) goto err; }
585 { if (!BN_add(rnd,rnd,rem)) goto err; }
587 /* we now have a random number 'rand' to test. */
590 for (i=1; i<NUMPRIMES; i++)
592 /* check that rnd is a prime */
593 if (BN_mod_word(rnd,(BN_ULONG)primes[i]) <= 1)
595 if (!BN_add(rnd,rnd,add)) goto err;
607 static int probable_prime_dh_safe(BIGNUM *p, int bits, const BIGNUM *padd,
608 const BIGNUM *rem, BN_CTX *ctx)
615 t1 = BN_CTX_get(ctx);
617 qadd = BN_CTX_get(ctx);
618 if (qadd == NULL) goto err;
620 if (!BN_rshift1(qadd,padd)) goto err;
622 if (!BN_rand(q,bits,0,1)) goto err;
624 /* we need ((rnd-rem) % add) == 0 */
625 if (!BN_mod(t1,q,qadd,ctx)) goto err;
626 if (!BN_sub(q,q,t1)) goto err;
628 { if (!BN_add_word(q,1)) goto err; }
631 if (!BN_rshift1(t1,rem)) goto err;
632 if (!BN_add(q,q,t1)) goto err;
635 /* we now have a random number 'rand' to test. */
636 if (!BN_lshift1(p,q)) goto err;
637 if (!BN_add_word(p,1)) goto err;
640 for (i=1; i<NUMPRIMES; i++)
642 /* check that p and q are prime */
643 /* check that for p and q
644 * gcd(p-1,primes) == 1 (except for 2) */
645 if ((BN_mod_word(p,(BN_ULONG)primes[i]) == 0) ||
646 (BN_mod_word(q,(BN_ULONG)primes[i]) == 0))
648 if (!BN_add(p,p,padd)) goto err;
649 if (!BN_add(q,q,qadd)) goto err;