1 /*
2  * Copyright 2018-2023 The OpenSSL Project Authors. All Rights Reserved.
3  * Copyright (c) 2018-2019, Oracle and/or its affiliates.  All rights reserved.
4  *
5  * Licensed under the Apache License 2.0 (the "License").  You may not use
6  * this file except in compliance with the License.  You can obtain a copy
7  * in the file LICENSE in the source distribution or at
8  * https://www.openssl.org/source/license.html
9  */
10 
11 /*
12  * According to NIST SP800-131A "Transitioning the use of cryptographic
13  * algorithms and key lengths" Generation of 1024 bit RSA keys are no longer
14  * allowed for signatures (Table 2) or key transport (Table 5). In the code
15  * below any attempt to generate 1024 bit RSA keys will result in an error (Note
16  * that digital signature verification can still use deprecated 1024 bit keys).
17  *
18  * FIPS 186-4 relies on the use of the auxiliary primes p1, p2, q1 and q2 that
19  * must be generated before the module generates the RSA primes p and q.
20  * Table B.1 in FIPS 186-4 specifies RSA modulus lengths of 2048 and
21  * 3072 bits only, the min/max total length of the auxiliary primes.
22  * FIPS 186-5 Table A.1 includes an additional entry for 4096 which has been
23  * included here.
24  */
25 #include <stdio.h>
26 #include <openssl/bn.h>
27 #include "bn_local.h"
28 #include "crypto/bn.h"
29 #include "internal/nelem.h"
30 
31 #if BN_BITS2 == 64
32 # define BN_DEF(lo, hi) (BN_ULONG)hi<<32|lo
33 #else
34 # define BN_DEF(lo, hi) lo, hi
35 #endif
36 
37 /* 1 / sqrt(2) * 2^256, rounded up */
38 static const BN_ULONG inv_sqrt_2_val[] = {
39     BN_DEF(0x83339916UL, 0xED17AC85UL), BN_DEF(0x893BA84CUL, 0x1D6F60BAUL),
40     BN_DEF(0x754ABE9FUL, 0x597D89B3UL), BN_DEF(0xF9DE6484UL, 0xB504F333UL)
41 };
42 
43 const BIGNUM ossl_bn_inv_sqrt_2 = {
44     (BN_ULONG *)inv_sqrt_2_val,
45     OSSL_NELEM(inv_sqrt_2_val),
46     OSSL_NELEM(inv_sqrt_2_val),
47     0,
48     BN_FLG_STATIC_DATA
49 };
50 
51 /*
52  * FIPS 186-5 Table A.1. "Min length of auxiliary primes p1, p2, q1, q2".
53  * (FIPS 186-5 has an entry for >= 4096 bits).
54  *
55  * Params:
56  *     nbits The key size in bits.
57  * Returns:
58  *     The minimum size of the auxiliary primes or 0 if nbits is invalid.
59  */
bn_rsa_fips186_5_aux_prime_min_size(int nbits)60 static int bn_rsa_fips186_5_aux_prime_min_size(int nbits)
61 {
62     if (nbits >= 4096)
63         return 201;
64     if (nbits >= 3072)
65         return 171;
66     if (nbits >= 2048)
67         return 141;
68     return 0;
69 }
70 
71 /*
72  * FIPS 186-5 Table A.1 "Max of len(p1) + len(p2) and
73  * len(q1) + len(q2) for p,q Probable Primes".
74  * (FIPS 186-5 has an entry for >= 4096 bits).
75  * Params:
76  *     nbits The key size in bits.
77  * Returns:
78  *     The maximum length or 0 if nbits is invalid.
79  */
bn_rsa_fips186_5_aux_prime_max_sum_size_for_prob_primes(int nbits)80 static int bn_rsa_fips186_5_aux_prime_max_sum_size_for_prob_primes(int nbits)
81 {
82     if (nbits >= 4096)
83         return 2030;
84     if (nbits >= 3072)
85         return 1518;
86     if (nbits >= 2048)
87         return 1007;
88     return 0;
89 }
90 
91 /*
92  * Find the first odd integer that is a probable prime.
93  *
94  * See section FIPS 186-4 B.3.6 (Steps 4.2/5.2).
95  *
96  * Params:
97  *     Xp1 The passed in starting point to find a probably prime.
98  *     p1 The returned probable prime (first odd integer >= Xp1)
99  *     ctx A BN_CTX object.
100  *     cb An optional BIGNUM callback.
101  * Returns: 1 on success otherwise it returns 0.
102  */
bn_rsa_fips186_4_find_aux_prob_prime(const BIGNUM * Xp1,BIGNUM * p1,BN_CTX * ctx,BN_GENCB * cb)103 static int bn_rsa_fips186_4_find_aux_prob_prime(const BIGNUM *Xp1,
104                                                 BIGNUM *p1, BN_CTX *ctx,
105                                                 BN_GENCB *cb)
106 {
107     int ret = 0;
108     int i = 0;
109     int tmp = 0;
110 
111     if (BN_copy(p1, Xp1) == NULL)
112         return 0;
113     BN_set_flags(p1, BN_FLG_CONSTTIME);
114 
115     /* Find the first odd number >= Xp1 that is probably prime */
116     for(;;) {
117         i++;
118         BN_GENCB_call(cb, 0, i);
119         /* MR test with trial division */
120         tmp = BN_check_prime(p1, ctx, cb);
121         if (tmp > 0)
122             break;
123         if (tmp < 0)
124             goto err;
125         /* Get next odd number */
126         if (!BN_add_word(p1, 2))
127             goto err;
128     }
129     BN_GENCB_call(cb, 2, i);
130     ret = 1;
131 err:
132     return ret;
133 }
134 
135 /*
136  * Generate a probable prime (p or q).
137  *
138  * See FIPS 186-4 B.3.6 (Steps 4 & 5)
139  *
140  * Params:
141  *     p The returned probable prime.
142  *     Xpout An optionally returned random number used during generation of p.
143  *     p1, p2 The returned auxiliary primes. If NULL they are not returned.
144  *     Xp An optional passed in value (that is random number used during
145  *        generation of p).
146  *     Xp1, Xp2 Optional passed in values that are normally generated
147  *              internally. Used to find p1, p2.
148  *     nlen The bit length of the modulus (the key size).
149  *     e The public exponent.
150  *     ctx A BN_CTX object.
151  *     cb An optional BIGNUM callback.
152  * Returns: 1 on success otherwise it returns 0.
153  */
ossl_bn_rsa_fips186_4_gen_prob_primes(BIGNUM * p,BIGNUM * Xpout,BIGNUM * p1,BIGNUM * p2,const BIGNUM * Xp,const BIGNUM * Xp1,const BIGNUM * Xp2,int nlen,const BIGNUM * e,BN_CTX * ctx,BN_GENCB * cb)154 int ossl_bn_rsa_fips186_4_gen_prob_primes(BIGNUM *p, BIGNUM *Xpout,
155                                           BIGNUM *p1, BIGNUM *p2,
156                                           const BIGNUM *Xp, const BIGNUM *Xp1,
157                                           const BIGNUM *Xp2, int nlen,
158                                           const BIGNUM *e, BN_CTX *ctx,
159                                           BN_GENCB *cb)
160 {
161     int ret = 0;
162     BIGNUM *p1i = NULL, *p2i = NULL, *Xp1i = NULL, *Xp2i = NULL;
163     int bitlen;
164 
165     if (p == NULL || Xpout == NULL)
166         return 0;
167 
168     BN_CTX_start(ctx);
169 
170     p1i = (p1 != NULL) ? p1 : BN_CTX_get(ctx);
171     p2i = (p2 != NULL) ? p2 : BN_CTX_get(ctx);
172     Xp1i = (Xp1 != NULL) ? (BIGNUM *)Xp1 : BN_CTX_get(ctx);
173     Xp2i = (Xp2 != NULL) ? (BIGNUM *)Xp2 : BN_CTX_get(ctx);
174     if (p1i == NULL || p2i == NULL || Xp1i == NULL || Xp2i == NULL)
175         goto err;
176 
177     bitlen = bn_rsa_fips186_5_aux_prime_min_size(nlen);
178     if (bitlen == 0)
179         goto err;
180 
181     /* (Steps 4.1/5.1): Randomly generate Xp1 if it is not passed in */
182     if (Xp1 == NULL) {
183         /* Set the top and bottom bits to make it odd and the correct size */
184         if (!BN_priv_rand_ex(Xp1i, bitlen, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ODD,
185                              0, ctx))
186             goto err;
187     }
188     /* (Steps 4.1/5.1): Randomly generate Xp2 if it is not passed in */
189     if (Xp2 == NULL) {
190         /* Set the top and bottom bits to make it odd and the correct size */
191         if (!BN_priv_rand_ex(Xp2i, bitlen, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ODD,
192                              0, ctx))
193             goto err;
194     }
195 
196     /* (Steps 4.2/5.2) - find first auxiliary probable primes */
197     if (!bn_rsa_fips186_4_find_aux_prob_prime(Xp1i, p1i, ctx, cb)
198             || !bn_rsa_fips186_4_find_aux_prob_prime(Xp2i, p2i, ctx, cb))
199         goto err;
200     /* (Table B.1) auxiliary prime Max length check */
201     if ((BN_num_bits(p1i) + BN_num_bits(p2i)) >=
202             bn_rsa_fips186_5_aux_prime_max_sum_size_for_prob_primes(nlen))
203         goto err;
204     /* (Steps 4.3/5.3) - generate prime */
205     if (!ossl_bn_rsa_fips186_4_derive_prime(p, Xpout, Xp, p1i, p2i, nlen, e,
206                                             ctx, cb))
207         goto err;
208     ret = 1;
209 err:
210     /* Zeroize any internally generated values that are not returned */
211     if (p1 == NULL)
212         BN_clear(p1i);
213     if (p2 == NULL)
214         BN_clear(p2i);
215     if (Xp1 == NULL)
216         BN_clear(Xp1i);
217     if (Xp2 == NULL)
218         BN_clear(Xp2i);
219     BN_CTX_end(ctx);
220     return ret;
221 }
222 
223 /*
224  * Constructs a probable prime (a candidate for p or q) using 2 auxiliary
225  * prime numbers and the Chinese Remainder Theorem.
226  *
227  * See FIPS 186-4 C.9 "Compute a Probable Prime Factor Based on Auxiliary
228  * Primes". Used by FIPS 186-4 B.3.6 Section (4.3) for p and Section (5.3) for q.
229  *
230  * Params:
231  *     Y The returned prime factor (private_prime_factor) of the modulus n.
232  *     X The returned random number used during generation of the prime factor.
233  *     Xin An optional passed in value for X used for testing purposes.
234  *     r1 An auxiliary prime.
235  *     r2 An auxiliary prime.
236  *     nlen The desired length of n (the RSA modulus).
237  *     e The public exponent.
238  *     ctx A BN_CTX object.
239  *     cb An optional BIGNUM callback object.
240  * Returns: 1 on success otherwise it returns 0.
241  * Assumptions:
242  *     Y, X, r1, r2, e are not NULL.
243  */
ossl_bn_rsa_fips186_4_derive_prime(BIGNUM * Y,BIGNUM * X,const BIGNUM * Xin,const BIGNUM * r1,const BIGNUM * r2,int nlen,const BIGNUM * e,BN_CTX * ctx,BN_GENCB * cb)244 int ossl_bn_rsa_fips186_4_derive_prime(BIGNUM *Y, BIGNUM *X, const BIGNUM *Xin,
245                                        const BIGNUM *r1, const BIGNUM *r2,
246                                        int nlen, const BIGNUM *e, BN_CTX *ctx,
247                                        BN_GENCB *cb)
248 {
249     int ret = 0;
250     int i, imax;
251     int bits = nlen >> 1;
252     BIGNUM *tmp, *R, *r1r2x2, *y1, *r1x2;
253     BIGNUM *base, *range;
254 
255     BN_CTX_start(ctx);
256 
257     base = BN_CTX_get(ctx);
258     range = BN_CTX_get(ctx);
259     R = BN_CTX_get(ctx);
260     tmp = BN_CTX_get(ctx);
261     r1r2x2 = BN_CTX_get(ctx);
262     y1 = BN_CTX_get(ctx);
263     r1x2 = BN_CTX_get(ctx);
264     if (r1x2 == NULL)
265         goto err;
266 
267     if (Xin != NULL && BN_copy(X, Xin) == NULL)
268         goto err;
269 
270     /*
271      * We need to generate a random number X in the range
272      * 1/sqrt(2) * 2^(nlen/2) <= X < 2^(nlen/2).
273      * We can rewrite that as:
274      * base = 1/sqrt(2) * 2^(nlen/2)
275      * range = ((2^(nlen/2))) - (1/sqrt(2) * 2^(nlen/2))
276      * X = base + random(range)
277      * We only have the first 256 bit of 1/sqrt(2)
278      */
279     if (Xin == NULL) {
280         if (bits < BN_num_bits(&ossl_bn_inv_sqrt_2))
281             goto err;
282         if (!BN_lshift(base, &ossl_bn_inv_sqrt_2,
283                        bits - BN_num_bits(&ossl_bn_inv_sqrt_2))
284             || !BN_lshift(range, BN_value_one(), bits)
285             || !BN_sub(range, range, base))
286             goto err;
287     }
288 
289     if (!(BN_lshift1(r1x2, r1)
290             /* (Step 1) GCD(2r1, r2) = 1 */
291             && BN_gcd(tmp, r1x2, r2, ctx)
292             && BN_is_one(tmp)
293             /* (Step 2) R = ((r2^-1 mod 2r1) * r2) - ((2r1^-1 mod r2)*2r1) */
294             && BN_mod_inverse(R, r2, r1x2, ctx)
295             && BN_mul(R, R, r2, ctx) /* R = (r2^-1 mod 2r1) * r2 */
296             && BN_mod_inverse(tmp, r1x2, r2, ctx)
297             && BN_mul(tmp, tmp, r1x2, ctx) /* tmp = (2r1^-1 mod r2)*2r1 */
298             && BN_sub(R, R, tmp)
299             /* Calculate 2r1r2 */
300             && BN_mul(r1r2x2, r1x2, r2, ctx)))
301         goto err;
302     /* Make positive by adding the modulus */
303     if (BN_is_negative(R) && !BN_add(R, R, r1r2x2))
304         goto err;
305 
306     /*
307      * In FIPS 186-4 imax was set to 5 * nlen/2.
308      * Analysis by Allen Roginsky (See https://csrc.nist.gov/CSRC/media/Publications/fips/186/4/final/documents/comments-received-fips186-4-december-2015.pdf
309      * page 68) indicates this has a 1 in 2 million chance of failure.
310      * The number has been updated to 20 * nlen/2 as used in
311      * FIPS186-5 Appendix B.9 Step 9.
312      */
313     imax = 20 * bits; /* max = 20/2 * nbits */
314     for (;;) {
315         if (Xin == NULL) {
316             /*
317              * (Step 3) Choose Random X such that
318              *    sqrt(2) * 2^(nlen/2-1) <= Random X <= (2^(nlen/2)) - 1.
319              */
320             if (!BN_priv_rand_range_ex(X, range, 0, ctx) || !BN_add(X, X, base))
321                 goto err;
322         }
323         /* (Step 4) Y = X + ((R - X) mod 2r1r2) */
324         if (!BN_mod_sub(Y, R, X, r1r2x2, ctx) || !BN_add(Y, Y, X))
325             goto err;
326         /* (Step 5) */
327         i = 0;
328         for (;;) {
329             /* (Step 6) */
330             if (BN_num_bits(Y) > bits) {
331                 if (Xin == NULL)
332                     break; /* Randomly Generated X so Go back to Step 3 */
333                 else
334                     goto err; /* X is not random so it will always fail */
335             }
336             BN_GENCB_call(cb, 0, 2);
337 
338             /* (Step 7) If GCD(Y-1) == 1 & Y is probably prime then return Y */
339             if (BN_copy(y1, Y) == NULL
340                     || !BN_sub_word(y1, 1)
341                     || !BN_gcd(tmp, y1, e, ctx))
342                 goto err;
343             if (BN_is_one(tmp)) {
344                 int rv = BN_check_prime(Y, ctx, cb);
345 
346                 if (rv > 0)
347                     goto end;
348                 if (rv < 0)
349                     goto err;
350             }
351             /* (Step 8-10) */
352             if (++i >= imax) {
353                 ERR_raise(ERR_LIB_BN, BN_R_NO_PRIME_CANDIDATE);
354                 goto err;
355             }
356             if (!BN_add(Y, Y, r1r2x2))
357                 goto err;
358         }
359     }
360 end:
361     ret = 1;
362     BN_GENCB_call(cb, 3, 0);
363 err:
364     BN_clear(y1);
365     BN_CTX_end(ctx);
366     return ret;
367 }
368