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