Support multi-prime RSA (RFC 8017)
* Introduce RSA_generate_multi_prime_key to generate multi-prime
RSA private key. As well as the following functions:
RSA_get_multi_prime_extra_count
RSA_get0_multi_prime_factors
RSA_get0_multi_prime_crt_params
RSA_set0_multi_prime_params
RSA_get_version
* Support EVP operations for multi-prime RSA
* Support ASN.1 operations for multi-prime RSA
* Support multi-prime check in RSA_check_key_ex
* Support multi-prime RSA in apps/genrsa and apps/speed
* Support multi-prime RSA manipulation functions
* Test cases and documentation are added
* CHANGES is updated
Reviewed-by: Tim Hudson <tjh@openssl.org>
Reviewed-by: Bernd Edlinger <bernd.edlinger@hotmail.de>
(Merged from https://github.com/openssl/openssl/pull/4241)
diff --git a/crypto/rsa/rsa_ossl.c b/crypto/rsa/rsa_ossl.c
index 40c84dd..ced11ad 100644
--- a/crypto/rsa/rsa_ossl.c
+++ b/crypto/rsa/rsa_ossl.c
@@ -38,7 +38,8 @@
NULL,
0, /* rsa_sign */
0, /* rsa_verify */
- NULL /* rsa_keygen */
+ NULL, /* rsa_keygen */
+ NULL /* rsa_multi_prime_keygen */
};
static const RSA_METHOD *default_RSA_meth = &rsa_pkcs1_ossl_meth;
@@ -308,6 +309,7 @@
}
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))) {
@@ -437,6 +439,7 @@
/* do the decrypt */
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))) {
@@ -601,17 +604,23 @@
static int rsa_ossl_mod_exp(BIGNUM *r0, const BIGNUM *I, RSA *rsa, BN_CTX *ctx)
{
- BIGNUM *r1, *m1, *vrfy;
- int ret = 0;
+ BIGNUM *r1, *m1, *vrfy, *r2, *m[RSA_MAX_PRIME_NUM];
+ int ret = 0, i, ex_primes = 0;
+ RSA_PRIME_INFO *pinfo;
BN_CTX_start(ctx);
r1 = BN_CTX_get(ctx);
+ r2 = BN_CTX_get(ctx);
m1 = BN_CTX_get(ctx);
vrfy = BN_CTX_get(ctx);
if (vrfy == NULL)
goto err;
+ if (rsa->version == RSA_ASN1_VERSION_MULTI
+ && (ex_primes = sk_RSA_PRIME_INFO_num(rsa->prime_infos)) <= 0)
+ goto err;
+
{
BIGNUM *p = BN_new(), *q = BN_new();
@@ -636,6 +645,28 @@
BN_free(q);
goto err;
}
+ if (ex_primes > 0) {
+ /* cache BN_MONT_CTX for other primes */
+ BIGNUM *r = BN_new();
+
+ if (r == NULL) {
+ BN_free(p);
+ BN_free(q);
+ goto err;
+ }
+
+ for (i = 0; i < ex_primes; i++) {
+ pinfo = sk_RSA_PRIME_INFO_value(rsa->prime_infos, i);
+ BN_with_flags(r, pinfo->r, BN_FLG_CONSTTIME);
+ if (!BN_MONT_CTX_set_locked(&pinfo->m, rsa->lock, r, ctx)) {
+ BN_free(p);
+ BN_free(q);
+ BN_free(r);
+ goto err;
+ }
+ }
+ BN_free(r);
+ }
}
/*
* We MUST free p and q before any further use of rsa->p and rsa->q
@@ -705,6 +736,56 @@
BN_free(dmp1);
}
+ /*
+ * calculate m_i in multi-prime case
+ *
+ * TODO:
+ * 1. squash the following two loops and calculate |m_i| there.
+ * 2. remove cc and reuse |c|.
+ * 3. remove |dmq1| and |dmp1| in previous block and use |di|.
+ *
+ * If these things are done, the code will be more readable.
+ */
+ if (ex_primes > 0) {
+ BIGNUM *di = BN_new(), *cc = BN_new();
+
+ if (cc == NULL || di == NULL) {
+ BN_free(cc);
+ BN_free(di);
+ goto err;
+ }
+
+ for (i = 0; i < ex_primes; i++) {
+ /* prepare m_i */
+ if ((m[i] = BN_CTX_get(ctx)) == NULL) {
+ BN_free(cc);
+ BN_free(di);
+ goto err;
+ }
+
+ pinfo = sk_RSA_PRIME_INFO_value(rsa->prime_infos, i);
+
+ /* prepare c and d_i */
+ BN_with_flags(cc, I, BN_FLG_CONSTTIME);
+ BN_with_flags(di, pinfo->d, BN_FLG_CONSTTIME);
+
+ if (!BN_mod(r1, cc, pinfo->r, ctx)) {
+ BN_free(cc);
+ BN_free(di);
+ goto err;
+ }
+ /* compute r1 ^ d_i mod r_i */
+ if (!rsa->meth->bn_mod_exp(m[i], r1, di, pinfo->r, ctx, pinfo->m)) {
+ BN_free(cc);
+ BN_free(di);
+ goto err;
+ }
+ }
+
+ BN_free(cc);
+ BN_free(di);
+ }
+
if (!BN_sub(r0, r0, m1))
goto err;
/*
@@ -747,6 +828,49 @@
if (!BN_add(r0, r1, m1))
goto err;
+ /* add m_i to m in multi-prime case */
+ if (ex_primes > 0) {
+ BIGNUM *pr2 = BN_new();
+
+ if (pr2 == NULL)
+ goto err;
+
+ for (i = 0; i < ex_primes; i++) {
+ pinfo = sk_RSA_PRIME_INFO_value(rsa->prime_infos, i);
+ if (!BN_sub(r1, m[i], r0)) {
+ BN_free(pr2);
+ goto err;
+ }
+
+ if (!BN_mul(r2, r1, pinfo->t, ctx)) {
+ BN_free(pr2);
+ goto err;
+ }
+
+ BN_with_flags(pr2, r2, BN_FLG_CONSTTIME);
+
+ if (!BN_mod(r1, pr2, pinfo->r, ctx)) {
+ BN_free(pr2);
+ goto err;
+ }
+
+ if (BN_is_negative(r1))
+ if (!BN_add(r1, r1, pinfo->r)) {
+ BN_free(pr2);
+ goto err;
+ }
+ if (!BN_mul(r1, r1, pinfo->pp, ctx)) {
+ BN_free(pr2);
+ goto err;
+ }
+ if (!BN_add(r0, r0, r1)) {
+ BN_free(pr2);
+ goto err;
+ }
+ }
+ BN_free(pr2);
+ }
+
if (rsa->e && rsa->n) {
if (!rsa->meth->bn_mod_exp(vrfy, r0, rsa->e, rsa->n, ctx,
rsa->_method_mod_n))
@@ -799,8 +923,15 @@
static int rsa_ossl_finish(RSA *rsa)
{
+ int i;
+ RSA_PRIME_INFO *pinfo;
+
BN_MONT_CTX_free(rsa->_method_mod_n);
BN_MONT_CTX_free(rsa->_method_mod_p);
BN_MONT_CTX_free(rsa->_method_mod_q);
+ for (i = 0; i < sk_RSA_PRIME_INFO_num(rsa->prime_infos); i++) {
+ pinfo = sk_RSA_PRIME_INFO_value(rsa->prime_infos, i);
+ BN_MONT_CTX_free(pinfo->m);
+ }
return 1;
}
