crypto/bn/bn_prime.c

   1 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
   2  * All rights reserved.
   3  *
   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.
   7  *
   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).
  14  *
  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.
  21  *
  22  * Redistribution and use in source and binary forms, with or without
  23  * modification, are permitted provided that the following conditions
  24  * are met:
  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)"
  39  *
  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
  50  * SUCH DAMAGE.
  51  *
  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.]
  56  */
  57 /* ====================================================================
  58  * Copyright (c) 1998-2001 The OpenSSL Project.  All rights reserved.
  59  *
  60  * Redistribution and use in source and binary forms, with or without
  61  * modification, are permitted provided that the following conditions
  62  * are met:
  63  *
  64  * 1. Redistributions of source code must retain the above copyright
  65  *    notice, this list of conditions and the following disclaimer.
  66  *
  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
  70  *    distribution.
  71  *
  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/)"
  76  *
  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.
  81  *
  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.
  85  *
  86  * 6. Redistributions of any form whatsoever must retain the following
  87  *    acknowledgment:
  88  *    "This product includes software developed by the OpenSSL Project
  89  *    for use in the OpenSSL Toolkit (http://www.openssl.org/)"
  90  *
  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  * ====================================================================
 104  *
 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).
 108  *
 109  */
 110
 111 #include <stdio.h>
 112 #include <time.h>
 113 #include "internal/cryptlib.h"
 114 #include "bn_lcl.h"
 115 #include <openssl/rand.h>
 116
 117 /*
 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.
 121  */
 122 #include "bn_prime.h"
 123
 124 static int witness(BIGNUM *w, const BIGNUM *a, const BIGNUM *a1,
 125                    const BIGNUM *a1_odd, int k, BN_CTX *ctx,
 126                    BN_MONT_CTX *mont);
 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,
 130                                   BN_CTX *ctx);
 131
 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,
 170     2309, 2311
 171 };
 172
 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;
 178
 179 int BN_GENCB_call(BN_GENCB *cb, int a, int b)
 180 {
 181     /* No callback means continue */
 182     if (!cb)
 183         return 1;
 184     switch (cb->ver) {
 185     case 1:
 186         /* Deprecated-style callbacks */
 187         if (!cb->cb.cb_1)
 188             return 1;
 189         cb->cb.cb_1(a, b, cb->arg);
 190         return 1;
 191     case 2:
 192         /* New-style callbacks */
 193         return cb->cb.cb_2(a, b, cb);
 194     default:
 195         break;
 196     }
 197     /* Unrecognised callback type */
 198     return 0;
 199 }
 200
 201 int BN_generate_prime_ex(BIGNUM *ret, int bits, int safe,
 202                          const BIGNUM *add, const BIGNUM *rem, BN_GENCB *cb)
 203 {
 204     BIGNUM *t;
 205     int found = 0;
 206     int i, j, c1 = 0;
 207     BN_CTX *ctx = NULL;
 208     prime_t *mods = NULL;
 209     int checks = BN_prime_checks_for_size(bits);
 210
 211     mods = OPENSSL_zalloc(sizeof(*mods) * NUMPRIMES);
 212     if (mods == NULL)
 213         goto err;
 214     if (bits < 2) {
 215         /* There are no prime numbers this small. */
 216         BNerr(BN_F_BN_GENERATE_PRIME_EX, BN_R_BITS_TOO_SMALL);
 217         return 0;
 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);
 221         return 0;
 222     }
 223
 224     ctx = BN_CTX_new();
 225     if (ctx == NULL)
 226         goto err;
 227     BN_CTX_start(ctx);
 228     t = BN_CTX_get(ctx);
 229     if (!t)
 230         goto err;
 231  loop:
 232     /* make a random number and set the top and bottom bits */
 233     if (add == NULL) {
 234         if (!probable_prime(ret, bits, mods))
 235             goto err;
 236     } else {
 237         if (safe) {
 238             if (!probable_prime_dh_safe(ret, bits, add, rem, ctx))
 239                 goto err;
 240         } else {
 241             if (!bn_probable_prime_dh(ret, bits, add, rem, ctx))
 242                 goto err;
 243         }
 244     }
 245     /* if (BN_mod_word(ret,(BN_ULONG)3) == 1) goto loop; */
 246     if (!BN_GENCB_call(cb, 0, c1++))
 247         /* aborted */
 248         goto err;
 249
 250     if (!safe) {
 251         i = BN_is_prime_fasttest_ex(ret, checks, ctx, 0, cb);
 252         if (i == -1)
 253             goto err;
 254         if (i == 0)
 255             goto loop;
 256     } else {
 257         /*
 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
 260          */
 261         if (!BN_rshift1(t, ret))
 262             goto err;
 263
 264         for (i = 0; i < checks; i++) {
 265             j = BN_is_prime_fasttest_ex(ret, 1, ctx, 0, cb);
 266             if (j == -1)
 267                 goto err;
 268             if (j == 0)
 269                 goto loop;
 270
 271             j = BN_is_prime_fasttest_ex(t, 1, ctx, 0, cb);
 272             if (j == -1)
 273                 goto err;
 274             if (j == 0)
 275                 goto loop;
 276
 277             if (!BN_GENCB_call(cb, 2, c1 - 1))
 278                 goto err;
 279             /* We have a safe prime test pass */
 280         }
 281     }
 282     /* we have a prime :-) */
 283     found = 1;
 284  err:
 285     OPENSSL_free(mods);
 286     if (ctx != NULL)
 287         BN_CTX_end(ctx);
 288     BN_CTX_free(ctx);
 289     bn_check_top(ret);
 290     return found;
 291 }
 292
 293 int BN_is_prime_ex(const BIGNUM *a, int checks, BN_CTX *ctx_passed,
 294                    BN_GENCB *cb)
 295 {
 296     return BN_is_prime_fasttest_ex(a, checks, ctx_passed, 0, cb);
 297 }
 298
 299 int BN_is_prime_fasttest_ex(const BIGNUM *a, int checks, BN_CTX *ctx_passed,
 300                             int do_trial_division, BN_GENCB *cb)
 301 {
 302     int i, j, ret = -1;
 303     int k;
 304     BN_CTX *ctx = NULL;
 305     BIGNUM *A1, *A1_odd, *check; /* taken from ctx */
 306     BN_MONT_CTX *mont = NULL;
 307     const BIGNUM *A = NULL;
 308
 309     if (BN_cmp(a, BN_value_one()) <= 0)
 310         return 0;
 311
 312     if (checks == BN_prime_checks)
 313         checks = BN_prime_checks_for_size(BN_num_bits(a));
 314
 315     /* first look for small factors */
 316     if (!BN_is_odd(a))
 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)
 322                 return 0;
 323         if (!BN_GENCB_call(cb, 1, -1))
 324             goto err;
 325     }
 326
 327     if (ctx_passed != NULL)
 328         ctx = ctx_passed;
 329     else if ((ctx = BN_CTX_new()) == NULL)
 330         goto err;
 331     BN_CTX_start(ctx);
 332
 333     /* A := abs(a) */
 334     if (a->neg) {
 335         BIGNUM *t;
 336         if ((t = BN_CTX_get(ctx)) == NULL)
 337             goto err;
 338         BN_copy(t, a);
 339         t->neg = 0;
 340         A = t;
 341     } else
 342         A = a;
 343     A1 = BN_CTX_get(ctx);
 344     A1_odd = BN_CTX_get(ctx);
 345     check = BN_CTX_get(ctx);
 346     if (check == NULL)
 347         goto err;
 348
 349     /* compute A1 := A - 1 */
 350     if (!BN_copy(A1, A))
 351         goto err;
 352     if (!BN_sub_word(A1, 1))
 353         goto err;
 354     if (BN_is_zero(A1)) {
 355         ret = 0;
 356         goto err;
 357     }
 358
 359     /* write  A1  as  A1_odd * 2^k */
 360     k = 1;
 361     while (!BN_is_bit_set(A1, k))
 362         k++;
 363     if (!BN_rshift(A1_odd, A1, k))
 364         goto err;
 365
 366     /* Montgomery setup for computations mod A */
 367     mont = BN_MONT_CTX_new();
 368     if (mont == NULL)
 369         goto err;
 370     if (!BN_MONT_CTX_set(mont, A, ctx))
 371         goto err;
 372
 373     for (i = 0; i < checks; i++) {
 374         if (!BN_pseudo_rand_range(check, A1))
 375             goto err;
 376         if (!BN_add_word(check, 1))
 377             goto err;
 378         /* now 1 <= check < A */
 379
 380         j = witness(check, A, A1, A1_odd, k, ctx, mont);
 381         if (j == -1)
 382             goto err;
 383         if (j) {
 384             ret = 0;
 385             goto err;
 386         }
 387         if (!BN_GENCB_call(cb, 1, i))
 388             goto err;
 389     }
 390     ret = 1;
 391  err:
 392     if (ctx != NULL) {
 393         BN_CTX_end(ctx);
 394         if (ctx_passed == NULL)
 395             BN_CTX_free(ctx);
 396     }
 397     BN_MONT_CTX_free(mont);
 398
 399     return (ret);
 400 }
 401
 402 int bn_probable_prime_dh_retry(BIGNUM *rnd, int bits, BN_CTX *ctx)
 403 {
 404     int i;
 405     int ret = 0;
 406
 407  loop:
 408     if (!BN_rand(rnd, bits, 0, 1))
 409         goto err;
 410
 411     /* we now have a random number 'rand' to test. */
 412
 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) {
 416             goto loop;
 417         }
 418     }
 419     ret = 1;
 420
 421  err:
 422     bn_check_top(rnd);
 423     return (ret);
 424 }
 425
 426 int bn_probable_prime_dh_coprime(BIGNUM *rnd, int bits, BN_CTX *ctx)
 427 {
 428     int i;
 429     BIGNUM *offset_index;
 430     BIGNUM *offset_count;
 431     int ret = 0;
 432
 433     OPENSSL_assert(bits > prime_multiplier_bits);
 434
 435     BN_CTX_start(ctx);
 436     if ((offset_index = BN_CTX_get(ctx)) == NULL)
 437         goto err;
 438     if ((offset_count = BN_CTX_get(ctx)) == NULL)
 439         goto err;
 440
 441     BN_add_word(offset_count, prime_offset_count);
 442
 443  loop:
 444     if (!BN_rand(rnd, bits - prime_multiplier_bits, 0, 1))
 445         goto err;
 446     if (BN_is_bit_set(rnd, bits))
 447         goto loop;
 448     if (!BN_rand_range(offset_index, offset_count))
 449         goto err;
 450
 451     BN_mul_word(rnd, prime_multiplier);
 452     BN_add_word(rnd, prime_offsets[BN_get_word(offset_index)]);
 453
 454     /* we now have a random number 'rand' to test. */
 455
 456     /* skip coprimes */
 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) {
 460             goto loop;
 461         }
 462     }
 463     ret = 1;
 464
 465  err:
 466     BN_CTX_end(ctx);
 467     bn_check_top(rnd);
 468     return ret;
 469 }
 470
 471 static int witness(BIGNUM *w, const BIGNUM *a, const BIGNUM *a1,
 472                    const BIGNUM *a1_odd, int k, BN_CTX *ctx,
 473                    BN_MONT_CTX *mont)
 474 {
 475     if (!BN_mod_exp_mont(w, w, a1_odd, a, ctx, mont)) /* w := w^a1_odd mod a */
 476         return -1;
 477     if (BN_is_one(w))
 478         return 0;               /* probably prime */
 479     if (BN_cmp(w, a1) == 0)
 480         return 0;               /* w == -1 (mod a), 'a' is probably prime */
 481     while (--k) {
 482         if (!BN_mod_mul(w, w, w, a, ctx)) /* w := w^2 mod a */
 483             return -1;
 484         if (BN_is_one(w))
 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 */
 489     }
 490     /*
 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
 493      */
 494     bn_check_top(w);
 495     return 1;
 496 }
 497
 498 static int probable_prime(BIGNUM *rnd, int bits, prime_t *mods)
 499 {
 500     int i;
 501     BN_ULONG delta;
 502     BN_ULONG maxdelta = BN_MASK2 - primes[NUMPRIMES - 1];
 503     char is_single_word = bits <= BN_BITS2;
 504
 505  again:
 506     if (!BN_rand(rnd, bits, 1, 1))
 507         return (0);
 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]);
 511     /*
 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.
 514      */
 515     if (is_single_word) {
 516         BN_ULONG size_limit;
 517
 518         if (bits == BN_BITS2) {
 519             /*
 520              * Shifting by this much has undefined behaviour so we do it a
 521              * different way
 522              */
 523             size_limit = ~((BN_ULONG)0) - BN_get_word(rnd);
 524         } else {
 525             size_limit = (((BN_ULONG)1) << bits) - BN_get_word(rnd) - 1;
 526         }
 527         if (size_limit < maxdelta)
 528             maxdelta = size_limit;
 529     }
 530     delta = 0;
 531  loop:
 532     if (is_single_word) {
 533         BN_ULONG rnd_word = BN_get_word(rnd);
 534
 535         /*-
 536          * In the case that the candidate prime is a single word then
 537          * we check that:
 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
 540          *      three.
 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
 544          *      that's true.
 545          */
 546         for (i = 1; i < NUMPRIMES && primes[i] < rnd_word; i++) {
 547             if ((mods[i] + delta) % primes[i] == 0) {
 548                 delta += 2;
 549                 if (delta > maxdelta)
 550                     goto again;
 551                 goto loop;
 552             }
 553         }
 554     } else {
 555         for (i = 1; i < NUMPRIMES; i++) {
 556             /*
 557              * check that rnd is not a prime and also that gcd(rnd-1,primes)
 558              * == 1 (except for 2)
 559              */
 560             if (((mods[i] + delta) % primes[i]) <= 1) {
 561                 delta += 2;
 562                 if (delta > maxdelta)
 563                     goto again;
 564                 goto loop;
 565             }
 566         }
 567     }
 568     if (!BN_add_word(rnd, delta))
 569         return (0);
 570     if (BN_num_bits(rnd) != bits)
 571         goto again;
 572     bn_check_top(rnd);
 573     return (1);
 574 }
 575
 576 int bn_probable_prime_dh(BIGNUM *rnd, int bits,
 577                          const BIGNUM *add, const BIGNUM *rem, BN_CTX *ctx)
 578 {
 579     int i, ret = 0;
 580     BIGNUM *t1;
 581
 582     BN_CTX_start(ctx);
 583     if ((t1 = BN_CTX_get(ctx)) == NULL)
 584         goto err;
 585
 586     if (!BN_rand(rnd, bits, 0, 1))
 587         goto err;
 588
 589     /* we need ((rnd-rem) % add) == 0 */
 590
 591     if (!BN_mod(t1, rnd, add, ctx))
 592         goto err;
 593     if (!BN_sub(rnd, rnd, t1))
 594         goto err;
 595     if (rem == NULL) {
 596         if (!BN_add_word(rnd, 1))
 597             goto err;
 598     } else {
 599         if (!BN_add(rnd, rnd, rem))
 600             goto err;
 601     }
 602
 603     /* we now have a random number 'rand' to test. */
 604
 605  loop:
 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))
 610                 goto err;
 611             goto loop;
 612         }
 613     }
 614     ret = 1;
 615
 616  err:
 617     BN_CTX_end(ctx);
 618     bn_check_top(rnd);
 619     return (ret);
 620 }
 621
 622 static int probable_prime_dh_safe(BIGNUM *p, int bits, const BIGNUM *padd,
 623                                   const BIGNUM *rem, BN_CTX *ctx)
 624 {
 625     int i, ret = 0;
 626     BIGNUM *t1, *qadd, *q;
 627
 628     bits--;
 629     BN_CTX_start(ctx);
 630     t1 = BN_CTX_get(ctx);
 631     q = BN_CTX_get(ctx);
 632     qadd = BN_CTX_get(ctx);
 633     if (qadd == NULL)
 634         goto err;
 635
 636     if (!BN_rshift1(qadd, padd))
 637         goto err;
 638
 639     if (!BN_rand(q, bits, 0, 1))
 640         goto err;
 641
 642     /* we need ((rnd-rem) % add) == 0 */
 643     if (!BN_mod(t1, q, qadd, ctx))
 644         goto err;
 645     if (!BN_sub(q, q, t1))
 646         goto err;
 647     if (rem == NULL) {
 648         if (!BN_add_word(q, 1))
 649             goto err;
 650     } else {
 651         if (!BN_rshift1(t1, rem))
 652             goto err;
 653         if (!BN_add(q, q, t1))
 654             goto err;
 655     }
 656
 657     /* we now have a random number 'rand' to test. */
 658     if (!BN_lshift1(p, q))
 659         goto err;
 660     if (!BN_add_word(p, 1))
 661         goto err;
 662
 663  loop:
 664     for (i = 1; i < NUMPRIMES; i++) {
 665         /* check that p and q are prime */
 666         /*
 667          * check that for p and q gcd(p-1,primes) == 1 (except for 2)
 668          */
 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))
 672                 goto err;
 673             if (!BN_add(q, q, qadd))
 674                 goto err;
 675             goto loop;
 676         }
 677     }
 678     ret = 1;
 679
 680  err:
 681     BN_CTX_end(ctx);
 682     bn_check_top(p);
 683     return (ret);
 684 }