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