Add BN_check_prime()
[openssl.git] / crypto / bn / bn_prime.c
1 /*
2  * Copyright 1995-2019 The OpenSSL Project Authors. All Rights Reserved.
3  *
4  * Licensed under the Apache License 2.0 (the "License").  You may not use
5  * this file except in compliance with the License.  You can obtain a copy
6  * in the file LICENSE in the source distribution or at
7  * https://www.openssl.org/source/license.html
8  */
9
10 #include <stdio.h>
11 #include <time.h>
12 #include "internal/cryptlib.h"
13 #include "bn_local.h"
14
15 /*
16  * The quick sieve algorithm approach to weeding out primes is Philip
17  * Zimmermann's, as implemented in PGP.  I have had a read of his comments
18  * and implemented my own version.
19  */
20 #include "bn_prime.h"
21
22 static int probable_prime(BIGNUM *rnd, int bits, int safe, prime_t *mods,
23                           BN_CTX *ctx);
24 static int probable_prime_dh(BIGNUM *rnd, int bits, int safe, prime_t *mods,
25                              const BIGNUM *add, const BIGNUM *rem,
26                              BN_CTX *ctx);
27 static int bn_is_prime_int(const BIGNUM *w, int checks, BN_CTX *ctx,
28                            int do_trial_division, BN_GENCB *cb);
29
30 #define square(x) ((BN_ULONG)(x) * (BN_ULONG)(x))
31
32 #if BN_BITS2 == 64
33 # define BN_DEF(lo, hi) (BN_ULONG)hi<<32|lo
34 #else
35 # define BN_DEF(lo, hi) lo, hi
36 #endif
37
38 /*
39  * See SP800 89 5.3.3 (Step f)
40  * The product of the set of primes ranging from 3 to 751
41  * Generated using process in test/bn_internal_test.c test_bn_small_factors().
42  * This includes 751 (which is not currently included in SP 800-89).
43  */
44 static const BN_ULONG small_prime_factors[] = {
45     BN_DEF(0x3ef4e3e1, 0xc4309333), BN_DEF(0xcd2d655f, 0x71161eb6),
46     BN_DEF(0x0bf94862, 0x95e2238c), BN_DEF(0x24f7912b, 0x3eb233d3),
47     BN_DEF(0xbf26c483, 0x6b55514b), BN_DEF(0x5a144871, 0x0a84d817),
48     BN_DEF(0x9b82210a, 0x77d12fee), BN_DEF(0x97f050b3, 0xdb5b93c2),
49     BN_DEF(0x4d6c026b, 0x4acad6b9), BN_DEF(0x54aec893, 0xeb7751f3),
50     BN_DEF(0x36bc85c4, 0xdba53368), BN_DEF(0x7f5ec78e, 0xd85a1b28),
51     BN_DEF(0x6b322244, 0x2eb072d8), BN_DEF(0x5e2b3aea, 0xbba51112),
52     BN_DEF(0x0e2486bf, 0x36ed1a6c), BN_DEF(0xec0c5727, 0x5f270460),
53     (BN_ULONG)0x000017b1
54 };
55
56 #define BN_SMALL_PRIME_FACTORS_TOP OSSL_NELEM(small_prime_factors)
57 static const BIGNUM _bignum_small_prime_factors = {
58     (BN_ULONG *)small_prime_factors,
59     BN_SMALL_PRIME_FACTORS_TOP,
60     BN_SMALL_PRIME_FACTORS_TOP,
61     0,
62     BN_FLG_STATIC_DATA
63 };
64
65 const BIGNUM *bn_get0_small_factors(void)
66 {
67     return &_bignum_small_prime_factors;
68 }
69
70 /*
71  * Calculate the number of trial divisions that gives the best speed in
72  * combination with Miller-Rabin prime test, based on the sized of the prime.
73  */
74 static int calc_trial_divisions(int bits)
75 {
76     if (bits <= 512)
77         return 64;
78     else if (bits <= 1024)
79         return 128;
80     else if (bits <= 2048)
81         return 384;
82     else if (bits <= 4096)
83         return 1024;
84     return NUMPRIMES;
85 }
86
87 /*
88  * Use a minimum of 64 rounds of Miller-Rabin, which should give a false
89  * positive rate of 2^-128. If the size of the prime is larger than 2048
90  * the user probably wants a higher security level than 128, so switch
91  * to 128 rounds giving a false positive rate of 2^-256.
92  * Returns the number of rounds.
93  */
94 static int bn_mr_min_checks(int bits)
95 {
96     if (bits > 2048)
97         return 128;
98     return 64;
99 }
100
101 int BN_GENCB_call(BN_GENCB *cb, int a, int b)
102 {
103     /* No callback means continue */
104     if (!cb)
105         return 1;
106     switch (cb->ver) {
107     case 1:
108         /* Deprecated-style callbacks */
109         if (!cb->cb.cb_1)
110             return 1;
111         cb->cb.cb_1(a, b, cb->arg);
112         return 1;
113     case 2:
114         /* New-style callbacks */
115         return cb->cb.cb_2(a, b, cb);
116     default:
117         break;
118     }
119     /* Unrecognised callback type */
120     return 0;
121 }
122
123 int BN_generate_prime_ex2(BIGNUM *ret, int bits, int safe,
124                           const BIGNUM *add, const BIGNUM *rem, BN_GENCB *cb,
125                           BN_CTX *ctx)
126 {
127     BIGNUM *t;
128     int found = 0;
129     int i, j, c1 = 0;
130     prime_t *mods = NULL;
131     int checks = bn_mr_min_checks(bits);
132
133     if (bits < 2) {
134         /* There are no prime numbers this small. */
135         BNerr(BN_F_BN_GENERATE_PRIME_EX2, BN_R_BITS_TOO_SMALL);
136         return 0;
137     } else if (add == NULL && safe && bits < 6 && bits != 3) {
138         /*
139          * The smallest safe prime (7) is three bits.
140          * But the following two safe primes with less than 6 bits (11, 23)
141          * are unreachable for BN_rand with BN_RAND_TOP_TWO.
142          */
143         BNerr(BN_F_BN_GENERATE_PRIME_EX2, BN_R_BITS_TOO_SMALL);
144         return 0;
145     }
146
147     mods = OPENSSL_zalloc(sizeof(*mods) * NUMPRIMES);
148     if (mods == NULL)
149         goto err;
150
151     BN_CTX_start(ctx);
152     t = BN_CTX_get(ctx);
153     if (t == NULL)
154         goto err;
155  loop:
156     /* make a random number and set the top and bottom bits */
157     if (add == NULL) {
158         if (!probable_prime(ret, bits, safe, mods, ctx))
159             goto err;
160     } else {
161         if (!probable_prime_dh(ret, bits, safe, mods, add, rem, ctx))
162             goto err;
163     }
164
165     if (!BN_GENCB_call(cb, 0, c1++))
166         /* aborted */
167         goto err;
168
169     if (!safe) {
170         i = bn_is_prime_int(ret, checks, ctx, 0, cb);
171         if (i == -1)
172             goto err;
173         if (i == 0)
174             goto loop;
175     } else {
176         /*
177          * for "safe prime" generation, check that (p-1)/2 is prime. Since a
178          * prime is odd, We just need to divide by 2
179          */
180         if (!BN_rshift1(t, ret))
181             goto err;
182
183         for (i = 0; i < checks; i++) {
184             j = bn_is_prime_int(ret, 1, ctx, 0, cb);
185             if (j == -1)
186                 goto err;
187             if (j == 0)
188                 goto loop;
189
190             j = bn_is_prime_int(t, 1, ctx, 0, cb);
191             if (j == -1)
192                 goto err;
193             if (j == 0)
194                 goto loop;
195
196             if (!BN_GENCB_call(cb, 2, c1 - 1))
197                 goto err;
198             /* We have a safe prime test pass */
199         }
200     }
201     /* we have a prime :-) */
202     found = 1;
203  err:
204     OPENSSL_free(mods);
205     BN_CTX_end(ctx);
206     bn_check_top(ret);
207     return found;
208 }
209
210 #ifndef FIPS_MODE
211 int BN_generate_prime_ex(BIGNUM *ret, int bits, int safe,
212                          const BIGNUM *add, const BIGNUM *rem, BN_GENCB *cb)
213 {
214     BN_CTX *ctx = BN_CTX_new();
215     int retval;
216
217     if (ctx == NULL)
218         return 0;
219
220     retval = BN_generate_prime_ex2(ret, bits, safe, add, rem, cb, ctx);
221
222     BN_CTX_free(ctx);
223     return retval;
224 }
225 #endif
226
227 #if !OPENSSL_API_3
228 int BN_is_prime_ex(const BIGNUM *a, int checks, BN_CTX *ctx_passed,
229                    BN_GENCB *cb)
230 {
231     return bn_check_prime_int(a, checks, ctx_passed, 0, cb);
232 }
233
234 int BN_is_prime_fasttest_ex(const BIGNUM *w, int checks, BN_CTX *ctx,
235                             int do_trial_division, BN_GENCB *cb)
236 {
237     return bn_check_prime_int(w, checks, ctx, do_trial_division, cb);
238 }
239 #endif
240
241 /* Wrapper around bn_is_prime_int that sets the minimum number of checks */
242 int bn_check_prime_int(const BIGNUM *w, int checks, BN_CTX *ctx,
243                        int do_trial_division, BN_GENCB *cb)
244 {
245     int min_checks = bn_mr_min_checks(BN_num_bits(w));
246
247     if (checks < min_checks)
248         checks = min_checks;
249
250     return bn_is_prime_int(w, checks, ctx, do_trial_division, cb);
251 }
252
253 int BN_check_prime(const BIGNUM *p, BN_CTX *ctx, BN_GENCB *cb)
254 {
255     return bn_check_prime_int(p, 0, ctx, 1, cb);
256 }
257
258 /*
259  * Tests that |w| is probably prime
260  * See FIPS 186-4 C.3.1 Miller Rabin Probabilistic Primality Test.
261  *
262  * Returns 0 when composite, 1 when probable prime, -1 on error.
263  */
264 static int bn_is_prime_int(const BIGNUM *w, int checks, BN_CTX *ctx,
265                            int do_trial_division, BN_GENCB *cb)
266 {
267     int i, status, ret = -1;
268 #ifndef FIPS_MODE
269     BN_CTX *ctxlocal = NULL;
270 #else
271
272     if (ctx == NULL)
273         return -1;
274 #endif
275
276     /* w must be bigger than 1 */
277     if (BN_cmp(w, BN_value_one()) <= 0)
278         return 0;
279
280     /* w must be odd */
281     if (BN_is_odd(w)) {
282         /* Take care of the really small prime 3 */
283         if (BN_is_word(w, 3))
284             return 1;
285     } else {
286         /* 2 is the only even prime */
287         return BN_is_word(w, 2);
288     }
289
290     /* first look for small factors */
291     if (do_trial_division) {
292         int trial_divisions = calc_trial_divisions(BN_num_bits(w));
293
294         for (i = 1; i < trial_divisions; i++) {
295             BN_ULONG mod = BN_mod_word(w, primes[i]);
296             if (mod == (BN_ULONG)-1)
297                 return -1;
298             if (mod == 0)
299                 return BN_is_word(w, primes[i]);
300         }
301         if (!BN_GENCB_call(cb, 1, -1))
302             return -1;
303     }
304 #ifndef FIPS_MODE
305     if (ctx == NULL && (ctxlocal = ctx = BN_CTX_new()) == NULL)
306         goto err;
307 #endif
308
309     ret = bn_miller_rabin_is_prime(w, checks, ctx, cb, 0, &status);
310     if (!ret)
311         goto err;
312     ret = (status == BN_PRIMETEST_PROBABLY_PRIME);
313 err:
314 #ifndef FIPS_MODE
315     BN_CTX_free(ctxlocal);
316 #endif
317     return ret;
318 }
319
320 /*
321  * Refer to FIPS 186-4 C.3.2 Enhanced Miller-Rabin Probabilistic Primality Test.
322  * OR C.3.1 Miller-Rabin Probabilistic Primality Test (if enhanced is zero).
323  * The Step numbers listed in the code refer to the enhanced case.
324  *
325  * if enhanced is set, then status returns one of the following:
326  *     BN_PRIMETEST_PROBABLY_PRIME
327  *     BN_PRIMETEST_COMPOSITE_WITH_FACTOR
328  *     BN_PRIMETEST_COMPOSITE_NOT_POWER_OF_PRIME
329  * if enhanced is zero, then status returns either
330  *     BN_PRIMETEST_PROBABLY_PRIME or
331  *     BN_PRIMETEST_COMPOSITE
332  *
333  * returns 0 if there was an error, otherwise it returns 1.
334  */
335 int bn_miller_rabin_is_prime(const BIGNUM *w, int iterations, BN_CTX *ctx,
336                              BN_GENCB *cb, int enhanced, int *status)
337 {
338     int i, j, a, ret = 0;
339     BIGNUM *g, *w1, *w3, *x, *m, *z, *b;
340     BN_MONT_CTX *mont = NULL;
341
342     /* w must be odd */
343     if (!BN_is_odd(w))
344         return 0;
345
346     BN_CTX_start(ctx);
347     g = BN_CTX_get(ctx);
348     w1 = BN_CTX_get(ctx);
349     w3 = BN_CTX_get(ctx);
350     x = BN_CTX_get(ctx);
351     m = BN_CTX_get(ctx);
352     z = BN_CTX_get(ctx);
353     b = BN_CTX_get(ctx);
354
355     if (!(b != NULL
356             /* w1 := w - 1 */
357             && BN_copy(w1, w)
358             && BN_sub_word(w1, 1)
359             /* w3 := w - 3 */
360             && BN_copy(w3, w)
361             && BN_sub_word(w3, 3)))
362         goto err;
363
364     /* check w is larger than 3, otherwise the random b will be too small */
365     if (BN_is_zero(w3) || BN_is_negative(w3))
366         goto err;
367
368     /* (Step 1) Calculate largest integer 'a' such that 2^a divides w-1 */
369     a = 1;
370     while (!BN_is_bit_set(w1, a))
371         a++;
372     /* (Step 2) m = (w-1) / 2^a */
373     if (!BN_rshift(m, w1, a))
374         goto err;
375
376     /* Montgomery setup for computations mod a */
377     mont = BN_MONT_CTX_new();
378     if (mont == NULL || !BN_MONT_CTX_set(mont, w, ctx))
379         goto err;
380
381     if (iterations == 0)
382         iterations = bn_mr_min_checks(BN_num_bits(w));
383
384     /* (Step 4) */
385     for (i = 0; i < iterations; ++i) {
386         /* (Step 4.1) obtain a Random string of bits b where 1 < b < w-1 */
387         if (!BN_priv_rand_range_ex(b, w3, ctx)
388                 || !BN_add_word(b, 2)) /* 1 < b < w-1 */
389             goto err;
390
391         if (enhanced) {
392             /* (Step 4.3) */
393             if (!BN_gcd(g, b, w, ctx))
394                 goto err;
395             /* (Step 4.4) */
396             if (!BN_is_one(g)) {
397                 *status = BN_PRIMETEST_COMPOSITE_WITH_FACTOR;
398                 ret = 1;
399                 goto err;
400             }
401         }
402         /* (Step 4.5) z = b^m mod w */
403         if (!BN_mod_exp_mont(z, b, m, w, ctx, mont))
404             goto err;
405         /* (Step 4.6) if (z = 1 or z = w-1) */
406         if (BN_is_one(z) || BN_cmp(z, w1) == 0)
407             goto outer_loop;
408         /* (Step 4.7) for j = 1 to a-1 */
409         for (j = 1; j < a ; ++j) {
410             /* (Step 4.7.1 - 4.7.2) x = z. z = x^2 mod w */
411             if (!BN_copy(x, z) || !BN_mod_mul(z, x, x, w, ctx))
412                 goto err;
413             /* (Step 4.7.3) */
414             if (BN_cmp(z, w1) == 0)
415                 goto outer_loop;
416             /* (Step 4.7.4) */
417             if (BN_is_one(z))
418                 goto composite;
419         }
420         /* At this point z = b^((w-1)/2) mod w */
421         /* (Steps 4.8 - 4.9) x = z, z = x^2 mod w */
422         if (!BN_copy(x, z) || !BN_mod_mul(z, x, x, w, ctx))
423             goto err;
424         /* (Step 4.10) */
425         if (BN_is_one(z))
426             goto composite;
427         /* (Step 4.11) x = b^(w-1) mod w */
428         if (!BN_copy(x, z))
429             goto err;
430 composite:
431         if (enhanced) {
432             /* (Step 4.1.2) g = GCD(x-1, w) */
433             if (!BN_sub_word(x, 1) || !BN_gcd(g, x, w, ctx))
434                 goto err;
435             /* (Steps 4.1.3 - 4.1.4) */
436             if (BN_is_one(g))
437                 *status = BN_PRIMETEST_COMPOSITE_NOT_POWER_OF_PRIME;
438             else
439                 *status = BN_PRIMETEST_COMPOSITE_WITH_FACTOR;
440         } else {
441             *status = BN_PRIMETEST_COMPOSITE;
442         }
443         ret = 1;
444         goto err;
445 outer_loop: ;
446         /* (Step 4.1.5) */
447         if (!BN_GENCB_call(cb, 1, i))
448             goto err;
449     }
450     /* (Step 5) */
451     *status = BN_PRIMETEST_PROBABLY_PRIME;
452     ret = 1;
453 err:
454     BN_clear(g);
455     BN_clear(w1);
456     BN_clear(w3);
457     BN_clear(x);
458     BN_clear(m);
459     BN_clear(z);
460     BN_clear(b);
461     BN_CTX_end(ctx);
462     BN_MONT_CTX_free(mont);
463     return ret;
464 }
465
466 /*
467  * Generate a random number of |bits| bits that is probably prime by sieving.
468  * If |safe| != 0, it generates a safe prime.
469  * |mods| is a preallocated array that gets reused when called again.
470  *
471  * The probably prime is saved in |rnd|.
472  *
473  * Returns 1 on success and 0 on error.
474  */
475 static int probable_prime(BIGNUM *rnd, int bits, int safe, prime_t *mods,
476                           BN_CTX *ctx)
477 {
478     int i;
479     BN_ULONG delta;
480     int trial_divisions = calc_trial_divisions(bits);
481     BN_ULONG maxdelta = BN_MASK2 - primes[trial_divisions - 1];
482
483  again:
484     /* TODO: Not all primes are private */
485     if (!BN_priv_rand_ex(rnd, bits, BN_RAND_TOP_TWO, BN_RAND_BOTTOM_ODD, ctx))
486         return 0;
487     if (safe && !BN_set_bit(rnd, 1))
488         return 0;
489     /* we now have a random number 'rnd' to test. */
490     for (i = 1; i < trial_divisions; i++) {
491         BN_ULONG mod = BN_mod_word(rnd, (BN_ULONG)primes[i]);
492         if (mod == (BN_ULONG)-1)
493             return 0;
494         mods[i] = (prime_t) mod;
495     }
496     delta = 0;
497  loop:
498     for (i = 1; i < trial_divisions; i++) {
499         /*
500          * check that rnd is a prime and also that
501          * gcd(rnd-1,primes) == 1 (except for 2)
502          * do the second check only if we are interested in safe primes
503          * in the case that the candidate prime is a single word then
504          * we check only the primes up to sqrt(rnd)
505          */
506         if (bits <= 31 && delta <= 0x7fffffff
507                 && square(primes[i]) > BN_get_word(rnd) + delta)
508             break;
509         if (safe ? (mods[i] + delta) % primes[i] <= 1
510                  : (mods[i] + delta) % primes[i] == 0) {
511             delta += safe ? 4 : 2;
512             if (delta > maxdelta)
513                 goto again;
514             goto loop;
515         }
516     }
517     if (!BN_add_word(rnd, delta))
518         return 0;
519     if (BN_num_bits(rnd) != bits)
520         goto again;
521     bn_check_top(rnd);
522     return 1;
523 }
524
525 /*
526  * Generate a random number |rnd| of |bits| bits that is probably prime
527  * and satisfies |rnd| % |add| == |rem| by sieving.
528  * If |safe| != 0, it generates a safe prime.
529  * |mods| is a preallocated array that gets reused when called again.
530  *
531  * Returns 1 on success and 0 on error.
532  */
533 static int probable_prime_dh(BIGNUM *rnd, int bits, int safe, prime_t *mods,
534                              const BIGNUM *add, const BIGNUM *rem,
535                              BN_CTX *ctx)
536 {
537     int i, ret = 0;
538     BIGNUM *t1;
539     BN_ULONG delta;
540     int trial_divisions = calc_trial_divisions(bits);
541     BN_ULONG maxdelta = BN_MASK2 - primes[trial_divisions - 1];
542
543     BN_CTX_start(ctx);
544     if ((t1 = BN_CTX_get(ctx)) == NULL)
545         goto err;
546
547     if (maxdelta > BN_MASK2 - BN_get_word(add))
548         maxdelta = BN_MASK2 - BN_get_word(add);
549
550  again:
551     if (!BN_rand_ex(rnd, bits, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ODD, ctx))
552         goto err;
553
554     /* we need ((rnd-rem) % add) == 0 */
555
556     if (!BN_mod(t1, rnd, add, ctx))
557         goto err;
558     if (!BN_sub(rnd, rnd, t1))
559         goto err;
560     if (rem == NULL) {
561         if (!BN_add_word(rnd, safe ? 3u : 1u))
562             goto err;
563     } else {
564         if (!BN_add(rnd, rnd, rem))
565             goto err;
566     }
567
568     if (BN_num_bits(rnd) < bits
569             || BN_get_word(rnd) < (safe ? 5u : 3u)) {
570         if (!BN_add(rnd, rnd, add))
571             goto err;
572     }
573
574     /* we now have a random number 'rnd' to test. */
575     for (i = 1; i < trial_divisions; i++) {
576         BN_ULONG mod = BN_mod_word(rnd, (BN_ULONG)primes[i]);
577         if (mod == (BN_ULONG)-1)
578             goto err;
579         mods[i] = (prime_t) mod;
580     }
581     delta = 0;
582  loop:
583     for (i = 1; i < trial_divisions; i++) {
584         /* check that rnd is a prime */
585         if (bits <= 31 && delta <= 0x7fffffff
586                 && square(primes[i]) > BN_get_word(rnd) + delta)
587             break;
588         /* rnd mod p == 1 implies q = (rnd-1)/2 is divisible by p */
589         if (safe ? (mods[i] + delta) % primes[i] <= 1
590                  : (mods[i] + delta) % primes[i] == 0) {
591             delta += BN_get_word(add);
592             if (delta > maxdelta)
593                 goto again;
594             goto loop;
595         }
596     }
597     if (!BN_add_word(rnd, delta))
598         goto err;
599     ret = 1;
600
601  err:
602     BN_CTX_end(ctx);
603     bn_check_top(rnd);
604     return ret;
605 }