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