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 = (((BN_ULONG)1) << bits) - BN_get_word(rnd) - 1;
 522         if (size_limit < maxdelta)
 523             maxdelta = size_limit;
 524     }
 525     delta = 0;
 526  loop:
 527     if (is_single_word) {
 528         BN_ULONG rnd_word = BN_get_word(rnd);
 529
 530         /*-
 531          * In the case that the candidate prime is a single word then
 532          * we check that:
 533          *   1) It's greater than primes[i] because we shouldn't reject
 534          *      3 as being a prime number because it's a multiple of
 535          *      three.
 536          *   2) That it's not a multiple of a known prime. We don't
 537          *      check that rnd-1 is also coprime to all the known
 538          *      primes because there aren't many small primes where
 539          *      that's true.
 540          */
 541         for (i = 1; i < NUMPRIMES && primes[i] < rnd_word; i++) {
 542             if ((mods[i] + delta) % primes[i] == 0) {
 543                 delta += 2;
 544                 if (delta > maxdelta)
 545                     goto again;
 546                 goto loop;
 547             }
 548         }
 549     } else {
 550         for (i = 1; i < NUMPRIMES; i++) {
 551             /*
 552              * check that rnd is not a prime and also that gcd(rnd-1,primes)
 553              * == 1 (except for 2)
 554              */
 555             if (((mods[i] + delta) % primes[i]) <= 1) {
 556                 delta += 2;
 557                 if (delta > maxdelta)
 558                     goto again;
 559                 goto loop;
 560             }
 561         }
 562     }
 563     if (!BN_add_word(rnd, delta))
 564         return (0);
 565     if (BN_num_bits(rnd) != bits)
 566         goto again;
 567     bn_check_top(rnd);
 568     return (1);
 569 }
 570
 571 int bn_probable_prime_dh(BIGNUM *rnd, int bits,
 572                          const BIGNUM *add, const BIGNUM *rem, BN_CTX *ctx)
 573 {
 574     int i, ret = 0;
 575     BIGNUM *t1;
 576
 577     BN_CTX_start(ctx);
 578     if ((t1 = BN_CTX_get(ctx)) == NULL)
 579         goto err;
 580
 581     if (!BN_rand(rnd, bits, 0, 1))
 582         goto err;
 583
 584     /* we need ((rnd-rem) % add) == 0 */
 585
 586     if (!BN_mod(t1, rnd, add, ctx))
 587         goto err;
 588     if (!BN_sub(rnd, rnd, t1))
 589         goto err;
 590     if (rem == NULL) {
 591         if (!BN_add_word(rnd, 1))
 592             goto err;
 593     } else {
 594         if (!BN_add(rnd, rnd, rem))
 595             goto err;
 596     }
 597
 598     /* we now have a random number 'rand' to test. */
 599
 600  loop:
 601     for (i = 1; i < NUMPRIMES; i++) {
 602         /* check that rnd is a prime */
 603         if (BN_mod_word(rnd, (BN_ULONG)primes[i]) <= 1) {
 604             if (!BN_add(rnd, rnd, add))
 605                 goto err;
 606             goto loop;
 607         }
 608     }
 609     ret = 1;
 610
 611  err:
 612     BN_CTX_end(ctx);
 613     bn_check_top(rnd);
 614     return (ret);
 615 }
 616
 617 static int probable_prime_dh_safe(BIGNUM *p, int bits, const BIGNUM *padd,
 618                                   const BIGNUM *rem, BN_CTX *ctx)
 619 {
 620     int i, ret = 0;
 621     BIGNUM *t1, *qadd, *q;
 622
 623     bits--;
 624     BN_CTX_start(ctx);
 625     t1 = BN_CTX_get(ctx);
 626     q = BN_CTX_get(ctx);
 627     qadd = BN_CTX_get(ctx);
 628     if (qadd == NULL)
 629         goto err;
 630
 631     if (!BN_rshift1(qadd, padd))
 632         goto err;
 633
 634     if (!BN_rand(q, bits, 0, 1))
 635         goto err;
 636
 637     /* we need ((rnd-rem) % add) == 0 */
 638     if (!BN_mod(t1, q, qadd, ctx))
 639         goto err;
 640     if (!BN_sub(q, q, t1))
 641         goto err;
 642     if (rem == NULL) {
 643         if (!BN_add_word(q, 1))
 644             goto err;
 645     } else {
 646         if (!BN_rshift1(t1, rem))
 647             goto err;
 648         if (!BN_add(q, q, t1))
 649             goto err;
 650     }
 651
 652     /* we now have a random number 'rand' to test. */
 653     if (!BN_lshift1(p, q))
 654         goto err;
 655     if (!BN_add_word(p, 1))
 656         goto err;
 657
 658  loop:
 659     for (i = 1; i < NUMPRIMES; i++) {
 660         /* check that p and q are prime */
 661         /*
 662          * check that for p and q gcd(p-1,primes) == 1 (except for 2)
 663          */
 664         if ((BN_mod_word(p, (BN_ULONG)primes[i]) == 0) ||
 665             (BN_mod_word(q, (BN_ULONG)primes[i]) == 0)) {
 666             if (!BN_add(p, p, padd))
 667                 goto err;
 668             if (!BN_add(q, q, qadd))
 669                 goto err;
 670             goto loop;
 671         }
 672     }
 673     ret = 1;
 674
 675  err:
 676     BN_CTX_end(ctx);
 677     bn_check_top(p);
 678     return (ret);
 679 }