/*
- * Copyright 1995-2020 The OpenSSL Project Authors. All Rights Reserved.
+ * Copyright 1995-2024 The OpenSSL Project Authors. All Rights Reserved.
*
* Licensed under the Apache License 2.0 (the "License"). You may not use
* this file except in compliance with the License. You can obtain a copy
#include "internal/cryptlib.h"
#include <openssl/bn.h>
#include <openssl/self_test.h>
+#include "prov/providercommon.h"
#include "rsa_local.h"
static int rsa_keygen_pairwise_test(RSA *rsa, OSSL_CALLBACK *cb, void *cbarg);
-static int rsa_keygen(OPENSSL_CTX *libctx, RSA *rsa, int bits, int primes,
+static int rsa_keygen(OSSL_LIB_CTX *libctx, RSA *rsa, int bits, int primes,
BIGNUM *e_value, BN_GENCB *cb, int pairwise_test);
/*
else
return 0;
}
-#endif /* FIPS_MODUKE */
+#endif /* FIPS_MODULE */
return rsa_keygen(rsa->libctx, rsa, bits, primes, e_value, cb, 0);
}
+DEFINE_STACK_OF(BIGNUM)
+
+/*
+ * Given input values, q, p, n, d and e, derive the exponents
+ * and coefficients for each prime in this key, placing the result
+ * on their respective exps and coeffs stacks
+ */
#ifndef FIPS_MODULE
+int ossl_rsa_multiprime_derive(RSA *rsa, int bits, int primes,
+ BIGNUM *e_value,
+ STACK_OF(BIGNUM) *factors,
+ STACK_OF(BIGNUM) *exps,
+ STACK_OF(BIGNUM) *coeffs)
+{
+ STACK_OF(BIGNUM) *pplist = NULL, *pdlist = NULL;
+ BIGNUM *factor = NULL, *newpp = NULL, *newpd = NULL;
+ BIGNUM *dval = NULL, *newexp = NULL, *newcoeff = NULL;
+ BIGNUM *p = NULL, *q = NULL;
+ BIGNUM *dmp1 = NULL, *dmq1 = NULL, *iqmp = NULL;
+ BIGNUM *r0 = NULL, *r1 = NULL, *r2 = NULL;
+ BN_CTX *ctx = NULL;
+ BIGNUM *tmp = NULL;
+ int i;
+ int ret = 0;
+
+ ctx = BN_CTX_new_ex(rsa->libctx);
+ if (ctx == NULL)
+ goto err;
+
+ BN_CTX_start(ctx);
+
+ pplist = sk_BIGNUM_new_null();
+ if (pplist == NULL)
+ goto err;
+
+ pdlist = sk_BIGNUM_new_null();
+ if (pdlist == NULL)
+ goto err;
+
+ r0 = BN_CTX_get(ctx);
+ r1 = BN_CTX_get(ctx);
+ r2 = BN_CTX_get(ctx);
+
+ if (r2 == NULL)
+ goto err;
+
+ BN_set_flags(r0, BN_FLG_CONSTTIME);
+ BN_set_flags(r1, BN_FLG_CONSTTIME);
+ BN_set_flags(r2, BN_FLG_CONSTTIME);
+
+ if (BN_copy(r1, rsa->n) == NULL)
+ goto err;
+
+ p = sk_BIGNUM_value(factors, 0);
+ q = sk_BIGNUM_value(factors, 1);
+
+ /* Build list of partial products of primes */
+ for (i = 0; i < sk_BIGNUM_num(factors); i++) {
+ switch (i) {
+ case 0:
+ /* our first prime, p */
+ if (!BN_sub(r2, p, BN_value_one()))
+ goto err;
+ BN_set_flags(r2, BN_FLG_CONSTTIME);
+ if (BN_mod_inverse(r1, r2, rsa->e, ctx) == NULL)
+ goto err;
+ break;
+ case 1:
+ /* second prime q */
+ if (!BN_mul(r1, p, q, ctx))
+ goto err;
+ tmp = BN_dup(r1);
+ if (tmp == NULL)
+ goto err;
+ if (!sk_BIGNUM_insert(pplist, tmp, sk_BIGNUM_num(pplist)))
+ goto err;
+ break;
+ default:
+ factor = sk_BIGNUM_value(factors, i);
+ /* all other primes */
+ if (!BN_mul(r1, r1, factor, ctx))
+ goto err;
+ tmp = BN_dup(r1);
+ if (tmp == NULL)
+ goto err;
+ if (!sk_BIGNUM_insert(pplist, tmp, sk_BIGNUM_num(pplist)))
+ goto err;
+ break;
+ }
+ }
+
+ /* build list of relative d values */
+ /* p -1 */
+ if (!BN_sub(r1, p, BN_value_one()))
+ goto err;
+ if (!BN_sub(r2, q, BN_value_one()))
+ goto err;
+ if (!BN_mul(r0, r1, r2, ctx))
+ goto err;
+ for (i = 2; i < sk_BIGNUM_num(factors); i++) {
+ factor = sk_BIGNUM_value(factors, i);
+ dval = BN_new();
+ if (dval == NULL)
+ goto err;
+ BN_set_flags(dval, BN_FLG_CONSTTIME);
+ if (!BN_sub(dval, factor, BN_value_one()))
+ goto err;
+ if (!BN_mul(r0, r0, dval, ctx))
+ goto err;
+ if (!sk_BIGNUM_insert(pdlist, dval, sk_BIGNUM_num(pdlist)))
+ goto err;
+ }
+
+ /* Calculate dmp1, dmq1 and additional exponents */
+ dmp1 = BN_secure_new();
+ if (dmp1 == NULL)
+ goto err;
+ dmq1 = BN_secure_new();
+ if (dmq1 == NULL)
+ goto err;
+
+ if (!BN_mod(dmp1, rsa->d, r1, ctx))
+ goto err;
+ if (!sk_BIGNUM_insert(exps, dmp1, sk_BIGNUM_num(exps)))
+ goto err;
+ dmp1 = NULL;
+
+ if (!BN_mod(dmq1, rsa->d, r2, ctx))
+ goto err;
+ if (!sk_BIGNUM_insert(exps, dmq1, sk_BIGNUM_num(exps)))
+ goto err;
+ dmq1 = NULL;
+
+ for (i = 2; i < sk_BIGNUM_num(factors); i++) {
+ newpd = sk_BIGNUM_value(pdlist, i - 2);
+ newexp = BN_new();
+ if (newexp == NULL)
+ goto err;
+ if (!BN_mod(newexp, rsa->d, newpd, ctx)) {
+ BN_free(newexp);
+ goto err;
+ }
+ if (!sk_BIGNUM_insert(exps, newexp, sk_BIGNUM_num(exps)))
+ goto err;
+ }
+
+ /* Calculate iqmp and additional coefficients */
+ iqmp = BN_new();
+ if (iqmp == NULL)
+ goto err;
+
+ if (BN_mod_inverse(iqmp, sk_BIGNUM_value(factors, 1),
+ sk_BIGNUM_value(factors, 0), ctx) == NULL)
+ goto err;
+ if (!sk_BIGNUM_insert(coeffs, iqmp, sk_BIGNUM_num(coeffs)))
+ goto err;
+ iqmp = NULL;
+
+ for (i = 2; i < sk_BIGNUM_num(factors); i++) {
+ newpp = sk_BIGNUM_value(pplist, i - 2);
+ newcoeff = BN_new();
+ if (newcoeff == NULL)
+ goto err;
+ if (BN_mod_inverse(newcoeff, newpp, sk_BIGNUM_value(factors, i),
+ ctx) == NULL) {
+ BN_free(newcoeff);
+ goto err;
+ }
+ if (!sk_BIGNUM_insert(coeffs, newcoeff, sk_BIGNUM_num(coeffs)))
+ goto err;
+ }
+
+ ret = 1;
+ err:
+ sk_BIGNUM_pop_free(pplist, BN_free);
+ sk_BIGNUM_pop_free(pdlist, BN_free);
+ BN_CTX_end(ctx);
+ BN_CTX_free(ctx);
+ BN_clear_free(dmp1);
+ BN_clear_free(dmq1);
+ BN_clear_free(iqmp);
+ return ret;
+}
+
static int rsa_multiprime_keygen(RSA *rsa, int bits, int primes,
BIGNUM *e_value, BN_GENCB *cb)
{
- BIGNUM *r0 = NULL, *r1 = NULL, *r2 = NULL, *tmp, *prime;
+ BIGNUM *r0 = NULL, *r1 = NULL, *r2 = NULL, *tmp, *tmp2, *prime;
int n = 0, bitsr[RSA_MAX_PRIME_NUM], bitse = 0;
int i = 0, quo = 0, rmd = 0, adj = 0, retries = 0;
RSA_PRIME_INFO *pinfo = NULL;
STACK_OF(RSA_PRIME_INFO) *prime_infos = NULL;
+ STACK_OF(BIGNUM) *factors = NULL;
+ STACK_OF(BIGNUM) *exps = NULL;
+ STACK_OF(BIGNUM) *coeffs = NULL;
BN_CTX *ctx = NULL;
BN_ULONG bitst = 0;
unsigned long error = 0;
int ok = -1;
if (bits < RSA_MIN_MODULUS_BITS) {
- ok = 0; /* we set our own err */
- RSAerr(0, RSA_R_KEY_SIZE_TOO_SMALL);
- goto err;
+ ERR_raise(ERR_LIB_RSA, RSA_R_KEY_SIZE_TOO_SMALL);
+ return 0;
+ }
+ if (e_value == NULL) {
+ ERR_raise(ERR_LIB_RSA, RSA_R_BAD_E_VALUE);
+ return 0;
}
-
/* A bad value for e can cause infinite loops */
- if (e_value != NULL && !rsa_check_public_exponent(e_value)) {
- RSAerr(0, RSA_R_PUB_EXPONENT_OUT_OF_RANGE);
+ if (!ossl_rsa_check_public_exponent(e_value)) {
+ ERR_raise(ERR_LIB_RSA, RSA_R_PUB_EXPONENT_OUT_OF_RANGE);
return 0;
}
- if (primes < RSA_DEFAULT_PRIME_NUM || primes > rsa_multip_cap(bits)) {
- ok = 0; /* we set our own err */
- RSAerr(0, RSA_R_KEY_PRIME_NUM_INVALID);
- goto err;
+ if (primes < RSA_DEFAULT_PRIME_NUM || primes > ossl_rsa_multip_cap(bits)) {
+ ERR_raise(ERR_LIB_RSA, RSA_R_KEY_PRIME_NUM_INVALID);
+ return 0;
}
- ctx = BN_CTX_new();
+ factors = sk_BIGNUM_new_null();
+ if (factors == NULL)
+ return 0;
+
+ exps = sk_BIGNUM_new_null();
+ if (exps == NULL)
+ goto err;
+
+ coeffs = sk_BIGNUM_new_null();
+ if (coeffs == NULL)
+ goto err;
+
+ ctx = BN_CTX_new_ex(rsa->libctx);
if (ctx == NULL)
goto err;
BN_CTX_start(ctx);
if (!rsa->q && ((rsa->q = BN_secure_new()) == NULL))
goto err;
BN_set_flags(rsa->q, BN_FLG_CONSTTIME);
- if (!rsa->dmp1 && ((rsa->dmp1 = BN_secure_new()) == NULL))
- goto err;
- BN_set_flags(rsa->dmp1, BN_FLG_CONSTTIME);
- if (!rsa->dmq1 && ((rsa->dmq1 = BN_secure_new()) == NULL))
- goto err;
- BN_set_flags(rsa->dmq1, BN_FLG_CONSTTIME);
- if (!rsa->iqmp && ((rsa->iqmp = BN_secure_new()) == NULL))
- goto err;
- BN_set_flags(rsa->iqmp, BN_FLG_CONSTTIME);
/* initialize multi-prime components */
if (primes > RSA_DEFAULT_PRIME_NUM) {
goto err;
if (rsa->prime_infos != NULL) {
/* could this happen? */
- sk_RSA_PRIME_INFO_pop_free(rsa->prime_infos, rsa_multip_info_free);
+ sk_RSA_PRIME_INFO_pop_free(rsa->prime_infos,
+ ossl_rsa_multip_info_free);
}
rsa->prime_infos = prime_infos;
/* prime_info from 2 to |primes| -1 */
for (i = 2; i < primes; i++) {
- pinfo = rsa_multip_info_new();
+ pinfo = ossl_rsa_multip_info_new();
if (pinfo == NULL)
goto err;
(void)sk_RSA_PRIME_INFO_push(prime_infos, pinfo);
for (;;) {
redo:
- if (!BN_generate_prime_ex(prime, bitsr[i] + adj, 0, NULL, NULL, cb))
+ if (!BN_generate_prime_ex2(prime, bitsr[i] + adj, 0, NULL, NULL,
+ cb, ctx))
goto err;
/*
* prime should not be equal to p, q, r_3...
ERR_set_mark();
BN_set_flags(r2, BN_FLG_CONSTTIME);
if (BN_mod_inverse(r1, r2, rsa->e, ctx) != NULL) {
- /* GCD == 1 since inverse exists */
+ /* GCD == 1 since inverse exists */
break;
}
error = ERR_peek_last_error();
/* i == 0, do nothing */
if (!BN_GENCB_call(cb, 3, i))
goto err;
+ tmp = BN_dup(prime);
+ if (tmp == NULL)
+ goto err;
+ if (!sk_BIGNUM_insert(factors, tmp, sk_BIGNUM_num(factors)))
+ goto err;
continue;
}
+
/*
* if |r1|, product of factors so far, is not as long as expected
* (by checking the first 4 bits are less than 0x9 or greater than
*/
i = -1;
bitse = 0;
+ sk_BIGNUM_pop_free(factors, BN_clear_free);
+ factors = sk_BIGNUM_new_null();
+ if (factors == NULL)
+ goto err;
continue;
}
retries++;
goto err;
if (!BN_GENCB_call(cb, 3, i))
goto err;
+ tmp = BN_dup(prime);
+ if (tmp == NULL)
+ goto err;
+ if (!sk_BIGNUM_insert(factors, tmp, sk_BIGNUM_num(factors)))
+ goto err;
}
if (BN_cmp(rsa->p, rsa->q) < 0) {
tmp = rsa->p;
rsa->p = rsa->q;
rsa->q = tmp;
+ /* mirror this in our factor stack */
+ if (!sk_BIGNUM_insert(factors, sk_BIGNUM_delete(factors, 0), 1))
+ goto err;
}
/* calculate d */
goto err;
}
- {
- BIGNUM *pr0 = BN_new();
-
- if (pr0 == NULL)
- goto err;
-
- BN_with_flags(pr0, r0, BN_FLG_CONSTTIME);
- if (!BN_mod_inverse(rsa->d, rsa->e, pr0, ctx)) {
- BN_free(pr0);
- goto err; /* d */
- }
- /* We MUST free pr0 before any further use of r0 */
- BN_free(pr0);
- }
-
- {
- BIGNUM *d = BN_new();
-
- if (d == NULL)
- goto err;
-
- BN_with_flags(d, rsa->d, BN_FLG_CONSTTIME);
-
- /* calculate d mod (p-1) and d mod (q - 1) */
- if (!BN_mod(rsa->dmp1, d, r1, ctx)
- || !BN_mod(rsa->dmq1, d, r2, ctx)) {
- BN_free(d);
- goto err;
- }
-
- /* calculate CRT exponents */
- for (i = 2; i < primes; i++) {
- pinfo = sk_RSA_PRIME_INFO_value(prime_infos, i - 2);
- /* pinfo->d == r_i - 1 */
- if (!BN_mod(pinfo->d, d, pinfo->d, ctx)) {
- BN_free(d);
- goto err;
- }
- }
- /* We MUST free d before any further use of rsa->d */
- BN_free(d);
+ BN_set_flags(r0, BN_FLG_CONSTTIME);
+ if (BN_mod_inverse(rsa->d, rsa->e, r0, ctx) == NULL) {
+ goto err; /* d */
}
- {
- BIGNUM *p = BN_new();
+ /* derive any missing exponents and coefficients */
+ if (!ossl_rsa_multiprime_derive(rsa, bits, primes, e_value,
+ factors, exps, coeffs))
+ goto err;
- if (p == NULL)
+ /*
+ * first 2 factors/exps are already tracked in p/q/dmq1/dmp1
+ * and the first coeff is in iqmp, so pop those off the stack
+ * Note, the first 2 factors/exponents are already tracked by p and q
+ * assign dmp1/dmq1 and iqmp
+ * the remaining pinfo values are separately allocated, so copy and delete
+ * those
+ */
+ BN_clear_free(sk_BIGNUM_delete(factors, 0));
+ BN_clear_free(sk_BIGNUM_delete(factors, 0));
+ rsa->dmp1 = sk_BIGNUM_delete(exps, 0);
+ rsa->dmq1 = sk_BIGNUM_delete(exps, 0);
+ rsa->iqmp = sk_BIGNUM_delete(coeffs, 0);
+ for (i = 2; i < primes; i++) {
+ pinfo = sk_RSA_PRIME_INFO_value(prime_infos, i - 2);
+ tmp = sk_BIGNUM_delete(factors, 0);
+ BN_copy(pinfo->r, tmp);
+ BN_clear_free(tmp);
+ tmp = sk_BIGNUM_delete(exps, 0);
+ tmp2 = BN_copy(pinfo->d, tmp);
+ BN_clear_free(tmp);
+ if (tmp2 == NULL)
goto err;
- BN_with_flags(p, rsa->p, BN_FLG_CONSTTIME);
-
- /* calculate inverse of q mod p */
- if (!BN_mod_inverse(rsa->iqmp, rsa->q, p, ctx)) {
- BN_free(p);
+ tmp = sk_BIGNUM_delete(coeffs, 0);
+ tmp2 = BN_copy(pinfo->t, tmp);
+ BN_clear_free(tmp);
+ if (tmp2 == NULL)
goto err;
- }
-
- /* calculate CRT coefficient for other primes */
- for (i = 2; i < primes; i++) {
- pinfo = sk_RSA_PRIME_INFO_value(prime_infos, i - 2);
- BN_with_flags(p, pinfo->r, BN_FLG_CONSTTIME);
- if (!BN_mod_inverse(pinfo->t, pinfo->pp, p, ctx)) {
- BN_free(p);
- goto err;
- }
- }
-
- /* We MUST free p before any further use of rsa->p */
- BN_free(p);
}
-
ok = 1;
err:
+ sk_BIGNUM_free(factors);
+ sk_BIGNUM_free(exps);
+ sk_BIGNUM_free(coeffs);
if (ok == -1) {
- RSAerr(0, ERR_LIB_BN);
+ ERR_raise(ERR_LIB_RSA, ERR_R_BN_LIB);
ok = 0;
}
BN_CTX_end(ctx);
}
#endif /* FIPS_MODULE */
-static int rsa_keygen(OPENSSL_CTX *libctx, RSA *rsa, int bits, int primes,
+static int rsa_keygen(OSSL_LIB_CTX *libctx, RSA *rsa, int bits, int primes,
BIGNUM *e_value, BN_GENCB *cb, int pairwise_test)
{
int ok = 0;
+#ifdef FIPS_MODULE
+ ok = ossl_rsa_sp800_56b_generate_key(rsa, bits, e_value, cb);
+ pairwise_test = 1; /* FIPS MODE needs to always run the pairwise test */
+#else
/*
- * Only multi-prime keys or insecure keys with a small key length will use
- * the older rsa_multiprime_keygen().
+ * Only multi-prime keys or insecure keys with a small key length or a
+ * public exponent <= 2^16 will use the older rsa_multiprime_keygen().
*/
- if (primes == 2 && bits >= 2048)
- ok = rsa_sp800_56b_generate_key(rsa, bits, e_value, cb);
-#ifndef FIPS_MODULE
+ if (primes == 2
+ && bits >= 2048
+ && (e_value == NULL || BN_num_bits(e_value) > 16))
+ ok = ossl_rsa_sp800_56b_generate_key(rsa, bits, e_value, cb);
else
ok = rsa_multiprime_keygen(rsa, bits, primes, e_value, cb);
#endif /* FIPS_MODULE */
-#ifdef FIPS_MODULE
- pairwise_test = 1; /* FIPS MODE needs to always run the pairwise test */
-#endif
if (pairwise_test && ok > 0) {
OSSL_CALLBACK *stcb = NULL;
void *stcbarg = NULL;
OSSL_SELF_TEST_get_callback(libctx, &stcb, &stcbarg);
ok = rsa_keygen_pairwise_test(rsa, stcb, stcbarg);
if (!ok) {
+ ossl_set_error_state(OSSL_SELF_TEST_TYPE_PCT);
/* Clear intermediate results */
BN_clear_free(rsa->d);
BN_clear_free(rsa->p);
BN_clear_free(rsa->dmp1);
BN_clear_free(rsa->dmq1);
BN_clear_free(rsa->iqmp);
+ rsa->d = NULL;
+ rsa->p = NULL;
+ rsa->q = NULL;
+ rsa->dmp1 = NULL;
+ rsa->dmq1 = NULL;
+ rsa->iqmp = NULL;
}
}
return ok;
unsigned int ciphertxt_len;
unsigned char *ciphertxt = NULL;
const unsigned char plaintxt[16] = {0};
- unsigned char decoded[256];
+ unsigned char *decoded = NULL;
unsigned int decoded_len;
unsigned int plaintxt_len = (unsigned int)sizeof(plaintxt_len);
int padding = RSA_PKCS1_PADDING;
OSSL_SELF_TEST_DESC_PCT_RSA_PKCS1);
ciphertxt_len = RSA_size(rsa);
- ciphertxt = OPENSSL_zalloc(ciphertxt_len);
+ /*
+ * RSA_private_encrypt() and RSA_private_decrypt() requires the 'to'
+ * parameter to be a maximum of RSA_size() - allocate space for both.
+ */
+ ciphertxt = OPENSSL_zalloc(ciphertxt_len * 2);
if (ciphertxt == NULL)
goto err;
+ decoded = ciphertxt + ciphertxt_len;
ciphertxt_len = RSA_public_encrypt(plaintxt_len, plaintxt, ciphertxt, rsa,
padding);