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 #define NUMPRIMES OSSL_NELEM(primes)
 125
 126 static int witness(BIGNUM *w, const BIGNUM *a, const BIGNUM *a1,
 127                    const BIGNUM *a1_odd, int k, BN_CTX *ctx,
 128                    BN_MONT_CTX *mont);
 129 static int probable_prime(BIGNUM *rnd, int bits, prime_t *mods);
 130 static int probable_prime_dh_safe(BIGNUM *rnd, int bits,
 131                                   const BIGNUM *add, const BIGNUM *rem,
 132                                   BN_CTX *ctx);
 133
 134 static const int prime_offsets[480] = {
 135     13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83,
 136     89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163,
 137     167, 169, 173, 179, 181, 191, 193, 197, 199, 211, 221, 223, 227, 229,
 138     233, 239, 241, 247, 251, 257, 263, 269, 271, 277, 281, 283, 289, 293,
 139     299, 307, 311, 313, 317, 323, 331, 337, 347, 349, 353, 359, 361, 367,
 140     373, 377, 379, 383, 389, 391, 397, 401, 403, 409, 419, 421, 431, 433,
 141     437, 439, 443, 449, 457, 461, 463, 467, 479, 481, 487, 491, 493, 499,
 142     503, 509, 521, 523, 527, 529, 533, 541, 547, 551, 557, 559, 563, 569,
 143     571, 577, 587, 589, 593, 599, 601, 607, 611, 613, 617, 619, 629, 631,
 144     641, 643, 647, 653, 659, 661, 667, 673, 677, 683, 689, 691, 697, 701,
 145     703, 709, 713, 719, 727, 731, 733, 739, 743, 751, 757, 761, 767, 769,
 146     773, 779, 787, 793, 797, 799, 809, 811, 817, 821, 823, 827, 829, 839,
 147     841, 851, 853, 857, 859, 863, 871, 877, 881, 883, 887, 893, 899, 901,
 148     907, 911, 919, 923, 929, 937, 941, 943, 947, 949, 953, 961, 967, 971,
 149     977, 983, 989, 991, 997, 1003, 1007, 1009, 1013, 1019, 1021, 1027, 1031,
 150     1033, 1037, 1039, 1049, 1051, 1061, 1063, 1069, 1073, 1079, 1081, 1087,
 151     1091, 1093, 1097, 1103, 1109, 1117, 1121, 1123, 1129, 1139, 1147, 1151,
 152     1153, 1157, 1159, 1163, 1171, 1181, 1187, 1189, 1193, 1201, 1207, 1213,
 153     1217, 1219, 1223, 1229, 1231, 1237, 1241, 1247, 1249, 1259, 1261, 1271,
 154     1273, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1313, 1319,
 155     1321, 1327, 1333, 1339, 1343, 1349, 1357, 1361, 1363, 1367, 1369, 1373,
 156     1381, 1387, 1391, 1399, 1403, 1409, 1411, 1417, 1423, 1427, 1429, 1433,
 157     1439, 1447, 1451, 1453, 1457, 1459, 1469, 1471, 1481, 1483, 1487, 1489,
 158     1493, 1499, 1501, 1511, 1513, 1517, 1523, 1531, 1537, 1541, 1543, 1549,
 159     1553, 1559, 1567, 1571, 1577, 1579, 1583, 1591, 1597, 1601, 1607, 1609,
 160     1613, 1619, 1621, 1627, 1633, 1637, 1643, 1649, 1651, 1657, 1663, 1667,
 161     1669, 1679, 1681, 1691, 1693, 1697, 1699, 1703, 1709, 1711, 1717, 1721,
 162     1723, 1733, 1739, 1741, 1747, 1751, 1753, 1759, 1763, 1769, 1777, 1781,
 163     1783, 1787, 1789, 1801, 1807, 1811, 1817, 1819, 1823, 1829, 1831, 1843,
 164     1847, 1849, 1853, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1891, 1901,
 165     1907, 1909, 1913, 1919, 1921, 1927, 1931, 1933, 1937, 1943, 1949, 1951,
 166     1957, 1961, 1963, 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017,
 167     2021, 2027, 2029, 2033, 2039, 2041, 2047, 2053, 2059, 2063, 2069, 2071,
 168     2077, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2117, 2119, 2129, 2131,
 169     2137, 2141, 2143, 2147, 2153, 2159, 2161, 2171, 2173, 2179, 2183, 2197,
 170     2201, 2203, 2207, 2209, 2213, 2221, 2227, 2231, 2237, 2239, 2243, 2249,
 171     2251, 2257, 2263, 2267, 2269, 2273, 2279, 2281, 2287, 2291, 2293, 2297,
 172     2309, 2311
 173 };
 174
 175 static const int prime_offset_count = 480;
 176 static const int prime_multiplier = 2310;
 177 static const int prime_multiplier_bits = 11; /* 2^|prime_multiplier_bits| <=
 178                                               * |prime_multiplier| */
 179 static const int first_prime_index = 5;
 180
 181 int BN_GENCB_call(BN_GENCB *cb, int a, int b)
 182 {
 183     /* No callback means continue */
 184     if (!cb)
 185         return 1;
 186     switch (cb->ver) {
 187     case 1:
 188         /* Deprecated-style callbacks */
 189         if (!cb->cb.cb_1)
 190             return 1;
 191         cb->cb.cb_1(a, b, cb->arg);
 192         return 1;
 193     case 2:
 194         /* New-style callbacks */
 195         return cb->cb.cb_2(a, b, cb);
 196     default:
 197         break;
 198     }
 199     /* Unrecognised callback type */
 200     return 0;
 201 }
 202
 203 int BN_generate_prime_ex(BIGNUM *ret, int bits, int safe,
 204                          const BIGNUM *add, const BIGNUM *rem, BN_GENCB *cb)
 205 {
 206     BIGNUM *t;
 207     int found = 0;
 208     int i, j, c1 = 0;
 209     BN_CTX *ctx = NULL;
 210     prime_t *mods = NULL;
 211     int checks = BN_prime_checks_for_size(bits);
 212
 213     mods = OPENSSL_zalloc(sizeof(*mods) * NUMPRIMES);
 214     if (mods == NULL)
 215         goto err;
 216     if (bits < 2) {
 217         /* There are no prime numbers this small. */
 218         BNerr(BN_F_BN_GENERATE_PRIME_EX, BN_R_BITS_TOO_SMALL);
 219         return 0;
 220     } else if (bits == 2 && safe) {
 221         /* The smallest safe prime (7) is three bits. */
 222         BNerr(BN_F_BN_GENERATE_PRIME_EX, BN_R_BITS_TOO_SMALL);
 223         return 0;
 224     }
 225
 226     ctx = BN_CTX_new();
 227     if (ctx == NULL)
 228         goto err;
 229     BN_CTX_start(ctx);
 230     t = BN_CTX_get(ctx);
 231     if (!t)
 232         goto err;
 233  loop:
 234     /* make a random number and set the top and bottom bits */
 235     if (add == NULL) {
 236         if (!probable_prime(ret, bits, mods))
 237             goto err;
 238     } else {
 239         if (safe) {
 240             if (!probable_prime_dh_safe(ret, bits, add, rem, ctx))
 241                 goto err;
 242         } else {
 243             if (!bn_probable_prime_dh(ret, bits, add, rem, ctx))
 244                 goto err;
 245         }
 246     }
 247     /* if (BN_mod_word(ret,(BN_ULONG)3) == 1) goto loop; */
 248     if (!BN_GENCB_call(cb, 0, c1++))
 249         /* aborted */
 250         goto err;
 251
 252     if (!safe) {
 253         i = BN_is_prime_fasttest_ex(ret, checks, ctx, 0, cb);
 254         if (i == -1)
 255             goto err;
 256         if (i == 0)
 257             goto loop;
 258     } else {
 259         /*
 260          * for "safe prime" generation, check that (p-1)/2 is prime. Since a
 261          * prime is odd, We just need to divide by 2
 262          */
 263         if (!BN_rshift1(t, ret))
 264             goto err;
 265
 266         for (i = 0; i < checks; i++) {
 267             j = BN_is_prime_fasttest_ex(ret, 1, ctx, 0, cb);
 268             if (j == -1)
 269                 goto err;
 270             if (j == 0)
 271                 goto loop;
 272
 273             j = BN_is_prime_fasttest_ex(t, 1, ctx, 0, cb);
 274             if (j == -1)
 275                 goto err;
 276             if (j == 0)
 277                 goto loop;
 278
 279             if (!BN_GENCB_call(cb, 2, c1 - 1))
 280                 goto err;
 281             /* We have a safe prime test pass */
 282         }
 283     }
 284     /* we have a prime :-) */
 285     found = 1;
 286  err:
 287     OPENSSL_free(mods);
 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, prime_t *mods)
 501 {
 502     int i;
 503     BN_ULONG delta;
 504     BN_ULONG maxdelta = BN_MASK2 - primes[NUMPRIMES - 1];
 505     char is_single_word = bits <= BN_BITS2;
 506
 507  again:
 508     if (!BN_rand(rnd, bits, 1, 1))
 509         return (0);
 510     /* we now have a random number 'rnd' to test. */
 511     for (i = 1; i < NUMPRIMES; i++)
 512         mods[i] = (prime_t) BN_mod_word(rnd, (BN_ULONG)primes[i]);
 513     /*
 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.
 516      */
 517     if (is_single_word) {
 518         BN_ULONG size_limit;
 519
 520         if (bits == BN_BITS2) {
 521             /*
 522              * Shifting by this much has undefined behaviour so we do it a
 523              * different way
 524              */
 525             size_limit = ~((BN_ULONG)0) - BN_get_word(rnd);
 526         } else {
 527             size_limit = (((BN_ULONG)1) << bits) - BN_get_word(rnd) - 1;
 528         }
 529         if (size_limit < maxdelta)
 530             maxdelta = size_limit;
 531     }
 532     delta = 0;
 533  loop:
 534     if (is_single_word) {
 535         BN_ULONG rnd_word = BN_get_word(rnd);
 536
 537         /*-
 538          * In the case that the candidate prime is a single word then
 539          * we check that:
 540          *   1) It's greater than primes[i] because we shouldn't reject
 541          *      3 as being a prime number because it's a multiple of
 542          *      three.
 543          *   2) That it's not a multiple of a known prime. We don't
 544          *      check that rnd-1 is also coprime to all the known
 545          *      primes because there aren't many small primes where
 546          *      that's true.
 547          */
 548         for (i = 1; i < NUMPRIMES && primes[i] < rnd_word; i++) {
 549             if ((mods[i] + delta) % primes[i] == 0) {
 550                 delta += 2;
 551                 if (delta > maxdelta)
 552                     goto again;
 553                 goto loop;
 554             }
 555         }
 556     } else {
 557         for (i = 1; i < NUMPRIMES; i++) {
 558             /*
 559              * check that rnd is not a prime and also that gcd(rnd-1,primes)
 560              * == 1 (except for 2)
 561              */
 562             if (((mods[i] + delta) % primes[i]) <= 1) {
 563                 delta += 2;
 564                 if (delta > maxdelta)
 565                     goto again;
 566                 goto loop;
 567             }
 568         }
 569     }
 570     if (!BN_add_word(rnd, delta))
 571         return (0);
 572     if (BN_num_bits(rnd) != bits)
 573         goto again;
 574     bn_check_top(rnd);
 575     return (1);
 576 }
 577
 578 int bn_probable_prime_dh(BIGNUM *rnd, int bits,
 579                          const BIGNUM *add, const BIGNUM *rem, BN_CTX *ctx)
 580 {
 581     int i, ret = 0;
 582     BIGNUM *t1;
 583
 584     BN_CTX_start(ctx);
 585     if ((t1 = BN_CTX_get(ctx)) == NULL)
 586         goto err;
 587
 588     if (!BN_rand(rnd, bits, 0, 1))
 589         goto err;
 590
 591     /* we need ((rnd-rem) % add) == 0 */
 592
 593     if (!BN_mod(t1, rnd, add, ctx))
 594         goto err;
 595     if (!BN_sub(rnd, rnd, t1))
 596         goto err;
 597     if (rem == NULL) {
 598         if (!BN_add_word(rnd, 1))
 599             goto err;
 600     } else {
 601         if (!BN_add(rnd, rnd, rem))
 602             goto err;
 603     }
 604
 605     /* we now have a random number 'rand' to test. */
 606
 607  loop:
 608     for (i = 1; i < NUMPRIMES; i++) {
 609         /* check that rnd is a prime */
 610         if (BN_mod_word(rnd, (BN_ULONG)primes[i]) <= 1) {
 611             if (!BN_add(rnd, rnd, add))
 612                 goto err;
 613             goto loop;
 614         }
 615     }
 616     ret = 1;
 617
 618  err:
 619     BN_CTX_end(ctx);
 620     bn_check_top(rnd);
 621     return (ret);
 622 }
 623
 624 static int probable_prime_dh_safe(BIGNUM *p, int bits, const BIGNUM *padd,
 625                                   const BIGNUM *rem, BN_CTX *ctx)
 626 {
 627     int i, ret = 0;
 628     BIGNUM *t1, *qadd, *q;
 629
 630     bits--;
 631     BN_CTX_start(ctx);
 632     t1 = BN_CTX_get(ctx);
 633     q = BN_CTX_get(ctx);
 634     qadd = BN_CTX_get(ctx);
 635     if (qadd == NULL)
 636         goto err;
 637
 638     if (!BN_rshift1(qadd, padd))
 639         goto err;
 640
 641     if (!BN_rand(q, bits, 0, 1))
 642         goto err;
 643
 644     /* we need ((rnd-rem) % add) == 0 */
 645     if (!BN_mod(t1, q, qadd, ctx))
 646         goto err;
 647     if (!BN_sub(q, q, t1))
 648         goto err;
 649     if (rem == NULL) {
 650         if (!BN_add_word(q, 1))
 651             goto err;
 652     } else {
 653         if (!BN_rshift1(t1, rem))
 654             goto err;
 655         if (!BN_add(q, q, t1))
 656             goto err;
 657     }
 658
 659     /* we now have a random number 'rand' to test. */
 660     if (!BN_lshift1(p, q))
 661         goto err;
 662     if (!BN_add_word(p, 1))
 663         goto err;
 664
 665  loop:
 666     for (i = 1; i < NUMPRIMES; i++) {
 667         /* check that p and q are prime */
 668         /*
 669          * check that for p and q gcd(p-1,primes) == 1 (except for 2)
 670          */
 671         if ((BN_mod_word(p, (BN_ULONG)primes[i]) == 0) ||
 672             (BN_mod_word(q, (BN_ULONG)primes[i]) == 0)) {
 673             if (!BN_add(p, p, padd))
 674                 goto err;
 675             if (!BN_add(q, q, qadd))
 676                 goto err;
 677             goto loop;
 678         }
 679     }
 680     ret = 1;
 681
 682  err:
 683     BN_CTX_end(ctx);
 684     bn_check_top(p);
 685     return (ret);
 686 }