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