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
 176 int BN_GENCB_call(BN_GENCB *cb, int a, int b)
 177         {
 178         /* No callback means continue */
 179         if(!cb) return 1;
 180         switch(cb->ver)
 181                 {
 182         case 1:
 183                 /* Deprecated-style callbacks */
 184                 if(!cb->cb.cb_1)
 185                         return 1;
 186                 cb->cb.cb_1(a, b, cb->arg);
 187                 return 1;
 188         case 2:
 189                 /* New-style callbacks */
 190                 return cb->cb.cb_2(a, b, cb);
 191         default:
 192                 break;
 193                 }
 194         /* Unrecognised callback type */
 195         return 0;
 196         }
 197
 198 int BN_generate_prime_ex(BIGNUM *ret, int bits, int safe,
 199         const BIGNUM *add, const BIGNUM *rem, BN_GENCB *cb)
 200         {
 201         BIGNUM *t;
 202         int found=0;
 203         int i,j,c1=0;
 204         BN_CTX *ctx;
 205         int checks = BN_prime_checks_for_size(bits);
 206
 207         if (bits < 2)
 208                 {
 209                 /* There are no prime numbers this small. */
 210                 BNerr(BN_F_BN_GENERATE_PRIME_EX, BN_R_BITS_TOO_SMALL);
 211                 return 0;
 212                 }
 213         else if (bits == 2 && safe)
 214                 {
 215                 /* The smallest safe prime (7) is three bits. */
 216                 BNerr(BN_F_BN_GENERATE_PRIME_EX, BN_R_BITS_TOO_SMALL);
 217                 return 0;
 218                 }
 219
 220         ctx=BN_CTX_new();
 221         if (ctx == NULL) goto err;
 222         BN_CTX_start(ctx);
 223         t = BN_CTX_get(ctx);
 224         if(!t) goto err;
 225 loop:
 226         /* make a random number and set the top and bottom bits */
 227         if (add == NULL)
 228                 {
 229                 if (!probable_prime(ret,bits)) goto err;
 230                 }
 231         else
 232                 {
 233                 if (safe)
 234                         {
 235                         if (!probable_prime_dh_safe(ret,bits,add,rem,ctx))
 236                                  goto err;
 237                         }
 238                 else
 239                         {
 240                         if (!bn_probable_prime_dh(ret,bits,add,rem,ctx))
 241                                 goto err;
 242                         }
 243                 }
 244         /* if (BN_mod_word(ret,(BN_ULONG)3) == 1) goto loop; */
 245         if(!BN_GENCB_call(cb, 0, c1++))
 246                 /* aborted */
 247                 goto err;
 248
 249         if (!safe)
 250                 {
 251                 i=BN_is_prime_fasttest_ex(ret,checks,ctx,0,cb);
 252                 if (i == -1) goto err;
 253                 if (i == 0) goto loop;
 254                 }
 255         else
 256                 {
 257                 /* for "safe prime" generation,
 258                  * check that (p-1)/2 is prime.
 259                  * Since a prime is odd, We just
 260                  * need to divide by 2 */
 261                 if (!BN_rshift1(t,ret)) goto err;
 262
 263                 for (i=0; i<checks; i++)
 264                         {
 265                         j=BN_is_prime_fasttest_ex(ret,1,ctx,0,cb);
 266                         if (j == -1) goto err;
 267                         if (j == 0) goto loop;
 268
 269                         j=BN_is_prime_fasttest_ex(t,1,ctx,0,cb);
 270                         if (j == -1) goto err;
 271                         if (j == 0) goto loop;
 272
 273                         if(!BN_GENCB_call(cb, 2, c1-1))
 274                                 goto err;
 275                         /* We have a safe prime test pass */
 276                         }
 277                 }
 278         /* we have a prime :-) */
 279         found = 1;
 280 err:
 281         if (ctx != NULL)
 282                 {
 283                 BN_CTX_end(ctx);
 284                 BN_CTX_free(ctx);
 285                 }
 286         bn_check_top(ret);
 287         return found;
 288         }
 289
 290 int BN_is_prime_ex(const BIGNUM *a, int checks, BN_CTX *ctx_passed, BN_GENCB *cb)
 291         {
 292         return BN_is_prime_fasttest_ex(a, checks, ctx_passed, 0, cb);
 293         }
 294
 295 int BN_is_prime_fasttest_ex(const BIGNUM *a, int checks, BN_CTX *ctx_passed,
 296                 int do_trial_division, BN_GENCB *cb)
 297         {
 298         int i, j, ret = -1;
 299         int k;
 300         BN_CTX *ctx = NULL;
 301         BIGNUM *A1, *A1_odd, *check; /* taken from ctx */
 302         BN_MONT_CTX *mont = NULL;
 303         const BIGNUM *A = NULL;
 304
 305         if (BN_cmp(a, BN_value_one()) <= 0)
 306                 return 0;
 307
 308         if (checks == BN_prime_checks)
 309                 checks = BN_prime_checks_for_size(BN_num_bits(a));
 310
 311         /* first look for small factors */
 312         if (!BN_is_odd(a))
 313                 /* a is even => a is prime if and only if a == 2 */
 314                 return BN_is_word(a, 2);
 315         if (do_trial_division)
 316                 {
 317                 for (i = 1; i < NUMPRIMES; i++)
 318                         if (BN_mod_word(a, primes[i]) == 0)
 319                                 return 0;
 320                 if(!BN_GENCB_call(cb, 1, -1))
 321                         goto err;
 322                 }
 323
 324         if (ctx_passed != NULL)
 325                 ctx = ctx_passed;
 326         else
 327                 if ((ctx=BN_CTX_new()) == NULL)
 328                         goto err;
 329         BN_CTX_start(ctx);
 330
 331         /* A := abs(a) */
 332         if (a->neg)
 333                 {
 334                 BIGNUM *t;
 335                 if ((t = BN_CTX_get(ctx)) == NULL) goto err;
 336                 BN_copy(t, a);
 337                 t->neg = 0;
 338                 A = t;
 339                 }
 340         else
 341                 A = a;
 342         A1 = BN_CTX_get(ctx);
 343         A1_odd = BN_CTX_get(ctx);
 344         check = BN_CTX_get(ctx);
 345         if (check == NULL) goto err;
 346
 347         /* compute A1 := A - 1 */
 348         if (!BN_copy(A1, A))
 349                 goto err;
 350         if (!BN_sub_word(A1, 1))
 351                 goto err;
 352         if (BN_is_zero(A1))
 353                 {
 354                 ret = 0;
 355                 goto err;
 356                 }
 357
 358         /* write  A1  as  A1_odd * 2^k */
 359         k = 1;
 360         while (!BN_is_bit_set(A1, k))
 361                 k++;
 362         if (!BN_rshift(A1_odd, A1, k))
 363                 goto err;
 364
 365         /* Montgomery setup for computations mod A */
 366         mont = BN_MONT_CTX_new();
 367         if (mont == NULL)
 368                 goto err;
 369         if (!BN_MONT_CTX_set(mont, A, ctx))
 370                 goto err;
 371
 372         for (i = 0; i < checks; i++)
 373                 {
 374                 if (!BN_pseudo_rand_range(check, A1))
 375                         goto err;
 376                 if (!BN_add_word(check, 1))
 377                         goto err;
 378                 /* now 1 <= check < A */
 379
 380                 j = witness(check, A, A1, A1_odd, k, ctx, mont);
 381                 if (j == -1) goto err;
 382                 if (j)
 383                         {
 384                         ret=0;
 385                         goto err;
 386                         }
 387                 if(!BN_GENCB_call(cb, 1, i))
 388                         goto err;
 389                 }
 390         ret=1;
 391 err:
 392         if (ctx != NULL)
 393                 {
 394                 BN_CTX_end(ctx);
 395                 if (ctx_passed == NULL)
 396                         BN_CTX_free(ctx);
 397                 }
 398         if (mont != NULL)
 399                 BN_MONT_CTX_free(mont);
 400
 401         return(ret);
 402         }
 403
 404 int bn_probable_prime_dh_retry(BIGNUM *rnd, int bits, BN_CTX *ctx)
 405         {
 406         int i;
 407         BIGNUM *t1;
 408         int ret = 0;
 409
 410         BN_CTX_start(ctx);
 411         if ((t1 = BN_CTX_get(ctx)) == NULL) goto err;
 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                         /*if (!BN_add(rnd, rnd, add)) goto err;*/
 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 primes 2, 3, 5, 7, 11 */
 460         for (i = 5; 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         }