]>
Commit | Line | Data |
---|---|---|
8240d5fa SL |
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_lcl.h" | |
33 | #include "internal/bn_int.h" | |
34 | ||
35 | /* | |
36 | * FIPS 186-4 Table B.1. "Min length of auxiliary primes p1, p2, q1, q2". | |
37 | * | |
38 | * Params: | |
39 | * nbits The key size in bits. | |
40 | * Returns: | |
41 | * The minimum size of the auxiliary primes or 0 if nbits is invalid. | |
42 | */ | |
43 | static int bn_rsa_fips186_4_aux_prime_min_size(int nbits) | |
44 | { | |
45 | if (nbits >= 3072) | |
46 | return 171; | |
47 | if (nbits == 2048) | |
48 | return 141; | |
49 | return 0; | |
50 | } | |
51 | ||
52 | /* | |
53 | * FIPS 186-4 Table B.1 "Maximum length of len(p1) + len(p2) and | |
54 | * len(q1) + len(q2) for p,q Probable Primes". | |
55 | * | |
56 | * Params: | |
57 | * nbits The key size in bits. | |
58 | * Returns: | |
59 | * The maximum length or 0 if nbits is invalid. | |
60 | */ | |
61 | static int bn_rsa_fips186_4_aux_prime_max_sum_size_for_prob_primes(int nbits) | |
62 | { | |
63 | if (nbits >= 3072) | |
64 | return 1518; | |
65 | if (nbits == 2048) | |
66 | return 1007; | |
67 | return 0; | |
68 | } | |
69 | ||
70 | /* | |
71 | * FIPS 186-4 Table C.3 for error probability of 2^-100 | |
72 | * Minimum number of Miller Rabin Rounds for p1, p2, q1 & q2. | |
73 | * | |
74 | * Params: | |
75 | * aux_prime_bits The auxiliary prime size in bits. | |
76 | * Returns: | |
77 | * The minimum number of Miller Rabin Rounds for an auxiliary prime, or | |
78 | * 0 if aux_prime_bits is invalid. | |
79 | */ | |
80 | static int bn_rsa_fips186_4_aux_prime_MR_min_checks(int aux_prime_bits) | |
81 | { | |
82 | if (aux_prime_bits > 170) | |
83 | return 27; | |
84 | if (aux_prime_bits > 140) | |
85 | return 32; | |
86 | return 0; /* Error case */ | |
87 | } | |
88 | ||
89 | /* | |
90 | * FIPS 186-4 Table C.3 for error probability of 2^-100 | |
91 | * Minimum number of Miller Rabin Rounds for p, q. | |
92 | * | |
93 | * Params: | |
94 | * nbits The key size in bits. | |
95 | * Returns: | |
96 | * The minimum number of Miller Rabin Rounds required, | |
97 | * or 0 if nbits is invalid. | |
98 | */ | |
99 | int bn_rsa_fips186_4_prime_MR_min_checks(int nbits) | |
100 | { | |
101 | if (nbits >= 3072) /* > 170 */ | |
102 | return 3; | |
103 | if (nbits == 2048) /* > 140 */ | |
104 | return 4; | |
105 | return 0; /* Error case */ | |
106 | } | |
107 | ||
108 | /* | |
109 | * Find the first odd integer that is a probable prime. | |
110 | * | |
111 | * See section FIPS 186-4 B.3.6 (Steps 4.2/5.2). | |
112 | * | |
113 | * Params: | |
114 | * Xp1 The passed in starting point to find a probably prime. | |
115 | * p1 The returned probable prime (first odd integer >= Xp1) | |
116 | * ctx A BN_CTX object. | |
117 | * cb An optional BIGNUM callback. | |
118 | * Returns: 1 on success otherwise it returns 0. | |
119 | */ | |
120 | static int bn_rsa_fips186_4_find_aux_prob_prime(const BIGNUM *Xp1, | |
121 | BIGNUM *p1, BN_CTX *ctx, | |
122 | BN_GENCB *cb) | |
123 | { | |
124 | int ret = 0; | |
125 | int i = 0; | |
126 | int checks = bn_rsa_fips186_4_aux_prime_MR_min_checks(BN_num_bits(Xp1)); | |
127 | ||
128 | if (checks == 0 || BN_copy(p1, Xp1) == NULL) | |
129 | return 0; | |
130 | ||
131 | /* Find the first odd number >= Xp1 that is probably prime */ | |
132 | for(;;) { | |
133 | i++; | |
134 | BN_GENCB_call(cb, 0, i); | |
135 | /* MR test with trial division */ | |
136 | if (BN_is_prime_fasttest_ex(p1, checks, ctx, 1, cb)) | |
137 | break; | |
138 | /* Get next odd number */ | |
139 | if (!BN_add_word(p1, 2)) | |
140 | goto err; | |
141 | } | |
142 | BN_GENCB_call(cb, 2, i); | |
143 | ret = 1; | |
144 | err: | |
145 | return ret; | |
146 | } | |
147 | ||
148 | /* | |
149 | * Generate a probable prime (p or q). | |
150 | * | |
151 | * See FIPS 186-4 B.3.6 (Steps 4 & 5) | |
152 | * | |
153 | * Params: | |
154 | * p The returned probable prime. | |
155 | * Xpout An optionally returned random number used during generation of p. | |
156 | * p1, p2 The returned auxiliary primes. If NULL they are not returned. | |
157 | * Xp An optional passed in value (that is random number used during | |
158 | * generation of p). | |
159 | * Xp1, Xp2 Optional passed in values that are normally generated | |
160 | * internally. Used to find p1, p2. | |
161 | * nlen The bit length of the modulus (the key size). | |
162 | * e The public exponent. | |
163 | * ctx A BN_CTX object. | |
164 | * cb An optional BIGNUM callback. | |
165 | * Returns: 1 on success otherwise it returns 0. | |
166 | */ | |
167 | int bn_rsa_fips186_4_gen_prob_primes(BIGNUM *p, BIGNUM *Xpout, | |
168 | BIGNUM *p1, BIGNUM *p2, | |
169 | const BIGNUM *Xp, const BIGNUM *Xp1, | |
170 | const BIGNUM *Xp2, int nlen, | |
171 | const BIGNUM *e, BN_CTX *ctx, BN_GENCB *cb) | |
172 | { | |
173 | int ret = 0; | |
174 | BIGNUM *p1i = NULL, *p2i = NULL, *Xp1i = NULL, *Xp2i = NULL; | |
175 | int bitlen; | |
176 | ||
177 | if (p == NULL || Xpout == NULL) | |
178 | return 0; | |
179 | ||
180 | BN_CTX_start(ctx); | |
181 | ||
182 | p1i = (p1 != NULL) ? p1 : BN_CTX_get(ctx); | |
183 | p2i = (p2 != NULL) ? p2 : BN_CTX_get(ctx); | |
184 | Xp1i = (Xp1 != NULL) ? (BIGNUM *)Xp1 : BN_CTX_get(ctx); | |
185 | Xp2i = (Xp2 != NULL) ? (BIGNUM *)Xp2 : BN_CTX_get(ctx); | |
186 | if (p1i == NULL || p2i == NULL || Xp1i == NULL || Xp2i == NULL) | |
187 | goto err; | |
188 | ||
189 | bitlen = bn_rsa_fips186_4_aux_prime_min_size(nlen); | |
190 | if (bitlen == 0) | |
191 | goto err; | |
192 | ||
193 | /* (Steps 4.1/5.1): Randomly generate Xp1 if it is not passed in */ | |
194 | if (Xp1 == NULL) { | |
195 | /* Set the top and bottom bits to make it odd and the correct size */ | |
196 | if (!BN_priv_rand(Xp1i, bitlen, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ODD)) | |
197 | goto err; | |
198 | } | |
199 | /* (Steps 4.1/5.1): Randomly generate Xp2 if it is not passed in */ | |
200 | if (Xp2 == NULL) { | |
201 | /* Set the top and bottom bits to make it odd and the correct size */ | |
202 | if (!BN_priv_rand(Xp2i, bitlen, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ODD)) | |
203 | goto err; | |
204 | } | |
205 | ||
206 | /* (Steps 4.2/5.2) - find first auxiliary probable primes */ | |
207 | if (!bn_rsa_fips186_4_find_aux_prob_prime(Xp1i, p1i, ctx, cb) | |
208 | || !bn_rsa_fips186_4_find_aux_prob_prime(Xp2i, p2i, ctx, cb)) | |
209 | goto err; | |
210 | /* (Table B.1) auxiliary prime Max length check */ | |
211 | if ((BN_num_bits(p1i) + BN_num_bits(p2i)) >= | |
212 | bn_rsa_fips186_4_aux_prime_max_sum_size_for_prob_primes(nlen)) | |
213 | goto err; | |
214 | /* (Steps 4.3/5.3) - generate prime */ | |
215 | if (!bn_rsa_fips186_4_derive_prime(p, Xpout, Xp, p1i, p2i, nlen, e, ctx, cb)) | |
216 | goto err; | |
217 | ret = 1; | |
218 | err: | |
219 | /* Zeroize any internally generated values that are not returned */ | |
220 | if (p1 == NULL) | |
221 | BN_clear(p1i); | |
222 | if (p2 == NULL) | |
223 | BN_clear(p2i); | |
224 | if (Xp1 == NULL) | |
225 | BN_clear(Xp1i); | |
226 | if (Xp2 == NULL) | |
227 | BN_clear(Xp2i); | |
228 | BN_CTX_end(ctx); | |
229 | return ret; | |
230 | } | |
231 | ||
232 | /* | |
233 | * Constructs a probable prime (a candidate for p or q) using 2 auxiliary | |
234 | * prime numbers and the Chinese Remainder Theorem. | |
235 | * | |
236 | * See FIPS 186-4 C.9 "Compute a Probable Prime Factor Based on Auxiliary | |
237 | * Primes". Used by FIPS 186-4 B.3.6 Section (4.3) for p and Section (5.3) for q. | |
238 | * | |
239 | * Params: | |
240 | * Y The returned prime factor (private_prime_factor) of the modulus n. | |
241 | * X The returned random number used during generation of the prime factor. | |
242 | * Xin An optional passed in value for X used for testing purposes. | |
243 | * r1 An auxiliary prime. | |
244 | * r2 An auxiliary prime. | |
245 | * nlen The desired length of n (the RSA modulus). | |
246 | * e The public exponent. | |
247 | * ctx A BN_CTX object. | |
248 | * cb An optional BIGNUM callback object. | |
249 | * Returns: 1 on success otherwise it returns 0. | |
250 | * Assumptions: | |
251 | * Y, X, r1, r2, e are not NULL. | |
252 | */ | |
253 | int bn_rsa_fips186_4_derive_prime(BIGNUM *Y, BIGNUM *X, const BIGNUM *Xin, | |
254 | const BIGNUM *r1, const BIGNUM *r2, int nlen, | |
255 | const BIGNUM *e, BN_CTX *ctx, BN_GENCB *cb) | |
256 | { | |
257 | int ret = 0; | |
258 | int i, imax; | |
259 | int bits = nlen >> 1; | |
260 | int checks = bn_rsa_fips186_4_prime_MR_min_checks(nlen); | |
261 | BIGNUM *tmp, *R, *r1r2x2, *y1, *r1x2; | |
262 | ||
263 | if (checks == 0) | |
264 | return 0; | |
265 | BN_CTX_start(ctx); | |
266 | ||
267 | R = BN_CTX_get(ctx); | |
268 | tmp = BN_CTX_get(ctx); | |
269 | r1r2x2 = BN_CTX_get(ctx); | |
270 | y1 = BN_CTX_get(ctx); | |
271 | r1x2 = BN_CTX_get(ctx); | |
272 | if (r1x2 == NULL) | |
273 | goto err; | |
274 | ||
275 | if (Xin != NULL && BN_copy(X, Xin) == NULL) | |
276 | goto err; | |
277 | ||
278 | if (!(BN_lshift1(r1x2, r1) | |
279 | /* (Step 1) GCD(2r1, r2) = 1 */ | |
280 | && BN_gcd(tmp, r1x2, r2, ctx) | |
281 | && BN_is_one(tmp) | |
282 | /* (Step 2) R = ((r2^-1 mod 2r1) * r2) - ((2r1^-1 mod r2)*2r1) */ | |
283 | && BN_mod_inverse(R, r2, r1x2, ctx) | |
284 | && BN_mul(R, R, r2, ctx) /* R = (r2^-1 mod 2r1) * r2 */ | |
285 | && BN_mod_inverse(tmp, r1x2, r2, ctx) | |
286 | && BN_mul(tmp, tmp, r1x2, ctx) /* tmp = (2r1^-1 mod r2)*2r1 */ | |
287 | && BN_sub(R, R, tmp) | |
288 | /* Calculate 2r1r2 */ | |
289 | && BN_mul(r1r2x2, r1x2, r2, ctx))) | |
290 | goto err; | |
291 | /* Make positive by adding the modulus */ | |
292 | if (BN_is_negative(R) && !BN_add(R, R, r1r2x2)) | |
293 | goto err; | |
294 | ||
295 | imax = 5 * bits; /* max = 5/2 * nbits */ | |
296 | for (;;) { | |
297 | if (Xin == NULL) { | |
298 | /* | |
299 | * (Step 3) Choose Random X such that | |
300 | * sqrt(2) * 2^(nlen/2-1) < Random X < (2^(nlen/2)) - 1. | |
301 | * | |
302 | * For the lower bound: | |
303 | * sqrt(2) * 2^(nlen/2 - 1) == sqrt(2)/2 * 2^(nlen/2) | |
304 | * where sqrt(2)/2 = 0.70710678.. = 0.B504FC33F9DE... | |
305 | * so largest number will have B5... as the top byte | |
306 | * Setting the top 2 bits gives 0xC0. | |
307 | */ | |
308 | if (!BN_priv_rand(X, bits, BN_RAND_TOP_TWO, BN_RAND_BOTTOM_ANY)) | |
309 | goto end; | |
310 | } | |
311 | /* (Step 4) Y = X + ((R - X) mod 2r1r2) */ | |
312 | if (!BN_mod_sub(Y, R, X, r1r2x2, ctx) || !BN_add(Y, Y, X)) | |
313 | goto err; | |
314 | /* (Step 5) */ | |
315 | i = 0; | |
316 | for (;;) { | |
317 | /* (Step 6) */ | |
318 | if (BN_num_bits(Y) > bits) { | |
319 | if (Xin == NULL) | |
320 | break; /* Randomly Generated X so Go back to Step 3 */ | |
321 | else | |
322 | goto err; /* X is not random so it will always fail */ | |
323 | } | |
324 | BN_GENCB_call(cb, 0, 2); | |
325 | ||
326 | /* (Step 7) If GCD(Y-1) == 1 & Y is probably prime then return Y */ | |
327 | if (BN_copy(y1, Y) == NULL | |
328 | || !BN_sub_word(y1, 1) | |
329 | || !BN_gcd(tmp, y1, e, ctx)) | |
330 | goto err; | |
331 | if (BN_is_one(tmp) | |
332 | && BN_is_prime_fasttest_ex(Y, checks, ctx, 1, cb)) | |
333 | goto end; | |
334 | /* (Step 8-10) */ | |
335 | if (++i >= imax || !BN_add(Y, Y, r1r2x2)) | |
336 | goto err; | |
337 | } | |
338 | } | |
339 | end: | |
340 | ret = 1; | |
341 | BN_GENCB_call(cb, 3, 0); | |
342 | err: | |
343 | BN_clear(y1); | |
344 | BN_CTX_end(ctx); | |
345 | return ret; | |
346 | } |