1/*
2 * Copyright 2018-2019 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 OpenSSL license (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 * Also see FIPS1402IG A.14
19 * FIPS 186-4 relies on the use of the auxiliary primes p1, p2, q1 and q2 that
20 * must be generated before the module generates the RSA primes p and q.
21 * Table B.1 in FIPS 186-4 specifies, for RSA modulus lengths of 2048 and
22 * 3072 bits only, the min/max total length of the auxiliary primes.
23 * When implementing the RSA signature generation algorithm
24 * with other approved RSA modulus sizes, the vendor shall use the limitations
25 * from Table B.1 that apply to the longest RSA modulus shown in Table B.1 of
26 * FIPS 186-4 whose length does not exceed that of the implementation's RSA
27 * modulus. In particular, when generating the primes for the 4096-bit RSA
28 * modulus the limitations stated for the 3072-bit modulus shall apply.
29 */
30#include <stdio.h>
31#include <openssl/bn.h>
32#include "bn_local.h"
33#include "crypto/bn.h"
34#include "internal/nelem.h"
35
36#if BN_BITS2 == 64
37# define BN_DEF(lo, hi) (BN_ULONG)hi<<32|lo
38#else
39# define BN_DEF(lo, hi) lo, hi
40#endif
41
42/* 1 / sqrt(2) * 2^256, rounded up */
43static const BN_ULONG inv_sqrt_2_val[] = {
44 BN_DEF(0x83339916UL, 0xED17AC85UL), BN_DEF(0x893BA84CUL, 0x1D6F60BAUL),
45 BN_DEF(0x754ABE9FUL, 0x597D89B3UL), BN_DEF(0xF9DE6484UL, 0xB504F333UL)
46};
47
48const BIGNUM bn_inv_sqrt_2 = {
49 (BN_ULONG *)inv_sqrt_2_val,
50 OSSL_NELEM(inv_sqrt_2_val),
51 OSSL_NELEM(inv_sqrt_2_val),
52 0,
53 BN_FLG_STATIC_DATA
54};
55
56/*
57 * FIPS 186-4 Table B.1. "Min length of auxiliary primes p1, p2, q1, q2".
58 *
59 * Params:
60 * nbits The key size in bits.
61 * Returns:
62 * The minimum size of the auxiliary primes or 0 if nbits is invalid.
63 */
64static int bn_rsa_fips186_4_aux_prime_min_size(int nbits)
65{
66 if (nbits >= 3072)
67 return 171;
68 if (nbits == 2048)
69 return 141;
70 return 0;
71}
72
73/*
74 * FIPS 186-4 Table B.1 "Maximum length of len(p1) + len(p2) and
75 * len(q1) + len(q2) for p,q Probable Primes".
76 *
77 * Params:
78 * nbits The key size in bits.
79 * Returns:
80 * The maximum length or 0 if nbits is invalid.
81 */
82static int bn_rsa_fips186_4_aux_prime_max_sum_size_for_prob_primes(int nbits)
83{
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 */
103static 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
110 if (BN_copy(p1, Xp1) == NULL)
111 return 0;
112
113 /* Find the first odd number >= Xp1 that is probably prime */
114 for(;;) {
115 i++;
116 BN_GENCB_call(cb, 0, i);
117 /* MR test with trial division */
118 if (BN_check_prime(p1, ctx, cb))
119 break;
120 /* Get next odd number */
121 if (!BN_add_word(p1, 2))
122 goto err;
123 }
124 BN_GENCB_call(cb, 2, i);
125 ret = 1;
126err:
127 return ret;
128}
129
130/*
131 * Generate a probable prime (p or q).
132 *
133 * See FIPS 186-4 B.3.6 (Steps 4 & 5)
134 *
135 * Params:
136 * p The returned probable prime.
137 * Xpout An optionally returned random number used during generation of p.
138 * p1, p2 The returned auxiliary primes. If NULL they are not returned.
139 * Xp An optional passed in value (that is random number used during
140 * generation of p).
141 * Xp1, Xp2 Optional passed in values that are normally generated
142 * internally. Used to find p1, p2.
143 * nlen The bit length of the modulus (the key size).
144 * e The public exponent.
145 * ctx A BN_CTX object.
146 * cb An optional BIGNUM callback.
147 * Returns: 1 on success otherwise it returns 0.
148 */
149int bn_rsa_fips186_4_gen_prob_primes(BIGNUM *p, BIGNUM *Xpout,
150 BIGNUM *p1, BIGNUM *p2,
151 const BIGNUM *Xp, const BIGNUM *Xp1,
152 const BIGNUM *Xp2, int nlen,
153 const BIGNUM *e, BN_CTX *ctx, BN_GENCB *cb)
154{
155 int ret = 0;
156 BIGNUM *p1i = NULL, *p2i = NULL, *Xp1i = NULL, *Xp2i = NULL;
157 int bitlen;
158
159 if (p == NULL || Xpout == NULL)
160 return 0;
161
162 BN_CTX_start(ctx);
163
164 p1i = (p1 != NULL) ? p1 : BN_CTX_get(ctx);
165 p2i = (p2 != NULL) ? p2 : BN_CTX_get(ctx);
166 Xp1i = (Xp1 != NULL) ? (BIGNUM *)Xp1 : BN_CTX_get(ctx);
167 Xp2i = (Xp2 != NULL) ? (BIGNUM *)Xp2 : BN_CTX_get(ctx);
168 if (p1i == NULL || p2i == NULL || Xp1i == NULL || Xp2i == NULL)
169 goto err;
170
171 bitlen = bn_rsa_fips186_4_aux_prime_min_size(nlen);
172 if (bitlen == 0)
173 goto err;
174
175 /* (Steps 4.1/5.1): Randomly generate Xp1 if it is not passed in */
176 if (Xp1 == NULL) {
177 /* Set the top and bottom bits to make it odd and the correct size */
178 if (!BN_priv_rand_ex(Xp1i, bitlen, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ODD,
179 ctx))
180 goto err;
181 }
182 /* (Steps 4.1/5.1): Randomly generate Xp2 if it is not passed in */
183 if (Xp2 == NULL) {
184 /* Set the top and bottom bits to make it odd and the correct size */
185 if (!BN_priv_rand_ex(Xp2i, bitlen, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ODD,
186 ctx))
187 goto err;
188 }
189
190 /* (Steps 4.2/5.2) - find first auxiliary probable primes */
191 if (!bn_rsa_fips186_4_find_aux_prob_prime(Xp1i, p1i, ctx, cb)
192 || !bn_rsa_fips186_4_find_aux_prob_prime(Xp2i, p2i, ctx, cb))
193 goto err;
194 /* (Table B.1) auxiliary prime Max length check */
195 if ((BN_num_bits(p1i) + BN_num_bits(p2i)) >=
196 bn_rsa_fips186_4_aux_prime_max_sum_size_for_prob_primes(nlen))
197 goto err;
198 /* (Steps 4.3/5.3) - generate prime */
199 if (!bn_rsa_fips186_4_derive_prime(p, Xpout, Xp, p1i, p2i, nlen, e, ctx, cb))
200 goto err;
201 ret = 1;
202err:
203 /* Zeroize any internally generated values that are not returned */
204 if (p1 == NULL)
205 BN_clear(p1i);
206 if (p2 == NULL)
207 BN_clear(p2i);
208 if (Xp1 == NULL)
209 BN_clear(Xp1i);
210 if (Xp2 == NULL)
211 BN_clear(Xp2i);
212 BN_CTX_end(ctx);
213 return ret;
214}
215
216/*
217 * Constructs a probable prime (a candidate for p or q) using 2 auxiliary
218 * prime numbers and the Chinese Remainder Theorem.
219 *
220 * See FIPS 186-4 C.9 "Compute a Probable Prime Factor Based on Auxiliary
221 * Primes". Used by FIPS 186-4 B.3.6 Section (4.3) for p and Section (5.3) for q.
222 *
223 * Params:
224 * Y The returned prime factor (private_prime_factor) of the modulus n.
225 * X The returned random number used during generation of the prime factor.
226 * Xin An optional passed in value for X used for testing purposes.
227 * r1 An auxiliary prime.
228 * r2 An auxiliary prime.
229 * nlen The desired length of n (the RSA modulus).
230 * e The public exponent.
231 * ctx A BN_CTX object.
232 * cb An optional BIGNUM callback object.
233 * Returns: 1 on success otherwise it returns 0.
234 * Assumptions:
235 * Y, X, r1, r2, e are not NULL.
236 */
237int bn_rsa_fips186_4_derive_prime(BIGNUM *Y, BIGNUM *X, const BIGNUM *Xin,
238 const BIGNUM *r1, const BIGNUM *r2, int nlen,
239 const BIGNUM *e, BN_CTX *ctx, BN_GENCB *cb)
240{
241 int ret = 0;
242 int i, imax;
243 int bits = nlen >> 1;
244 BIGNUM *tmp, *R, *r1r2x2, *y1, *r1x2;
245 BIGNUM *base, *range;
246
247 BN_CTX_start(ctx);
248
249 base = BN_CTX_get(ctx);
250 range = BN_CTX_get(ctx);
251 R = BN_CTX_get(ctx);
252 tmp = BN_CTX_get(ctx);
253 r1r2x2 = BN_CTX_get(ctx);
254 y1 = BN_CTX_get(ctx);
255 r1x2 = BN_CTX_get(ctx);
256 if (r1x2 == NULL)
257 goto err;
258
259 if (Xin != NULL && BN_copy(X, Xin) == NULL)
260 goto err;
261
262 /*
263 * We need to generate a random number X in the range
264 * 1/sqrt(2) * 2^(nlen/2) <= X < 2^(nlen/2).
265 * We can rewrite that as:
266 * base = 1/sqrt(2) * 2^(nlen/2)
267 * range = ((2^(nlen/2))) - (1/sqrt(2) * 2^(nlen/2))
268 * X = base + random(range)
269 * We only have the first 256 bit of 1/sqrt(2)
270 */
271 if (Xin == NULL) {
272 if (bits < BN_num_bits(&bn_inv_sqrt_2))
273 goto err;
274 if (!BN_lshift(base, &bn_inv_sqrt_2, bits - BN_num_bits(&bn_inv_sqrt_2))
275 || !BN_lshift(range, BN_value_one(), bits)
276 || !BN_sub(range, range, base))
277 goto err;
278 }
279
280 if (!(BN_lshift1(r1x2, r1)
281 /* (Step 1) GCD(2r1, r2) = 1 */
282 && BN_gcd(tmp, r1x2, r2, ctx)
283 && BN_is_one(tmp)
284 /* (Step 2) R = ((r2^-1 mod 2r1) * r2) - ((2r1^-1 mod r2)*2r1) */
285 && BN_mod_inverse(R, r2, r1x2, ctx)
286 && BN_mul(R, R, r2, ctx) /* R = (r2^-1 mod 2r1) * r2 */
287 && BN_mod_inverse(tmp, r1x2, r2, ctx)
288 && BN_mul(tmp, tmp, r1x2, ctx) /* tmp = (2r1^-1 mod r2)*2r1 */
289 && BN_sub(R, R, tmp)
290 /* Calculate 2r1r2 */
291 && BN_mul(r1r2x2, r1x2, r2, ctx)))
292 goto err;
293 /* Make positive by adding the modulus */
294 if (BN_is_negative(R) && !BN_add(R, R, r1r2x2))
295 goto err;
296
297 imax = 5 * bits; /* max = 5/2 * nbits */
298 for (;;) {
299 if (Xin == NULL) {
300 /*
301 * (Step 3) Choose Random X such that
302 * sqrt(2) * 2^(nlen/2-1) <= Random X <= (2^(nlen/2)) - 1.
303 */
304 if (!BN_priv_rand_range_ex(X, range, ctx) || !BN_add(X, X, base))
305 goto end;
306 }
307 /* (Step 4) Y = X + ((R - X) mod 2r1r2) */
308 if (!BN_mod_sub(Y, R, X, r1r2x2, ctx) || !BN_add(Y, Y, X))
309 goto err;
310 /* (Step 5) */
311 i = 0;
312 for (;;) {
313 /* (Step 6) */
314 if (BN_num_bits(Y) > bits) {
315 if (Xin == NULL)
316 break; /* Randomly Generated X so Go back to Step 3 */
317 else
318 goto err; /* X is not random so it will always fail */
319 }
320 BN_GENCB_call(cb, 0, 2);
321
322 /* (Step 7) If GCD(Y-1) == 1 & Y is probably prime then return Y */
323 if (BN_copy(y1, Y) == NULL
324 || !BN_sub_word(y1, 1)
325 || !BN_gcd(tmp, y1, e, ctx))
326 goto err;
327 if (BN_is_one(tmp) && BN_check_prime(Y, ctx, cb))
328 goto end;
329 /* (Step 8-10) */
330 if (++i >= imax || !BN_add(Y, Y, r1r2x2))
331 goto err;
332 }
333 }
334end:
335 ret = 1;
336 BN_GENCB_call(cb, 3, 0);
337err:
338 BN_clear(y1);
339 BN_CTX_end(ctx);
340 return ret;
341}
342