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     if (bits < 2) {
 212         /* There are no prime numbers this small. */
 213         BNerr(BN_F_BN_GENERATE_PRIME_EX, BN_R_BITS_TOO_SMALL);
 214         return 0;
 215     } 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);
 218         return 0;
 219     }
 220
 221     mods = OPENSSL_zalloc(sizeof(*mods) * NUMPRIMES);
 222     if (mods == NULL)
 223         goto err;
 224
 225     ctx = BN_CTX_new();
 226     if (ctx == NULL)
 227         goto err;
 228     BN_CTX_start(ctx);
 229     t = BN_CTX_get(ctx);
 230     if (!t)
 231         goto err;
 232  loop:
 233     /* make a random number and set the top and bottom bits */
 234     if (add == NULL) {
 235         if (!probable_prime(ret, bits, mods))
 236             goto err;
 237     } else {
 238         if (safe) {
 239             if (!probable_prime_dh_safe(ret, bits, add, rem, ctx))
 240                 goto err;
 241         } else {
 242             if (!bn_probable_prime_dh(ret, bits, add, rem, ctx))
 243                 goto err;
 244         }
 245     }
 246     /* if (BN_mod_word(ret,(BN_ULONG)3) == 1) goto loop; */
 247     if (!BN_GENCB_call(cb, 0, c1++))
 248         /* aborted */
 249         goto err;
 250
 251     if (!safe) {
 252         i = BN_is_prime_fasttest_ex(ret, checks, ctx, 0, cb);
 253         if (i == -1)
 254             goto err;
 255         if (i == 0)
 256             goto loop;
 257     } else {
 258         /*
 259          * for "safe prime" generation, check that (p-1)/2 is prime. Since a
 260          * prime is odd, We just need to divide by 2
 261          */
 262         if (!BN_rshift1(t, ret))
 263             goto err;
 264
 265         for (i = 0; i < checks; i++) {
 266             j = BN_is_prime_fasttest_ex(ret, 1, ctx, 0, cb);
 267             if (j == -1)
 268                 goto err;
 269             if (j == 0)
 270                 goto loop;
 271
 272             j = BN_is_prime_fasttest_ex(t, 1, ctx, 0, cb);
 273             if (j == -1)
 274                 goto err;
 275             if (j == 0)
 276                 goto loop;
 277
 278             if (!BN_GENCB_call(cb, 2, c1 - 1))
 279                 goto err;
 280             /* We have a safe prime test pass */
 281         }
 282     }
 283     /* we have a prime :-) */
 284     found = 1;
 285  err:
 286     OPENSSL_free(mods);
 287     if (ctx != NULL)
 288         BN_CTX_end(ctx);
 289     BN_CTX_free(ctx);
 290     bn_check_top(ret);
 291     return found;
 292 }
 293
 294 int BN_is_prime_ex(const BIGNUM *a, int checks, BN_CTX *ctx_passed,
 295                    BN_GENCB *cb)
 296 {
 297     return BN_is_prime_fasttest_ex(a, checks, ctx_passed, 0, cb);
 298 }
 299
 300 int BN_is_prime_fasttest_ex(const BIGNUM *a, int checks, BN_CTX *ctx_passed,
 301                             int do_trial_division, BN_GENCB *cb)
 302 {
 303     int i, j, ret = -1;
 304     int k;
 305     BN_CTX *ctx = NULL;
 306     BIGNUM *A1, *A1_odd, *check; /* taken from ctx */
 307     BN_MONT_CTX *mont = NULL;
 308     const BIGNUM *A = NULL;
 309
 310     if (BN_cmp(a, BN_value_one()) <= 0)
 311         return 0;
 312
 313     if (checks == BN_prime_checks)
 314         checks = BN_prime_checks_for_size(BN_num_bits(a));
 315
 316     /* first look for small factors */
 317     if (!BN_is_odd(a))
 318         /* a is even => a is prime if and only if a == 2 */
 319         return BN_is_word(a, 2);
 320     if (do_trial_division) {
 321         for (i = 1; i < NUMPRIMES; i++)
 322             if (BN_mod_word(a, primes[i]) == 0)
 323                 return 0;
 324         if (!BN_GENCB_call(cb, 1, -1))
 325             goto err;
 326     }
 327
 328     if (ctx_passed != NULL)
 329         ctx = ctx_passed;
 330     else if ((ctx = BN_CTX_new()) == NULL)
 331         goto err;
 332     BN_CTX_start(ctx);
 333
 334     /* A := abs(a) */
 335     if (a->neg) {
 336         BIGNUM *t;
 337         if ((t = BN_CTX_get(ctx)) == NULL)
 338             goto err;
 339         BN_copy(t, a);
 340         t->neg = 0;
 341         A = t;
 342     } else
 343         A = a;
 344     A1 = BN_CTX_get(ctx);
 345     A1_odd = BN_CTX_get(ctx);
 346     check = BN_CTX_get(ctx);
 347     if (check == NULL)
 348         goto err;
 349
 350     /* compute A1 := A - 1 */
 351     if (!BN_copy(A1, A))
 352         goto err;
 353     if (!BN_sub_word(A1, 1))
 354         goto err;
 355     if (BN_is_zero(A1)) {
 356         ret = 0;
 357         goto err;
 358     }
 359
 360     /* write  A1  as  A1_odd * 2^k */
 361     k = 1;
 362     while (!BN_is_bit_set(A1, k))
 363         k++;
 364     if (!BN_rshift(A1_odd, A1, k))
 365         goto err;
 366
 367     /* Montgomery setup for computations mod A */
 368     mont = BN_MONT_CTX_new();
 369     if (mont == NULL)
 370         goto err;
 371     if (!BN_MONT_CTX_set(mont, A, ctx))
 372         goto err;
 373
 374     for (i = 0; i < checks; i++) {
 375         if (!BN_pseudo_rand_range(check, A1))
 376             goto err;
 377         if (!BN_add_word(check, 1))
 378             goto err;
 379         /* now 1 <= check < A */
 380
 381         j = witness(check, A, A1, A1_odd, k, ctx, mont);
 382         if (j == -1)
 383             goto err;
 384         if (j) {
 385             ret = 0;
 386             goto err;
 387         }
 388         if (!BN_GENCB_call(cb, 1, i))
 389             goto err;
 390     }
 391     ret = 1;
 392  err:
 393     if (ctx != NULL) {
 394         BN_CTX_end(ctx);
 395         if (ctx_passed == NULL)
 396             BN_CTX_free(ctx);
 397     }
 398     BN_MONT_CTX_free(mont);
 399
 400     return (ret);
 401 }
 402
 403 int bn_probable_prime_dh_retry(BIGNUM *rnd, int bits, BN_CTX *ctx)
 404 {
 405     int i;
 406     int ret = 0;
 407
 408  loop:
 409     if (!BN_rand(rnd, bits, 0, 1))
 410         goto err;
 411
 412     /* we now have a random number 'rand' to test. */
 413
 414     for (i = 1; i < NUMPRIMES; i++) {
 415         /* check that rnd is a prime */
 416         if (BN_mod_word(rnd, (BN_ULONG)primes[i]) <= 1) {
 417             goto loop;
 418         }
 419     }
 420     ret = 1;
 421
 422  err:
 423     bn_check_top(rnd);
 424     return (ret);
 425 }
 426
 427 int bn_probable_prime_dh_coprime(BIGNUM *rnd, int bits, BN_CTX *ctx)
 428 {
 429     int i;
 430     BIGNUM *offset_index;
 431     BIGNUM *offset_count;
 432     int ret = 0;
 433
 434     OPENSSL_assert(bits > prime_multiplier_bits);
 435
 436     BN_CTX_start(ctx);
 437     if ((offset_index = BN_CTX_get(ctx)) == NULL)
 438         goto err;
 439     if ((offset_count = BN_CTX_get(ctx)) == NULL)
 440         goto err;
 441
 442     BN_add_word(offset_count, prime_offset_count);
 443
 444  loop:
 445     if (!BN_rand(rnd, bits - prime_multiplier_bits, 0, 1))
 446         goto err;
 447     if (BN_is_bit_set(rnd, bits))
 448         goto loop;
 449     if (!BN_rand_range(offset_index, offset_count))
 450         goto err;
 451
 452     BN_mul_word(rnd, prime_multiplier);
 453     BN_add_word(rnd, prime_offsets[BN_get_word(offset_index)]);
 454
 455     /* we now have a random number 'rand' to test. */
 456
 457     /* skip coprimes */
 458     for (i = first_prime_index; i < NUMPRIMES; i++) {
 459         /* check that rnd is a prime */
 460         if (BN_mod_word(rnd, (BN_ULONG)primes[i]) <= 1) {
 461             goto loop;
 462         }
 463     }
 464     ret = 1;
 465
 466  err:
 467     BN_CTX_end(ctx);
 468     bn_check_top(rnd);
 469     return ret;
 470 }
 471
 472 static int witness(BIGNUM *w, const BIGNUM *a, const BIGNUM *a1,
 473                    const BIGNUM *a1_odd, int k, BN_CTX *ctx,
 474                    BN_MONT_CTX *mont)
 475 {
 476     if (!BN_mod_exp_mont(w, w, a1_odd, a, ctx, mont)) /* w := w^a1_odd mod a */
 477         return -1;
 478     if (BN_is_one(w))
 479         return 0;               /* probably prime */
 480     if (BN_cmp(w, a1) == 0)
 481         return 0;               /* w == -1 (mod a), 'a' is probably prime */
 482     while (--k) {
 483         if (!BN_mod_mul(w, w, w, a, ctx)) /* w := w^2 mod a */
 484             return -1;
 485         if (BN_is_one(w))
 486             return 1;           /* 'a' is composite, otherwise a previous 'w'
 487                                  * would have been == -1 (mod 'a') */
 488         if (BN_cmp(w, a1) == 0)
 489             return 0;           /* w == -1 (mod a), 'a' is probably prime */
 490     }
 491     /*
 492      * If we get here, 'w' is the (a-1)/2-th power of the original 'w', and
 493      * it is neither -1 nor +1 -- so 'a' cannot be prime
 494      */
 495     bn_check_top(w);
 496     return 1;
 497 }
 498
 499 static int probable_prime(BIGNUM *rnd, int bits, prime_t *mods)
 500 {
 501     int i;
 502     BN_ULONG delta;
 503     BN_ULONG maxdelta = BN_MASK2 - primes[NUMPRIMES - 1];
 504     char is_single_word = bits <= BN_BITS2;
 505
 506  again:
 507     if (!BN_rand(rnd, bits, 1, 1))
 508         return (0);
 509     /* we now have a random number 'rnd' to test. */
 510     for (i = 1; i < NUMPRIMES; i++)
 511         mods[i] = (prime_t) BN_mod_word(rnd, (BN_ULONG)primes[i]);
 512     /*
 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.
 515      */
 516     if (is_single_word) {
 517         BN_ULONG size_limit;
 518
 519         if (bits == BN_BITS2) {
 520             /*
 521              * Shifting by this much has undefined behaviour so we do it a
 522              * different way
 523              */
 524             size_limit = ~((BN_ULONG)0) - BN_get_word(rnd);
 525         } else {
 526             size_limit = (((BN_ULONG)1) << bits) - BN_get_word(rnd) - 1;
 527         }
 528         if (size_limit < maxdelta)
 529             maxdelta = size_limit;
 530     }
 531     delta = 0;
 532  loop:
 533     if (is_single_word) {
 534         BN_ULONG rnd_word = BN_get_word(rnd);
 535
 536         /*-
 537          * In the case that the candidate prime is a single word then
 538          * we check that:
 539          *   1) It's greater than primes[i] because we shouldn't reject
 540          *      3 as being a prime number because it's a multiple of
 541          *      three.
 542          *   2) That it's not a multiple of a known prime. We don't
 543          *      check that rnd-1 is also coprime to all the known
 544          *      primes because there aren't many small primes where
 545          *      that's true.
 546          */
 547         for (i = 1; i < NUMPRIMES && primes[i] < rnd_word; i++) {
 548             if ((mods[i] + delta) % primes[i] == 0) {
 549                 delta += 2;
 550                 if (delta > maxdelta)
 551                     goto again;
 552                 goto loop;
 553             }
 554         }
 555     } else {
 556         for (i = 1; i < NUMPRIMES; i++) {
 557             /*
 558              * check that rnd is not a prime and also that gcd(rnd-1,primes)
 559              * == 1 (except for 2)
 560              */
 561             if (((mods[i] + delta) % primes[i]) <= 1) {
 562                 delta += 2;
 563                 if (delta > maxdelta)
 564                     goto again;
 565                 goto loop;
 566             }
 567         }
 568     }
 569     if (!BN_add_word(rnd, delta))
 570         return (0);
 571     if (BN_num_bits(rnd) != bits)
 572         goto again;
 573     bn_check_top(rnd);
 574     return (1);
 575 }
 576
 577 int bn_probable_prime_dh(BIGNUM *rnd, int bits,
 578                          const BIGNUM *add, const BIGNUM *rem, BN_CTX *ctx)
 579 {
 580     int i, ret = 0;
 581     BIGNUM *t1;
 582
 583     BN_CTX_start(ctx);
 584     if ((t1 = BN_CTX_get(ctx)) == NULL)
 585         goto err;
 586
 587     if (!BN_rand(rnd, bits, 0, 1))
 588         goto err;
 589
 590     /* we need ((rnd-rem) % add) == 0 */
 591
 592     if (!BN_mod(t1, rnd, add, ctx))
 593         goto err;
 594     if (!BN_sub(rnd, rnd, t1))
 595         goto err;
 596     if (rem == NULL) {
 597         if (!BN_add_word(rnd, 1))
 598             goto err;
 599     } else {
 600         if (!BN_add(rnd, rnd, rem))
 601             goto err;
 602     }
 603
 604     /* we now have a random number 'rand' to test. */
 605
 606  loop:
 607     for (i = 1; i < NUMPRIMES; i++) {
 608         /* check that rnd is a prime */
 609         if (BN_mod_word(rnd, (BN_ULONG)primes[i]) <= 1) {
 610             if (!BN_add(rnd, rnd, add))
 611                 goto err;
 612             goto loop;
 613         }
 614     }
 615     ret = 1;
 616
 617  err:
 618     BN_CTX_end(ctx);
 619     bn_check_top(rnd);
 620     return (ret);
 621 }
 622
 623 static int probable_prime_dh_safe(BIGNUM *p, int bits, const BIGNUM *padd,
 624                                   const BIGNUM *rem, BN_CTX *ctx)
 625 {
 626     int i, ret = 0;
 627     BIGNUM *t1, *qadd, *q;
 628
 629     bits--;
 630     BN_CTX_start(ctx);
 631     t1 = BN_CTX_get(ctx);
 632     q = BN_CTX_get(ctx);
 633     qadd = BN_CTX_get(ctx);
 634     if (qadd == NULL)
 635         goto err;
 636
 637     if (!BN_rshift1(qadd, padd))
 638         goto err;
 639
 640     if (!BN_rand(q, bits, 0, 1))
 641         goto err;
 642
 643     /* we need ((rnd-rem) % add) == 0 */
 644     if (!BN_mod(t1, q, qadd, ctx))
 645         goto err;
 646     if (!BN_sub(q, q, t1))
 647         goto err;
 648     if (rem == NULL) {
 649         if (!BN_add_word(q, 1))
 650             goto err;
 651     } else {
 652         if (!BN_rshift1(t1, rem))
 653             goto err;
 654         if (!BN_add(q, q, t1))
 655             goto err;
 656     }
 657
 658     /* we now have a random number 'rand' to test. */
 659     if (!BN_lshift1(p, q))
 660         goto err;
 661     if (!BN_add_word(p, 1))
 662         goto err;
 663
 664  loop:
 665     for (i = 1; i < NUMPRIMES; i++) {
 666         /* check that p and q are prime */
 667         /*
 668          * check that for p and q gcd(p-1,primes) == 1 (except for 2)
 669          */
 670         if ((BN_mod_word(p, (BN_ULONG)primes[i]) == 0) ||
 671             (BN_mod_word(q, (BN_ULONG)primes[i]) == 0)) {
 672             if (!BN_add(p, p, padd))
 673                 goto err;
 674             if (!BN_add(q, q, qadd))
 675                 goto err;
 676             goto loop;
 677         }
 678     }
 679     ret = 1;
 680
 681  err:
 682     BN_CTX_end(ctx);
 683     bn_check_top(p);
 684     return (ret);
 685 }