crypto/bn/bn_prime.c

   1 /* crypto/bn/bn_prime.c */
   2 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
   3  * All rights reserved.
   4  *
   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.
   8  *
   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).
  15  *
  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.
  22  *
  23  * Redistribution and use in source and binary forms, with or without
  24  * modification, are permitted provided that the following conditions
  25  * are met:
  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)"
  40  *
  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
  51  * SUCH DAMAGE.
  52  *
  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.]
  57  */
  58 /* ====================================================================
  59  * Copyright (c) 1998-2001 The OpenSSL Project.  All rights reserved.
  60  *
  61  * Redistribution and use in source and binary forms, with or without
  62  * modification, are permitted provided that the following conditions
  63  * are met:
  64  *
  65  * 1. Redistributions of source code must retain the above copyright
  66  *    notice, this list of conditions and the following disclaimer.
  67  *
  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
  71  *    distribution.
  72  *
  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/)"
  77  *
  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.
  82  *
  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.
  86  *
  87  * 6. Redistributions of any form whatsoever must retain the following
  88  *    acknowledgment:
  89  *    "This product includes software developed by the OpenSSL Project
  90  *    for use in the OpenSSL Toolkit (http://www.openssl.org/)"
  91  *
  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  * ====================================================================
 105  *
 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).
 109  *
 110  */
 111
 112 #include <stdio.h>
 113 #include <time.h>
 114 #include "internal/cryptlib.h"
 115 #include "bn_lcl.h"
 116 #include <openssl/rand.h>
 117
 118 /*
 119  * NB: these functions have been "upgraded", the deprecated versions (which
 120  * are compatibility wrappers using these functions) are in bn_depr.c. -
 121  * Geoff
 122  */
 123
 124 /*
 125  * The quick sieve algorithm approach to weeding out primes is Philip
 126  * Zimmermann's, as implemented in PGP.  I have had a read of his comments
 127  * and implemented my own version.
 128  */
 129 #include "bn_prime.h"
 130
 131 static int witness(BIGNUM *w, const BIGNUM *a, const BIGNUM *a1,
 132                    const BIGNUM *a1_odd, int k, BN_CTX *ctx,
 133                    BN_MONT_CTX *mont);
 134 static int probable_prime(BIGNUM *rnd, int bits);
 135 static int probable_prime_dh_safe(BIGNUM *rnd, int bits,
 136                                   const BIGNUM *add, const BIGNUM *rem,
 137                                   BN_CTX *ctx);
 138
 139 static const int prime_offsets[480] = {
 140     13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83,
 141     89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163,
 142     167, 169, 173, 179, 181, 191, 193, 197, 199, 211, 221, 223, 227, 229,
 143     233, 239, 241, 247, 251, 257, 263, 269, 271, 277, 281, 283, 289, 293,
 144     299, 307, 311, 313, 317, 323, 331, 337, 347, 349, 353, 359, 361, 367,
 145     373, 377, 379, 383, 389, 391, 397, 401, 403, 409, 419, 421, 431, 433,
 146     437, 439, 443, 449, 457, 461, 463, 467, 479, 481, 487, 491, 493, 499,
 147     503, 509, 521, 523, 527, 529, 533, 541, 547, 551, 557, 559, 563, 569,
 148     571, 577, 587, 589, 593, 599, 601, 607, 611, 613, 617, 619, 629, 631,
 149     641, 643, 647, 653, 659, 661, 667, 673, 677, 683, 689, 691, 697, 701,
 150     703, 709, 713, 719, 727, 731, 733, 739, 743, 751, 757, 761, 767, 769,
 151     773, 779, 787, 793, 797, 799, 809, 811, 817, 821, 823, 827, 829, 839,
 152     841, 851, 853, 857, 859, 863, 871, 877, 881, 883, 887, 893, 899, 901,
 153     907, 911, 919, 923, 929, 937, 941, 943, 947, 949, 953, 961, 967, 971,
 154     977, 983, 989, 991, 997, 1003, 1007, 1009, 1013, 1019, 1021, 1027, 1031,
 155     1033, 1037, 1039, 1049, 1051, 1061, 1063, 1069, 1073, 1079, 1081, 1087,
 156     1091, 1093, 1097, 1103, 1109, 1117, 1121, 1123, 1129, 1139, 1147, 1151,
 157     1153, 1157, 1159, 1163, 1171, 1181, 1187, 1189, 1193, 1201, 1207, 1213,
 158     1217, 1219, 1223, 1229, 1231, 1237, 1241, 1247, 1249, 1259, 1261, 1271,
 159     1273, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1313, 1319,
 160     1321, 1327, 1333, 1339, 1343, 1349, 1357, 1361, 1363, 1367, 1369, 1373,
 161     1381, 1387, 1391, 1399, 1403, 1409, 1411, 1417, 1423, 1427, 1429, 1433,
 162     1439, 1447, 1451, 1453, 1457, 1459, 1469, 1471, 1481, 1483, 1487, 1489,
 163     1493, 1499, 1501, 1511, 1513, 1517, 1523, 1531, 1537, 1541, 1543, 1549,
 164     1553, 1559, 1567, 1571, 1577, 1579, 1583, 1591, 1597, 1601, 1607, 1609,
 165     1613, 1619, 1621, 1627, 1633, 1637, 1643, 1649, 1651, 1657, 1663, 1667,
 166     1669, 1679, 1681, 1691, 1693, 1697, 1699, 1703, 1709, 1711, 1717, 1721,
 167     1723, 1733, 1739, 1741, 1747, 1751, 1753, 1759, 1763, 1769, 1777, 1781,
 168     1783, 1787, 1789, 1801, 1807, 1811, 1817, 1819, 1823, 1829, 1831, 1843,
 169     1847, 1849, 1853, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1891, 1901,
 170     1907, 1909, 1913, 1919, 1921, 1927, 1931, 1933, 1937, 1943, 1949, 1951,
 171     1957, 1961, 1963, 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017,
 172     2021, 2027, 2029, 2033, 2039, 2041, 2047, 2053, 2059, 2063, 2069, 2071,
 173     2077, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2117, 2119, 2129, 2131,
 174     2137, 2141, 2143, 2147, 2153, 2159, 2161, 2171, 2173, 2179, 2183, 2197,
 175     2201, 2203, 2207, 2209, 2213, 2221, 2227, 2231, 2237, 2239, 2243, 2249,
 176     2251, 2257, 2263, 2267, 2269, 2273, 2279, 2281, 2287, 2291, 2293, 2297,
 177     2309, 2311
 178 };
 179
 180 static const int prime_offset_count = 480;
 181 static const int prime_multiplier = 2310;
 182 static const int prime_multiplier_bits = 11; /* 2^|prime_multiplier_bits| <=
 183                                               * |prime_multiplier| */
 184 static const int first_prime_index = 5;
 185
 186 int BN_GENCB_call(BN_GENCB *cb, int a, int b)
 187 {
 188     /* No callback means continue */
 189     if (!cb)
 190         return 1;
 191     switch (cb->ver) {
 192     case 1:
 193         /* Deprecated-style callbacks */
 194         if (!cb->cb.cb_1)
 195             return 1;
 196         cb->cb.cb_1(a, b, cb->arg);
 197         return 1;
 198     case 2:
 199         /* New-style callbacks */
 200         return cb->cb.cb_2(a, b, cb);
 201     default:
 202         break;
 203     }
 204     /* Unrecognised callback type */
 205     return 0;
 206 }
 207
 208 int BN_generate_prime_ex(BIGNUM *ret, int bits, int safe,
 209                          const BIGNUM *add, const BIGNUM *rem, BN_GENCB *cb)
 210 {
 211     BIGNUM *t;
 212     int found = 0;
 213     int i, j, c1 = 0;
 214     BN_CTX *ctx;
 215     int checks = BN_prime_checks_for_size(bits);
 216
 217     if (bits < 2) {
 218         /* There are no prime numbers this small. */
 219         BNerr(BN_F_BN_GENERATE_PRIME_EX, BN_R_BITS_TOO_SMALL);
 220         return 0;
 221     } else if (bits == 2 && safe) {
 222         /* The smallest safe prime (7) is three bits. */
 223         BNerr(BN_F_BN_GENERATE_PRIME_EX, BN_R_BITS_TOO_SMALL);
 224         return 0;
 225     }
 226
 227     ctx = BN_CTX_new();
 228     if (ctx == NULL)
 229         goto err;
 230     BN_CTX_start(ctx);
 231     t = BN_CTX_get(ctx);
 232     if (!t)
 233         goto err;
 234  loop:
 235     /* make a random number and set the top and bottom bits */
 236     if (add == NULL) {
 237         if (!probable_prime(ret, bits))
 238             goto err;
 239     } else {
 240         if (safe) {
 241             if (!probable_prime_dh_safe(ret, bits, add, rem, ctx))
 242                 goto err;
 243         } else {
 244             if (!bn_probable_prime_dh(ret, bits, add, rem, ctx))
 245                 goto err;
 246         }
 247     }
 248     /* if (BN_mod_word(ret,(BN_ULONG)3) == 1) goto loop; */
 249     if (!BN_GENCB_call(cb, 0, c1++))
 250         /* aborted */
 251         goto err;
 252
 253     if (!safe) {
 254         i = BN_is_prime_fasttest_ex(ret, checks, ctx, 0, cb);
 255         if (i == -1)
 256             goto err;
 257         if (i == 0)
 258             goto loop;
 259     } else {
 260         /*
 261          * for "safe prime" generation, check that (p-1)/2 is prime. Since a
 262          * prime is odd, We just need to divide by 2
 263          */
 264         if (!BN_rshift1(t, ret))
 265             goto err;
 266
 267         for (i = 0; i < checks; i++) {
 268             j = BN_is_prime_fasttest_ex(ret, 1, ctx, 0, cb);
 269             if (j == -1)
 270                 goto err;
 271             if (j == 0)
 272                 goto loop;
 273
 274             j = BN_is_prime_fasttest_ex(t, 1, ctx, 0, cb);
 275             if (j == -1)
 276                 goto err;
 277             if (j == 0)
 278                 goto loop;
 279
 280             if (!BN_GENCB_call(cb, 2, c1 - 1))
 281                 goto err;
 282             /* We have a safe prime test pass */
 283         }
 284     }
 285     /* we have a prime :-) */
 286     found = 1;
 287  err:
 288     if (ctx != NULL)
 289         BN_CTX_end(ctx);
 290     BN_CTX_free(ctx);
 291     bn_check_top(ret);
 292     return found;
 293 }
 294
 295 int BN_is_prime_ex(const BIGNUM *a, int checks, BN_CTX *ctx_passed,
 296                    BN_GENCB *cb)
 297 {
 298     return BN_is_prime_fasttest_ex(a, checks, ctx_passed, 0, cb);
 299 }
 300
 301 int BN_is_prime_fasttest_ex(const BIGNUM *a, int checks, BN_CTX *ctx_passed,
 302                             int do_trial_division, BN_GENCB *cb)
 303 {
 304     int i, j, ret = -1;
 305     int k;
 306     BN_CTX *ctx = NULL;
 307     BIGNUM *A1, *A1_odd, *check; /* taken from ctx */
 308     BN_MONT_CTX *mont = NULL;
 309     const BIGNUM *A = NULL;
 310
 311     if (BN_cmp(a, BN_value_one()) <= 0)
 312         return 0;
 313
 314     if (checks == BN_prime_checks)
 315         checks = BN_prime_checks_for_size(BN_num_bits(a));
 316
 317     /* first look for small factors */
 318     if (!BN_is_odd(a))
 319         /* a is even => a is prime if and only if a == 2 */
 320         return BN_is_word(a, 2);
 321     if (do_trial_division) {
 322         for (i = 1; i < NUMPRIMES; i++)
 323             if (BN_mod_word(a, primes[i]) == 0)
 324                 return 0;
 325         if (!BN_GENCB_call(cb, 1, -1))
 326             goto err;
 327     }
 328
 329     if (ctx_passed != NULL)
 330         ctx = ctx_passed;
 331     else if ((ctx = BN_CTX_new()) == NULL)
 332         goto err;
 333     BN_CTX_start(ctx);
 334
 335     /* A := abs(a) */
 336     if (a->neg) {
 337         BIGNUM *t;
 338         if ((t = BN_CTX_get(ctx)) == NULL)
 339             goto err;
 340         BN_copy(t, a);
 341         t->neg = 0;
 342         A = t;
 343     } else
 344         A = a;
 345     A1 = BN_CTX_get(ctx);
 346     A1_odd = BN_CTX_get(ctx);
 347     check = BN_CTX_get(ctx);
 348     if (check == NULL)
 349         goto err;
 350
 351     /* compute A1 := A - 1 */
 352     if (!BN_copy(A1, A))
 353         goto err;
 354     if (!BN_sub_word(A1, 1))
 355         goto err;
 356     if (BN_is_zero(A1)) {
 357         ret = 0;
 358         goto err;
 359     }
 360
 361     /* write  A1  as  A1_odd * 2^k */
 362     k = 1;
 363     while (!BN_is_bit_set(A1, k))
 364         k++;
 365     if (!BN_rshift(A1_odd, A1, k))
 366         goto err;
 367
 368     /* Montgomery setup for computations mod A */
 369     mont = BN_MONT_CTX_new();
 370     if (mont == NULL)
 371         goto err;
 372     if (!BN_MONT_CTX_set(mont, A, ctx))
 373         goto err;
 374
 375     for (i = 0; i < checks; i++) {
 376         if (!BN_pseudo_rand_range(check, A1))
 377             goto err;
 378         if (!BN_add_word(check, 1))
 379             goto err;
 380         /* now 1 <= check < A */
 381
 382         j = witness(check, A, A1, A1_odd, k, ctx, mont);
 383         if (j == -1)
 384             goto err;
 385         if (j) {
 386             ret = 0;
 387             goto err;
 388         }
 389         if (!BN_GENCB_call(cb, 1, i))
 390             goto err;
 391     }
 392     ret = 1;
 393  err:
 394     if (ctx != NULL) {
 395         BN_CTX_end(ctx);
 396         if (ctx_passed == NULL)
 397             BN_CTX_free(ctx);
 398     }
 399     BN_MONT_CTX_free(mont);
 400
 401     return (ret);
 402 }
 403
 404 int bn_probable_prime_dh_retry(BIGNUM *rnd, int bits, BN_CTX *ctx)
 405 {
 406     int i;
 407     int ret = 0;
 408
 409  loop:
 410     if (!BN_rand(rnd, bits, 0, 1))
 411         goto err;
 412
 413     /* we now have a random number 'rand' to test. */
 414
 415     for (i = 1; i < NUMPRIMES; i++) {
 416         /* check that rnd is a prime */
 417         if (BN_mod_word(rnd, (BN_ULONG)primes[i]) <= 1) {
 418             goto loop;
 419         }
 420     }
 421     ret = 1;
 422
 423  err:
 424     bn_check_top(rnd);
 425     return (ret);
 426 }
 427
 428 int bn_probable_prime_dh_coprime(BIGNUM *rnd, int bits, BN_CTX *ctx)
 429 {
 430     int i;
 431     BIGNUM *offset_index;
 432     BIGNUM *offset_count;
 433     int ret = 0;
 434
 435     OPENSSL_assert(bits > prime_multiplier_bits);
 436
 437     BN_CTX_start(ctx);
 438     if ((offset_index = BN_CTX_get(ctx)) == NULL)
 439         goto err;
 440     if ((offset_count = BN_CTX_get(ctx)) == NULL)
 441         goto err;
 442
 443     BN_add_word(offset_count, prime_offset_count);
 444
 445  loop:
 446     if (!BN_rand(rnd, bits - prime_multiplier_bits, 0, 1))
 447         goto err;
 448     if (BN_is_bit_set(rnd, bits))
 449         goto loop;
 450     if (!BN_rand_range(offset_index, offset_count))
 451         goto err;
 452
 453     BN_mul_word(rnd, prime_multiplier);
 454     BN_add_word(rnd, prime_offsets[BN_get_word(offset_index)]);
 455
 456     /* we now have a random number 'rand' to test. */
 457
 458     /* skip coprimes */
 459     for (i = first_prime_index; i < NUMPRIMES; i++) {
 460         /* check that rnd is a prime */
 461         if (BN_mod_word(rnd, (BN_ULONG)primes[i]) <= 1) {
 462             goto loop;
 463         }
 464     }
 465     ret = 1;
 466
 467  err:
 468     BN_CTX_end(ctx);
 469     bn_check_top(rnd);
 470     return ret;
 471 }
 472
 473 static int witness(BIGNUM *w, const BIGNUM *a, const BIGNUM *a1,
 474                    const BIGNUM *a1_odd, int k, BN_CTX *ctx,
 475                    BN_MONT_CTX *mont)
 476 {
 477     if (!BN_mod_exp_mont(w, w, a1_odd, a, ctx, mont)) /* w := w^a1_odd mod a */
 478         return -1;
 479     if (BN_is_one(w))
 480         return 0;               /* probably prime */
 481     if (BN_cmp(w, a1) == 0)
 482         return 0;               /* w == -1 (mod a), 'a' is probably prime */
 483     while (--k) {
 484         if (!BN_mod_mul(w, w, w, a, ctx)) /* w := w^2 mod a */
 485             return -1;
 486         if (BN_is_one(w))
 487             return 1;           /* 'a' is composite, otherwise a previous 'w'
 488                                  * would have been == -1 (mod 'a') */
 489         if (BN_cmp(w, a1) == 0)
 490             return 0;           /* w == -1 (mod a), 'a' is probably prime */
 491     }
 492     /*
 493      * If we get here, 'w' is the (a-1)/2-th power of the original 'w', and
 494      * it is neither -1 nor +1 -- so 'a' cannot be prime
 495      */
 496     bn_check_top(w);
 497     return 1;
 498 }
 499
 500 static int probable_prime(BIGNUM *rnd, int bits)
 501 {
 502     int i;
 503     prime_t mods[NUMPRIMES];
 504     BN_ULONG delta;
 505     BN_ULONG maxdelta = BN_MASK2 - primes[NUMPRIMES - 1];
 506     char is_single_word = bits <= BN_BITS2;
 507
 508  again:
 509     if (!BN_rand(rnd, bits, 1, 1))
 510         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     /*
 515      * If bits is so small that it fits into a single word then we
 516      * additionally don't want to exceed that many bits.
 517      */
 518     if (is_single_word) {
 519         BN_ULONG size_limit;
 520
 521         if (bits == BN_BITS2) {
 522             /*
 523              * Shifting by this much has undefined behaviour so we do it a
 524              * different way
 525              */
 526             size_limit = ~((BN_ULONG)0) - BN_get_word(rnd);
 527         } else {
 528             size_limit = (((BN_ULONG)1) << bits) - BN_get_word(rnd) - 1;
 529         }
 530         if (size_limit < maxdelta)
 531             maxdelta = size_limit;
 532     }
 533     delta = 0;
 534  loop:
 535     if (is_single_word) {
 536         BN_ULONG rnd_word = BN_get_word(rnd);
 537
 538         /*-
 539          * In the case that the candidate prime is a single word then
 540          * we check that:
 541          *   1) It's greater than primes[i] because we shouldn't reject
 542          *      3 as being a prime number because it's a multiple of
 543          *      three.
 544          *   2) That it's not a multiple of a known prime. We don't
 545          *      check that rnd-1 is also coprime to all the known
 546          *      primes because there aren't many small primes where
 547          *      that's true.
 548          */
 549         for (i = 1; i < NUMPRIMES && primes[i] < rnd_word; i++) {
 550             if ((mods[i] + delta) % primes[i] == 0) {
 551                 delta += 2;
 552                 if (delta > maxdelta)
 553                     goto again;
 554                 goto loop;
 555             }
 556         }
 557     } else {
 558         for (i = 1; i < NUMPRIMES; i++) {
 559             /*
 560              * check that rnd is not a prime and also that gcd(rnd-1,primes)
 561              * == 1 (except for 2)
 562              */
 563             if (((mods[i] + delta) % primes[i]) <= 1) {
 564                 delta += 2;
 565                 if (delta > maxdelta)
 566                     goto again;
 567                 goto loop;
 568             }
 569         }
 570     }
 571     if (!BN_add_word(rnd, delta))
 572         return (0);
 573     if (BN_num_bits(rnd) != bits)
 574         goto again;
 575     bn_check_top(rnd);
 576     return (1);
 577 }
 578
 579 int bn_probable_prime_dh(BIGNUM *rnd, int bits,
 580                          const BIGNUM *add, const BIGNUM *rem, BN_CTX *ctx)
 581 {
 582     int i, ret = 0;
 583     BIGNUM *t1;
 584
 585     BN_CTX_start(ctx);
 586     if ((t1 = BN_CTX_get(ctx)) == NULL)
 587         goto err;
 588
 589     if (!BN_rand(rnd, bits, 0, 1))
 590         goto err;
 591
 592     /* we need ((rnd-rem) % add) == 0 */
 593
 594     if (!BN_mod(t1, rnd, add, ctx))
 595         goto err;
 596     if (!BN_sub(rnd, rnd, t1))
 597         goto err;
 598     if (rem == NULL) {
 599         if (!BN_add_word(rnd, 1))
 600             goto err;
 601     } else {
 602         if (!BN_add(rnd, rnd, rem))
 603             goto err;
 604     }
 605
 606     /* we now have a random number 'rand' to test. */
 607
 608  loop:
 609     for (i = 1; i < NUMPRIMES; i++) {
 610         /* check that rnd is a prime */
 611         if (BN_mod_word(rnd, (BN_ULONG)primes[i]) <= 1) {
 612             if (!BN_add(rnd, rnd, add))
 613                 goto err;
 614             goto loop;
 615         }
 616     }
 617     ret = 1;
 618
 619  err:
 620     BN_CTX_end(ctx);
 621     bn_check_top(rnd);
 622     return (ret);
 623 }
 624
 625 static int probable_prime_dh_safe(BIGNUM *p, int bits, const BIGNUM *padd,
 626                                   const BIGNUM *rem, BN_CTX *ctx)
 627 {
 628     int i, ret = 0;
 629     BIGNUM *t1, *qadd, *q;
 630
 631     bits--;
 632     BN_CTX_start(ctx);
 633     t1 = BN_CTX_get(ctx);
 634     q = BN_CTX_get(ctx);
 635     qadd = BN_CTX_get(ctx);
 636     if (qadd == NULL)
 637         goto err;
 638
 639     if (!BN_rshift1(qadd, padd))
 640         goto err;
 641
 642     if (!BN_rand(q, bits, 0, 1))
 643         goto err;
 644
 645     /* we need ((rnd-rem) % add) == 0 */
 646     if (!BN_mod(t1, q, qadd, ctx))
 647         goto err;
 648     if (!BN_sub(q, q, t1))
 649         goto err;
 650     if (rem == NULL) {
 651         if (!BN_add_word(q, 1))
 652             goto err;
 653     } else {
 654         if (!BN_rshift1(t1, rem))
 655             goto err;
 656         if (!BN_add(q, q, t1))
 657             goto err;
 658     }
 659
 660     /* we now have a random number 'rand' to test. */
 661     if (!BN_lshift1(p, q))
 662         goto err;
 663     if (!BN_add_word(p, 1))
 664         goto err;
 665
 666  loop:
 667     for (i = 1; i < NUMPRIMES; i++) {
 668         /* check that p and q are prime */
 669         /*
 670          * check that for p and q gcd(p-1,primes) == 1 (except for 2)
 671          */
 672         if ((BN_mod_word(p, (BN_ULONG)primes[i]) == 0) ||
 673             (BN_mod_word(q, (BN_ULONG)primes[i]) == 0)) {
 674             if (!BN_add(p, p, padd))
 675                 goto err;
 676             if (!BN_add(q, q, qadd))
 677                 goto err;
 678             goto loop;
 679         }
 680     }
 681     ret = 1;
 682
 683  err:
 684     BN_CTX_end(ctx);
 685     bn_check_top(p);
 686     return (ret);
 687 }