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 */ |
43 | static 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 | |
48 | const 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 | */ |
64 | static 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 | */ |
82 | static 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 | */ |
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 | |
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; |
126 | err: |
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 | */ |
149 | int 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; |
202 | err: |
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 | */ |
237 | int 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 | } |
334 | end: |
335 | ret = 1; |
336 | BN_GENCB_call(cb, 3, 0); |
337 | err: |
338 | BN_clear(y1); |
339 | BN_CTX_end(ctx); |
340 | return ret; |
341 | } |
342 | |