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         BIGNUM *t1;
 409         int ret = 0;
 410
 411         BN_CTX_start(ctx);
 412         if ((t1 = BN_CTX_get(ctx)) == NULL) goto err;
 413
 414 loop:
 415         if (!BN_rand(rnd, bits, 0, 1)) goto err;
 416
 417         /* we now have a random number 'rand' to test. */
 418
 419         for (i = 1; i < NUMPRIMES; i++)
 420                 {
 421                 /* check that rnd is a prime */
 422                 if (BN_mod_word(rnd, (BN_ULONG)primes[i]) <= 1)
 423                         {
 424                         goto loop;
 425                         }
 426                 }
 427         ret=1;
 428
 429 err:
 430         BN_CTX_end(ctx);
 431         bn_check_top(rnd);
 432         return(ret);
 433         }
 434
 435 int bn_probable_prime_dh_coprime(BIGNUM *rnd, int bits, BN_CTX *ctx)
 436         {
 437         int i;
 438         BIGNUM *t1;
 439         BIGNUM *offset_index;
 440         BIGNUM *offset_count;
 441         int ret = 0;
 442
 443         BN_CTX_start(ctx);
 444         if ((t1 = BN_CTX_get(ctx)) == NULL) goto err;
 445         if ((offset_index = BN_CTX_get(ctx)) == NULL) goto err;
 446         if ((offset_count = BN_CTX_get(ctx)) == NULL) goto err;
 447
 448         BN_add_word(offset_count, prime_offset_count);
 449
 450 loop:
 451         if (!BN_rand(rnd, bits, 0, 1)) goto err;
 452         if (!BN_rand_range(offset_index, offset_count)) goto err;
 453
 454         BN_mul_word(rnd, prime_multiplier);
 455         BN_add_word(rnd, prime_offsets[BN_get_word(offset_index)]);
 456
 457         /* we now have a random number 'rand' to test. */
 458
 459         /* skip coprimes */
 460         for (i = first_prime_index; i < NUMPRIMES; i++)
 461                 {
 462                 /* check that rnd is a prime */
 463                 if (BN_mod_word(rnd, (BN_ULONG)primes[i]) <= 1)
 464                         {
 465                         goto loop;
 466                         }
 467                 }
 468         ret=1;
 469
 470 err:
 471         BN_CTX_end(ctx);
 472         bn_check_top(rnd);
 473         return(ret);
 474         }
 475
 476 static int witness(BIGNUM *w, const BIGNUM *a, const BIGNUM *a1,
 477         const BIGNUM *a1_odd, int k, BN_CTX *ctx, 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                 {
 487                 if (!BN_mod_mul(w, w, w, a, ctx)) /* w := w^2 mod a */
 488                         return -1;
 489                 if (BN_is_one(w))
 490                         return 1; /* 'a' is composite, otherwise a previous 'w' would
 491                                    * have been == -1 (mod 'a') */
 492                 if (BN_cmp(w, a1) == 0)
 493                         return 0; /* w == -1 (mod a), 'a' is probably prime */
 494                 }
 495         /* If we get here, 'w' is the (a-1)/2-th power of the original 'w',
 496          * and it is neither -1 nor +1 -- so 'a' cannot be prime */
 497         bn_check_top(w);
 498         return 1;
 499         }
 500
 501 static int probable_prime(BIGNUM *rnd, int bits)
 502         {
 503         int i;
 504         prime_t mods[NUMPRIMES];
 505         BN_ULONG delta;
 506         BN_ULONG maxdelta = BN_MASK2 - primes[NUMPRIMES-1];
 507         char is_single_word = bits <= BN_BITS2;
 508
 509 again:
 510         if (!BN_rand(rnd,bits,1,1)) return(0);
 511         /* we now have a random number 'rnd' to test. */
 512         for (i=1; i<NUMPRIMES; i++)
 513                 mods[i]=(prime_t)BN_mod_word(rnd,(BN_ULONG)primes[i]);
 514         /* If bits is so small that it fits into a single word then we
 515          * additionally don't want to exceed that many bits. */
 516         if (is_single_word)
 517                 {
 518                 BN_ULONG size_limit = (((BN_ULONG) 1) << bits) - BN_get_word(rnd) - 1;
 519                 if (size_limit < maxdelta)
 520                         maxdelta = size_limit;
 521                 }
 522         delta=0;
 523 loop:
 524         if (is_single_word)
 525                 {
 526                 BN_ULONG rnd_word = BN_get_word(rnd);
 527
 528                 /* In the case that the candidate prime is a single word then
 529                  * we check that:
 530                  *   1) It's greater than primes[i] because we shouldn't reject
 531                  *      3 as being a prime number because it's a multiple of
 532                  *      three.
 533                  *   2) That it's not a multiple of a known prime. We don't
 534                  *      check that rnd-1 is also coprime to all the known
 535                  *      primes because there aren't many small primes where
 536                  *      that's true. */
 537                 for (i=1; i<NUMPRIMES && primes[i]<rnd_word; i++)
 538                         {
 539                         if ((mods[i]+delta)%primes[i] == 0)
 540                                 {
 541                                 delta+=2;
 542                                 if (delta > maxdelta) goto again;
 543                                 goto loop;
 544                                 }
 545                         }
 546                 }
 547         else
 548                 {
 549                 for (i=1; i<NUMPRIMES; i++)
 550                         {
 551                         /* check that rnd is not a prime and also
 552                          * that gcd(rnd-1,primes) == 1 (except for 2) */
 553                         if (((mods[i]+delta)%primes[i]) <= 1)
 554                                 {
 555                                 delta+=2;
 556                                 if (delta > maxdelta) goto again;
 557                                 goto loop;
 558                                 }
 559                         }
 560                 }
 561         if (!BN_add_word(rnd,delta)) return(0);
 562         if (BN_num_bits(rnd) != bits)
 563                 goto again;
 564         bn_check_top(rnd);
 565         return(1);
 566         }
 567
 568 int bn_probable_prime_dh(BIGNUM *rnd, int bits,
 569         const BIGNUM *add, const BIGNUM *rem, BN_CTX *ctx)
 570         {
 571         int i,ret=0;
 572         BIGNUM *t1;
 573
 574         BN_CTX_start(ctx);
 575         if ((t1 = BN_CTX_get(ctx)) == NULL) goto err;
 576
 577         if (!BN_rand(rnd,bits,0,1)) goto err;
 578
 579         /* we need ((rnd-rem) % add) == 0 */
 580
 581         if (!BN_mod(t1,rnd,add,ctx)) goto err;
 582         if (!BN_sub(rnd,rnd,t1)) goto err;
 583         if (rem == NULL)
 584                 { if (!BN_add_word(rnd,1)) goto err; }
 585         else
 586                 { if (!BN_add(rnd,rnd,rem)) goto err; }
 587
 588         /* we now have a random number 'rand' to test. */
 589
 590 loop:
 591         for (i=1; i<NUMPRIMES; i++)
 592                 {
 593                 /* check that rnd is a prime */
 594                 if (BN_mod_word(rnd,(BN_ULONG)primes[i]) <= 1)
 595                         {
 596                         if (!BN_add(rnd,rnd,add)) goto err;
 597                         goto loop;
 598                         }
 599                 }
 600         ret=1;
 601
 602 err:
 603         BN_CTX_end(ctx);
 604         bn_check_top(rnd);
 605         return(ret);
 606         }
 607
 608 static int probable_prime_dh_safe(BIGNUM *p, int bits, const BIGNUM *padd,
 609         const BIGNUM *rem, BN_CTX *ctx)
 610         {
 611         int i,ret=0;
 612         BIGNUM *t1,*qadd,*q;
 613
 614         bits--;
 615         BN_CTX_start(ctx);
 616         t1 = BN_CTX_get(ctx);
 617         q = BN_CTX_get(ctx);
 618         qadd = BN_CTX_get(ctx);
 619         if (qadd == NULL) goto err;
 620
 621         if (!BN_rshift1(qadd,padd)) goto err;
 622
 623         if (!BN_rand(q,bits,0,1)) goto err;
 624
 625         /* we need ((rnd-rem) % add) == 0 */
 626         if (!BN_mod(t1,q,qadd,ctx)) goto err;
 627         if (!BN_sub(q,q,t1)) goto err;
 628         if (rem == NULL)
 629                 { if (!BN_add_word(q,1)) goto err; }
 630         else
 631                 {
 632                 if (!BN_rshift1(t1,rem)) goto err;
 633                 if (!BN_add(q,q,t1)) goto err;
 634                 }
 635
 636         /* we now have a random number 'rand' to test. */
 637         if (!BN_lshift1(p,q)) goto err;
 638         if (!BN_add_word(p,1)) goto err;
 639
 640 loop:
 641         for (i=1; i<NUMPRIMES; i++)
 642                 {
 643                 /* check that p and q are prime */
 644                 /* check that for p and q
 645                  * gcd(p-1,primes) == 1 (except for 2) */
 646                 if ((BN_mod_word(p,(BN_ULONG)primes[i]) == 0) ||
 647                         (BN_mod_word(q,(BN_ULONG)primes[i]) == 0))
 648                         {
 649                         if (!BN_add(p,p,padd)) goto err;
 650                         if (!BN_add(q,q,qadd)) goto err;
 651                         goto loop;
 652                         }
 653                 }
 654         ret=1;
 655
 656 err:
 657         BN_CTX_end(ctx);
 658         bn_check_top(p);
 659         return(ret);
 660         }