/*
- * Copyright 1995-2021 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
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 */
ERR_raise(ERR_LIB_RSA, RSA_R_KEY_SIZE_TOO_SMALL);
- goto err;
+ 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 && !ossl_rsa_check_public_exponent(e_value)) {
+ 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 > ossl_rsa_multip_cap(bits)) {
- ok = 0; /* we set our own err */
ERR_raise(ERR_LIB_RSA, RSA_R_KEY_PRIME_NUM_INVALID);
- goto err;
+ return 0;
}
+ 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;
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) {
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);
+ BN_set_flags(r0, BN_FLG_CONSTTIME);
+ if (BN_mod_inverse(rsa->d, rsa->e, r0, ctx) == NULL) {
+ goto err; /* d */
}
- {
- 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);
- }
-
- {
- 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) {
ERR_raise(ERR_LIB_RSA, ERR_R_BN_LIB);
ok = 0;
{
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)
+ 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);
-#ifndef FIPS_MODULE
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;