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 int prime_offsets[480] = {
136 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89,
137 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167,
138 169, 173, 179, 181, 191, 193, 197, 199, 211, 221, 223, 227, 229, 233, 239,
139 241, 247, 251, 257, 263, 269, 271, 277, 281, 283, 289, 293, 299, 307, 311,
140 313, 317, 323, 331, 337, 347, 349, 353, 359, 361, 367, 373, 377, 379, 383,
141 389, 391, 397, 401, 403, 409, 419, 421, 431, 433, 437, 439, 443, 449, 457,
142 461, 463, 467, 479, 481, 487, 491, 493, 499, 503, 509, 521, 523, 527, 529,
143 533, 541, 547, 551, 557, 559, 563, 569, 571, 577, 587, 589, 593, 599, 601,
144 607, 611, 613, 617, 619, 629, 631, 641, 643, 647, 653, 659, 661, 667, 673,
145 677, 683, 689, 691, 697, 701, 703, 709, 713, 719, 727, 731, 733, 739, 743,
146 751, 757, 761, 767, 769, 773, 779, 787, 793, 797, 799, 809, 811, 817, 821,
147 823, 827, 829, 839, 841, 851, 853, 857, 859, 863, 871, 877, 881, 883, 887,
148 893, 899, 901, 907, 911, 919, 923, 929, 937, 941, 943, 947, 949, 953, 961,
149 967, 971, 977, 983, 989, 991, 997, 1003, 1007, 1009, 1013, 1019, 1021, 1027,
150 1031, 1033, 1037, 1039, 1049, 1051, 1061, 1063, 1069, 1073, 1079, 1081,
151 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1121, 1123, 1129, 1139, 1147,
152 1151, 1153, 1157, 1159, 1163, 1171, 1181, 1187, 1189, 1193, 1201, 1207,
153 1213, 1217, 1219, 1223, 1229, 1231, 1237, 1241, 1247, 1249, 1259, 1261,
154 1271, 1273, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1313,
155 1319, 1321, 1327, 1333, 1339, 1343, 1349, 1357, 1361, 1363, 1367, 1369,
156 1373, 1381, 1387, 1391, 1399, 1403, 1409, 1411, 1417, 1423, 1427, 1429,
157 1433, 1439, 1447, 1451, 1453, 1457, 1459, 1469, 1471, 1481, 1483, 1487,
158 1489, 1493, 1499, 1501, 1511, 1513, 1517, 1523, 1531, 1537, 1541, 1543,
159 1549, 1553, 1559, 1567, 1571, 1577, 1579, 1583, 1591, 1597, 1601, 1607,
160 1609, 1613, 1619, 1621, 1627, 1633, 1637, 1643, 1649, 1651, 1657, 1663,
161 1667, 1669, 1679, 1681, 1691, 1693, 1697, 1699, 1703, 1709, 1711, 1717,
162 1721, 1723, 1733, 1739, 1741, 1747, 1751, 1753, 1759, 1763, 1769, 1777,
163 1781, 1783, 1787, 1789, 1801, 1807, 1811, 1817, 1819, 1823, 1829, 1831,
164 1843, 1847, 1849, 1853, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1891,
165 1901, 1907, 1909, 1913, 1919, 1921, 1927, 1931, 1933, 1937, 1943, 1949,
166 1951, 1957, 1961, 1963, 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011,
167 2017, 2021, 2027, 2029, 2033, 2039, 2041, 2047, 2053, 2059, 2063, 2069,
168 2071, 2077, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2117, 2119, 2129,
169 2131, 2137, 2141, 2143, 2147, 2153, 2159, 2161, 2171, 2173, 2179, 2183,
170 2197, 2201, 2203, 2207, 2209, 2213, 2221, 2227, 2231, 2237, 2239, 2243,
171 2249, 2251, 2257, 2263, 2267, 2269, 2273, 2279, 2281, 2287, 2291, 2293,
173 static int prime_offset_count = 480;
174 static int prime_multiplier = 2310;
175 static int first_prime_index = 5;
177 int BN_GENCB_call(BN_GENCB *cb, int a, int b)
179 /* No callback means continue */
184 /* Deprecated-style callbacks */
187 cb->cb.cb_1(a, b, cb->arg);
190 /* New-style callbacks */
191 return cb->cb.cb_2(a, b, cb);
195 /* Unrecognised callback type */
199 int BN_generate_prime_ex(BIGNUM *ret, int bits, int safe,
200 const BIGNUM *add, const BIGNUM *rem, BN_GENCB *cb)
206 int checks = BN_prime_checks_for_size(bits);
210 /* There are no prime numbers this small. */
211 BNerr(BN_F_BN_GENERATE_PRIME_EX, BN_R_BITS_TOO_SMALL);
214 else if (bits == 2 && safe)
216 /* The smallest safe prime (7) is three bits. */
217 BNerr(BN_F_BN_GENERATE_PRIME_EX, BN_R_BITS_TOO_SMALL);
222 if (ctx == NULL) goto err;
227 /* make a random number and set the top and bottom bits */
230 if (!probable_prime(ret,bits)) goto err;
236 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++))
252 i=BN_is_prime_fasttest_ex(ret,checks,ctx,0,cb);
253 if (i == -1) goto err;
254 if (i == 0) goto loop;
258 /* for "safe prime" generation,
259 * check that (p-1)/2 is prime.
260 * Since a prime is odd, We just
261 * need to divide by 2 */
262 if (!BN_rshift1(t,ret)) goto err;
264 for (i=0; i<checks; i++)
266 j=BN_is_prime_fasttest_ex(ret,1,ctx,0,cb);
267 if (j == -1) goto err;
268 if (j == 0) goto loop;
270 j=BN_is_prime_fasttest_ex(t,1,ctx,0,cb);
271 if (j == -1) goto err;
272 if (j == 0) goto loop;
274 if(!BN_GENCB_call(cb, 2, c1-1))
276 /* We have a safe prime test pass */
279 /* we have a prime :-) */
291 int BN_is_prime_ex(const BIGNUM *a, int checks, BN_CTX *ctx_passed, BN_GENCB *cb)
293 return BN_is_prime_fasttest_ex(a, checks, ctx_passed, 0, cb);
296 int BN_is_prime_fasttest_ex(const BIGNUM *a, int checks, BN_CTX *ctx_passed,
297 int do_trial_division, BN_GENCB *cb)
302 BIGNUM *A1, *A1_odd, *check; /* taken from ctx */
303 BN_MONT_CTX *mont = NULL;
304 const BIGNUM *A = NULL;
306 if (BN_cmp(a, BN_value_one()) <= 0)
309 if (checks == BN_prime_checks)
310 checks = BN_prime_checks_for_size(BN_num_bits(a));
312 /* first look for small factors */
314 /* a is even => a is prime if and only if a == 2 */
315 return BN_is_word(a, 2);
316 if (do_trial_division)
318 for (i = 1; i < NUMPRIMES; i++)
319 if (BN_mod_word(a, primes[i]) == 0)
321 if(!BN_GENCB_call(cb, 1, -1))
325 if (ctx_passed != NULL)
328 if ((ctx=BN_CTX_new()) == NULL)
336 if ((t = BN_CTX_get(ctx)) == NULL) goto err;
343 A1 = BN_CTX_get(ctx);
344 A1_odd = BN_CTX_get(ctx);
345 check = BN_CTX_get(ctx);
346 if (check == NULL) goto err;
348 /* compute A1 := A - 1 */
351 if (!BN_sub_word(A1, 1))
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++)
375 if (!BN_pseudo_rand_range(check, A1))
377 if (!BN_add_word(check, 1))
379 /* now 1 <= check < A */
381 j = witness(check, A, A1, A1_odd, k, ctx, mont);
382 if (j == -1) goto err;
388 if(!BN_GENCB_call(cb, 1, i))
396 if (ctx_passed == NULL)
400 BN_MONT_CTX_free(mont);
405 int bn_probable_prime_dh_retry(BIGNUM *rnd, int bits, BN_CTX *ctx)
412 if ((t1 = BN_CTX_get(ctx)) == NULL) goto err;
415 if (!BN_rand(rnd, bits, 0, 1)) goto err;
417 /* we now have a random number 'rand' to test. */
419 for (i = 1; i < NUMPRIMES; i++)
421 /* check that rnd is a prime */
422 if (BN_mod_word(rnd, (BN_ULONG)primes[i]) <= 1)
435 int bn_probable_prime_dh_coprime(BIGNUM *rnd, int bits, BN_CTX *ctx)
439 BIGNUM *offset_index;
440 BIGNUM *offset_count;
444 if ((t1 = BN_CTX_get(ctx)) == NULL) goto err;
445 if ((offset_index = BN_CTX_get(ctx)) == NULL) goto err;
446 if ((offset_count = BN_CTX_get(ctx)) == NULL) goto err;
448 BN_add_word(offset_count, prime_offset_count);
451 if (!BN_rand(rnd, bits, 0, 1)) goto err;
452 if (!BN_rand_range(offset_index, offset_count)) goto err;
454 BN_mul_word(rnd, prime_multiplier);
455 BN_add_word(rnd, prime_offsets[BN_get_word(offset_index)]);
457 /* we now have a random number 'rand' to test. */
460 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)
476 static int witness(BIGNUM *w, const BIGNUM *a, const BIGNUM *a1,
477 const BIGNUM *a1_odd, int k, BN_CTX *ctx, BN_MONT_CTX *mont)
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 */
487 if (!BN_mod_mul(w, w, w, a, ctx)) /* w := w^2 mod a */
490 return 1; /* 'a' is composite, otherwise a previous 'w' would
491 * have been == -1 (mod 'a') */
492 if (BN_cmp(w, a1) == 0)
493 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',
496 * and it is neither -1 nor +1 -- so 'a' cannot be prime */
501 static int probable_prime(BIGNUM *rnd, int bits)
504 prime_t mods[NUMPRIMES];
506 BN_ULONG maxdelta = BN_MASK2 - primes[NUMPRIMES-1];
507 char is_single_word = bits <= BN_BITS2;
510 if (!BN_rand(rnd,bits,1,1)) return(0);
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]);
514 /* If bits is so small that it fits into a single word then we
515 * additionally don't want to exceed that many bits. */
518 BN_ULONG size_limit = (((BN_ULONG) 1) << bits) - BN_get_word(rnd) - 1;
519 if (size_limit < maxdelta)
520 maxdelta = size_limit;
526 BN_ULONG rnd_word = BN_get_word(rnd);
528 /* In the case that the candidate prime is a single word then
530 * 1) It's greater than primes[i] because we shouldn't reject
531 * 3 as being a prime number because it's a multiple of
533 * 2) That it's not a multiple of a known prime. We don't
534 * check that rnd-1 is also coprime to all the known
535 * primes because there aren't many small primes where
537 for (i=1; i<NUMPRIMES && primes[i]<rnd_word; i++)
539 if ((mods[i]+delta)%primes[i] == 0)
542 if (delta > maxdelta) goto again;
549 for (i=1; i<NUMPRIMES; i++)
551 /* check that rnd is not a prime and also
552 * that gcd(rnd-1,primes) == 1 (except for 2) */
553 if (((mods[i]+delta)%primes[i]) <= 1)
556 if (delta > maxdelta) goto again;
561 if (!BN_add_word(rnd,delta)) return(0);
562 if (BN_num_bits(rnd) != bits)
568 int bn_probable_prime_dh(BIGNUM *rnd, int bits,
569 const BIGNUM *add, const BIGNUM *rem, BN_CTX *ctx)
575 if ((t1 = BN_CTX_get(ctx)) == NULL) goto err;
577 if (!BN_rand(rnd,bits,0,1)) goto err;
579 /* we need ((rnd-rem) % add) == 0 */
581 if (!BN_mod(t1,rnd,add,ctx)) goto err;
582 if (!BN_sub(rnd,rnd,t1)) goto err;
584 { if (!BN_add_word(rnd,1)) goto err; }
586 { if (!BN_add(rnd,rnd,rem)) goto err; }
588 /* we now have a random number 'rand' to test. */
591 for (i=1; i<NUMPRIMES; i++)
593 /* check that rnd is a prime */
594 if (BN_mod_word(rnd,(BN_ULONG)primes[i]) <= 1)
596 if (!BN_add(rnd,rnd,add)) goto err;
608 static int probable_prime_dh_safe(BIGNUM *p, int bits, const BIGNUM *padd,
609 const BIGNUM *rem, BN_CTX *ctx)
616 t1 = BN_CTX_get(ctx);
618 qadd = BN_CTX_get(ctx);
619 if (qadd == NULL) goto err;
621 if (!BN_rshift1(qadd,padd)) goto err;
623 if (!BN_rand(q,bits,0,1)) goto err;
625 /* we need ((rnd-rem) % add) == 0 */
626 if (!BN_mod(t1,q,qadd,ctx)) goto err;
627 if (!BN_sub(q,q,t1)) goto err;
629 { if (!BN_add_word(q,1)) goto err; }
632 if (!BN_rshift1(t1,rem)) goto err;
633 if (!BN_add(q,q,t1)) goto err;
636 /* we now have a random number 'rand' to test. */
637 if (!BN_lshift1(p,q)) goto err;
638 if (!BN_add_word(p,1)) goto err;
641 for (i=1; i<NUMPRIMES; i++)
643 /* check that p and q are prime */
644 /* check that for p and q
645 * gcd(p-1,primes) == 1 (except for 2) */
646 if ((BN_mod_word(p,(BN_ULONG)primes[i]) == 0) ||
647 (BN_mod_word(q,(BN_ULONG)primes[i]) == 0))
649 if (!BN_add(p,p,padd)) goto err;
650 if (!BN_add(q,q,qadd)) goto err;