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