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