2 * Copyright 1995-2016 The OpenSSL Project Authors. All Rights Reserved.
4 * Licensed under the OpenSSL license (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
10 #include "internal/cryptlib.h"
11 #include "internal/bn_int.h"
16 static int rsa_ossl_public_encrypt(int flen, const unsigned char *from,
17 unsigned char *to, RSA *rsa, int padding);
18 static int rsa_ossl_private_encrypt(int flen, const unsigned char *from,
19 unsigned char *to, RSA *rsa, int padding);
20 static int rsa_ossl_public_decrypt(int flen, const unsigned char *from,
21 unsigned char *to, RSA *rsa, int padding);
22 static int rsa_ossl_private_decrypt(int flen, const unsigned char *from,
23 unsigned char *to, RSA *rsa, int padding);
24 static int rsa_ossl_mod_exp(BIGNUM *r0, const BIGNUM *i, RSA *rsa,
26 static int rsa_ossl_init(RSA *rsa);
27 static int rsa_ossl_finish(RSA *rsa);
28 static RSA_METHOD rsa_pkcs1_ossl_meth = {
29 "OpenSSL PKCS#1 RSA (from Eric Young)",
30 rsa_ossl_public_encrypt,
31 rsa_ossl_public_decrypt, /* signature verification */
32 rsa_ossl_private_encrypt, /* signing */
33 rsa_ossl_private_decrypt,
35 BN_mod_exp_mont, /* XXX probably we should not use Montgomery
39 RSA_FLAG_FIPS_METHOD, /* flags */
46 const RSA_METHOD *RSA_PKCS1_OpenSSL(void)
48 return &rsa_pkcs1_ossl_meth;
51 static int rsa_ossl_public_encrypt(int flen, const unsigned char *from,
52 unsigned char *to, RSA *rsa, int padding)
55 int i, j, k, num = 0, r = -1;
56 unsigned char *buf = NULL;
59 if (BN_num_bits(rsa->n) > OPENSSL_RSA_MAX_MODULUS_BITS) {
60 RSAerr(RSA_F_RSA_OSSL_PUBLIC_ENCRYPT, RSA_R_MODULUS_TOO_LARGE);
64 if (BN_ucmp(rsa->n, rsa->e) <= 0) {
65 RSAerr(RSA_F_RSA_OSSL_PUBLIC_ENCRYPT, RSA_R_BAD_E_VALUE);
69 /* for large moduli, enforce exponent limit */
70 if (BN_num_bits(rsa->n) > OPENSSL_RSA_SMALL_MODULUS_BITS) {
71 if (BN_num_bits(rsa->e) > OPENSSL_RSA_MAX_PUBEXP_BITS) {
72 RSAerr(RSA_F_RSA_OSSL_PUBLIC_ENCRYPT, RSA_R_BAD_E_VALUE);
77 if ((ctx = BN_CTX_new()) == NULL)
81 ret = BN_CTX_get(ctx);
82 num = BN_num_bytes(rsa->n);
83 buf = OPENSSL_malloc(num);
84 if (f == NULL || ret == NULL || buf == NULL) {
85 RSAerr(RSA_F_RSA_OSSL_PUBLIC_ENCRYPT, ERR_R_MALLOC_FAILURE);
90 case RSA_PKCS1_PADDING:
91 i = RSA_padding_add_PKCS1_type_2(buf, num, from, flen);
93 case RSA_PKCS1_OAEP_PADDING:
94 i = RSA_padding_add_PKCS1_OAEP(buf, num, from, flen, NULL, 0);
96 case RSA_SSLV23_PADDING:
97 i = RSA_padding_add_SSLv23(buf, num, from, flen);
100 i = RSA_padding_add_none(buf, num, from, flen);
103 RSAerr(RSA_F_RSA_OSSL_PUBLIC_ENCRYPT, RSA_R_UNKNOWN_PADDING_TYPE);
109 if (BN_bin2bn(buf, num, f) == NULL)
112 if (BN_ucmp(f, rsa->n) >= 0) {
113 /* usually the padding functions would catch this */
114 RSAerr(RSA_F_RSA_OSSL_PUBLIC_ENCRYPT,
115 RSA_R_DATA_TOO_LARGE_FOR_MODULUS);
119 if (rsa->flags & RSA_FLAG_CACHE_PUBLIC)
120 if (!BN_MONT_CTX_set_locked
121 (&rsa->_method_mod_n, rsa->lock, rsa->n, ctx))
124 if (!rsa->meth->bn_mod_exp(ret, f, rsa->e, rsa->n, ctx,
129 * put in leading 0 bytes if the number is less than the length of the
132 j = BN_num_bytes(ret);
133 i = BN_bn2bin(ret, &(to[num - j]));
134 for (k = 0; k < (num - i); k++)
142 OPENSSL_clear_free(buf, num);
146 static BN_BLINDING *rsa_get_blinding(RSA *rsa, int *local, BN_CTX *ctx)
150 CRYPTO_THREAD_write_lock(rsa->lock);
152 if (rsa->blinding == NULL) {
153 rsa->blinding = RSA_setup_blinding(rsa, ctx);
160 if (BN_BLINDING_is_current_thread(ret)) {
161 /* rsa->blinding is ours! */
165 /* resort to rsa->mt_blinding instead */
168 * instructs rsa_blinding_convert(), rsa_blinding_invert() that the
169 * BN_BLINDING is shared, meaning that accesses require locks, and
170 * that the blinding factor must be stored outside the BN_BLINDING
174 if (rsa->mt_blinding == NULL) {
175 rsa->mt_blinding = RSA_setup_blinding(rsa, ctx);
177 ret = rsa->mt_blinding;
181 CRYPTO_THREAD_unlock(rsa->lock);
185 static int rsa_blinding_convert(BN_BLINDING *b, BIGNUM *f, BIGNUM *unblind,
190 * Local blinding: store the unblinding factor in BN_BLINDING.
192 return BN_BLINDING_convert_ex(f, NULL, b, ctx);
195 * Shared blinding: store the unblinding factor outside BN_BLINDING.
200 ret = BN_BLINDING_convert_ex(f, unblind, b, ctx);
201 BN_BLINDING_unlock(b);
207 static int rsa_blinding_invert(BN_BLINDING *b, BIGNUM *f, BIGNUM *unblind,
211 * For local blinding, unblind is set to NULL, and BN_BLINDING_invert_ex
212 * will use the unblinding factor stored in BN_BLINDING. If BN_BLINDING
213 * is shared between threads, unblind must be non-null:
214 * BN_BLINDING_invert_ex will then use the local unblinding factor, and
215 * will only read the modulus from BN_BLINDING. In both cases it's safe
216 * to access the blinding without a lock.
218 return BN_BLINDING_invert_ex(f, unblind, b, ctx);
222 static int rsa_ossl_private_encrypt(int flen, const unsigned char *from,
223 unsigned char *to, RSA *rsa, int padding)
225 BIGNUM *f, *ret, *res;
226 int i, j, k, num = 0, r = -1;
227 unsigned char *buf = NULL;
229 int local_blinding = 0;
231 * Used only if the blinding structure is shared. A non-NULL unblind
232 * instructs rsa_blinding_convert() and rsa_blinding_invert() to store
233 * the unblinding factor outside the blinding structure.
235 BIGNUM *unblind = NULL;
236 BN_BLINDING *blinding = NULL;
238 if ((ctx = BN_CTX_new()) == NULL)
242 ret = BN_CTX_get(ctx);
243 num = BN_num_bytes(rsa->n);
244 buf = OPENSSL_malloc(num);
245 if (f == NULL || ret == NULL || buf == NULL) {
246 RSAerr(RSA_F_RSA_OSSL_PRIVATE_ENCRYPT, ERR_R_MALLOC_FAILURE);
251 case RSA_PKCS1_PADDING:
252 i = RSA_padding_add_PKCS1_type_1(buf, num, from, flen);
254 case RSA_X931_PADDING:
255 i = RSA_padding_add_X931(buf, num, from, flen);
258 i = RSA_padding_add_none(buf, num, from, flen);
260 case RSA_SSLV23_PADDING:
262 RSAerr(RSA_F_RSA_OSSL_PRIVATE_ENCRYPT, RSA_R_UNKNOWN_PADDING_TYPE);
268 if (BN_bin2bn(buf, num, f) == NULL)
271 if (BN_ucmp(f, rsa->n) >= 0) {
272 /* usually the padding functions would catch this */
273 RSAerr(RSA_F_RSA_OSSL_PRIVATE_ENCRYPT,
274 RSA_R_DATA_TOO_LARGE_FOR_MODULUS);
278 if (!(rsa->flags & RSA_FLAG_NO_BLINDING)) {
279 blinding = rsa_get_blinding(rsa, &local_blinding, ctx);
280 if (blinding == NULL) {
281 RSAerr(RSA_F_RSA_OSSL_PRIVATE_ENCRYPT, ERR_R_INTERNAL_ERROR);
286 if (blinding != NULL) {
287 if (!local_blinding && ((unblind = BN_CTX_get(ctx)) == NULL)) {
288 RSAerr(RSA_F_RSA_OSSL_PRIVATE_ENCRYPT, ERR_R_MALLOC_FAILURE);
291 if (!rsa_blinding_convert(blinding, f, unblind, ctx))
295 if ((rsa->flags & RSA_FLAG_EXT_PKEY) ||
298 (rsa->dmp1 != NULL) && (rsa->dmq1 != NULL) && (rsa->iqmp != NULL))) {
299 if (!rsa->meth->rsa_mod_exp(ret, f, rsa, ctx))
302 BIGNUM *d = BN_new();
304 RSAerr(RSA_F_RSA_OSSL_PRIVATE_ENCRYPT, ERR_R_MALLOC_FAILURE);
307 BN_with_flags(d, rsa->d, BN_FLG_CONSTTIME);
309 if (rsa->flags & RSA_FLAG_CACHE_PUBLIC)
310 if (!BN_MONT_CTX_set_locked
311 (&rsa->_method_mod_n, rsa->lock, rsa->n, ctx)) {
316 if (!rsa->meth->bn_mod_exp(ret, f, d, rsa->n, ctx,
317 rsa->_method_mod_n)) {
321 /* We MUST free d before any further use of rsa->d */
326 if (!rsa_blinding_invert(blinding, ret, unblind, ctx))
329 if (padding == RSA_X931_PADDING) {
330 BN_sub(f, rsa->n, ret);
331 if (BN_cmp(ret, f) > 0)
339 * put in leading 0 bytes if the number is less than the length of the
342 j = BN_num_bytes(res);
343 i = BN_bn2bin(res, &(to[num - j]));
344 for (k = 0; k < (num - i); k++)
352 OPENSSL_clear_free(buf, num);
356 static int rsa_ossl_private_decrypt(int flen, const unsigned char *from,
357 unsigned char *to, RSA *rsa, int padding)
360 int j, num = 0, r = -1;
362 unsigned char *buf = NULL;
364 int local_blinding = 0;
366 * Used only if the blinding structure is shared. A non-NULL unblind
367 * instructs rsa_blinding_convert() and rsa_blinding_invert() to store
368 * the unblinding factor outside the blinding structure.
370 BIGNUM *unblind = NULL;
371 BN_BLINDING *blinding = NULL;
373 if ((ctx = BN_CTX_new()) == NULL)
377 ret = BN_CTX_get(ctx);
378 num = BN_num_bytes(rsa->n);
379 buf = OPENSSL_malloc(num);
380 if (f == NULL || ret == NULL || buf == NULL) {
381 RSAerr(RSA_F_RSA_OSSL_PRIVATE_DECRYPT, ERR_R_MALLOC_FAILURE);
386 * This check was for equality but PGP does evil things and chops off the
390 RSAerr(RSA_F_RSA_OSSL_PRIVATE_DECRYPT,
391 RSA_R_DATA_GREATER_THAN_MOD_LEN);
395 /* make data into a big number */
396 if (BN_bin2bn(from, (int)flen, f) == NULL)
399 if (BN_ucmp(f, rsa->n) >= 0) {
400 RSAerr(RSA_F_RSA_OSSL_PRIVATE_DECRYPT,
401 RSA_R_DATA_TOO_LARGE_FOR_MODULUS);
405 if (!(rsa->flags & RSA_FLAG_NO_BLINDING)) {
406 blinding = rsa_get_blinding(rsa, &local_blinding, ctx);
407 if (blinding == NULL) {
408 RSAerr(RSA_F_RSA_OSSL_PRIVATE_DECRYPT, ERR_R_INTERNAL_ERROR);
413 if (blinding != NULL) {
414 if (!local_blinding && ((unblind = BN_CTX_get(ctx)) == NULL)) {
415 RSAerr(RSA_F_RSA_OSSL_PRIVATE_DECRYPT, ERR_R_MALLOC_FAILURE);
418 if (!rsa_blinding_convert(blinding, f, unblind, ctx))
423 if ((rsa->flags & RSA_FLAG_EXT_PKEY) ||
426 (rsa->dmp1 != NULL) && (rsa->dmq1 != NULL) && (rsa->iqmp != NULL))) {
427 if (!rsa->meth->rsa_mod_exp(ret, f, rsa, ctx))
430 BIGNUM *d = BN_new();
432 RSAerr(RSA_F_RSA_OSSL_PRIVATE_DECRYPT, ERR_R_MALLOC_FAILURE);
435 BN_with_flags(d, rsa->d, BN_FLG_CONSTTIME);
437 if (rsa->flags & RSA_FLAG_CACHE_PUBLIC)
438 if (!BN_MONT_CTX_set_locked
439 (&rsa->_method_mod_n, rsa->lock, rsa->n, ctx)) {
443 if (!rsa->meth->bn_mod_exp(ret, f, d, rsa->n, ctx,
444 rsa->_method_mod_n)) {
448 /* We MUST free d before any further use of rsa->d */
453 if (!rsa_blinding_invert(blinding, ret, unblind, ctx))
457 j = BN_bn2bin(ret, p); /* j is only used with no-padding mode */
460 case RSA_PKCS1_PADDING:
461 r = RSA_padding_check_PKCS1_type_2(to, num, buf, j, num);
463 case RSA_PKCS1_OAEP_PADDING:
464 r = RSA_padding_check_PKCS1_OAEP(to, num, buf, j, num, NULL, 0);
466 case RSA_SSLV23_PADDING:
467 r = RSA_padding_check_SSLv23(to, num, buf, j, num);
470 r = RSA_padding_check_none(to, num, buf, j, num);
473 RSAerr(RSA_F_RSA_OSSL_PRIVATE_DECRYPT, RSA_R_UNKNOWN_PADDING_TYPE);
477 RSAerr(RSA_F_RSA_OSSL_PRIVATE_DECRYPT, RSA_R_PADDING_CHECK_FAILED);
483 OPENSSL_clear_free(buf, num);
487 /* signature verification */
488 static int rsa_ossl_public_decrypt(int flen, const unsigned char *from,
489 unsigned char *to, RSA *rsa, int padding)
492 int i, num = 0, r = -1;
494 unsigned char *buf = NULL;
497 if (BN_num_bits(rsa->n) > OPENSSL_RSA_MAX_MODULUS_BITS) {
498 RSAerr(RSA_F_RSA_OSSL_PUBLIC_DECRYPT, RSA_R_MODULUS_TOO_LARGE);
502 if (BN_ucmp(rsa->n, rsa->e) <= 0) {
503 RSAerr(RSA_F_RSA_OSSL_PUBLIC_DECRYPT, RSA_R_BAD_E_VALUE);
507 /* for large moduli, enforce exponent limit */
508 if (BN_num_bits(rsa->n) > OPENSSL_RSA_SMALL_MODULUS_BITS) {
509 if (BN_num_bits(rsa->e) > OPENSSL_RSA_MAX_PUBEXP_BITS) {
510 RSAerr(RSA_F_RSA_OSSL_PUBLIC_DECRYPT, RSA_R_BAD_E_VALUE);
515 if ((ctx = BN_CTX_new()) == NULL)
519 ret = BN_CTX_get(ctx);
520 num = BN_num_bytes(rsa->n);
521 buf = OPENSSL_malloc(num);
522 if (f == NULL || ret == NULL || buf == NULL) {
523 RSAerr(RSA_F_RSA_OSSL_PUBLIC_DECRYPT, ERR_R_MALLOC_FAILURE);
528 * This check was for equality but PGP does evil things and chops off the
532 RSAerr(RSA_F_RSA_OSSL_PUBLIC_DECRYPT, RSA_R_DATA_GREATER_THAN_MOD_LEN);
536 if (BN_bin2bn(from, flen, f) == NULL)
539 if (BN_ucmp(f, rsa->n) >= 0) {
540 RSAerr(RSA_F_RSA_OSSL_PUBLIC_DECRYPT,
541 RSA_R_DATA_TOO_LARGE_FOR_MODULUS);
545 if (rsa->flags & RSA_FLAG_CACHE_PUBLIC)
546 if (!BN_MONT_CTX_set_locked
547 (&rsa->_method_mod_n, rsa->lock, rsa->n, ctx))
550 if (!rsa->meth->bn_mod_exp(ret, f, rsa->e, rsa->n, ctx,
554 if ((padding == RSA_X931_PADDING) && ((bn_get_words(ret)[0] & 0xf) != 12))
555 if (!BN_sub(ret, rsa->n, ret))
559 i = BN_bn2bin(ret, p);
562 case RSA_PKCS1_PADDING:
563 r = RSA_padding_check_PKCS1_type_1(to, num, buf, i, num);
565 case RSA_X931_PADDING:
566 r = RSA_padding_check_X931(to, num, buf, i, num);
569 r = RSA_padding_check_none(to, num, buf, i, num);
572 RSAerr(RSA_F_RSA_OSSL_PUBLIC_DECRYPT, RSA_R_UNKNOWN_PADDING_TYPE);
576 RSAerr(RSA_F_RSA_OSSL_PUBLIC_DECRYPT, RSA_R_PADDING_CHECK_FAILED);
582 OPENSSL_clear_free(buf, num);
586 static int rsa_ossl_mod_exp(BIGNUM *r0, const BIGNUM *I, RSA *rsa, BN_CTX *ctx)
588 BIGNUM *r1, *m1, *vrfy;
593 r1 = BN_CTX_get(ctx);
594 m1 = BN_CTX_get(ctx);
595 vrfy = BN_CTX_get(ctx);
598 BIGNUM *p = BN_new(), *q = BN_new();
601 * Make sure BN_mod_inverse in Montgomery initialization uses the
602 * BN_FLG_CONSTTIME flag
604 if (p == NULL || q == NULL) {
609 BN_with_flags(p, rsa->p, BN_FLG_CONSTTIME);
610 BN_with_flags(q, rsa->q, BN_FLG_CONSTTIME);
612 if (rsa->flags & RSA_FLAG_CACHE_PRIVATE) {
613 if (!BN_MONT_CTX_set_locked
614 (&rsa->_method_mod_p, rsa->lock, p, ctx)
615 || !BN_MONT_CTX_set_locked(&rsa->_method_mod_q,
616 rsa->lock, q, ctx)) {
623 * We MUST free p and q before any further use of rsa->p and rsa->q
629 if (rsa->flags & RSA_FLAG_CACHE_PUBLIC)
630 if (!BN_MONT_CTX_set_locked
631 (&rsa->_method_mod_n, rsa->lock, rsa->n, ctx))
634 /* compute I mod q */
636 BIGNUM *c = BN_new();
639 BN_with_flags(c, I, BN_FLG_CONSTTIME);
641 if (!BN_mod(r1, c, rsa->q, ctx)) {
647 BIGNUM *dmq1 = BN_new();
652 BN_with_flags(dmq1, rsa->dmq1, BN_FLG_CONSTTIME);
654 /* compute r1^dmq1 mod q */
655 if (!rsa->meth->bn_mod_exp(m1, r1, dmq1, rsa->q, ctx,
656 rsa->_method_mod_q)) {
661 /* We MUST free dmq1 before any further use of rsa->dmq1 */
665 /* compute I mod p */
666 if (!BN_mod(r1, c, rsa->p, ctx)) {
670 /* We MUST free c before any further use of I */
675 BIGNUM *dmp1 = BN_new();
678 BN_with_flags(dmp1, rsa->dmp1, BN_FLG_CONSTTIME);
680 /* compute r1^dmp1 mod p */
681 if (!rsa->meth->bn_mod_exp(r0, r1, dmp1, rsa->p, ctx,
682 rsa->_method_mod_p)) {
686 /* We MUST free dmp1 before any further use of rsa->dmp1 */
690 if (!BN_sub(r0, r0, m1))
693 * This will help stop the size of r0 increasing, which does affect the
694 * multiply if it optimised for a power of 2 size
696 if (BN_is_negative(r0))
697 if (!BN_add(r0, r0, rsa->p))
700 if (!BN_mul(r1, r0, rsa->iqmp, ctx))
704 BIGNUM *pr1 = BN_new();
707 BN_with_flags(pr1, r1, BN_FLG_CONSTTIME);
709 if (!BN_mod(r0, pr1, rsa->p, ctx)) {
713 /* We MUST free pr1 before any further use of r1 */
718 * If p < q it is occasionally possible for the correction of adding 'p'
719 * if r0 is negative above to leave the result still negative. This can
720 * break the private key operations: the following second correction
721 * should *always* correct this rare occurrence. This will *never* happen
722 * with OpenSSL generated keys because they ensure p > q [steve]
724 if (BN_is_negative(r0))
725 if (!BN_add(r0, r0, rsa->p))
727 if (!BN_mul(r1, r0, rsa->q, ctx))
729 if (!BN_add(r0, r1, m1))
732 if (rsa->e && rsa->n) {
733 if (!rsa->meth->bn_mod_exp(vrfy, r0, rsa->e, rsa->n, ctx,
737 * If 'I' was greater than (or equal to) rsa->n, the operation will
738 * be equivalent to using 'I mod n'. However, the result of the
739 * verify will *always* be less than 'n' so we don't check for
740 * absolute equality, just congruency.
742 if (!BN_sub(vrfy, vrfy, I))
744 if (!BN_mod(vrfy, vrfy, rsa->n, ctx))
746 if (BN_is_negative(vrfy))
747 if (!BN_add(vrfy, vrfy, rsa->n))
749 if (!BN_is_zero(vrfy)) {
751 * 'I' and 'vrfy' aren't congruent mod n. Don't leak
752 * miscalculated CRT output, just do a raw (slower) mod_exp and
753 * return that instead.
756 BIGNUM *d = BN_new();
759 BN_with_flags(d, rsa->d, BN_FLG_CONSTTIME);
761 if (!rsa->meth->bn_mod_exp(r0, I, d, rsa->n, ctx,
762 rsa->_method_mod_n)) {
766 /* We MUST free d before any further use of rsa->d */
776 static int rsa_ossl_init(RSA *rsa)
778 rsa->flags |= RSA_FLAG_CACHE_PUBLIC | RSA_FLAG_CACHE_PRIVATE;
782 static int rsa_ossl_finish(RSA *rsa)
784 BN_MONT_CTX_free(rsa->_method_mod_n);
785 BN_MONT_CTX_free(rsa->_method_mod_p);
786 BN_MONT_CTX_free(rsa->_method_mod_q);