1 /*
2 * Copyright 1995-2026 The OpenSSL Project Authors. All Rights Reserved.
3 *
4 * Licensed under the Apache License 2.0 (the "License"). You may not use
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
8 */
9
10 /*
11 * RSA low level APIs are deprecated for public use, but still ok for
12 * internal use.
13 */
14 #include "internal/deprecated.h"
15
16 #include "internal/cryptlib.h"
17 #include "crypto/bn.h"
18 #include "rsa_local.h"
19 #include "internal/constant_time.h"
20 #include <openssl/evp.h>
21 #include <openssl/sha.h>
22 #include <openssl/hmac.h>
23
24 static int rsa_ossl_public_encrypt(int flen, const unsigned char *from,
25 unsigned char *to, RSA *rsa, int padding);
26 static int rsa_ossl_private_encrypt(int flen, const unsigned char *from,
27 unsigned char *to, RSA *rsa, int padding);
28 static int rsa_ossl_public_decrypt(int flen, const unsigned char *from,
29 unsigned char *to, RSA *rsa, int padding);
30 static int rsa_ossl_private_decrypt(int flen, const unsigned char *from,
31 unsigned char *to, RSA *rsa, int padding);
32 static int rsa_ossl_mod_exp(BIGNUM *r0, const BIGNUM *i, RSA *rsa,
33 BN_CTX *ctx);
34 static int rsa_ossl_init(RSA *rsa);
35 static int rsa_ossl_finish(RSA *rsa);
36 #ifdef S390X_MOD_EXP
37 static int rsa_ossl_s390x_mod_exp(BIGNUM *r0, const BIGNUM *i, RSA *rsa,
38 BN_CTX *ctx);
39 static RSA_METHOD rsa_pkcs1_ossl_meth = {
40 "OpenSSL PKCS#1 RSA",
41 rsa_ossl_public_encrypt,
42 rsa_ossl_public_decrypt, /* signature verification */
43 rsa_ossl_private_encrypt, /* signing */
44 rsa_ossl_private_decrypt,
45 rsa_ossl_s390x_mod_exp,
46 s390x_mod_exp,
47 rsa_ossl_init,
48 rsa_ossl_finish,
49 RSA_FLAG_FIPS_METHOD, /* flags */
50 NULL,
51 0, /* rsa_sign */
52 0, /* rsa_verify */
53 NULL, /* rsa_keygen */
54 NULL /* rsa_multi_prime_keygen */
55 };
56 #else
57 static RSA_METHOD rsa_pkcs1_ossl_meth = {
58 "OpenSSL PKCS#1 RSA",
59 rsa_ossl_public_encrypt,
60 rsa_ossl_public_decrypt, /* signature verification */
61 rsa_ossl_private_encrypt, /* signing */
62 rsa_ossl_private_decrypt,
63 rsa_ossl_mod_exp,
64 BN_mod_exp_mont, /* XXX probably we should not use Montgomery
65 * if e == 3 */
66 rsa_ossl_init,
67 rsa_ossl_finish,
68 RSA_FLAG_FIPS_METHOD, /* flags */
69 NULL,
70 0, /* rsa_sign */
71 0, /* rsa_verify */
72 NULL, /* rsa_keygen */
73 NULL /* rsa_multi_prime_keygen */
74 };
75 #endif
76
77 static const RSA_METHOD *default_RSA_meth = &rsa_pkcs1_ossl_meth;
78
RSA_set_default_method(const RSA_METHOD * meth)79 void RSA_set_default_method(const RSA_METHOD *meth)
80 {
81 default_RSA_meth = meth;
82 }
83
RSA_get_default_method(void)84 const RSA_METHOD *RSA_get_default_method(void)
85 {
86 return default_RSA_meth;
87 }
88
RSA_PKCS1_OpenSSL(void)89 const RSA_METHOD *RSA_PKCS1_OpenSSL(void)
90 {
91 return &rsa_pkcs1_ossl_meth;
92 }
93
RSA_null_method(void)94 const RSA_METHOD *RSA_null_method(void)
95 {
96 return NULL;
97 }
98
rsa_ossl_public_encrypt(int flen,const unsigned char * from,unsigned char * to,RSA * rsa,int padding)99 static int rsa_ossl_public_encrypt(int flen, const unsigned char *from,
100 unsigned char *to, RSA *rsa, int padding)
101 {
102 BIGNUM *f, *ret;
103 int i, num = 0, r = -1;
104 unsigned char *buf = NULL;
105 BN_CTX *ctx = NULL;
106
107 if (BN_num_bits(rsa->n) > OPENSSL_RSA_MAX_MODULUS_BITS) {
108 ERR_raise(ERR_LIB_RSA, RSA_R_MODULUS_TOO_LARGE);
109 return -1;
110 }
111
112 if (BN_ucmp(rsa->n, rsa->e) <= 0) {
113 ERR_raise(ERR_LIB_RSA, RSA_R_BAD_E_VALUE);
114 return -1;
115 }
116
117 /* for large moduli, enforce exponent limit */
118 if (BN_num_bits(rsa->n) > OPENSSL_RSA_SMALL_MODULUS_BITS) {
119 if (BN_num_bits(rsa->e) > OPENSSL_RSA_MAX_PUBEXP_BITS) {
120 ERR_raise(ERR_LIB_RSA, RSA_R_BAD_E_VALUE);
121 return -1;
122 }
123 }
124
125 if ((ctx = BN_CTX_new_ex(rsa->libctx)) == NULL)
126 goto err;
127 BN_CTX_start(ctx);
128 f = BN_CTX_get(ctx);
129 ret = BN_CTX_get(ctx);
130 num = BN_num_bytes(rsa->n);
131 buf = OPENSSL_malloc(num);
132 if (ret == NULL || buf == NULL)
133 goto err;
134
135 switch (padding) {
136 case RSA_PKCS1_PADDING:
137 i = ossl_rsa_padding_add_PKCS1_type_2_ex(rsa->libctx, buf, num,
138 from, flen);
139 break;
140 case RSA_PKCS1_OAEP_PADDING:
141 i = ossl_rsa_padding_add_PKCS1_OAEP_mgf1_ex(rsa->libctx, buf, num,
142 from, flen, NULL, 0,
143 NULL, NULL);
144 break;
145 case RSA_NO_PADDING:
146 i = RSA_padding_add_none(buf, num, from, flen);
147 break;
148 default:
149 ERR_raise(ERR_LIB_RSA, RSA_R_UNKNOWN_PADDING_TYPE);
150 goto err;
151 }
152 if (i <= 0)
153 goto err;
154
155 if (BN_bin2bn(buf, num, f) == NULL)
156 goto err;
157
158 #ifdef FIPS_MODULE
159 /*
160 * See SP800-56Br2, section 7.1.1.1
161 * RSAEP: 1 < f < (n – 1).
162 * (where f is the plaintext).
163 *
164 * This bound is somewhat overkill here. RSASVE.GENERATE (7.2.1.2)
165 * regenerates z until 1 < z < n-1, so on that path the plaintext is in
166 * range unconditionally. On the OAEP path the leading 0x00 octet of the
167 * encoding forces m < n-1 unconditionally, while m = 0 or 1 is only
168 * cryptographically negligible, not impossible. The check is kept to
169 * mirror the RSADP bound in rsa_ossl_private_decrypt() and to keep RSAEP
170 * faithful to 7.1.1 of the SP; nothing in the SP relies on it here.
171 */
172 if (padding == RSA_NO_PADDING) {
173 BIGNUM *nminus1 = BN_CTX_get(ctx);
174
175 if (BN_ucmp(f, BN_value_one()) <= 0) {
176 ERR_raise(ERR_LIB_RSA, RSA_R_DATA_TOO_SMALL);
177 goto err;
178 }
179 if (nminus1 == NULL
180 || BN_copy(nminus1, rsa->n) == NULL
181 || !BN_sub_word(nminus1, 1))
182 goto err;
183 if (BN_ucmp(f, nminus1) >= 0) {
184 ERR_raise(ERR_LIB_RSA, RSA_R_DATA_TOO_LARGE_FOR_MODULUS);
185 goto err;
186 }
187 } else
188 #endif
189 {
190 if (BN_ucmp(f, rsa->n) >= 0) {
191 /* usually the padding functions would catch this */
192 ERR_raise(ERR_LIB_RSA, RSA_R_DATA_TOO_LARGE_FOR_MODULUS);
193 goto err;
194 }
195 }
196
197 if (rsa->flags & RSA_FLAG_CACHE_PUBLIC)
198 if (!BN_MONT_CTX_set_locked(&rsa->_method_mod_n, rsa->lock,
199 rsa->n, ctx))
200 goto err;
201
202 if (!rsa->meth->bn_mod_exp(ret, f, rsa->e, rsa->n, ctx,
203 rsa->_method_mod_n))
204 goto err;
205
206 /*
207 * BN_bn2binpad puts in leading 0 bytes if the number is less than
208 * the length of the modulus.
209 */
210 r = BN_bn2binpad(ret, to, num);
211 err:
212 BN_CTX_end(ctx);
213 BN_CTX_free(ctx);
214 OPENSSL_clear_free(buf, num);
215 return r;
216 }
217
rsa_get_blinding(RSA * rsa,int * local,BN_CTX * ctx)218 static BN_BLINDING *rsa_get_blinding(RSA *rsa, int *local, BN_CTX *ctx)
219 {
220 BN_BLINDING *ret;
221
222 if (!CRYPTO_THREAD_read_lock(rsa->lock))
223 return NULL;
224
225 if (rsa->blinding == NULL) {
226 /*
227 * This dance with upgrading the lock from read to write will be
228 * slower in cases of a single use RSA object, but should be
229 * significantly better in multi-thread cases (e.g. servers). It's
230 * probably worth it.
231 */
232 CRYPTO_THREAD_unlock(rsa->lock);
233 if (!CRYPTO_THREAD_write_lock(rsa->lock))
234 return NULL;
235 if (rsa->blinding == NULL)
236 rsa->blinding = RSA_setup_blinding(rsa, ctx);
237 }
238
239 ret = rsa->blinding;
240 if (ret == NULL)
241 goto err;
242
243 if (BN_BLINDING_is_current_thread(ret)) {
244 /* rsa->blinding is ours! */
245
246 *local = 1;
247 } else {
248 /* resort to rsa->mt_blinding instead */
249
250 /*
251 * instructs rsa_blinding_convert(), rsa_blinding_invert() that the
252 * BN_BLINDING is shared, meaning that accesses require locks, and
253 * that the blinding factor must be stored outside the BN_BLINDING
254 */
255 *local = 0;
256
257 if (rsa->mt_blinding == NULL) {
258 CRYPTO_THREAD_unlock(rsa->lock);
259 if (!CRYPTO_THREAD_write_lock(rsa->lock))
260 return NULL;
261 if (rsa->mt_blinding == NULL)
262 rsa->mt_blinding = RSA_setup_blinding(rsa, ctx);
263 }
264 ret = rsa->mt_blinding;
265 }
266
267 err:
268 CRYPTO_THREAD_unlock(rsa->lock);
269 return ret;
270 }
271
rsa_blinding_convert(BN_BLINDING * b,BIGNUM * f,BIGNUM * unblind,BN_CTX * ctx)272 static int rsa_blinding_convert(BN_BLINDING *b, BIGNUM *f, BIGNUM *unblind,
273 BN_CTX *ctx)
274 {
275 if (unblind == NULL) {
276 /*
277 * Local blinding: store the unblinding factor in BN_BLINDING.
278 */
279 return BN_BLINDING_convert_ex(f, NULL, b, ctx);
280 } else {
281 /*
282 * Shared blinding: store the unblinding factor outside BN_BLINDING.
283 */
284 int ret;
285
286 if (!BN_BLINDING_lock(b))
287 return 0;
288
289 ret = BN_BLINDING_convert_ex(f, unblind, b, ctx);
290 BN_BLINDING_unlock(b);
291
292 return ret;
293 }
294 }
295
rsa_blinding_invert(BN_BLINDING * b,BIGNUM * f,BIGNUM * unblind,BN_CTX * ctx)296 static int rsa_blinding_invert(BN_BLINDING *b, BIGNUM *f, BIGNUM *unblind,
297 BN_CTX *ctx)
298 {
299 /*
300 * For local blinding, unblind is set to NULL, and BN_BLINDING_invert_ex
301 * will use the unblinding factor stored in BN_BLINDING. If BN_BLINDING
302 * is shared between threads, unblind must be non-null:
303 * BN_BLINDING_invert_ex will then use the local unblinding factor, and
304 * will only read the modulus from BN_BLINDING. In both cases it's safe
305 * to access the blinding without a lock.
306 */
307 BN_set_flags(f, BN_FLG_CONSTTIME);
308 return BN_BLINDING_invert_ex(f, unblind, b, ctx);
309 }
310
311 /* signing */
rsa_ossl_private_encrypt(int flen,const unsigned char * from,unsigned char * to,RSA * rsa,int padding)312 static int rsa_ossl_private_encrypt(int flen, const unsigned char *from,
313 unsigned char *to, RSA *rsa, int padding)
314 {
315 BIGNUM *f, *ret, *res;
316 int i, num = 0, r = -1;
317 unsigned char *buf = NULL;
318 BN_CTX *ctx = NULL;
319 int local_blinding = 0;
320 /*
321 * Used only if the blinding structure is shared. A non-NULL unblind
322 * instructs rsa_blinding_convert() and rsa_blinding_invert() to store
323 * the unblinding factor outside the blinding structure.
324 */
325 BIGNUM *unblind = NULL;
326 BN_BLINDING *blinding = NULL;
327
328 if ((ctx = BN_CTX_new_ex(rsa->libctx)) == NULL)
329 goto err;
330 BN_CTX_start(ctx);
331 f = BN_CTX_get(ctx);
332 ret = BN_CTX_get(ctx);
333 num = BN_num_bytes(rsa->n);
334 buf = OPENSSL_malloc(num);
335 if (ret == NULL || buf == NULL)
336 goto err;
337
338 switch (padding) {
339 case RSA_PKCS1_PADDING:
340 i = RSA_padding_add_PKCS1_type_1(buf, num, from, flen);
341 break;
342 case RSA_X931_PADDING:
343 i = RSA_padding_add_X931(buf, num, from, flen);
344 break;
345 case RSA_NO_PADDING:
346 i = RSA_padding_add_none(buf, num, from, flen);
347 break;
348 default:
349 ERR_raise(ERR_LIB_RSA, RSA_R_UNKNOWN_PADDING_TYPE);
350 goto err;
351 }
352 if (i <= 0)
353 goto err;
354
355 if (BN_bin2bn(buf, num, f) == NULL)
356 goto err;
357
358 if (BN_ucmp(f, rsa->n) >= 0) {
359 /* usually the padding functions would catch this */
360 ERR_raise(ERR_LIB_RSA, RSA_R_DATA_TOO_LARGE_FOR_MODULUS);
361 goto err;
362 }
363
364 if (rsa->flags & RSA_FLAG_CACHE_PUBLIC)
365 if (!BN_MONT_CTX_set_locked(&rsa->_method_mod_n, rsa->lock,
366 rsa->n, ctx))
367 goto err;
368
369 if (!(rsa->flags & RSA_FLAG_NO_BLINDING)) {
370 blinding = rsa_get_blinding(rsa, &local_blinding, ctx);
371 if (blinding == NULL) {
372 ERR_raise(ERR_LIB_RSA, ERR_R_INTERNAL_ERROR);
373 goto err;
374 }
375 }
376
377 if (blinding != NULL) {
378 if (!local_blinding && ((unblind = BN_CTX_get(ctx)) == NULL)) {
379 ERR_raise(ERR_LIB_RSA, ERR_R_BN_LIB);
380 goto err;
381 }
382 if (!rsa_blinding_convert(blinding, f, unblind, ctx))
383 goto err;
384 }
385
386 if ((rsa->flags & RSA_FLAG_EXT_PKEY) || (rsa->version == RSA_ASN1_VERSION_MULTI) || ((rsa->p != NULL) && (rsa->q != NULL) && (rsa->dmp1 != NULL) && (rsa->dmq1 != NULL) && (rsa->iqmp != NULL))) {
387 if (!rsa->meth->rsa_mod_exp(ret, f, rsa, ctx))
388 goto err;
389 } else {
390 BIGNUM *d = BN_new();
391 if (d == NULL) {
392 ERR_raise(ERR_LIB_RSA, ERR_R_BN_LIB);
393 goto err;
394 }
395 if (rsa->d == NULL) {
396 ERR_raise(ERR_LIB_RSA, RSA_R_MISSING_PRIVATE_KEY);
397 BN_free(d);
398 goto err;
399 }
400 BN_with_flags(d, rsa->d, BN_FLG_CONSTTIME);
401
402 if (!rsa->meth->bn_mod_exp(ret, f, d, rsa->n, ctx,
403 rsa->_method_mod_n)) {
404 BN_free(d);
405 goto err;
406 }
407 /* We MUST free d before any further use of rsa->d */
408 BN_free(d);
409 }
410
411 if (blinding)
412 if (!rsa_blinding_invert(blinding, ret, unblind, ctx))
413 goto err;
414
415 if (padding == RSA_X931_PADDING) {
416 if (!BN_sub(f, rsa->n, ret))
417 goto err;
418 if (BN_cmp(ret, f) > 0)
419 res = f;
420 else
421 res = ret;
422 } else {
423 res = ret;
424 }
425
426 /*
427 * BN_bn2binpad puts in leading 0 bytes if the number is less than
428 * the length of the modulus.
429 */
430 r = BN_bn2binpad(res, to, num);
431 err:
432 BN_CTX_end(ctx);
433 BN_CTX_free(ctx);
434 OPENSSL_clear_free(buf, num);
435 return r;
436 }
437
derive_kdk(int flen,const unsigned char * from,RSA * rsa,unsigned char * buf,int num,unsigned char * kdk)438 static int derive_kdk(int flen, const unsigned char *from, RSA *rsa,
439 unsigned char *buf, int num, unsigned char *kdk)
440 {
441 int ret = 0;
442 HMAC_CTX *hmac = NULL;
443 EVP_MD *md = NULL;
444 unsigned int md_len = SHA256_DIGEST_LENGTH;
445 unsigned char d_hash[SHA256_DIGEST_LENGTH] = { 0 };
446 /*
447 * because we use d as a handle to rsa->d we need to keep it local and
448 * free before any further use of rsa->d
449 */
450 BIGNUM *d = BN_new();
451
452 if (d == NULL) {
453 ERR_raise(ERR_LIB_RSA, ERR_R_CRYPTO_LIB);
454 goto err;
455 }
456 if (rsa->d == NULL) {
457 ERR_raise(ERR_LIB_RSA, RSA_R_MISSING_PRIVATE_KEY);
458 BN_free(d);
459 goto err;
460 }
461 BN_with_flags(d, rsa->d, BN_FLG_CONSTTIME);
462 if (BN_bn2binpad(d, buf, num) < 0) {
463 ERR_raise(ERR_LIB_RSA, ERR_R_INTERNAL_ERROR);
464 BN_free(d);
465 goto err;
466 }
467 BN_free(d);
468
469 /*
470 * we use hardcoded hash so that migrating between versions that use
471 * different hash doesn't provide a Bleichenbacher oracle:
472 * if the attacker can see that different versions return different
473 * messages for the same ciphertext, they'll know that the message is
474 * synthetically generated, which means that the padding check failed
475 */
476 md = EVP_MD_fetch(rsa->libctx, "sha256", NULL);
477 if (md == NULL) {
478 ERR_raise(ERR_LIB_RSA, ERR_R_FETCH_FAILED);
479 goto err;
480 }
481
482 if (EVP_Digest(buf, num, d_hash, NULL, md, NULL) <= 0) {
483 ERR_raise(ERR_LIB_RSA, ERR_R_INTERNAL_ERROR);
484 goto err;
485 }
486
487 hmac = HMAC_CTX_new();
488 if (hmac == NULL) {
489 ERR_raise(ERR_LIB_RSA, ERR_R_CRYPTO_LIB);
490 goto err;
491 }
492
493 if (HMAC_Init_ex(hmac, d_hash, sizeof(d_hash), md, NULL) <= 0) {
494 ERR_raise(ERR_LIB_RSA, ERR_R_INTERNAL_ERROR);
495 goto err;
496 }
497
498 if (flen < num) {
499 memset(buf, 0, num - flen);
500 if (HMAC_Update(hmac, buf, num - flen) <= 0) {
501 ERR_raise(ERR_LIB_RSA, ERR_R_INTERNAL_ERROR);
502 goto err;
503 }
504 }
505 if (HMAC_Update(hmac, from, flen) <= 0) {
506 ERR_raise(ERR_LIB_RSA, ERR_R_INTERNAL_ERROR);
507 goto err;
508 }
509
510 md_len = SHA256_DIGEST_LENGTH;
511 if (HMAC_Final(hmac, kdk, &md_len) <= 0) {
512 ERR_raise(ERR_LIB_RSA, ERR_R_INTERNAL_ERROR);
513 goto err;
514 }
515 ret = 1;
516
517 err:
518 HMAC_CTX_free(hmac);
519 EVP_MD_free(md);
520 return ret;
521 }
522
rsa_ossl_private_decrypt(int flen,const unsigned char * from,unsigned char * to,RSA * rsa,int padding)523 static int rsa_ossl_private_decrypt(int flen, const unsigned char *from,
524 unsigned char *to, RSA *rsa, int padding)
525 {
526 BIGNUM *f, *ret;
527 int j, num = 0, r = -1;
528 unsigned char *buf = NULL;
529 unsigned char kdk[SHA256_DIGEST_LENGTH] = { 0 };
530 BN_CTX *ctx = NULL;
531 int local_blinding = 0;
532 /*
533 * Used only if the blinding structure is shared. A non-NULL unblind
534 * instructs rsa_blinding_convert() and rsa_blinding_invert() to store
535 * the unblinding factor outside the blinding structure.
536 */
537 BIGNUM *unblind = NULL;
538 BN_BLINDING *blinding = NULL;
539
540 /*
541 * we need the value of the private exponent to perform implicit rejection
542 */
543 if ((rsa->flags & RSA_FLAG_EXT_PKEY) && (padding == RSA_PKCS1_PADDING))
544 padding = RSA_PKCS1_NO_IMPLICIT_REJECT_PADDING;
545
546 if ((ctx = BN_CTX_new_ex(rsa->libctx)) == NULL)
547 goto err;
548 BN_CTX_start(ctx);
549 f = BN_CTX_get(ctx);
550 ret = BN_CTX_get(ctx);
551 if (ret == NULL) {
552 ERR_raise(ERR_LIB_RSA, ERR_R_BN_LIB);
553 goto err;
554 }
555 num = BN_num_bytes(rsa->n);
556 buf = OPENSSL_malloc(num);
557 if (buf == NULL)
558 goto err;
559
560 /*
561 * This check was for equality but PGP does evil things and chops off the
562 * top '0' bytes
563 */
564 if (flen > num) {
565 ERR_raise(ERR_LIB_RSA, RSA_R_DATA_GREATER_THAN_MOD_LEN);
566 goto err;
567 }
568
569 if (flen < 1) {
570 ERR_raise(ERR_LIB_RSA, RSA_R_DATA_TOO_SMALL);
571 goto err;
572 }
573
574 /* make data into a big number */
575 if (BN_bin2bn(from, (int)flen, f) == NULL)
576 goto err;
577
578 #ifdef FIPS_MODULE
579 /*
580 * See SP800-56Br2, section 7.1.2.1
581 * RSADP: 1 < f < (n – 1)
582 * (where f is the ciphertext).
583 *
584 * Kept under FIPS_MODULE because SP 800-56B KTS-OAEP (section 9.2) also
585 * decrypts through RSADP and needs this bound in a FIPS build, and there
586 * is no KTS-OAEP-specific path to attach it to. The non-FIPS RSASVE path
587 * applies the same 1 < c < n-1 in rsasve_recover()
588 * (providers/implementations/kem/rsa_kem.c); keep the two in step.
589 */
590 if (padding == RSA_NO_PADDING) {
591 BIGNUM *nminus1 = BN_CTX_get(ctx);
592
593 if (BN_ucmp(f, BN_value_one()) <= 0) {
594 ERR_raise(ERR_LIB_RSA, RSA_R_DATA_TOO_SMALL);
595 goto err;
596 }
597 if (nminus1 == NULL
598 || BN_copy(nminus1, rsa->n) == NULL
599 || !BN_sub_word(nminus1, 1))
600 goto err;
601 if (BN_ucmp(f, nminus1) >= 0) {
602 ERR_raise(ERR_LIB_RSA, RSA_R_DATA_TOO_LARGE_FOR_MODULUS);
603 goto err;
604 }
605 } else
606 #endif
607 {
608 if (BN_ucmp(f, rsa->n) >= 0) {
609 ERR_raise(ERR_LIB_RSA, RSA_R_DATA_TOO_LARGE_FOR_MODULUS);
610 goto err;
611 }
612 }
613 if (rsa->flags & RSA_FLAG_CACHE_PUBLIC)
614 if (!BN_MONT_CTX_set_locked(&rsa->_method_mod_n, rsa->lock,
615 rsa->n, ctx))
616 goto err;
617
618 if (!(rsa->flags & RSA_FLAG_NO_BLINDING)) {
619 blinding = rsa_get_blinding(rsa, &local_blinding, ctx);
620 if (blinding == NULL) {
621 ERR_raise(ERR_LIB_RSA, ERR_R_INTERNAL_ERROR);
622 goto err;
623 }
624 }
625
626 if (blinding != NULL) {
627 if (!local_blinding && ((unblind = BN_CTX_get(ctx)) == NULL)) {
628 ERR_raise(ERR_LIB_RSA, ERR_R_BN_LIB);
629 goto err;
630 }
631 if (!rsa_blinding_convert(blinding, f, unblind, ctx))
632 goto err;
633 }
634
635 /* do the decrypt */
636 if ((rsa->flags & RSA_FLAG_EXT_PKEY) || (rsa->version == RSA_ASN1_VERSION_MULTI) || ((rsa->p != NULL) && (rsa->q != NULL) && (rsa->dmp1 != NULL) && (rsa->dmq1 != NULL) && (rsa->iqmp != NULL))) {
637 if (!rsa->meth->rsa_mod_exp(ret, f, rsa, ctx))
638 goto err;
639 } else {
640 BIGNUM *d = BN_new();
641 if (d == NULL) {
642 ERR_raise(ERR_LIB_RSA, ERR_R_BN_LIB);
643 goto err;
644 }
645 if (rsa->d == NULL) {
646 ERR_raise(ERR_LIB_RSA, RSA_R_MISSING_PRIVATE_KEY);
647 BN_free(d);
648 goto err;
649 }
650 BN_with_flags(d, rsa->d, BN_FLG_CONSTTIME);
651 if (!rsa->meth->bn_mod_exp(ret, f, d, rsa->n, ctx,
652 rsa->_method_mod_n)) {
653 BN_free(d);
654 goto err;
655 }
656 /* We MUST free d before any further use of rsa->d */
657 BN_free(d);
658 }
659
660 if (blinding)
661 if (!rsa_blinding_invert(blinding, ret, unblind, ctx))
662 goto err;
663
664 /*
665 * derive the Key Derivation Key from private exponent and public
666 * ciphertext
667 */
668 if (padding == RSA_PKCS1_PADDING) {
669 if (derive_kdk(flen, from, rsa, buf, num, kdk) == 0)
670 goto err;
671 }
672
673 j = BN_bn2binpad(ret, buf, num);
674 if (j < 0)
675 goto err;
676
677 switch (padding) {
678 case RSA_PKCS1_NO_IMPLICIT_REJECT_PADDING:
679 r = RSA_padding_check_PKCS1_type_2(to, num, buf, j, num);
680 break;
681 case RSA_PKCS1_PADDING:
682 r = ossl_rsa_padding_check_PKCS1_type_2(rsa->libctx, to, num, buf, j, num, kdk);
683 break;
684 case RSA_PKCS1_OAEP_PADDING:
685 r = RSA_padding_check_PKCS1_OAEP(to, num, buf, j, num, NULL, 0);
686 break;
687 case RSA_NO_PADDING:
688 memcpy(to, buf, (r = j));
689 break;
690 default:
691 ERR_raise(ERR_LIB_RSA, RSA_R_UNKNOWN_PADDING_TYPE);
692 goto err;
693 }
694 #ifndef FIPS_MODULE
695 /*
696 * This trick doesn't work in the FIPS provider because libcrypto manages
697 * the error stack. Instead we opt not to put an error on the stack at all
698 * in case of padding failure in the FIPS provider.
699 */
700 ERR_raise(ERR_LIB_RSA, RSA_R_PADDING_CHECK_FAILED);
701 err_clear_last_constant_time(1 & ~constant_time_msb(r));
702 #endif
703
704 err:
705 BN_CTX_end(ctx);
706 BN_CTX_free(ctx);
707 OPENSSL_clear_free(buf, num);
708 return r;
709 }
710
711 /* signature verification */
rsa_ossl_public_decrypt(int flen,const unsigned char * from,unsigned char * to,RSA * rsa,int padding)712 static int rsa_ossl_public_decrypt(int flen, const unsigned char *from,
713 unsigned char *to, RSA *rsa, int padding)
714 {
715 BIGNUM *f, *ret;
716 int i, num = 0, r = -1;
717 unsigned char *buf = NULL;
718 BN_CTX *ctx = NULL;
719
720 if (BN_num_bits(rsa->n) > OPENSSL_RSA_MAX_MODULUS_BITS) {
721 ERR_raise(ERR_LIB_RSA, RSA_R_MODULUS_TOO_LARGE);
722 return -1;
723 }
724
725 if (BN_ucmp(rsa->n, rsa->e) <= 0) {
726 ERR_raise(ERR_LIB_RSA, RSA_R_BAD_E_VALUE);
727 return -1;
728 }
729
730 /* for large moduli, enforce exponent limit */
731 if (BN_num_bits(rsa->n) > OPENSSL_RSA_SMALL_MODULUS_BITS) {
732 if (BN_num_bits(rsa->e) > OPENSSL_RSA_MAX_PUBEXP_BITS) {
733 ERR_raise(ERR_LIB_RSA, RSA_R_BAD_E_VALUE);
734 return -1;
735 }
736 }
737
738 if ((ctx = BN_CTX_new_ex(rsa->libctx)) == NULL)
739 goto err;
740 BN_CTX_start(ctx);
741 f = BN_CTX_get(ctx);
742 ret = BN_CTX_get(ctx);
743 if (ret == NULL) {
744 ERR_raise(ERR_LIB_RSA, ERR_R_BN_LIB);
745 goto err;
746 }
747 num = BN_num_bytes(rsa->n);
748 buf = OPENSSL_malloc(num);
749 if (buf == NULL)
750 goto err;
751
752 /*
753 * This check was for equality but PGP does evil things and chops off the
754 * top '0' bytes
755 */
756 if (flen > num) {
757 ERR_raise(ERR_LIB_RSA, RSA_R_DATA_GREATER_THAN_MOD_LEN);
758 goto err;
759 }
760
761 if (BN_bin2bn(from, flen, f) == NULL)
762 goto err;
763
764 if (BN_ucmp(f, rsa->n) >= 0) {
765 ERR_raise(ERR_LIB_RSA, RSA_R_DATA_TOO_LARGE_FOR_MODULUS);
766 goto err;
767 }
768
769 if (rsa->flags & RSA_FLAG_CACHE_PUBLIC)
770 if (!BN_MONT_CTX_set_locked(&rsa->_method_mod_n, rsa->lock,
771 rsa->n, ctx))
772 goto err;
773
774 if (!rsa->meth->bn_mod_exp(ret, f, rsa->e, rsa->n, ctx,
775 rsa->_method_mod_n))
776 goto err;
777
778 /* For X9.31: Assuming e is odd it does a 12 mod 16 test */
779 if ((padding == RSA_X931_PADDING) && ((bn_get_words(ret)[0] & 0xf) != 12))
780 if (!BN_sub(ret, rsa->n, ret))
781 goto err;
782
783 i = BN_bn2binpad(ret, buf, num);
784 if (i < 0)
785 goto err;
786
787 switch (padding) {
788 case RSA_PKCS1_PADDING:
789 r = RSA_padding_check_PKCS1_type_1(to, num, buf, i, num);
790 break;
791 case RSA_X931_PADDING:
792 r = RSA_padding_check_X931(to, num, buf, i, num);
793 break;
794 case RSA_NO_PADDING:
795 memcpy(to, buf, (r = i));
796 break;
797 default:
798 ERR_raise(ERR_LIB_RSA, RSA_R_UNKNOWN_PADDING_TYPE);
799 goto err;
800 }
801 if (r < 0)
802 ERR_raise(ERR_LIB_RSA, RSA_R_PADDING_CHECK_FAILED);
803
804 err:
805 BN_CTX_end(ctx);
806 BN_CTX_free(ctx);
807 OPENSSL_clear_free(buf, num);
808 return r;
809 }
810
rsa_ossl_mod_exp(BIGNUM * r0,const BIGNUM * I,RSA * rsa,BN_CTX * ctx)811 static int rsa_ossl_mod_exp(BIGNUM *r0, const BIGNUM *I, RSA *rsa, BN_CTX *ctx)
812 {
813 BIGNUM *r1, *m1, *vrfy;
814 int ret = 0, smooth = 0;
815 #ifndef FIPS_MODULE
816 BIGNUM *r2, *m[RSA_MAX_PRIME_NUM - 2];
817 int i, ex_primes = 0;
818 RSA_PRIME_INFO *pinfo;
819 #endif
820
821 BN_CTX_start(ctx);
822
823 r1 = BN_CTX_get(ctx);
824 #ifndef FIPS_MODULE
825 r2 = BN_CTX_get(ctx);
826 #endif
827 m1 = BN_CTX_get(ctx);
828 vrfy = BN_CTX_get(ctx);
829 if (vrfy == NULL)
830 goto err;
831
832 #ifndef FIPS_MODULE
833 if (rsa->version == RSA_ASN1_VERSION_MULTI
834 && ((ex_primes = sk_RSA_PRIME_INFO_num(rsa->prime_infos)) <= 0
835 || ex_primes > RSA_MAX_PRIME_NUM - 2))
836 goto err;
837 #endif
838
839 if (rsa->flags & RSA_FLAG_CACHE_PRIVATE) {
840 BIGNUM *factor = BN_new();
841
842 if (factor == NULL)
843 goto err;
844
845 /*
846 * Make sure BN_mod_inverse in Montgomery initialization uses the
847 * BN_FLG_CONSTTIME flag
848 */
849 if (!(BN_with_flags(factor, rsa->p, BN_FLG_CONSTTIME),
850 BN_MONT_CTX_set_locked(&rsa->_method_mod_p, rsa->lock,
851 factor, ctx))
852 || !(BN_with_flags(factor, rsa->q, BN_FLG_CONSTTIME),
853 BN_MONT_CTX_set_locked(&rsa->_method_mod_q, rsa->lock,
854 factor, ctx))) {
855 BN_free(factor);
856 goto err;
857 }
858 #ifndef FIPS_MODULE
859 for (i = 0; i < ex_primes; i++) {
860 pinfo = sk_RSA_PRIME_INFO_value(rsa->prime_infos, i);
861 BN_with_flags(factor, pinfo->r, BN_FLG_CONSTTIME);
862 if (!BN_MONT_CTX_set_locked(&pinfo->m, rsa->lock, factor, ctx)) {
863 BN_free(factor);
864 goto err;
865 }
866 }
867 #endif
868 /*
869 * We MUST free |factor| before any further use of the prime factors
870 */
871 BN_free(factor);
872
873 smooth = (rsa->meth->bn_mod_exp == BN_mod_exp_mont)
874 #ifndef FIPS_MODULE
875 && (ex_primes == 0)
876 #endif
877 && (BN_num_bits(rsa->q) == BN_num_bits(rsa->p));
878 }
879
880 if (rsa->flags & RSA_FLAG_CACHE_PUBLIC)
881 if (!BN_MONT_CTX_set_locked(&rsa->_method_mod_n, rsa->lock,
882 rsa->n, ctx))
883 goto err;
884
885 if (smooth) {
886 /*
887 * Conversion from Montgomery domain, a.k.a. Montgomery reduction,
888 * accepts values in [0-m*2^w) range. w is m's bit width rounded up
889 * to limb width. So that at the very least if |I| is fully reduced,
890 * i.e. less than p*q, we can count on from-to round to perform
891 * below modulo operations on |I|. Unlike BN_mod it's constant time.
892 */
893 if (/* m1 = I moq q */
894 !bn_from_mont_fixed_top(m1, I, rsa->_method_mod_q, ctx)
895 || !bn_to_mont_fixed_top(m1, m1, rsa->_method_mod_q, ctx)
896 /* r1 = I mod p */
897 || !bn_from_mont_fixed_top(r1, I, rsa->_method_mod_p, ctx)
898 || !bn_to_mont_fixed_top(r1, r1, rsa->_method_mod_p, ctx)
899 /*
900 * Use parallel exponentiations optimization if possible,
901 * otherwise fallback to two sequential exponentiations:
902 * m1 = m1^dmq1 mod q
903 * r1 = r1^dmp1 mod p
904 */
905 || !BN_mod_exp_mont_consttime_x2(m1, m1, rsa->dmq1, rsa->q,
906 rsa->_method_mod_q,
907 r1, r1, rsa->dmp1, rsa->p,
908 rsa->_method_mod_p,
909 ctx)
910 /* r1 = (r1 - m1) mod p */
911 /*
912 * bn_mod_sub_fixed_top is not regular modular subtraction,
913 * it can tolerate subtrahend to be larger than modulus, but
914 * not bit-wise wider. This makes up for uncommon q>p case,
915 * when |m1| can be larger than |rsa->p|.
916 */
917 || !bn_mod_sub_fixed_top(r1, r1, m1, rsa->p)
918
919 /* r1 = r1 * iqmp mod p */
920 || !bn_to_mont_fixed_top(r1, r1, rsa->_method_mod_p, ctx)
921 || !bn_mul_mont_fixed_top(r1, r1, rsa->iqmp, rsa->_method_mod_p,
922 ctx)
923 /* r0 = r1 * q + m1 */
924 || !bn_mul_fixed_top(r0, r1, rsa->q, ctx)
925 || !bn_mod_add_fixed_top(r0, r0, m1, rsa->n))
926 goto err;
927
928 goto tail;
929 }
930
931 /* compute I mod q */
932 {
933 BIGNUM *c = BN_new();
934 if (c == NULL)
935 goto err;
936 BN_with_flags(c, I, BN_FLG_CONSTTIME);
937
938 if (!BN_mod(r1, c, rsa->q, ctx)) {
939 BN_free(c);
940 goto err;
941 }
942
943 {
944 BIGNUM *dmq1 = BN_new();
945 if (dmq1 == NULL) {
946 BN_free(c);
947 goto err;
948 }
949 BN_with_flags(dmq1, rsa->dmq1, BN_FLG_CONSTTIME);
950
951 /* compute r1^dmq1 mod q */
952 if (!rsa->meth->bn_mod_exp(m1, r1, dmq1, rsa->q, ctx,
953 rsa->_method_mod_q)) {
954 BN_free(c);
955 BN_free(dmq1);
956 goto err;
957 }
958 /* We MUST free dmq1 before any further use of rsa->dmq1 */
959 BN_free(dmq1);
960 }
961
962 /* compute I mod p */
963 if (!BN_mod(r1, c, rsa->p, ctx)) {
964 BN_free(c);
965 goto err;
966 }
967 /* We MUST free c before any further use of I */
968 BN_free(c);
969 }
970
971 {
972 BIGNUM *dmp1 = BN_new();
973 if (dmp1 == NULL)
974 goto err;
975 BN_with_flags(dmp1, rsa->dmp1, BN_FLG_CONSTTIME);
976
977 /* compute r1^dmp1 mod p */
978 if (!rsa->meth->bn_mod_exp(r0, r1, dmp1, rsa->p, ctx,
979 rsa->_method_mod_p)) {
980 BN_free(dmp1);
981 goto err;
982 }
983 /* We MUST free dmp1 before any further use of rsa->dmp1 */
984 BN_free(dmp1);
985 }
986
987 #ifndef FIPS_MODULE
988 if (ex_primes > 0) {
989 BIGNUM *di = BN_new(), *cc = BN_new();
990
991 if (cc == NULL || di == NULL) {
992 BN_free(cc);
993 BN_free(di);
994 goto err;
995 }
996
997 for (i = 0; i < ex_primes; i++) {
998 /* prepare m_i */
999 if ((m[i] = BN_CTX_get(ctx)) == NULL) {
1000 BN_free(cc);
1001 BN_free(di);
1002 goto err;
1003 }
1004
1005 pinfo = sk_RSA_PRIME_INFO_value(rsa->prime_infos, i);
1006
1007 /* prepare c and d_i */
1008 BN_with_flags(cc, I, BN_FLG_CONSTTIME);
1009 BN_with_flags(di, pinfo->d, BN_FLG_CONSTTIME);
1010
1011 if (!BN_mod(r1, cc, pinfo->r, ctx)) {
1012 BN_free(cc);
1013 BN_free(di);
1014 goto err;
1015 }
1016 /* compute r1 ^ d_i mod r_i */
1017 if (!rsa->meth->bn_mod_exp(m[i], r1, di, pinfo->r, ctx, pinfo->m)) {
1018 BN_free(cc);
1019 BN_free(di);
1020 goto err;
1021 }
1022 }
1023
1024 BN_free(cc);
1025 BN_free(di);
1026 }
1027 #endif
1028
1029 if (!BN_sub(r0, r0, m1))
1030 goto err;
1031 /*
1032 * This will help stop the size of r0 increasing, which does affect the
1033 * multiply if it optimised for a power of 2 size
1034 */
1035 if (BN_is_negative(r0))
1036 if (!BN_add(r0, r0, rsa->p))
1037 goto err;
1038
1039 if (!BN_mul(r1, r0, rsa->iqmp, ctx))
1040 goto err;
1041
1042 {
1043 BIGNUM *pr1 = BN_new();
1044 if (pr1 == NULL)
1045 goto err;
1046 BN_with_flags(pr1, r1, BN_FLG_CONSTTIME);
1047
1048 if (!BN_mod(r0, pr1, rsa->p, ctx)) {
1049 BN_free(pr1);
1050 goto err;
1051 }
1052 /* We MUST free pr1 before any further use of r1 */
1053 BN_free(pr1);
1054 }
1055
1056 /*
1057 * If p < q it is occasionally possible for the correction of adding 'p'
1058 * if r0 is negative above to leave the result still negative. This can
1059 * break the private key operations: the following second correction
1060 * should *always* correct this rare occurrence. This will *never* happen
1061 * with OpenSSL generated keys because they ensure p > q [steve]
1062 */
1063 if (BN_is_negative(r0))
1064 if (!BN_add(r0, r0, rsa->p))
1065 goto err;
1066 if (!BN_mul(r1, r0, rsa->q, ctx))
1067 goto err;
1068 if (!BN_add(r0, r1, m1))
1069 goto err;
1070
1071 #ifndef FIPS_MODULE
1072 /* add m_i to m in multi-prime case */
1073 if (ex_primes > 0) {
1074 BIGNUM *pr2 = BN_new();
1075
1076 if (pr2 == NULL)
1077 goto err;
1078
1079 for (i = 0; i < ex_primes; i++) {
1080 pinfo = sk_RSA_PRIME_INFO_value(rsa->prime_infos, i);
1081 if (!BN_sub(r1, m[i], r0)) {
1082 BN_free(pr2);
1083 goto err;
1084 }
1085
1086 if (!BN_mul(r2, r1, pinfo->t, ctx)) {
1087 BN_free(pr2);
1088 goto err;
1089 }
1090
1091 BN_with_flags(pr2, r2, BN_FLG_CONSTTIME);
1092
1093 if (!BN_mod(r1, pr2, pinfo->r, ctx)) {
1094 BN_free(pr2);
1095 goto err;
1096 }
1097
1098 if (BN_is_negative(r1))
1099 if (!BN_add(r1, r1, pinfo->r)) {
1100 BN_free(pr2);
1101 goto err;
1102 }
1103 if (!BN_mul(r1, r1, pinfo->pp, ctx)) {
1104 BN_free(pr2);
1105 goto err;
1106 }
1107 if (!BN_add(r0, r0, r1)) {
1108 BN_free(pr2);
1109 goto err;
1110 }
1111 }
1112 BN_free(pr2);
1113 }
1114 #endif
1115
1116 tail:
1117 if (rsa->e && rsa->n) {
1118 if (rsa->meth->bn_mod_exp == BN_mod_exp_mont) {
1119 if (!BN_mod_exp_mont(vrfy, r0, rsa->e, rsa->n, ctx,
1120 rsa->_method_mod_n))
1121 goto err;
1122 } else {
1123 bn_correct_top(r0);
1124 if (!rsa->meth->bn_mod_exp(vrfy, r0, rsa->e, rsa->n, ctx,
1125 rsa->_method_mod_n))
1126 goto err;
1127 }
1128 /*
1129 * If 'I' was greater than (or equal to) rsa->n, the operation will
1130 * be equivalent to using 'I mod n'. However, the result of the
1131 * verify will *always* be less than 'n' so we don't check for
1132 * absolute equality, just congruency.
1133 */
1134 if (!BN_sub(vrfy, vrfy, I))
1135 goto err;
1136 if (BN_is_zero(vrfy)) {
1137 bn_correct_top(r0);
1138 ret = 1;
1139 goto err; /* not actually error */
1140 }
1141 if (!BN_mod(vrfy, vrfy, rsa->n, ctx))
1142 goto err;
1143 if (BN_is_negative(vrfy))
1144 if (!BN_add(vrfy, vrfy, rsa->n))
1145 goto err;
1146 if (!BN_is_zero(vrfy)) {
1147 /*
1148 * 'I' and 'vrfy' aren't congruent mod n. Don't leak
1149 * miscalculated CRT output, just do a raw (slower) mod_exp and
1150 * return that instead.
1151 */
1152
1153 BIGNUM *d = BN_new();
1154 if (d == NULL)
1155 goto err;
1156 BN_with_flags(d, rsa->d, BN_FLG_CONSTTIME);
1157
1158 if (!rsa->meth->bn_mod_exp(r0, I, d, rsa->n, ctx,
1159 rsa->_method_mod_n)) {
1160 BN_free(d);
1161 goto err;
1162 }
1163 /* We MUST free d before any further use of rsa->d */
1164 BN_free(d);
1165 }
1166 }
1167 /*
1168 * It's unfortunate that we have to bn_correct_top(r0). What hopefully
1169 * saves the day is that correction is highly unlike, and private key
1170 * operations are customarily performed on blinded message. Which means
1171 * that attacker won't observe correlation with chosen plaintext.
1172 * Secondly, remaining code would still handle it in same computational
1173 * time and even conceal memory access pattern around corrected top.
1174 */
1175 bn_correct_top(r0);
1176 ret = 1;
1177 err:
1178 BN_CTX_end(ctx);
1179 return ret;
1180 }
1181
rsa_ossl_init(RSA * rsa)1182 static int rsa_ossl_init(RSA *rsa)
1183 {
1184 rsa->flags |= RSA_FLAG_CACHE_PUBLIC | RSA_FLAG_CACHE_PRIVATE;
1185 return 1;
1186 }
1187
rsa_ossl_finish(RSA * rsa)1188 static int rsa_ossl_finish(RSA *rsa)
1189 {
1190 #ifndef FIPS_MODULE
1191 int i;
1192 RSA_PRIME_INFO *pinfo;
1193
1194 for (i = 0; i < sk_RSA_PRIME_INFO_num(rsa->prime_infos); i++) {
1195 pinfo = sk_RSA_PRIME_INFO_value(rsa->prime_infos, i);
1196 BN_MONT_CTX_free(pinfo->m);
1197 }
1198 #endif
1199
1200 BN_MONT_CTX_free(rsa->_method_mod_n);
1201 BN_MONT_CTX_free(rsa->_method_mod_p);
1202 BN_MONT_CTX_free(rsa->_method_mod_q);
1203 return 1;
1204 }
1205
1206 #ifdef S390X_MOD_EXP
rsa_ossl_s390x_mod_exp(BIGNUM * r0,const BIGNUM * i,RSA * rsa,BN_CTX * ctx)1207 static int rsa_ossl_s390x_mod_exp(BIGNUM *r0, const BIGNUM *i, RSA *rsa,
1208 BN_CTX *ctx)
1209 {
1210 if (rsa->version != RSA_ASN1_VERSION_MULTI) {
1211 if (s390x_crt(r0, i, rsa->p, rsa->q, rsa->dmp1, rsa->dmq1, rsa->iqmp) == 1)
1212 return 1;
1213 }
1214 return rsa_ossl_mod_exp(r0, i, rsa, ctx);
1215 }
1216
1217 #endif
1218