crypto/bn/bn_prime.c

   1 /*
   2  * WARNING: do not edit!
   3  * Generated by crypto/bn/bn_prime.pl
   4  * Copyright 1995-2016 The OpenSSL Project Authors. All Rights Reserved.
   5  *
   6  * Licensed under the OpenSSL license (the "License").  You may not use
   7  * this file except in compliance with the License.  You can obtain a copy
   8  * in the file LICENSE in the source distribution or at
   9  * https://www.openssl.org/source/license.html
  10  */
  11
  12 #include <stdio.h>
  13 #include <time.h>
  14 #include "internal/cryptlib.h"
  15 #include "bn_lcl.h"
  16
  17 /*
  18  * The quick sieve algorithm approach to weeding out primes is Philip
  19  * Zimmermann's, as implemented in PGP.  I have had a read of his comments
  20  * and implemented my own version.
  21  */
  22 #include "bn_prime.h"
  23
  24 static int witness(BIGNUM *w, const BIGNUM *a, const BIGNUM *a1,
  25                    const BIGNUM *a1_odd, int k, BN_CTX *ctx,
  26                    BN_MONT_CTX *mont);
  27 static int probable_prime(BIGNUM *rnd, int bits, prime_t *mods);
  28 static int probable_prime_dh_safe(BIGNUM *rnd, int bits,
  29                                   const BIGNUM *add, const BIGNUM *rem,
  30                                   BN_CTX *ctx);
  31
  32 int BN_GENCB_call(BN_GENCB *cb, int a, int b)
  33 {
  34     /* No callback means continue */
  35     if (!cb)
  36         return 1;
  37     switch (cb->ver) {
  38     case 1:
  39         /* Deprecated-style callbacks */
  40         if (!cb->cb.cb_1)
  41             return 1;
  42         cb->cb.cb_1(a, b, cb->arg);
  43         return 1;
  44     case 2:
  45         /* New-style callbacks */
  46         return cb->cb.cb_2(a, b, cb);
  47     default:
  48         break;
  49     }
  50     /* Unrecognised callback type */
  51     return 0;
  52 }
  53
  54 int BN_generate_prime_ex(BIGNUM *ret, int bits, int safe,
  55                          const BIGNUM *add, const BIGNUM *rem, BN_GENCB *cb)
  56 {
  57     BIGNUM *t;
  58     int found = 0;
  59     int i, j, c1 = 0;
  60     BN_CTX *ctx = NULL;
  61     prime_t *mods = NULL;
  62     int checks = BN_prime_checks_for_size(bits);
  63
  64     if (bits < 2) {
  65         /* There are no prime numbers this small. */
  66         BNerr(BN_F_BN_GENERATE_PRIME_EX, BN_R_BITS_TOO_SMALL);
  67         return 0;
  68     } else if (bits == 2 && safe) {
  69         /* The smallest safe prime (7) is three bits. */
  70         BNerr(BN_F_BN_GENERATE_PRIME_EX, BN_R_BITS_TOO_SMALL);
  71         return 0;
  72     }
  73
  74     mods = OPENSSL_zalloc(sizeof(*mods) * NUMPRIMES);
  75     if (mods == NULL)
  76         goto err;
  77
  78     ctx = BN_CTX_new();
  79     if (ctx == NULL)
  80         goto err;
  81     BN_CTX_start(ctx);
  82     t = BN_CTX_get(ctx);
  83     if (!t)
  84         goto err;
  85  loop:
  86     /* make a random number and set the top and bottom bits */
  87     if (add == NULL) {
  88         if (!probable_prime(ret, bits, mods))
  89             goto err;
  90     } else {
  91         if (safe) {
  92             if (!probable_prime_dh_safe(ret, bits, add, rem, ctx))
  93                 goto err;
  94         } else {
  95             if (!bn_probable_prime_dh(ret, bits, add, rem, ctx))
  96                 goto err;
  97         }
  98     }
  99
 100     if (!BN_GENCB_call(cb, 0, c1++))
 101         /* aborted */
 102         goto err;
 103
 104     if (!safe) {
 105         i = BN_is_prime_fasttest_ex(ret, checks, ctx, 0, cb);
 106         if (i == -1)
 107             goto err;
 108         if (i == 0)
 109             goto loop;
 110     } else {
 111         /*
 112          * for "safe prime" generation, check that (p-1)/2 is prime. Since a
 113          * prime is odd, We just need to divide by 2
 114          */
 115         if (!BN_rshift1(t, ret))
 116             goto err;
 117
 118         for (i = 0; i < checks; i++) {
 119             j = BN_is_prime_fasttest_ex(ret, 1, ctx, 0, cb);
 120             if (j == -1)
 121                 goto err;
 122             if (j == 0)
 123                 goto loop;
 124
 125             j = BN_is_prime_fasttest_ex(t, 1, ctx, 0, cb);
 126             if (j == -1)
 127                 goto err;
 128             if (j == 0)
 129                 goto loop;
 130
 131             if (!BN_GENCB_call(cb, 2, c1 - 1))
 132                 goto err;
 133             /* We have a safe prime test pass */
 134         }
 135     }
 136     /* we have a prime :-) */
 137     found = 1;
 138  err:
 139     OPENSSL_free(mods);
 140     if (ctx != NULL)
 141         BN_CTX_end(ctx);
 142     BN_CTX_free(ctx);
 143     bn_check_top(ret);
 144     return found;
 145 }
 146
 147 int BN_is_prime_ex(const BIGNUM *a, int checks, BN_CTX *ctx_passed,
 148                    BN_GENCB *cb)
 149 {
 150     return BN_is_prime_fasttest_ex(a, checks, ctx_passed, 0, cb);
 151 }
 152
 153 int BN_is_prime_fasttest_ex(const BIGNUM *a, int checks, BN_CTX *ctx_passed,
 154                             int do_trial_division, BN_GENCB *cb)
 155 {
 156     int i, j, ret = -1;
 157     int k;
 158     BN_CTX *ctx = NULL;
 159     BIGNUM *A1, *A1_odd, *check; /* taken from ctx */
 160     BN_MONT_CTX *mont = NULL;
 161     const BIGNUM *A = NULL;
 162
 163     if (BN_cmp(a, BN_value_one()) <= 0)
 164         return 0;
 165
 166     if (checks == BN_prime_checks)
 167         checks = BN_prime_checks_for_size(BN_num_bits(a));
 168
 169     /* first look for small factors */
 170     if (!BN_is_odd(a))
 171         /* a is even => a is prime if and only if a == 2 */
 172         return BN_is_word(a, 2);
 173     if (do_trial_division) {
 174         for (i = 1; i < NUMPRIMES; i++) {
 175             BN_ULONG mod = BN_mod_word(a, primes[i]);
 176             if (mod == (BN_ULONG)-1)
 177                 goto err;
 178             if (mod == 0)
 179                 return BN_is_word(a, primes[i]);
 180         }
 181         if (!BN_GENCB_call(cb, 1, -1))
 182             goto err;
 183     }
 184
 185     if (ctx_passed != NULL)
 186         ctx = ctx_passed;
 187     else if ((ctx = BN_CTX_new()) == NULL)
 188         goto err;
 189     BN_CTX_start(ctx);
 190
 191     /* A := abs(a) */
 192     if (a->neg) {
 193         BIGNUM *t;
 194         if ((t = BN_CTX_get(ctx)) == NULL)
 195             goto err;
 196         if (BN_copy(t, a) == NULL)
 197             goto err;
 198         t->neg = 0;
 199         A = t;
 200     } else
 201         A = a;
 202     A1 = BN_CTX_get(ctx);
 203     A1_odd = BN_CTX_get(ctx);
 204     check = BN_CTX_get(ctx);
 205     if (check == NULL)
 206         goto err;
 207
 208     /* compute A1 := A - 1 */
 209     if (!BN_copy(A1, A))
 210         goto err;
 211     if (!BN_sub_word(A1, 1))
 212         goto err;
 213     if (BN_is_zero(A1)) {
 214         ret = 0;
 215         goto err;
 216     }
 217
 218     /* write  A1  as  A1_odd * 2^k */
 219     k = 1;
 220     while (!BN_is_bit_set(A1, k))
 221         k++;
 222     if (!BN_rshift(A1_odd, A1, k))
 223         goto err;
 224
 225     /* Montgomery setup for computations mod A */
 226     mont = BN_MONT_CTX_new();
 227     if (mont == NULL)
 228         goto err;
 229     if (!BN_MONT_CTX_set(mont, A, ctx))
 230         goto err;
 231
 232     for (i = 0; i < checks; i++) {
 233         if (!BN_pseudo_rand_range(check, A1))
 234             goto err;
 235         if (!BN_add_word(check, 1))
 236             goto err;
 237         /* now 1 <= check < A */
 238
 239         j = witness(check, A, A1, A1_odd, k, ctx, mont);
 240         if (j == -1)
 241             goto err;
 242         if (j) {
 243             ret = 0;
 244             goto err;
 245         }
 246         if (!BN_GENCB_call(cb, 1, i))
 247             goto err;
 248     }
 249     ret = 1;
 250  err:
 251     if (ctx != NULL) {
 252         BN_CTX_end(ctx);
 253         if (ctx_passed == NULL)
 254             BN_CTX_free(ctx);
 255     }
 256     BN_MONT_CTX_free(mont);
 257
 258     return (ret);
 259 }
 260
 261 static int witness(BIGNUM *w, const BIGNUM *a, const BIGNUM *a1,
 262                    const BIGNUM *a1_odd, int k, BN_CTX *ctx,
 263                    BN_MONT_CTX *mont)
 264 {
 265     if (!BN_mod_exp_mont(w, w, a1_odd, a, ctx, mont)) /* w := w^a1_odd mod a */
 266         return -1;
 267     if (BN_is_one(w))
 268         return 0;               /* probably prime */
 269     if (BN_cmp(w, a1) == 0)
 270         return 0;               /* w == -1 (mod a), 'a' is probably prime */
 271     while (--k) {
 272         if (!BN_mod_mul(w, w, w, a, ctx)) /* w := w^2 mod a */
 273             return -1;
 274         if (BN_is_one(w))
 275             return 1;           /* 'a' is composite, otherwise a previous 'w'
 276                                  * would have been == -1 (mod 'a') */
 277         if (BN_cmp(w, a1) == 0)
 278             return 0;           /* w == -1 (mod a), 'a' is probably prime */
 279     }
 280     /*
 281      * If we get here, 'w' is the (a-1)/2-th power of the original 'w', and
 282      * it is neither -1 nor +1 -- so 'a' cannot be prime
 283      */
 284     bn_check_top(w);
 285     return 1;
 286 }
 287
 288 static int probable_prime(BIGNUM *rnd, int bits, prime_t *mods)
 289 {
 290     int i;
 291     BN_ULONG delta;
 292     BN_ULONG maxdelta = BN_MASK2 - primes[NUMPRIMES - 1];
 293     char is_single_word = bits <= BN_BITS2;
 294
 295  again:
 296     if (!BN_rand(rnd, bits, BN_RAND_TOP_TWO, BN_RAND_BOTTOM_ODD))
 297         return (0);
 298     /* we now have a random number 'rnd' to test. */
 299     for (i = 1; i < NUMPRIMES; i++) {
 300         BN_ULONG mod = BN_mod_word(rnd, (BN_ULONG)primes[i]);
 301         if (mod == (BN_ULONG)-1)
 302             return 0;
 303         mods[i] = (prime_t) mod;
 304     }
 305     /*
 306      * If bits is so small that it fits into a single word then we
 307      * additionally don't want to exceed that many bits.
 308      */
 309     if (is_single_word) {
 310         BN_ULONG size_limit;
 311
 312         if (bits == BN_BITS2) {
 313             /*
 314              * Shifting by this much has undefined behaviour so we do it a
 315              * different way
 316              */
 317             size_limit = ~((BN_ULONG)0) - BN_get_word(rnd);
 318         } else {
 319             size_limit = (((BN_ULONG)1) << bits) - BN_get_word(rnd) - 1;
 320         }
 321         if (size_limit < maxdelta)
 322             maxdelta = size_limit;
 323     }
 324     delta = 0;
 325  loop:
 326     if (is_single_word) {
 327         BN_ULONG rnd_word = BN_get_word(rnd);
 328
 329         /*-
 330          * In the case that the candidate prime is a single word then
 331          * we check that:
 332          *   1) It's greater than primes[i] because we shouldn't reject
 333          *      3 as being a prime number because it's a multiple of
 334          *      three.
 335          *   2) That it's not a multiple of a known prime. We don't
 336          *      check that rnd-1 is also coprime to all the known
 337          *      primes because there aren't many small primes where
 338          *      that's true.
 339          */
 340         for (i = 1; i < NUMPRIMES && primes[i] < rnd_word; i++) {
 341             if ((mods[i] + delta) % primes[i] == 0) {
 342                 delta += 2;
 343                 if (delta > maxdelta)
 344                     goto again;
 345                 goto loop;
 346             }
 347         }
 348     } else {
 349         for (i = 1; i < NUMPRIMES; i++) {
 350             /*
 351              * check that rnd is not a prime and also that gcd(rnd-1,primes)
 352              * == 1 (except for 2)
 353              */
 354             if (((mods[i] + delta) % primes[i]) <= 1) {
 355                 delta += 2;
 356                 if (delta > maxdelta)
 357                     goto again;
 358                 goto loop;
 359             }
 360         }
 361     }
 362     if (!BN_add_word(rnd, delta))
 363         return (0);
 364     if (BN_num_bits(rnd) != bits)
 365         goto again;
 366     bn_check_top(rnd);
 367     return (1);
 368 }
 369
 370 int bn_probable_prime_dh(BIGNUM *rnd, int bits,
 371                          const BIGNUM *add, const BIGNUM *rem, BN_CTX *ctx)
 372 {
 373     int i, ret = 0;
 374     BIGNUM *t1;
 375
 376     BN_CTX_start(ctx);
 377     if ((t1 = BN_CTX_get(ctx)) == NULL)
 378         goto err;
 379
 380     if (!BN_rand(rnd, bits, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ODD))
 381         goto err;
 382
 383     /* we need ((rnd-rem) % add) == 0 */
 384
 385     if (!BN_mod(t1, rnd, add, ctx))
 386         goto err;
 387     if (!BN_sub(rnd, rnd, t1))
 388         goto err;
 389     if (rem == NULL) {
 390         if (!BN_add_word(rnd, 1))
 391             goto err;
 392     } else {
 393         if (!BN_add(rnd, rnd, rem))
 394             goto err;
 395     }
 396
 397     /* we now have a random number 'rand' to test. */
 398
 399  loop:
 400     for (i = 1; i < NUMPRIMES; i++) {
 401         /* check that rnd is a prime */
 402         BN_ULONG mod = BN_mod_word(rnd, (BN_ULONG)primes[i]);
 403         if (mod == (BN_ULONG)-1)
 404             goto err;
 405         if (mod <= 1) {
 406             if (!BN_add(rnd, rnd, add))
 407                 goto err;
 408             goto loop;
 409         }
 410     }
 411     ret = 1;
 412
 413  err:
 414     BN_CTX_end(ctx);
 415     bn_check_top(rnd);
 416     return (ret);
 417 }
 418
 419 static int probable_prime_dh_safe(BIGNUM *p, int bits, const BIGNUM *padd,
 420                                   const BIGNUM *rem, BN_CTX *ctx)
 421 {
 422     int i, ret = 0;
 423     BIGNUM *t1, *qadd, *q;
 424
 425     bits--;
 426     BN_CTX_start(ctx);
 427     t1 = BN_CTX_get(ctx);
 428     q = BN_CTX_get(ctx);
 429     qadd = BN_CTX_get(ctx);
 430     if (qadd == NULL)
 431         goto err;
 432
 433     if (!BN_rshift1(qadd, padd))
 434         goto err;
 435
 436     if (!BN_rand(q, bits, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ODD))
 437         goto err;
 438
 439     /* we need ((rnd-rem) % add) == 0 */
 440     if (!BN_mod(t1, q, qadd, ctx))
 441         goto err;
 442     if (!BN_sub(q, q, t1))
 443         goto err;
 444     if (rem == NULL) {
 445         if (!BN_add_word(q, 1))
 446             goto err;
 447     } else {
 448         if (!BN_rshift1(t1, rem))
 449             goto err;
 450         if (!BN_add(q, q, t1))
 451             goto err;
 452     }
 453
 454     /* we now have a random number 'rand' to test. */
 455     if (!BN_lshift1(p, q))
 456         goto err;
 457     if (!BN_add_word(p, 1))
 458         goto err;
 459
 460  loop:
 461     for (i = 1; i < NUMPRIMES; i++) {
 462         /* check that p and q are prime */
 463         /*
 464          * check that for p and q gcd(p-1,primes) == 1 (except for 2)
 465          */
 466         BN_ULONG pmod = BN_mod_word(p, (BN_ULONG)primes[i]);
 467         BN_ULONG qmod = BN_mod_word(q, (BN_ULONG)primes[i]);
 468         if (pmod == (BN_ULONG)-1 || qmod == (BN_ULONG)-1)
 469             goto err;
 470         if (pmod == 0 || qmod == 0) {
 471             if (!BN_add(p, p, padd))
 472                 goto err;
 473             if (!BN_add(q, q, qadd))
 474                 goto err;
 475             goto loop;
 476         }
 477     }
 478     ret = 1;
 479
 480  err:
 481     BN_CTX_end(ctx);
 482     bn_check_top(p);
 483     return (ret);
 484 }