src/third_party/boringssl/src/crypto/bn/prime.c

   1 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
   2  * All rights reserved.
   3  *
   4  * This package is an SSL implementation written
   5  * by Eric Young (eay@cryptsoft.com).
   6  * The implementation was written so as to conform with Netscapes SSL.
   7  *
   8  * This library is free for commercial and non-commercial use as long as
   9  * the following conditions are aheared to.  The following conditions
  10  * apply to all code found in this distribution, be it the RC4, RSA,
  11  * lhash, DES, etc., code; not just the SSL code.  The SSL documentation
  12  * included with this distribution is covered by the same copyright terms
  13  * except that the holder is Tim Hudson (tjh@cryptsoft.com).
  14  *
  15  * Copyright remains Eric Young's, and as such any Copyright notices in
  16  * the code are not to be removed.
  17  * If this package is used in a product, Eric Young should be given attribution
  18  * as the author of the parts of the library used.
  19  * This can be in the form of a textual message at program startup or
  20  * in documentation (online or textual) provided with the package.
  21  *
  22  * Redistribution and use in source and binary forms, with or without
  23  * modification, are permitted provided that the following conditions
  24  * are met:
  25  * 1. Redistributions of source code must retain the copyright
  26  *    notice, this list of conditions and the following disclaimer.
  27  * 2. Redistributions in binary form must reproduce the above copyright
  28  *    notice, this list of conditions and the following disclaimer in the
  29  *    documentation and/or other materials provided with the distribution.
  30  * 3. All advertising materials mentioning features or use of this software
  31  *    must display the following acknowledgement:
  32  *    "This product includes cryptographic software written by
  33  *     Eric Young (eay@cryptsoft.com)"
  34  *    The word 'cryptographic' can be left out if the rouines from the library
  35  *    being used are not cryptographic related :-).
  36  * 4. If you include any Windows specific code (or a derivative thereof) from
  37  *    the apps directory (application code) you must include an acknowledgement:
  38  *    "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
  39  *
  40  * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
  41  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  42  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  43  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  44  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  45  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  46  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  47  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  48  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  49  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  50  * SUCH DAMAGE.
  51  *
  52  * The licence and distribution terms for any publically available version or
  53  * derivative of this code cannot be changed.  i.e. this code cannot simply be
  54  * copied and put under another distribution licence
  55  * [including the GNU Public Licence.]
  56  */
  57 /* ====================================================================
  58  * Copyright (c) 1998-2001 The OpenSSL Project.  All rights reserved.
  59  *
  60  * Redistribution and use in source and binary forms, with or without
  61  * modification, are permitted provided that the following conditions
  62  * are met:
  63  *
  64  * 1. Redistributions of source code must retain the above copyright
  65  *    notice, this list of conditions and the following disclaimer.
  66  *
  67  * 2. Redistributions in binary form must reproduce the above copyright
  68  *    notice, this list of conditions and the following disclaimer in
  69  *    the documentation and/or other materials provided with the
  70  *    distribution.
  71  *
  72  * 3. All advertising materials mentioning features or use of this
  73  *    software must display the following acknowledgment:
  74  *    "This product includes software developed by the OpenSSL Project
  75  *    for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
  76  *
  77  * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
  78  *    endorse or promote products derived from this software without
  79  *    prior written permission. For written permission, please contact
  80  *    openssl-core@openssl.org.
  81  *
  82  * 5. Products derived from this software may not be called "OpenSSL"
  83  *    nor may "OpenSSL" appear in their names without prior written
  84  *    permission of the OpenSSL Project.
  85  *
  86  * 6. Redistributions of any form whatsoever must retain the following
  87  *    acknowledgment:
  88  *    "This product includes software developed by the OpenSSL Project
  89  *    for use in the OpenSSL Toolkit (http://www.openssl.org/)"
  90  *
  91  * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
  92  * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  93  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  94  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OpenSSL PROJECT OR
  95  * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  96  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  97  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  98  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  99  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
 100  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 101  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
 102  * OF THE POSSIBILITY OF SUCH DAMAGE.
 103  * ====================================================================
 104  *
 105  * This product includes cryptographic software written by Eric Young
 106  * (eay@cryptsoft.com).  This product includes software written by Tim
 107  * Hudson (tjh@cryptsoft.com). */
 108
 109 #include <openssl/bn.h>
 110
 111 #include <openssl/err.h>
 112 #include <openssl/mem.h>
 113
 114 #include "internal.h"
 115
 116 /* number of Miller-Rabin iterations for an error rate  of less than 2^-80
 117  * for random 'b'-bit input, b >= 100 (taken from table 4.4 in the Handbook
 118  * of Applied Cryptography [Menezes, van Oorschot, Vanstone; CRC Press 1996];
 119  * original paper: Damgaard, Landrock, Pomerance: Average case error estimates
 120  * for the strong probable prime test. -- Math. Comp. 61 (1993) 177-194) */
 121 #define BN_prime_checks_for_size(b) ((b) >= 1300 ?  2 : \
 122                                 (b) >=  850 ?  3 : \
 123                                 (b) >=  650 ?  4 : \
 124                                 (b) >=  550 ?  5 : \
 125                                 (b) >=  450 ?  6 : \
 126                                 (b) >=  400 ?  7 : \
 127                                 (b) >=  350 ?  8 : \
 128                                 (b) >=  300 ?  9 : \
 129                                 (b) >=  250 ? 12 : \
 130                                 (b) >=  200 ? 15 : \
 131                                 (b) >=  150 ? 18 : \
 132                                 /* b >= 100 */ 27)
 133
 134 /* The quick sieve algorithm approach to weeding out primes is Philip
 135  * Zimmermann's, as implemented in PGP.  I have had a read of his comments and
 136  * implemented my own version. */
 137
 138 /* NUMPRIMES is the number of primes that fit into a uint16_t. */
 139 #define NUMPRIMES 2048
 140
 141 /* primes is defined at the bottom of the file and contains all the primes that
 142  * fit into a uint16_t. */
 143 static const uint16_t primes[NUMPRIMES];
 144
 145 static int witness(BIGNUM *w, const BIGNUM *a, const BIGNUM *a1,
 146                    const BIGNUM *a1_odd, int k, BN_CTX *ctx, BN_MONT_CTX *mont);
 147 static int probable_prime(BIGNUM *rnd, int bits);
 148 static int probable_prime_dh(BIGNUM *rnd, int bits, const BIGNUM *add,
 149                              const BIGNUM *rem, BN_CTX *ctx);
 150 static int probable_prime_dh_safe(BIGNUM *rnd, int bits, const BIGNUM *add,
 151                                   const BIGNUM *rem, BN_CTX *ctx);
 152
 153 void BN_GENCB_set(BN_GENCB *callback,
 154                   int (*f)(int event, int n, struct bn_gencb_st *),
 155                   void *arg) {
 156   callback->callback = f;
 157   callback->arg = arg;
 158 }
 159
 160 int BN_GENCB_call(BN_GENCB *callback, int event, int n) {
 161   if (!callback) {
 162     return 1;
 163   }
 164
 165   return callback->callback(event, n, callback);
 166 }
 167
 168 int BN_generate_prime_ex(BIGNUM *ret, int bits, int safe, const BIGNUM *add,
 169                          const BIGNUM *rem, BN_GENCB *cb) {
 170   BIGNUM *t;
 171   int found = 0;
 172   int i, j, c1 = 0;
 173   BN_CTX *ctx;
 174   int checks = BN_prime_checks_for_size(bits);
 175
 176   if (bits < 2) {
 177     /* There are no prime numbers this small. */
 178     OPENSSL_PUT_ERROR(BN, BN_generate_prime_ex, BN_R_BITS_TOO_SMALL);
 179     return 0;
 180   } else if (bits == 2 && safe) {
 181     /* The smallest safe prime (7) is three bits. */
 182     OPENSSL_PUT_ERROR(BN, BN_generate_prime_ex, BN_R_BITS_TOO_SMALL);
 183     return 0;
 184   }
 185
 186   ctx = BN_CTX_new();
 187   if (ctx == NULL) {
 188     goto err;
 189   }
 190   BN_CTX_start(ctx);
 191   t = BN_CTX_get(ctx);
 192   if (!t) {
 193     goto err;
 194   }
 195
 196 loop:
 197   /* make a random number and set the top and bottom bits */
 198   if (add == NULL) {
 199     if (!probable_prime(ret, bits)) {
 200       goto err;
 201     }
 202   } else {
 203     if (safe) {
 204       if (!probable_prime_dh_safe(ret, bits, add, rem, ctx)) {
 205         goto err;
 206       }
 207     } else {
 208       if (!probable_prime_dh(ret, bits, add, rem, ctx)) {
 209         goto err;
 210       }
 211     }
 212   }
 213
 214   if (!BN_GENCB_call(cb, BN_GENCB_GENERATED, c1++)) {
 215     /* aborted */
 216     goto err;
 217   }
 218
 219   if (!safe) {
 220     i = BN_is_prime_fasttest_ex(ret, checks, ctx, 0, cb);
 221     if (i == -1) {
 222       goto err;
 223     } else if (i == 0) {
 224       goto loop;
 225     }
 226   } else {
 227     /* for "safe prime" generation, check that (p-1)/2 is prime. Since a prime
 228      * is odd, We just need to divide by 2 */
 229     if (!BN_rshift1(t, ret)) {
 230       goto err;
 231     }
 232
 233     for (i = 0; i < checks; i++) {
 234       j = BN_is_prime_fasttest_ex(ret, 1, ctx, 0, NULL);
 235       if (j == -1) {
 236         goto err;
 237       } else if (j == 0) {
 238         goto loop;
 239       }
 240
 241       j = BN_is_prime_fasttest_ex(t, 1, ctx, 0, NULL);
 242       if (j == -1) {
 243         goto err;
 244       } else if (j == 0) {
 245         goto loop;
 246       }
 247
 248       if (!BN_GENCB_call(cb, i, c1 - 1)) {
 249         goto err;
 250       }
 251       /* We have a safe prime test pass */
 252     }
 253   }
 254
 255   /* we have a prime :-) */
 256   found = 1;
 257
 258 err:
 259   if (ctx != NULL) {
 260     BN_CTX_end(ctx);
 261     BN_CTX_free(ctx);
 262   }
 263
 264   return found;
 265 }
 266
 267 int BN_primality_test(int *is_probably_prime, const BIGNUM *candidate,
 268                       int checks, BN_CTX *ctx, int do_trial_division,
 269                       BN_GENCB *cb) {
 270   switch (BN_is_prime_fasttest_ex(candidate, checks, ctx, do_trial_division, cb)) {
 271     case 1:
 272       *is_probably_prime = 1;
 273       return 1;
 274     case 0:
 275       *is_probably_prime = 0;
 276       return 1;
 277     default:
 278       *is_probably_prime = 0;
 279       return 0;
 280   }
 281 }
 282
 283 int BN_is_prime_ex(const BIGNUM *candidate, int checks, BN_CTX *ctx, BN_GENCB *cb) {
 284   return BN_is_prime_fasttest_ex(candidate, checks, ctx, 0, cb);
 285 }
 286
 287 int BN_is_prime_fasttest_ex(const BIGNUM *a, int checks, BN_CTX *ctx_passed,
 288                             int do_trial_division, BN_GENCB *cb) {
 289   int i, j, ret = -1;
 290   int k;
 291   BN_CTX *ctx = NULL;
 292   BIGNUM *A1, *A1_odd, *check; /* taken from ctx */
 293   BN_MONT_CTX *mont = NULL;
 294   const BIGNUM *A = NULL;
 295
 296   if (BN_cmp(a, BN_value_one()) <= 0) {
 297     return 0;
 298   }
 299
 300   if (checks == BN_prime_checks) {
 301     checks = BN_prime_checks_for_size(BN_num_bits(a));
 302   }
 303
 304   /* first look for small factors */
 305   if (!BN_is_odd(a)) {
 306     /* a is even => a is prime if and only if a == 2 */
 307     return BN_is_word(a, 2);
 308   }
 309
 310   if (do_trial_division) {
 311     for (i = 1; i < NUMPRIMES; i++) {
 312       if (BN_mod_word(a, primes[i]) == 0) {
 313         return 0;
 314       }
 315     }
 316
 317     if (!BN_GENCB_call(cb, 1, -1)) {
 318       goto err;
 319     }
 320   }
 321
 322   if (ctx_passed != NULL) {
 323     ctx = ctx_passed;
 324   } else if ((ctx = BN_CTX_new()) == NULL) {
 325     goto err;
 326   }
 327   BN_CTX_start(ctx);
 328
 329   /* A := abs(a) */
 330   if (a->neg) {
 331     BIGNUM *t;
 332     if ((t = BN_CTX_get(ctx)) == NULL) {
 333       goto err;
 334     }
 335     BN_copy(t, a);
 336     t->neg = 0;
 337     A = t;
 338   } else {
 339     A = a;
 340   }
 341
 342   A1 = BN_CTX_get(ctx);
 343   A1_odd = BN_CTX_get(ctx);
 344   check = BN_CTX_get(ctx);
 345   if (check == NULL) {
 346     goto err;
 347   }
 348
 349   /* compute A1 := A - 1 */
 350   if (!BN_copy(A1, A)) {
 351     goto err;
 352   }
 353   if (!BN_sub_word(A1, 1)) {
 354     goto err;
 355   }
 356   if (BN_is_zero(A1)) {
 357     ret = 0;
 358     goto err;
 359   }
 360
 361   /* write  A1  as  A1_odd * 2^k */
 362   k = 1;
 363   while (!BN_is_bit_set(A1, k)) {
 364     k++;
 365   }
 366   if (!BN_rshift(A1_odd, A1, k)) {
 367     goto err;
 368   }
 369
 370   /* Montgomery setup for computations mod A */
 371   mont = BN_MONT_CTX_new();
 372   if (mont == NULL) {
 373     goto err;
 374   }
 375   if (!BN_MONT_CTX_set(mont, A, ctx)) {
 376     goto err;
 377   }
 378
 379   for (i = 0; i < checks; i++) {
 380     if (!BN_pseudo_rand_range(check, A1)) {
 381       goto err;
 382     }
 383     if (!BN_add_word(check, 1)) {
 384       goto err;
 385     }
 386     /* now 1 <= check < A */
 387
 388     j = witness(check, A, A1, A1_odd, k, ctx, mont);
 389     if (j == -1) {
 390       goto err;
 391     }
 392     if (j) {
 393       ret = 0;
 394       goto err;
 395     }
 396     if (!BN_GENCB_call(cb, 1, i)) {
 397       goto err;
 398     }
 399   }
 400   ret = 1;
 401
 402 err:
 403   if (ctx != NULL) {
 404     BN_CTX_end(ctx);
 405     if (ctx_passed == NULL) {
 406       BN_CTX_free(ctx);
 407     }
 408   }
 409   if (mont != NULL) {
 410     BN_MONT_CTX_free(mont);
 411   }
 412
 413   return ret;
 414 }
 415
 416 static int witness(BIGNUM *w, const BIGNUM *a, const BIGNUM *a1,
 417                    const BIGNUM *a1_odd, int k, BN_CTX *ctx,
 418                    BN_MONT_CTX *mont) {
 419   if (!BN_mod_exp_mont(w, w, a1_odd, a, ctx, mont)) { /* w := w^a1_odd mod a */
 420     return -1;
 421   }
 422   if (BN_is_one(w)) {
 423     return 0; /* probably prime */
 424   }
 425   if (BN_cmp(w, a1) == 0) {
 426     return 0; /* w == -1 (mod a),  'a' is probably prime */
 427   }
 428
 429   while (--k) {
 430     if (!BN_mod_mul(w, w, w, a, ctx)) { /* w := w^2 mod a */
 431       return -1;
 432     }
 433
 434     if (BN_is_one(w)) {
 435       return 1; /* 'a' is composite, otherwise a previous 'w' would
 436                  * have been == -1 (mod 'a') */
 437     }
 438
 439     if (BN_cmp(w, a1) == 0) {
 440       return 0; /* w == -1 (mod a), 'a' is probably prime */
 441     }
 442   }
 443
 444   /* If we get here, 'w' is the (a-1)/2-th power of the original 'w',
 445    * and it is neither -1 nor +1 -- so 'a' cannot be prime */
 446   return 1;
 447 }
 448
 449 static BN_ULONG get_word(const BIGNUM *bn) {
 450   if (bn->top == 1) {
 451     return bn->d[0];
 452   }
 453   return 0;
 454 }
 455
 456 static int probable_prime(BIGNUM *rnd, int bits) {
 457   int i;
 458   uint16_t mods[NUMPRIMES];
 459   BN_ULONG delta;
 460   BN_ULONG maxdelta = BN_MASK2 - primes[NUMPRIMES - 1];
 461   char is_single_word = bits <= BN_BITS2;
 462
 463 again:
 464   if (!BN_rand(rnd, bits, 1, 1)) {
 465     return 0;
 466   }
 467
 468   /* we now have a random number 'rnd' to test. */
 469   for (i = 1; i < NUMPRIMES; i++) {
 470     mods[i] = (uint16_t)BN_mod_word(rnd, (BN_ULONG)primes[i]);
 471   }
 472   /* If bits is so small that it fits into a single word then we
 473    * additionally don't want to exceed that many bits. */
 474   if (is_single_word) {
 475     BN_ULONG size_limit = (((BN_ULONG)1) << bits) - get_word(rnd) - 1;
 476     if (size_limit < maxdelta) {
 477       maxdelta = size_limit;
 478     }
 479   }
 480   delta = 0;
 481
 482 loop:
 483   if (is_single_word) {
 484     BN_ULONG rnd_word = get_word(rnd);
 485
 486     /* In the case that the candidate prime is a single word then
 487      * we check that:
 488      *   1) It's greater than primes[i] because we shouldn't reject
 489      *      3 as being a prime number because it's a multiple of
 490      *      three.
 491      *   2) That it's not a multiple of a known prime. We don't
 492      *      check that rnd-1 is also coprime to all the known
 493      *      primes because there aren't many small primes where
 494      *      that's true. */
 495     for (i = 1; i < NUMPRIMES && primes[i] < rnd_word; i++) {
 496       if ((mods[i] + delta) % primes[i] == 0) {
 497         delta += 2;
 498         if (delta > maxdelta)
 499           goto again;
 500         goto loop;
 501       }
 502     }
 503   } else {
 504     for (i = 1; i < NUMPRIMES; i++) {
 505       /* check that rnd is not a prime and also
 506        * that gcd(rnd-1,primes) == 1 (except for 2) */
 507       if (((mods[i] + delta) % primes[i]) <= 1) {
 508         delta += 2;
 509         if (delta > maxdelta)
 510           goto again;
 511         goto loop;
 512       }
 513     }
 514   }
 515
 516   if (!BN_add_word(rnd, delta)) {
 517     return 0;
 518   }
 519   if (BN_num_bits(rnd) != bits) {
 520     goto again;
 521   }
 522
 523   return 1;
 524 }
 525
 526 static int probable_prime_dh(BIGNUM *rnd, int bits, const BIGNUM *add,
 527                              const BIGNUM *rem, BN_CTX *ctx) {
 528   int i, ret = 0;
 529   BIGNUM *t1;
 530
 531   BN_CTX_start(ctx);
 532   if ((t1 = BN_CTX_get(ctx)) == NULL) {
 533     goto err;
 534   }
 535
 536   if (!BN_rand(rnd, bits, 0, 1)) {
 537     goto err;
 538   }
 539
 540   /* we need ((rnd-rem) % add) == 0 */
 541
 542   if (!BN_mod(t1, rnd, add, ctx)) {
 543     goto err;
 544   }
 545   if (!BN_sub(rnd, rnd, t1)) {
 546     goto err;
 547   }
 548   if (rem == NULL) {
 549     if (!BN_add_word(rnd, 1)) {
 550       goto err;
 551     }
 552   } else {
 553     if (!BN_add(rnd, rnd, rem)) {
 554       goto err;
 555     }
 556   }
 557   /* we now have a random number 'rand' to test. */
 558
 559 loop:
 560   for (i = 1; i < NUMPRIMES; i++) {
 561     /* check that rnd is a prime */
 562     if (BN_mod_word(rnd, (BN_ULONG)primes[i]) <= 1) {
 563       if (!BN_add(rnd, rnd, add)) {
 564         goto err;
 565       }
 566       goto loop;
 567     }
 568   }
 569
 570   ret = 1;
 571
 572 err:
 573   BN_CTX_end(ctx);
 574   return ret;
 575 }
 576
 577 static int probable_prime_dh_safe(BIGNUM *p, int bits, const BIGNUM *padd,
 578                                   const BIGNUM *rem, BN_CTX *ctx) {
 579   int i, ret = 0;
 580   BIGNUM *t1, *qadd, *q;
 581
 582   bits--;
 583   BN_CTX_start(ctx);
 584   t1 = BN_CTX_get(ctx);
 585   q = BN_CTX_get(ctx);
 586   qadd = BN_CTX_get(ctx);
 587   if (qadd == NULL) {
 588     goto err;
 589   }
 590
 591   if (!BN_rshift1(qadd, padd)) {
 592     goto err;
 593   }
 594
 595   if (!BN_rand(q, bits, 0, 1)) {
 596     goto err;
 597   }
 598
 599   /* we need ((rnd-rem) % add) == 0 */
 600   if (!BN_mod(t1, q, qadd, ctx)) {
 601     goto err;
 602   }
 603
 604   if (!BN_sub(q, q, t1)) {
 605     goto err;
 606   }
 607
 608   if (rem == NULL) {
 609     if (!BN_add_word(q, 1)) {
 610       goto err;
 611     }
 612   } else {
 613     if (!BN_rshift1(t1, rem)) {
 614       goto err;
 615     }
 616     if (!BN_add(q, q, t1)) {
 617       goto err;
 618     }
 619   }
 620
 621   /* we now have a random number 'rand' to test. */
 622   if (!BN_lshift1(p, q)) {
 623     goto err;
 624   }
 625   if (!BN_add_word(p, 1)) {
 626     goto err;
 627   }
 628
 629 loop:
 630   for (i = 1; i < NUMPRIMES; i++) {
 631     /* check that p and q are prime */
 632     /* check that for p and q
 633      * gcd(p-1,primes) == 1 (except for 2) */
 634     if ((BN_mod_word(p, (BN_ULONG)primes[i]) == 0) ||
 635         (BN_mod_word(q, (BN_ULONG)primes[i]) == 0)) {
 636       if (!BN_add(p, p, padd)) {
 637         goto err;
 638       }
 639       if (!BN_add(q, q, qadd)) {
 640         goto err;
 641       }
 642       goto loop;
 643     }
 644   }
 645
 646   ret = 1;
 647
 648 err:
 649   BN_CTX_end(ctx);
 650   return ret;
 651 }
 652
 653 static const uint16_t primes[NUMPRIMES] = {
 654     2,     3,     5,     7,     11,    13,    17,    19,    23,    29,    31,
 655     37,    41,    43,    47,    53,    59,    61,    67,    71,    73,    79,
 656     83,    89,    97,    101,   103,   107,   109,   113,   127,   131,   137,
 657     139,   149,   151,   157,   163,   167,   173,   179,   181,   191,   193,
 658     197,   199,   211,   223,   227,   229,   233,   239,   241,   251,   257,
 659     263,   269,   271,   277,   281,   283,   293,   307,   311,   313,   317,
 660     331,   337,   347,   349,   353,   359,   367,   373,   379,   383,   389,
 661     397,   401,   409,   419,   421,   431,   433,   439,   443,   449,   457,
 662     461,   463,   467,   479,   487,   491,   499,   503,   509,   521,   523,
 663     541,   547,   557,   563,   569,   571,   577,   587,   593,   599,   601,
 664     607,   613,   617,   619,   631,   641,   643,   647,   653,   659,   661,
 665     673,   677,   683,   691,   701,   709,   719,   727,   733,   739,   743,
 666     751,   757,   761,   769,   773,   787,   797,   809,   811,   821,   823,
 667     827,   829,   839,   853,   857,   859,   863,   877,   881,   883,   887,
 668     907,   911,   919,   929,   937,   941,   947,   953,   967,   971,   977,
 669     983,   991,   997,   1009,  1013,  1019,  1021,  1031,  1033,  1039,  1049,
 670     1051,  1061,  1063,  1069,  1087,  1091,  1093,  1097,  1103,  1109,  1117,
 671     1123,  1129,  1151,  1153,  1163,  1171,  1181,  1187,  1193,  1201,  1213,
 672     1217,  1223,  1229,  1231,  1237,  1249,  1259,  1277,  1279,  1283,  1289,
 673     1291,  1297,  1301,  1303,  1307,  1319,  1321,  1327,  1361,  1367,  1373,
 674     1381,  1399,  1409,  1423,  1427,  1429,  1433,  1439,  1447,  1451,  1453,
 675     1459,  1471,  1481,  1483,  1487,  1489,  1493,  1499,  1511,  1523,  1531,
 676     1543,  1549,  1553,  1559,  1567,  1571,  1579,  1583,  1597,  1601,  1607,
 677     1609,  1613,  1619,  1621,  1627,  1637,  1657,  1663,  1667,  1669,  1693,
 678     1697,  1699,  1709,  1721,  1723,  1733,  1741,  1747,  1753,  1759,  1777,
 679     1783,  1787,  1789,  1801,  1811,  1823,  1831,  1847,  1861,  1867,  1871,
 680     1873,  1877,  1879,  1889,  1901,  1907,  1913,  1931,  1933,  1949,  1951,
 681     1973,  1979,  1987,  1993,  1997,  1999,  2003,  2011,  2017,  2027,  2029,
 682     2039,  2053,  2063,  2069,  2081,  2083,  2087,  2089,  2099,  2111,  2113,
 683     2129,  2131,  2137,  2141,  2143,  2153,  2161,  2179,  2203,  2207,  2213,
 684     2221,  2237,  2239,  2243,  2251,  2267,  2269,  2273,  2281,  2287,  2293,
 685     2297,  2309,  2311,  2333,  2339,  2341,  2347,  2351,  2357,  2371,  2377,
 686     2381,  2383,  2389,  2393,  2399,  2411,  2417,  2423,  2437,  2441,  2447,
 687     2459,  2467,  2473,  2477,  2503,  2521,  2531,  2539,  2543,  2549,  2551,
 688     2557,  2579,  2591,  2593,  2609,  2617,  2621,  2633,  2647,  2657,  2659,
 689     2663,  2671,  2677,  2683,  2687,  2689,  2693,  2699,  2707,  2711,  2713,
 690     2719,  2729,  2731,  2741,  2749,  2753,  2767,  2777,  2789,  2791,  2797,
 691     2801,  2803,  2819,  2833,  2837,  2843,  2851,  2857,  2861,  2879,  2887,
 692     2897,  2903,  2909,  2917,  2927,  2939,  2953,  2957,  2963,  2969,  2971,
 693     2999,  3001,  3011,  3019,  3023,  3037,  3041,  3049,  3061,  3067,  3079,
 694     3083,  3089,  3109,  3119,  3121,  3137,  3163,  3167,  3169,  3181,  3187,
 695     3191,  3203,  3209,  3217,  3221,  3229,  3251,  3253,  3257,  3259,  3271,
 696     3299,  3301,  3307,  3313,  3319,  3323,  3329,  3331,  3343,  3347,  3359,
 697     3361,  3371,  3373,  3389,  3391,  3407,  3413,  3433,  3449,  3457,  3461,
 698     3463,  3467,  3469,  3491,  3499,  3511,  3517,  3527,  3529,  3533,  3539,
 699     3541,  3547,  3557,  3559,  3571,  3581,  3583,  3593,  3607,  3613,  3617,
 700     3623,  3631,  3637,  3643,  3659,  3671,  3673,  3677,  3691,  3697,  3701,
 701     3709,  3719,  3727,  3733,  3739,  3761,  3767,  3769,  3779,  3793,  3797,
 702     3803,  3821,  3823,  3833,  3847,  3851,  3853,  3863,  3877,  3881,  3889,
 703     3907,  3911,  3917,  3919,  3923,  3929,  3931,  3943,  3947,  3967,  3989,
 704     4001,  4003,  4007,  4013,  4019,  4021,  4027,  4049,  4051,  4057,  4073,
 705     4079,  4091,  4093,  4099,  4111,  4127,  4129,  4133,  4139,  4153,  4157,
 706     4159,  4177,  4201,  4211,  4217,  4219,  4229,  4231,  4241,  4243,  4253,
 707     4259,  4261,  4271,  4273,  4283,  4289,  4297,  4327,  4337,  4339,  4349,
 708     4357,  4363,  4373,  4391,  4397,  4409,  4421,  4423,  4441,  4447,  4451,
 709     4457,  4463,  4481,  4483,  4493,  4507,  4513,  4517,  4519,  4523,  4547,
 710     4549,  4561,  4567,  4583,  4591,  4597,  4603,  4621,  4637,  4639,  4643,
 711     4649,  4651,  4657,  4663,  4673,  4679,  4691,  4703,  4721,  4723,  4729,
 712     4733,  4751,  4759,  4783,  4787,  4789,  4793,  4799,  4801,  4813,  4817,
 713     4831,  4861,  4871,  4877,  4889,  4903,  4909,  4919,  4931,  4933,  4937,
 714     4943,  4951,  4957,  4967,  4969,  4973,  4987,  4993,  4999,  5003,  5009,
 715     5011,  5021,  5023,  5039,  5051,  5059,  5077,  5081,  5087,  5099,  5101,
 716     5107,  5113,  5119,  5147,  5153,  5167,  5171,  5179,  5189,  5197,  5209,
 717     5227,  5231,  5233,  5237,  5261,  5273,  5279,  5281,  5297,  5303,  5309,
 718     5323,  5333,  5347,  5351,  5381,  5387,  5393,  5399,  5407,  5413,  5417,
 719     5419,  5431,  5437,  5441,  5443,  5449,  5471,  5477,  5479,  5483,  5501,
 720     5503,  5507,  5519,  5521,  5527,  5531,  5557,  5563,  5569,  5573,  5581,
 721     5591,  5623,  5639,  5641,  5647,  5651,  5653,  5657,  5659,  5669,  5683,
 722     5689,  5693,  5701,  5711,  5717,  5737,  5741,  5743,  5749,  5779,  5783,
 723     5791,  5801,  5807,  5813,  5821,  5827,  5839,  5843,  5849,  5851,  5857,
 724     5861,  5867,  5869,  5879,  5881,  5897,  5903,  5923,  5927,  5939,  5953,
 725     5981,  5987,  6007,  6011,  6029,  6037,  6043,  6047,  6053,  6067,  6073,
 726     6079,  6089,  6091,  6101,  6113,  6121,  6131,  6133,  6143,  6151,  6163,
 727     6173,  6197,  6199,  6203,  6211,  6217,  6221,  6229,  6247,  6257,  6263,
 728     6269,  6271,  6277,  6287,  6299,  6301,  6311,  6317,  6323,  6329,  6337,
 729     6343,  6353,  6359,  6361,  6367,  6373,  6379,  6389,  6397,  6421,  6427,
 730     6449,  6451,  6469,  6473,  6481,  6491,  6521,  6529,  6547,  6551,  6553,
 731     6563,  6569,  6571,  6577,  6581,  6599,  6607,  6619,  6637,  6653,  6659,
 732     6661,  6673,  6679,  6689,  6691,  6701,  6703,  6709,  6719,  6733,  6737,
 733     6761,  6763,  6779,  6781,  6791,  6793,  6803,  6823,  6827,  6829,  6833,
 734     6841,  6857,  6863,  6869,  6871,  6883,  6899,  6907,  6911,  6917,  6947,
 735     6949,  6959,  6961,  6967,  6971,  6977,  6983,  6991,  6997,  7001,  7013,
 736     7019,  7027,  7039,  7043,  7057,  7069,  7079,  7103,  7109,  7121,  7127,
 737     7129,  7151,  7159,  7177,  7187,  7193,  7207,  7211,  7213,  7219,  7229,
 738     7237,  7243,  7247,  7253,  7283,  7297,  7307,  7309,  7321,  7331,  7333,
 739     7349,  7351,  7369,  7393,  7411,  7417,  7433,  7451,  7457,  7459,  7477,
 740     7481,  7487,  7489,  7499,  7507,  7517,  7523,  7529,  7537,  7541,  7547,
 741     7549,  7559,  7561,  7573,  7577,  7583,  7589,  7591,  7603,  7607,  7621,
 742     7639,  7643,  7649,  7669,  7673,  7681,  7687,  7691,  7699,  7703,  7717,
 743     7723,  7727,  7741,  7753,  7757,  7759,  7789,  7793,  7817,  7823,  7829,
 744     7841,  7853,  7867,  7873,  7877,  7879,  7883,  7901,  7907,  7919,  7927,
 745     7933,  7937,  7949,  7951,  7963,  7993,  8009,  8011,  8017,  8039,  8053,
 746     8059,  8069,  8081,  8087,  8089,  8093,  8101,  8111,  8117,  8123,  8147,
 747     8161,  8167,  8171,  8179,  8191,  8209,  8219,  8221,  8231,  8233,  8237,
 748     8243,  8263,  8269,  8273,  8287,  8291,  8293,  8297,  8311,  8317,  8329,
 749     8353,  8363,  8369,  8377,  8387,  8389,  8419,  8423,  8429,  8431,  8443,
 750     8447,  8461,  8467,  8501,  8513,  8521,  8527,  8537,  8539,  8543,  8563,
 751     8573,  8581,  8597,  8599,  8609,  8623,  8627,  8629,  8641,  8647,  8663,
 752     8669,  8677,  8681,  8689,  8693,  8699,  8707,  8713,  8719,  8731,  8737,
 753     8741,  8747,  8753,  8761,  8779,  8783,  8803,  8807,  8819,  8821,  8831,
 754     8837,  8839,  8849,  8861,  8863,  8867,  8887,  8893,  8923,  8929,  8933,
 755     8941,  8951,  8963,  8969,  8971,  8999,  9001,  9007,  9011,  9013,  9029,
 756     9041,  9043,  9049,  9059,  9067,  9091,  9103,  9109,  9127,  9133,  9137,
 757     9151,  9157,  9161,  9173,  9181,  9187,  9199,  9203,  9209,  9221,  9227,
 758     9239,  9241,  9257,  9277,  9281,  9283,  9293,  9311,  9319,  9323,  9337,
 759     9341,  9343,  9349,  9371,  9377,  9391,  9397,  9403,  9413,  9419,  9421,
 760     9431,  9433,  9437,  9439,  9461,  9463,  9467,  9473,  9479,  9491,  9497,
 761     9511,  9521,  9533,  9539,  9547,  9551,  9587,  9601,  9613,  9619,  9623,
 762     9629,  9631,  9643,  9649,  9661,  9677,  9679,  9689,  9697,  9719,  9721,
 763     9733,  9739,  9743,  9749,  9767,  9769,  9781,  9787,  9791,  9803,  9811,
 764     9817,  9829,  9833,  9839,  9851,  9857,  9859,  9871,  9883,  9887,  9901,
 765     9907,  9923,  9929,  9931,  9941,  9949,  9967,  9973,  10007, 10009, 10037,
 766     10039, 10061, 10067, 10069, 10079, 10091, 10093, 10099, 10103, 10111, 10133,
 767     10139, 10141, 10151, 10159, 10163, 10169, 10177, 10181, 10193, 10211, 10223,
 768     10243, 10247, 10253, 10259, 10267, 10271, 10273, 10289, 10301, 10303, 10313,
 769     10321, 10331, 10333, 10337, 10343, 10357, 10369, 10391, 10399, 10427, 10429,
 770     10433, 10453, 10457, 10459, 10463, 10477, 10487, 10499, 10501, 10513, 10529,
 771     10531, 10559, 10567, 10589, 10597, 10601, 10607, 10613, 10627, 10631, 10639,
 772     10651, 10657, 10663, 10667, 10687, 10691, 10709, 10711, 10723, 10729, 10733,
 773     10739, 10753, 10771, 10781, 10789, 10799, 10831, 10837, 10847, 10853, 10859,
 774     10861, 10867, 10883, 10889, 10891, 10903, 10909, 10937, 10939, 10949, 10957,
 775     10973, 10979, 10987, 10993, 11003, 11027, 11047, 11057, 11059, 11069, 11071,
 776     11083, 11087, 11093, 11113, 11117, 11119, 11131, 11149, 11159, 11161, 11171,
 777     11173, 11177, 11197, 11213, 11239, 11243, 11251, 11257, 11261, 11273, 11279,
 778     11287, 11299, 11311, 11317, 11321, 11329, 11351, 11353, 11369, 11383, 11393,
 779     11399, 11411, 11423, 11437, 11443, 11447, 11467, 11471, 11483, 11489, 11491,
 780     11497, 11503, 11519, 11527, 11549, 11551, 11579, 11587, 11593, 11597, 11617,
 781     11621, 11633, 11657, 11677, 11681, 11689, 11699, 11701, 11717, 11719, 11731,
 782     11743, 11777, 11779, 11783, 11789, 11801, 11807, 11813, 11821, 11827, 11831,
 783     11833, 11839, 11863, 11867, 11887, 11897, 11903, 11909, 11923, 11927, 11933,
 784     11939, 11941, 11953, 11959, 11969, 11971, 11981, 11987, 12007, 12011, 12037,
 785     12041, 12043, 12049, 12071, 12073, 12097, 12101, 12107, 12109, 12113, 12119,
 786     12143, 12149, 12157, 12161, 12163, 12197, 12203, 12211, 12227, 12239, 12241,
 787     12251, 12253, 12263, 12269, 12277, 12281, 12289, 12301, 12323, 12329, 12343,
 788     12347, 12373, 12377, 12379, 12391, 12401, 12409, 12413, 12421, 12433, 12437,
 789     12451, 12457, 12473, 12479, 12487, 12491, 12497, 12503, 12511, 12517, 12527,
 790     12539, 12541, 12547, 12553, 12569, 12577, 12583, 12589, 12601, 12611, 12613,
 791     12619, 12637, 12641, 12647, 12653, 12659, 12671, 12689, 12697, 12703, 12713,
 792     12721, 12739, 12743, 12757, 12763, 12781, 12791, 12799, 12809, 12821, 12823,
 793     12829, 12841, 12853, 12889, 12893, 12899, 12907, 12911, 12917, 12919, 12923,
 794     12941, 12953, 12959, 12967, 12973, 12979, 12983, 13001, 13003, 13007, 13009,
 795     13033, 13037, 13043, 13049, 13063, 13093, 13099, 13103, 13109, 13121, 13127,
 796     13147, 13151, 13159, 13163, 13171, 13177, 13183, 13187, 13217, 13219, 13229,
 797     13241, 13249, 13259, 13267, 13291, 13297, 13309, 13313, 13327, 13331, 13337,
 798     13339, 13367, 13381, 13397, 13399, 13411, 13417, 13421, 13441, 13451, 13457,
 799     13463, 13469, 13477, 13487, 13499, 13513, 13523, 13537, 13553, 13567, 13577,
 800     13591, 13597, 13613, 13619, 13627, 13633, 13649, 13669, 13679, 13681, 13687,
 801     13691, 13693, 13697, 13709, 13711, 13721, 13723, 13729, 13751, 13757, 13759,
 802     13763, 13781, 13789, 13799, 13807, 13829, 13831, 13841, 13859, 13873, 13877,
 803     13879, 13883, 13901, 13903, 13907, 13913, 13921, 13931, 13933, 13963, 13967,
 804     13997, 13999, 14009, 14011, 14029, 14033, 14051, 14057, 14071, 14081, 14083,
 805     14087, 14107, 14143, 14149, 14153, 14159, 14173, 14177, 14197, 14207, 14221,
 806     14243, 14249, 14251, 14281, 14293, 14303, 14321, 14323, 14327, 14341, 14347,
 807     14369, 14387, 14389, 14401, 14407, 14411, 14419, 14423, 14431, 14437, 14447,
 808     14449, 14461, 14479, 14489, 14503, 14519, 14533, 14537, 14543, 14549, 14551,
 809     14557, 14561, 14563, 14591, 14593, 14621, 14627, 14629, 14633, 14639, 14653,
 810     14657, 14669, 14683, 14699, 14713, 14717, 14723, 14731, 14737, 14741, 14747,
 811     14753, 14759, 14767, 14771, 14779, 14783, 14797, 14813, 14821, 14827, 14831,
 812     14843, 14851, 14867, 14869, 14879, 14887, 14891, 14897, 14923, 14929, 14939,
 813     14947, 14951, 14957, 14969, 14983, 15013, 15017, 15031, 15053, 15061, 15073,
 814     15077, 15083, 15091, 15101, 15107, 15121, 15131, 15137, 15139, 15149, 15161,
 815     15173, 15187, 15193, 15199, 15217, 15227, 15233, 15241, 15259, 15263, 15269,
 816     15271, 15277, 15287, 15289, 15299, 15307, 15313, 15319, 15329, 15331, 15349,
 817     15359, 15361, 15373, 15377, 15383, 15391, 15401, 15413, 15427, 15439, 15443,
 818     15451, 15461, 15467, 15473, 15493, 15497, 15511, 15527, 15541, 15551, 15559,
 819     15569, 15581, 15583, 15601, 15607, 15619, 15629, 15641, 15643, 15647, 15649,
 820     15661, 15667, 15671, 15679, 15683, 15727, 15731, 15733, 15737, 15739, 15749,
 821     15761, 15767, 15773, 15787, 15791, 15797, 15803, 15809, 15817, 15823, 15859,
 822     15877, 15881, 15887, 15889, 15901, 15907, 15913, 15919, 15923, 15937, 15959,
 823     15971, 15973, 15991, 16001, 16007, 16033, 16057, 16061, 16063, 16067, 16069,
 824     16073, 16087, 16091, 16097, 16103, 16111, 16127, 16139, 16141, 16183, 16187,
 825     16189, 16193, 16217, 16223, 16229, 16231, 16249, 16253, 16267, 16273, 16301,
 826     16319, 16333, 16339, 16349, 16361, 16363, 16369, 16381, 16411, 16417, 16421,
 827     16427, 16433, 16447, 16451, 16453, 16477, 16481, 16487, 16493, 16519, 16529,
 828     16547, 16553, 16561, 16567, 16573, 16603, 16607, 16619, 16631, 16633, 16649,
 829     16651, 16657, 16661, 16673, 16691, 16693, 16699, 16703, 16729, 16741, 16747,
 830     16759, 16763, 16787, 16811, 16823, 16829, 16831, 16843, 16871, 16879, 16883,
 831     16889, 16901, 16903, 16921, 16927, 16931, 16937, 16943, 16963, 16979, 16981,
 832     16987, 16993, 17011, 17021, 17027, 17029, 17033, 17041, 17047, 17053, 17077,
 833     17093, 17099, 17107, 17117, 17123, 17137, 17159, 17167, 17183, 17189, 17191,
 834     17203, 17207, 17209, 17231, 17239, 17257, 17291, 17293, 17299, 17317, 17321,
 835     17327, 17333, 17341, 17351, 17359, 17377, 17383, 17387, 17389, 17393, 17401,
 836     17417, 17419, 17431, 17443, 17449, 17467, 17471, 17477, 17483, 17489, 17491,
 837     17497, 17509, 17519, 17539, 17551, 17569, 17573, 17579, 17581, 17597, 17599,
 838     17609, 17623, 17627, 17657, 17659, 17669, 17681, 17683, 17707, 17713, 17729,
 839     17737, 17747, 17749, 17761, 17783, 17789, 17791, 17807, 17827, 17837, 17839,
 840     17851, 17863, };