]>
Commit | Line | Data |
---|---|---|
2039c421 | 1 | /* |
da1c088f | 2 | * Copyright 1995-2023 The OpenSSL Project Authors. All Rights Reserved. |
0f113f3e | 3 | * |
2a7b6f39 | 4 | * Licensed under the Apache License 2.0 (the "License"). You may not use |
2039c421 RS |
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 | |
d02b48c6 RE |
8 | */ |
9 | ||
0f113f3e MC |
10 | /* |
11 | * NB: these functions have been "upgraded", the deprecated versions (which | |
12 | * are compatibility wrappers using these functions) are in rsa_depr.c. - | |
13 | * Geoff | |
e9224c71 GT |
14 | */ |
15 | ||
c5f87134 P |
16 | /* |
17 | * RSA low level APIs are deprecated for public use, but still ok for | |
18 | * internal use. | |
19 | */ | |
20 | #include "internal/deprecated.h" | |
21 | ||
d02b48c6 RE |
22 | #include <stdio.h> |
23 | #include <time.h> | |
b39fc560 | 24 | #include "internal/cryptlib.h" |
ec577822 | 25 | #include <openssl/bn.h> |
47c239c6 | 26 | #include <openssl/self_test.h> |
35e6ea3b | 27 | #include "prov/providercommon.h" |
706457b7 | 28 | #include "rsa_local.h" |
d02b48c6 | 29 | |
47c239c6 | 30 | static int rsa_keygen_pairwise_test(RSA *rsa, OSSL_CALLBACK *cb, void *cbarg); |
b4250010 | 31 | static int rsa_keygen(OSSL_LIB_CTX *libctx, RSA *rsa, int bits, int primes, |
47c239c6 | 32 | BIGNUM *e_value, BN_GENCB *cb, int pairwise_test); |
2814c629 | 33 | |
0f113f3e MC |
34 | /* |
35 | * NB: this wrapper would normally be placed in rsa_lib.c and the static | |
36 | * implementation would probably be in rsa_eay.c. Nonetheless, is kept here | |
37 | * so that we don't introduce a new linker dependency. Eg. any application | |
38 | * that wasn't previously linking object code related to key-generation won't | |
39 | * have to now just because key-generation is part of RSA_METHOD. | |
40 | */ | |
bcfea9fb | 41 | int RSA_generate_key_ex(RSA *rsa, int bits, BIGNUM *e_value, BN_GENCB *cb) |
0f113f3e | 42 | { |
665d899f | 43 | if (rsa->meth->rsa_keygen != NULL) |
0f113f3e | 44 | return rsa->meth->rsa_keygen(rsa, bits, e_value, cb); |
665d899f PY |
45 | |
46 | return RSA_generate_multi_prime_key(rsa, bits, RSA_DEFAULT_PRIME_NUM, | |
47 | e_value, cb); | |
0f113f3e MC |
48 | } |
49 | ||
665d899f PY |
50 | int RSA_generate_multi_prime_key(RSA *rsa, int bits, int primes, |
51 | BIGNUM *e_value, BN_GENCB *cb) | |
52 | { | |
f844f9eb | 53 | #ifndef FIPS_MODULE |
665d899f | 54 | /* multi-prime is only supported with the builtin key generation */ |
e44480cc | 55 | if (rsa->meth->rsa_multi_prime_keygen != NULL) { |
665d899f PY |
56 | return rsa->meth->rsa_multi_prime_keygen(rsa, bits, primes, |
57 | e_value, cb); | |
e44480cc AP |
58 | } else if (rsa->meth->rsa_keygen != NULL) { |
59 | /* | |
60 | * However, if rsa->meth implements only rsa_keygen, then we | |
61 | * have to honour it in 2-prime case and assume that it wouldn't | |
62 | * know what to do with multi-prime key generated by builtin | |
63 | * subroutine... | |
64 | */ | |
65 | if (primes == 2) | |
66 | return rsa->meth->rsa_keygen(rsa, bits, e_value, cb); | |
67 | else | |
68 | return 0; | |
69 | } | |
6f04bcc7 | 70 | #endif /* FIPS_MODULE */ |
4f2271d5 | 71 | return rsa_keygen(rsa->libctx, rsa, bits, primes, e_value, cb, 0); |
665d899f PY |
72 | } |
73 | ||
f3be5366 NH |
74 | DEFINE_STACK_OF(BIGNUM) |
75 | ||
76 | /* | |
77 | * Given input values, q, p, n, d and e, derive the exponents | |
78 | * and coefficients for each prime in this key, placing the result | |
79 | * on their respective exps and coeffs stacks | |
80 | */ | |
8bf37709 | 81 | #ifndef FIPS_MODULE |
f3be5366 NH |
82 | int ossl_rsa_multiprime_derive(RSA *rsa, int bits, int primes, |
83 | BIGNUM *e_value, | |
84 | STACK_OF(BIGNUM) *factors, | |
85 | STACK_OF(BIGNUM) *exps, | |
86 | STACK_OF(BIGNUM) *coeffs) | |
87 | { | |
88 | STACK_OF(BIGNUM) *pplist = NULL, *pdlist = NULL; | |
89 | BIGNUM *factor = NULL, *newpp = NULL, *newpd = NULL; | |
90 | BIGNUM *dval = NULL, *newexp = NULL, *newcoeff = NULL; | |
91 | BIGNUM *p = NULL, *q = NULL; | |
92 | BIGNUM *dmp1 = NULL, *dmq1 = NULL, *iqmp = NULL; | |
93 | BIGNUM *r0 = NULL, *r1 = NULL, *r2 = NULL; | |
94 | BN_CTX *ctx = NULL; | |
95 | BIGNUM *tmp = NULL; | |
96 | int i; | |
97 | int ret = 0; | |
98 | ||
99 | ctx = BN_CTX_new_ex(rsa->libctx); | |
100 | if (ctx == NULL) | |
101 | goto err; | |
102 | ||
103 | BN_CTX_start(ctx); | |
104 | ||
105 | pplist = sk_BIGNUM_new_null(); | |
106 | if (pplist == NULL) | |
107 | goto err; | |
108 | ||
109 | pdlist = sk_BIGNUM_new_null(); | |
110 | if (pdlist == NULL) | |
111 | goto err; | |
112 | ||
113 | r0 = BN_CTX_get(ctx); | |
114 | r1 = BN_CTX_get(ctx); | |
115 | r2 = BN_CTX_get(ctx); | |
116 | ||
117 | if (r2 == NULL) | |
118 | goto err; | |
119 | ||
120 | BN_set_flags(r0, BN_FLG_CONSTTIME); | |
121 | BN_set_flags(r1, BN_FLG_CONSTTIME); | |
122 | BN_set_flags(r2, BN_FLG_CONSTTIME); | |
123 | ||
124 | if (BN_copy(r1, rsa->n) == NULL) | |
125 | goto err; | |
126 | ||
127 | p = sk_BIGNUM_value(factors, 0); | |
128 | q = sk_BIGNUM_value(factors, 1); | |
129 | ||
130 | /* Build list of partial products of primes */ | |
131 | for (i = 0; i < sk_BIGNUM_num(factors); i++) { | |
132 | switch (i) { | |
133 | case 0: | |
134 | /* our first prime, p */ | |
135 | if (!BN_sub(r2, p, BN_value_one())) | |
136 | goto err; | |
137 | BN_set_flags(r2, BN_FLG_CONSTTIME); | |
138 | if (BN_mod_inverse(r1, r2, rsa->e, ctx) == NULL) | |
139 | goto err; | |
140 | break; | |
141 | case 1: | |
142 | /* second prime q */ | |
143 | if (!BN_mul(r1, p, q, ctx)) | |
144 | goto err; | |
145 | tmp = BN_dup(r1); | |
146 | if (tmp == NULL) | |
147 | goto err; | |
148 | if (!sk_BIGNUM_insert(pplist, tmp, sk_BIGNUM_num(pplist))) | |
149 | goto err; | |
150 | break; | |
151 | default: | |
152 | factor = sk_BIGNUM_value(factors, i); | |
153 | /* all other primes */ | |
154 | if (!BN_mul(r1, r1, factor, ctx)) | |
155 | goto err; | |
156 | tmp = BN_dup(r1); | |
157 | if (tmp == NULL) | |
158 | goto err; | |
159 | if (!sk_BIGNUM_insert(pplist, tmp, sk_BIGNUM_num(pplist))) | |
160 | goto err; | |
161 | break; | |
162 | } | |
163 | } | |
164 | ||
165 | /* build list of relative d values */ | |
166 | /* p -1 */ | |
167 | if (!BN_sub(r1, p, BN_value_one())) | |
168 | goto err; | |
169 | if (!BN_sub(r2, q, BN_value_one())) | |
170 | goto err; | |
171 | if (!BN_mul(r0, r1, r2, ctx)) | |
172 | goto err; | |
173 | for (i = 2; i < sk_BIGNUM_num(factors); i++) { | |
174 | factor = sk_BIGNUM_value(factors, i); | |
175 | dval = BN_new(); | |
176 | if (dval == NULL) | |
177 | goto err; | |
178 | BN_set_flags(dval, BN_FLG_CONSTTIME); | |
179 | if (!BN_sub(dval, factor, BN_value_one())) | |
180 | goto err; | |
181 | if (!BN_mul(r0, r0, dval, ctx)) | |
182 | goto err; | |
183 | if (!sk_BIGNUM_insert(pdlist, dval, sk_BIGNUM_num(pdlist))) | |
184 | goto err; | |
185 | } | |
186 | ||
187 | /* Calculate dmp1, dmq1 and additional exponents */ | |
188 | dmp1 = BN_secure_new(); | |
189 | if (dmp1 == NULL) | |
190 | goto err; | |
191 | dmq1 = BN_secure_new(); | |
192 | if (dmq1 == NULL) | |
193 | goto err; | |
194 | ||
195 | if (!BN_mod(dmp1, rsa->d, r1, ctx)) | |
196 | goto err; | |
197 | if (!sk_BIGNUM_insert(exps, dmp1, sk_BIGNUM_num(exps))) | |
198 | goto err; | |
199 | dmp1 = NULL; | |
200 | ||
201 | if (!BN_mod(dmq1, rsa->d, r2, ctx)) | |
202 | goto err; | |
203 | if (!sk_BIGNUM_insert(exps, dmq1, sk_BIGNUM_num(exps))) | |
204 | goto err; | |
205 | dmq1 = NULL; | |
206 | ||
207 | for (i = 2; i < sk_BIGNUM_num(factors); i++) { | |
208 | newpd = sk_BIGNUM_value(pdlist, i - 2); | |
209 | newexp = BN_new(); | |
210 | if (newexp == NULL) | |
211 | goto err; | |
212 | if (!BN_mod(newexp, rsa->d, newpd, ctx)) { | |
213 | BN_free(newexp); | |
214 | goto err; | |
215 | } | |
216 | if (!sk_BIGNUM_insert(exps, newexp, sk_BIGNUM_num(exps))) | |
217 | goto err; | |
218 | } | |
219 | ||
220 | /* Calculate iqmp and additional coefficients */ | |
221 | iqmp = BN_new(); | |
222 | if (iqmp == NULL) | |
223 | goto err; | |
224 | ||
225 | if (BN_mod_inverse(iqmp, sk_BIGNUM_value(factors, 1), | |
226 | sk_BIGNUM_value(factors, 0), ctx) == NULL) | |
227 | goto err; | |
228 | if (!sk_BIGNUM_insert(coeffs, iqmp, sk_BIGNUM_num(coeffs))) | |
229 | goto err; | |
230 | iqmp = NULL; | |
231 | ||
232 | for (i = 2; i < sk_BIGNUM_num(factors); i++) { | |
233 | newpp = sk_BIGNUM_value(pplist, i - 2); | |
234 | newcoeff = BN_new(); | |
235 | if (newcoeff == NULL) | |
236 | goto err; | |
237 | if (BN_mod_inverse(newcoeff, newpp, sk_BIGNUM_value(factors, i), | |
238 | ctx) == NULL) { | |
239 | BN_free(newcoeff); | |
240 | goto err; | |
241 | } | |
242 | if (!sk_BIGNUM_insert(coeffs, newcoeff, sk_BIGNUM_num(coeffs))) | |
243 | goto err; | |
244 | } | |
245 | ||
246 | ret = 1; | |
247 | err: | |
248 | sk_BIGNUM_pop_free(pplist, BN_free); | |
249 | sk_BIGNUM_pop_free(pdlist, BN_free); | |
250 | BN_CTX_end(ctx); | |
251 | BN_CTX_free(ctx); | |
252 | BN_clear_free(dmp1); | |
253 | BN_clear_free(dmq1); | |
254 | BN_clear_free(iqmp); | |
255 | return ret; | |
256 | } | |
257 | ||
8bf37709 SL |
258 | static int rsa_multiprime_keygen(RSA *rsa, int bits, int primes, |
259 | BIGNUM *e_value, BN_GENCB *cb) | |
0f113f3e | 260 | { |
f3be5366 | 261 | BIGNUM *r0 = NULL, *r1 = NULL, *r2 = NULL, *tmp, *tmp2, *prime; |
47c239c6 | 262 | int n = 0, bitsr[RSA_MAX_PRIME_NUM], bitse = 0; |
665d899f PY |
263 | int i = 0, quo = 0, rmd = 0, adj = 0, retries = 0; |
264 | RSA_PRIME_INFO *pinfo = NULL; | |
265 | STACK_OF(RSA_PRIME_INFO) *prime_infos = NULL; | |
f3be5366 NH |
266 | STACK_OF(BIGNUM) *factors = NULL; |
267 | STACK_OF(BIGNUM) *exps = NULL; | |
268 | STACK_OF(BIGNUM) *coeffs = NULL; | |
0f113f3e | 269 | BN_CTX *ctx = NULL; |
665d899f | 270 | BN_ULONG bitst = 0; |
8db7946e | 271 | unsigned long error = 0; |
8bf37709 | 272 | int ok = -1; |
665d899f | 273 | |
cac19d19 | 274 | if (bits < RSA_MIN_MODULUS_BITS) { |
9311d0c4 | 275 | ERR_raise(ERR_LIB_RSA, RSA_R_KEY_SIZE_TOO_SMALL); |
7efc653c | 276 | return 0; |
277 | } | |
278 | if (e_value == NULL) { | |
279 | ERR_raise(ERR_LIB_RSA, RSA_R_BAD_E_VALUE); | |
280 | return 0; | |
69795831 | 281 | } |
8bf37709 | 282 | /* A bad value for e can cause infinite loops */ |
7efc653c | 283 | if (!ossl_rsa_check_public_exponent(e_value)) { |
9311d0c4 | 284 | ERR_raise(ERR_LIB_RSA, RSA_R_PUB_EXPONENT_OUT_OF_RANGE); |
8bf37709 SL |
285 | return 0; |
286 | } | |
287 | ||
4158b0dc | 288 | if (primes < RSA_DEFAULT_PRIME_NUM || primes > ossl_rsa_multip_cap(bits)) { |
9311d0c4 | 289 | ERR_raise(ERR_LIB_RSA, RSA_R_KEY_PRIME_NUM_INVALID); |
7efc653c | 290 | return 0; |
665d899f PY |
291 | } |
292 | ||
f3be5366 NH |
293 | factors = sk_BIGNUM_new_null(); |
294 | if (factors == NULL) | |
295 | return 0; | |
296 | ||
297 | exps = sk_BIGNUM_new_null(); | |
298 | if (exps == NULL) | |
299 | goto err; | |
300 | ||
301 | coeffs = sk_BIGNUM_new_null(); | |
302 | if (coeffs == NULL) | |
303 | goto err; | |
304 | ||
d11f644b | 305 | ctx = BN_CTX_new_ex(rsa->libctx); |
0f113f3e MC |
306 | if (ctx == NULL) |
307 | goto err; | |
308 | BN_CTX_start(ctx); | |
309 | r0 = BN_CTX_get(ctx); | |
310 | r1 = BN_CTX_get(ctx); | |
311 | r2 = BN_CTX_get(ctx); | |
665d899f PY |
312 | if (r2 == NULL) |
313 | goto err; | |
314 | ||
315 | /* divide bits into 'primes' pieces evenly */ | |
316 | quo = bits / primes; | |
317 | rmd = bits % primes; | |
318 | ||
665d899f PY |
319 | for (i = 0; i < primes; i++) |
320 | bitsr[i] = (i < rmd) ? quo + 1 : quo; | |
0f113f3e | 321 | |
29be6023 RL |
322 | rsa->dirty_cnt++; |
323 | ||
0f113f3e MC |
324 | /* We need the RSA components non-NULL */ |
325 | if (!rsa->n && ((rsa->n = BN_new()) == NULL)) | |
326 | goto err; | |
74924dcb | 327 | if (!rsa->d && ((rsa->d = BN_secure_new()) == NULL)) |
0f113f3e | 328 | goto err; |
d4bf0d57 | 329 | BN_set_flags(rsa->d, BN_FLG_CONSTTIME); |
0f113f3e MC |
330 | if (!rsa->e && ((rsa->e = BN_new()) == NULL)) |
331 | goto err; | |
74924dcb | 332 | if (!rsa->p && ((rsa->p = BN_secure_new()) == NULL)) |
0f113f3e | 333 | goto err; |
d4bf0d57 | 334 | BN_set_flags(rsa->p, BN_FLG_CONSTTIME); |
74924dcb | 335 | if (!rsa->q && ((rsa->q = BN_secure_new()) == NULL)) |
0f113f3e | 336 | goto err; |
d4bf0d57 | 337 | BN_set_flags(rsa->q, BN_FLG_CONSTTIME); |
0f113f3e | 338 | |
665d899f PY |
339 | /* initialize multi-prime components */ |
340 | if (primes > RSA_DEFAULT_PRIME_NUM) { | |
341 | rsa->version = RSA_ASN1_VERSION_MULTI; | |
342 | prime_infos = sk_RSA_PRIME_INFO_new_reserve(NULL, primes - 2); | |
343 | if (prime_infos == NULL) | |
344 | goto err; | |
345 | if (rsa->prime_infos != NULL) { | |
346 | /* could this happen? */ | |
4158b0dc SL |
347 | sk_RSA_PRIME_INFO_pop_free(rsa->prime_infos, |
348 | ossl_rsa_multip_info_free); | |
665d899f PY |
349 | } |
350 | rsa->prime_infos = prime_infos; | |
351 | ||
352 | /* prime_info from 2 to |primes| -1 */ | |
353 | for (i = 2; i < primes; i++) { | |
4158b0dc | 354 | pinfo = ossl_rsa_multip_info_new(); |
665d899f PY |
355 | if (pinfo == NULL) |
356 | goto err; | |
357 | (void)sk_RSA_PRIME_INFO_push(prime_infos, pinfo); | |
358 | } | |
359 | } | |
360 | ||
78e09b53 RS |
361 | if (BN_copy(rsa->e, e_value) == NULL) |
362 | goto err; | |
0f113f3e | 363 | |
665d899f PY |
364 | /* generate p, q and other primes (if any) */ |
365 | for (i = 0; i < primes; i++) { | |
366 | adj = 0; | |
367 | retries = 0; | |
368 | ||
369 | if (i == 0) { | |
370 | prime = rsa->p; | |
371 | } else if (i == 1) { | |
372 | prime = rsa->q; | |
373 | } else { | |
374 | pinfo = sk_RSA_PRIME_INFO_value(prime_infos, i - 2); | |
375 | prime = pinfo->r; | |
376 | } | |
54f007af | 377 | BN_set_flags(prime, BN_FLG_CONSTTIME); |
665d899f PY |
378 | |
379 | for (;;) { | |
380 | redo: | |
d11f644b JS |
381 | if (!BN_generate_prime_ex2(prime, bitsr[i] + adj, 0, NULL, NULL, |
382 | cb, ctx)) | |
665d899f PY |
383 | goto err; |
384 | /* | |
385 | * prime should not be equal to p, q, r_3... | |
386 | * (those primes prior to this one) | |
387 | */ | |
388 | { | |
389 | int j; | |
390 | ||
391 | for (j = 0; j < i; j++) { | |
392 | BIGNUM *prev_prime; | |
393 | ||
394 | if (j == 0) | |
395 | prev_prime = rsa->p; | |
396 | else if (j == 1) | |
397 | prev_prime = rsa->q; | |
398 | else | |
399 | prev_prime = sk_RSA_PRIME_INFO_value(prime_infos, | |
400 | j - 2)->r; | |
401 | ||
402 | if (!BN_cmp(prime, prev_prime)) { | |
403 | goto redo; | |
404 | } | |
405 | } | |
406 | } | |
407 | if (!BN_sub(r2, prime, BN_value_one())) | |
408 | goto err; | |
8db7946e SW |
409 | ERR_set_mark(); |
410 | BN_set_flags(r2, BN_FLG_CONSTTIME); | |
411 | if (BN_mod_inverse(r1, r2, rsa->e, ctx) != NULL) { | |
f3be5366 | 412 | /* GCD == 1 since inverse exists */ |
665d899f | 413 | break; |
8db7946e SW |
414 | } |
415 | error = ERR_peek_last_error(); | |
416 | if (ERR_GET_LIB(error) == ERR_LIB_BN | |
417 | && ERR_GET_REASON(error) == BN_R_NO_INVERSE) { | |
418 | /* GCD != 1 */ | |
419 | ERR_pop_to_mark(); | |
420 | } else { | |
421 | goto err; | |
422 | } | |
665d899f PY |
423 | if (!BN_GENCB_call(cb, 2, n++)) |
424 | goto err; | |
425 | } | |
426 | ||
427 | bitse += bitsr[i]; | |
428 | ||
429 | /* calculate n immediately to see if it's sufficient */ | |
430 | if (i == 1) { | |
431 | /* we get at least 2 primes */ | |
432 | if (!BN_mul(r1, rsa->p, rsa->q, ctx)) | |
433 | goto err; | |
434 | } else if (i != 0) { | |
435 | /* modulus n = p * q * r_3 * r_4 ... */ | |
436 | if (!BN_mul(r1, rsa->n, prime, ctx)) | |
437 | goto err; | |
438 | } else { | |
439 | /* i == 0, do nothing */ | |
440 | if (!BN_GENCB_call(cb, 3, i)) | |
441 | goto err; | |
f3be5366 NH |
442 | tmp = BN_dup(prime); |
443 | if (tmp == NULL) | |
444 | goto err; | |
445 | if (!sk_BIGNUM_insert(factors, tmp, sk_BIGNUM_num(factors))) | |
446 | goto err; | |
665d899f PY |
447 | continue; |
448 | } | |
f3be5366 | 449 | |
665d899f PY |
450 | /* |
451 | * if |r1|, product of factors so far, is not as long as expected | |
452 | * (by checking the first 4 bits are less than 0x9 or greater than | |
453 | * 0xF). If so, re-generate the last prime. | |
454 | * | |
455 | * NOTE: This actually can't happen in two-prime case, because of | |
456 | * the way factors are generated. | |
457 | * | |
458 | * Besides, another consideration is, for multi-prime case, even the | |
459 | * length modulus is as long as expected, the modulus could start at | |
460 | * 0x8, which could be utilized to distinguish a multi-prime private | |
461 | * key by using the modulus in a certificate. This is also covered | |
462 | * by checking the length should not be less than 0x9. | |
463 | */ | |
464 | if (!BN_rshift(r2, r1, bitse - 4)) | |
0f113f3e | 465 | goto err; |
665d899f PY |
466 | bitst = BN_get_word(r2); |
467 | ||
468 | if (bitst < 0x9 || bitst > 0xF) { | |
469 | /* | |
470 | * For keys with more than 4 primes, we attempt longer factor to | |
471 | * meet length requirement. | |
472 | * | |
473 | * Otherwise, we just re-generate the prime with the same length. | |
474 | * | |
475 | * This strategy has the following goals: | |
476 | * | |
c2969ff6 | 477 | * 1. 1024-bit factors are efficient when using 3072 and 4096-bit key |
665d899f PY |
478 | * 2. stay the same logic with normal 2-prime key |
479 | */ | |
480 | bitse -= bitsr[i]; | |
481 | if (!BN_GENCB_call(cb, 2, n++)) | |
0f113f3e | 482 | goto err; |
665d899f PY |
483 | if (primes > 4) { |
484 | if (bitst < 0x9) | |
485 | adj++; | |
486 | else | |
487 | adj--; | |
488 | } else if (retries == 4) { | |
489 | /* | |
490 | * re-generate all primes from scratch, mainly used | |
491 | * in 4 prime case to avoid long loop. Max retry times | |
492 | * is set to 4. | |
493 | */ | |
494 | i = -1; | |
495 | bitse = 0; | |
f3be5366 NH |
496 | sk_BIGNUM_pop_free(factors, BN_clear_free); |
497 | factors = sk_BIGNUM_new_null(); | |
498 | if (factors == NULL) | |
499 | goto err; | |
665d899f PY |
500 | continue; |
501 | } | |
502 | retries++; | |
503 | goto redo; | |
504 | } | |
505 | /* save product of primes for further use, for multi-prime only */ | |
506 | if (i > 1 && BN_copy(pinfo->pp, rsa->n) == NULL) | |
0f113f3e | 507 | goto err; |
665d899f | 508 | if (BN_copy(rsa->n, r1) == NULL) |
0f113f3e | 509 | goto err; |
665d899f | 510 | if (!BN_GENCB_call(cb, 3, i)) |
0f113f3e | 511 | goto err; |
f3be5366 NH |
512 | tmp = BN_dup(prime); |
513 | if (tmp == NULL) | |
514 | goto err; | |
515 | if (!sk_BIGNUM_insert(factors, tmp, sk_BIGNUM_num(factors))) | |
516 | goto err; | |
0f113f3e | 517 | } |
665d899f | 518 | |
0f113f3e MC |
519 | if (BN_cmp(rsa->p, rsa->q) < 0) { |
520 | tmp = rsa->p; | |
521 | rsa->p = rsa->q; | |
522 | rsa->q = tmp; | |
f3be5366 NH |
523 | /* mirror this in our factor stack */ |
524 | if (!sk_BIGNUM_insert(factors, sk_BIGNUM_delete(factors, 0), 1)) | |
525 | goto err; | |
0f113f3e MC |
526 | } |
527 | ||
0f113f3e | 528 | /* calculate d */ |
665d899f PY |
529 | |
530 | /* p - 1 */ | |
0f113f3e | 531 | if (!BN_sub(r1, rsa->p, BN_value_one())) |
665d899f PY |
532 | goto err; |
533 | /* q - 1 */ | |
0f113f3e | 534 | if (!BN_sub(r2, rsa->q, BN_value_one())) |
665d899f PY |
535 | goto err; |
536 | /* (p - 1)(q - 1) */ | |
0f113f3e | 537 | if (!BN_mul(r0, r1, r2, ctx)) |
665d899f PY |
538 | goto err; |
539 | /* multi-prime */ | |
540 | for (i = 2; i < primes; i++) { | |
541 | pinfo = sk_RSA_PRIME_INFO_value(prime_infos, i - 2); | |
542 | /* save r_i - 1 to pinfo->d temporarily */ | |
543 | if (!BN_sub(pinfo->d, pinfo->r, BN_value_one())) | |
544 | goto err; | |
545 | if (!BN_mul(r0, r0, pinfo->d, ctx)) | |
546 | goto err; | |
547 | } | |
548 | ||
5584f65a | 549 | |
f3be5366 NH |
550 | BN_set_flags(r0, BN_FLG_CONSTTIME); |
551 | if (BN_mod_inverse(rsa->d, rsa->e, r0, ctx) == NULL) { | |
552 | goto err; /* d */ | |
fd7d2520 | 553 | } |
0f113f3e | 554 | |
f3be5366 NH |
555 | /* derive any missing exponents and coefficients */ |
556 | if (!ossl_rsa_multiprime_derive(rsa, bits, primes, e_value, | |
557 | factors, exps, coeffs)) | |
558 | goto err; | |
5584f65a | 559 | |
f3be5366 NH |
560 | /* |
561 | * first 2 factors/exps are already tracked in p/q/dmq1/dmp1 | |
562 | * and the first coeff is in iqmp, so pop those off the stack | |
563 | * Note, the first 2 factors/exponents are already tracked by p and q | |
564 | * assign dmp1/dmq1 and iqmp | |
565 | * the remaining pinfo values are separately allocated, so copy and delete | |
566 | * those | |
567 | */ | |
568 | BN_clear_free(sk_BIGNUM_delete(factors, 0)); | |
569 | BN_clear_free(sk_BIGNUM_delete(factors, 0)); | |
570 | rsa->dmp1 = sk_BIGNUM_delete(exps, 0); | |
571 | rsa->dmq1 = sk_BIGNUM_delete(exps, 0); | |
572 | rsa->iqmp = sk_BIGNUM_delete(coeffs, 0); | |
573 | for (i = 2; i < primes; i++) { | |
574 | pinfo = sk_RSA_PRIME_INFO_value(prime_infos, i - 2); | |
575 | tmp = sk_BIGNUM_delete(factors, 0); | |
576 | BN_copy(pinfo->r, tmp); | |
577 | BN_clear_free(tmp); | |
578 | tmp = sk_BIGNUM_delete(exps, 0); | |
579 | tmp2 = BN_copy(pinfo->d, tmp); | |
580 | BN_clear_free(tmp); | |
581 | if (tmp2 == NULL) | |
5584f65a | 582 | goto err; |
f3be5366 NH |
583 | tmp = sk_BIGNUM_delete(coeffs, 0); |
584 | tmp2 = BN_copy(pinfo->t, tmp); | |
585 | BN_clear_free(tmp); | |
586 | if (tmp2 == NULL) | |
fd7d2520 | 587 | goto err; |
fd7d2520 | 588 | } |
0f113f3e MC |
589 | ok = 1; |
590 | err: | |
f3be5366 NH |
591 | sk_BIGNUM_free(factors); |
592 | sk_BIGNUM_free(exps); | |
593 | sk_BIGNUM_free(coeffs); | |
0f113f3e | 594 | if (ok == -1) { |
c5689319 | 595 | ERR_raise(ERR_LIB_RSA, ERR_R_BN_LIB); |
0f113f3e MC |
596 | ok = 0; |
597 | } | |
ce1415ed | 598 | BN_CTX_end(ctx); |
23a1d5e9 | 599 | BN_CTX_free(ctx); |
8bf37709 SL |
600 | return ok; |
601 | } | |
602 | #endif /* FIPS_MODULE */ | |
603 | ||
b4250010 | 604 | static int rsa_keygen(OSSL_LIB_CTX *libctx, RSA *rsa, int bits, int primes, |
8bf37709 SL |
605 | BIGNUM *e_value, BN_GENCB *cb, int pairwise_test) |
606 | { | |
607 | int ok = 0; | |
608 | ||
27c1cfd7 | 609 | #ifdef FIPS_MODULE |
610 | ok = ossl_rsa_sp800_56b_generate_key(rsa, bits, e_value, cb); | |
611 | pairwise_test = 1; /* FIPS MODE needs to always run the pairwise test */ | |
612 | #else | |
8bf37709 | 613 | /* |
27c1cfd7 | 614 | * Only multi-prime keys or insecure keys with a small key length or a |
615 | * public exponent <= 2^16 will use the older rsa_multiprime_keygen(). | |
8bf37709 | 616 | */ |
27c1cfd7 | 617 | if (primes == 2 |
618 | && bits >= 2048 | |
619 | && (e_value == NULL || BN_num_bits(e_value) > 16)) | |
23b2fc0b | 620 | ok = ossl_rsa_sp800_56b_generate_key(rsa, bits, e_value, cb); |
8bf37709 SL |
621 | else |
622 | ok = rsa_multiprime_keygen(rsa, bits, primes, e_value, cb); | |
f844f9eb | 623 | #endif /* FIPS_MODULE */ |
47c239c6 SL |
624 | |
625 | if (pairwise_test && ok > 0) { | |
626 | OSSL_CALLBACK *stcb = NULL; | |
627 | void *stcbarg = NULL; | |
628 | ||
629 | OSSL_SELF_TEST_get_callback(libctx, &stcb, &stcbarg); | |
630 | ok = rsa_keygen_pairwise_test(rsa, stcb, stcbarg); | |
631 | if (!ok) { | |
35e6ea3b | 632 | ossl_set_error_state(OSSL_SELF_TEST_TYPE_PCT); |
47c239c6 SL |
633 | /* Clear intermediate results */ |
634 | BN_clear_free(rsa->d); | |
635 | BN_clear_free(rsa->p); | |
636 | BN_clear_free(rsa->q); | |
637 | BN_clear_free(rsa->dmp1); | |
638 | BN_clear_free(rsa->dmq1); | |
639 | BN_clear_free(rsa->iqmp); | |
7905806c SL |
640 | rsa->d = NULL; |
641 | rsa->p = NULL; | |
642 | rsa->q = NULL; | |
643 | rsa->dmp1 = NULL; | |
644 | rsa->dmq1 = NULL; | |
645 | rsa->iqmp = NULL; | |
47c239c6 SL |
646 | } |
647 | } | |
648 | return ok; | |
649 | } | |
650 | ||
651 | /* | |
652 | * For RSA key generation it is not known whether the key pair will be used | |
653 | * for key transport or signatures. FIPS 140-2 IG 9.9 states that in this case | |
654 | * either a signature verification OR an encryption operation may be used to | |
655 | * perform the pairwise consistency check. The simpler encrypt/decrypt operation | |
656 | * has been chosen for this case. | |
657 | */ | |
658 | static int rsa_keygen_pairwise_test(RSA *rsa, OSSL_CALLBACK *cb, void *cbarg) | |
659 | { | |
660 | int ret = 0; | |
661 | unsigned int ciphertxt_len; | |
662 | unsigned char *ciphertxt = NULL; | |
663 | const unsigned char plaintxt[16] = {0}; | |
1ee04b79 | 664 | unsigned char *decoded = NULL; |
47c239c6 SL |
665 | unsigned int decoded_len; |
666 | unsigned int plaintxt_len = (unsigned int)sizeof(plaintxt_len); | |
667 | int padding = RSA_PKCS1_PADDING; | |
668 | OSSL_SELF_TEST *st = NULL; | |
669 | ||
670 | st = OSSL_SELF_TEST_new(cb, cbarg); | |
671 | if (st == NULL) | |
672 | goto err; | |
673 | OSSL_SELF_TEST_onbegin(st, OSSL_SELF_TEST_TYPE_PCT, | |
674 | OSSL_SELF_TEST_DESC_PCT_RSA_PKCS1); | |
675 | ||
676 | ciphertxt_len = RSA_size(rsa); | |
1ee04b79 SL |
677 | /* |
678 | * RSA_private_encrypt() and RSA_private_decrypt() requires the 'to' | |
679 | * parameter to be a maximum of RSA_size() - allocate space for both. | |
680 | */ | |
681 | ciphertxt = OPENSSL_zalloc(ciphertxt_len * 2); | |
47c239c6 SL |
682 | if (ciphertxt == NULL) |
683 | goto err; | |
1ee04b79 | 684 | decoded = ciphertxt + ciphertxt_len; |
47c239c6 SL |
685 | |
686 | ciphertxt_len = RSA_public_encrypt(plaintxt_len, plaintxt, ciphertxt, rsa, | |
687 | padding); | |
688 | if (ciphertxt_len <= 0) | |
689 | goto err; | |
690 | if (ciphertxt_len == plaintxt_len | |
70e18f9d | 691 | && memcmp(ciphertxt, plaintxt, plaintxt_len) == 0) |
47c239c6 SL |
692 | goto err; |
693 | ||
694 | OSSL_SELF_TEST_oncorrupt_byte(st, ciphertxt); | |
695 | ||
696 | decoded_len = RSA_private_decrypt(ciphertxt_len, ciphertxt, decoded, rsa, | |
697 | padding); | |
698 | if (decoded_len != plaintxt_len | |
699 | || memcmp(decoded, plaintxt, decoded_len) != 0) | |
700 | goto err; | |
701 | ||
702 | ret = 1; | |
703 | err: | |
704 | OSSL_SELF_TEST_onend(st, ret); | |
705 | OSSL_SELF_TEST_free(st); | |
706 | OPENSSL_free(ciphertxt); | |
707 | ||
708 | return ret; | |
0f113f3e | 709 | } |