diff options
author | Paul Yang <yang.yang@baishancloud.com> | 2017-08-02 02:19:43 +0800 |
---|---|---|
committer | Paul Yang <yang.yang@baishancloud.com> | 2017-11-21 14:38:42 +0800 |
commit | 665d899fa6d3571da016925067ebcf1789d7d19c (patch) | |
tree | 1674f352dc0feee9e68e6221d21c5d79bd1935ab /crypto/rsa | |
parent | b0004708730f300a2e5c6a11c887caab50b6c42a (diff) | |
download | openssl-665d899fa6d3571da016925067ebcf1789d7d19c.tar.gz |
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)
Diffstat (limited to 'crypto/rsa')
-rw-r--r-- | crypto/rsa/build.info | 2 | ||||
-rw-r--r-- | crypto/rsa/rsa_ameth.c | 41 | ||||
-rw-r--r-- | crypto/rsa/rsa_asn1.c | 24 | ||||
-rw-r--r-- | crypto/rsa/rsa_chk.c | 81 | ||||
-rw-r--r-- | crypto/rsa/rsa_err.c | 11 | ||||
-rw-r--r-- | crypto/rsa/rsa_gen.c | 293 | ||||
-rw-r--r-- | crypto/rsa/rsa_lib.c | 128 | ||||
-rw-r--r-- | crypto/rsa/rsa_locl.h | 26 | ||||
-rw-r--r-- | crypto/rsa/rsa_meth.c | 14 | ||||
-rw-r--r-- | crypto/rsa/rsa_mp.c | 95 | ||||
-rw-r--r-- | crypto/rsa/rsa_ossl.c | 137 | ||||
-rw-r--r-- | crypto/rsa/rsa_pmeth.c | 27 |
12 files changed, 813 insertions, 66 deletions
diff --git a/crypto/rsa/build.info b/crypto/rsa/build.info index 4575b28879..87f924922f 100644 --- a/crypto/rsa/build.info +++ b/crypto/rsa/build.info @@ -3,4 +3,4 @@ SOURCE[../../libcrypto]=\ rsa_ossl.c rsa_gen.c rsa_lib.c rsa_sign.c rsa_saos.c rsa_err.c \ rsa_pk1.c rsa_ssl.c rsa_none.c rsa_oaep.c rsa_chk.c \ rsa_pss.c rsa_x931.c rsa_asn1.c rsa_depr.c rsa_ameth.c rsa_prn.c \ - rsa_pmeth.c rsa_crpt.c rsa_x931g.c rsa_meth.c + rsa_pmeth.c rsa_crpt.c rsa_x931g.c rsa_meth.c rsa_mp.c diff --git a/crypto/rsa/rsa_ameth.c b/crypto/rsa/rsa_ameth.c index 97a37ba47d..98121b5e64 100644 --- a/crypto/rsa/rsa_ameth.c +++ b/crypto/rsa/rsa_ameth.c @@ -316,10 +316,11 @@ static int pkey_rsa_print(BIO *bp, const EVP_PKEY *pkey, int off, int priv) const RSA *x = pkey->pkey.rsa; char *str; const char *s; - int ret = 0, mod_len = 0; + int ret = 0, mod_len = 0, ex_primes; if (x->n != NULL) mod_len = BN_num_bits(x->n); + ex_primes = sk_RSA_PRIME_INFO_num(x->prime_infos); if (!BIO_indent(bp, off, 128)) goto err; @@ -328,7 +329,8 @@ static int pkey_rsa_print(BIO *bp, const EVP_PKEY *pkey, int off, int priv) goto err; if (priv && x->d) { - if (BIO_printf(bp, "Private-Key: (%d bit)\n", mod_len) <= 0) + if (BIO_printf(bp, "Private-Key: (%d bit, %d primes)\n", + mod_len, ex_primes <= 0 ? 2 : ex_primes + 2) <= 0) goto err; str = "modulus:"; s = "publicExponent:"; @@ -343,6 +345,8 @@ static int pkey_rsa_print(BIO *bp, const EVP_PKEY *pkey, int off, int priv) if (!ASN1_bn_print(bp, s, x->e, NULL, off)) goto err; if (priv) { + int i; + if (!ASN1_bn_print(bp, "privateExponent:", x->d, NULL, off)) goto err; if (!ASN1_bn_print(bp, "prime1:", x->p, NULL, off)) @@ -355,6 +359,39 @@ static int pkey_rsa_print(BIO *bp, const EVP_PKEY *pkey, int off, int priv) goto err; if (!ASN1_bn_print(bp, "coefficient:", x->iqmp, NULL, off)) goto err; + for (i = 0; i < sk_RSA_PRIME_INFO_num(x->prime_infos); i++) { + /* print multi-prime info */ + BIGNUM *bn = NULL; + RSA_PRIME_INFO *pinfo; + int j; + + pinfo = sk_RSA_PRIME_INFO_value(x->prime_infos, i); + for (j = 0; j < 3; j++) { + if (!BIO_indent(bp, off, 128)) + goto err; + switch (j) { + case 0: + if (BIO_printf(bp, "prime%d:", i + 3) <= 0) + goto err; + bn = pinfo->r; + break; + case 1: + if (BIO_printf(bp, "exponent%d:", i + 3) <= 0) + goto err; + bn = pinfo->d; + break; + case 2: + if (BIO_printf(bp, "coefficient%d:", i + 3) <= 0) + goto err; + bn = pinfo->t; + break; + default: + break; + } + if (!ASN1_bn_print(bp, "", bn, NULL, off)) + goto err; + } + } } if (pkey_is_pss(pkey) && !rsa_pss_param_print(bp, 1, x->pss, off)) goto err; diff --git a/crypto/rsa/rsa_asn1.c b/crypto/rsa/rsa_asn1.c index 43c8fc27ae..9fe62c82eb 100644 --- a/crypto/rsa/rsa_asn1.c +++ b/crypto/rsa/rsa_asn1.c @@ -1,5 +1,5 @@ /* - * Copyright 2000-2016 The OpenSSL Project Authors. All Rights Reserved. + * Copyright 2000-2017 The OpenSSL Project Authors. All Rights Reserved. * * Licensed under the OpenSSL license (the "License"). You may not use * this file except in compliance with the License. You can obtain a copy @@ -14,7 +14,11 @@ #include <openssl/asn1t.h> #include "rsa_locl.h" -/* Override the default free and new methods */ +/* + * Override the default free and new methods, + * and calculate helper products for multi-prime + * RSA keys. + */ static int rsa_cb(int operation, ASN1_VALUE **pval, const ASN1_ITEM *it, void *exarg) { @@ -27,10 +31,23 @@ static int rsa_cb(int operation, ASN1_VALUE **pval, const ASN1_ITEM *it, RSA_free((RSA *)*pval); *pval = NULL; return 2; + } else if (operation == ASN1_OP_D2I_POST) { + if (((RSA *)*pval)->version != RSA_ASN1_VERSION_MULTI) { + /* not a multi-prime key, skip */ + return 1; + } + return (rsa_multip_calc_product((RSA *)*pval) == 1) ? 2 : 0; } return 1; } +/* Based on definitions in RFC 8017 appendix A.1.2 */ +ASN1_SEQUENCE(RSA_PRIME_INFO) = { + ASN1_SIMPLE(RSA_PRIME_INFO, r, CBIGNUM), + ASN1_SIMPLE(RSA_PRIME_INFO, d, CBIGNUM), + ASN1_SIMPLE(RSA_PRIME_INFO, t, CBIGNUM), +} ASN1_SEQUENCE_END(RSA_PRIME_INFO) + ASN1_SEQUENCE_cb(RSAPrivateKey, rsa_cb) = { ASN1_EMBED(RSA, version, INT32), ASN1_SIMPLE(RSA, n, BIGNUM), @@ -40,7 +57,8 @@ ASN1_SEQUENCE_cb(RSAPrivateKey, rsa_cb) = { ASN1_SIMPLE(RSA, q, CBIGNUM), ASN1_SIMPLE(RSA, dmp1, CBIGNUM), ASN1_SIMPLE(RSA, dmq1, CBIGNUM), - ASN1_SIMPLE(RSA, iqmp, CBIGNUM) + ASN1_SIMPLE(RSA, iqmp, CBIGNUM), + ASN1_SEQUENCE_OF_OPT(RSA, prime_infos, RSA_PRIME_INFO) } ASN1_SEQUENCE_END_cb(RSA, RSAPrivateKey) diff --git a/crypto/rsa/rsa_chk.c b/crypto/rsa/rsa_chk.c index 00260fb18e..4cf682258b 100644 --- a/crypto/rsa/rsa_chk.c +++ b/crypto/rsa/rsa_chk.c @@ -1,5 +1,5 @@ /* - * Copyright 1999-2016 The OpenSSL Project Authors. All Rights Reserved. + * Copyright 1999-2017 The OpenSSL Project Authors. All Rights Reserved. * * Licensed under the OpenSSL license (the "License"). You may not use * this file except in compliance with the License. You can obtain a copy @@ -20,7 +20,8 @@ int RSA_check_key_ex(const RSA *key, BN_GENCB *cb) { BIGNUM *i, *j, *k, *l, *m; BN_CTX *ctx; - int ret = 1; + int ret = 1, ex_primes = 0, idx; + RSA_PRIME_INFO *pinfo; if (key->p == NULL || key->q == NULL || key->n == NULL || key->e == NULL || key->d == NULL) { @@ -28,6 +29,13 @@ int RSA_check_key_ex(const RSA *key, BN_GENCB *cb) return 0; } + /* multi-prime? */ + if (key->version == RSA_ASN1_VERSION_MULTI + && (ex_primes = sk_RSA_PRIME_INFO_num(key->prime_infos)) <= 0) { + RSAerr(RSA_F_RSA_CHECK_KEY_EX, RSA_R_INVALID_MULTI_PRIME_KEY); + return 0; + } + i = BN_new(); j = BN_new(); k = BN_new(); @@ -62,17 +70,37 @@ int RSA_check_key_ex(const RSA *key, BN_GENCB *cb) RSAerr(RSA_F_RSA_CHECK_KEY_EX, RSA_R_Q_NOT_PRIME); } - /* n = p*q? */ + /* r_i prime? */ + for (idx = 0; idx < ex_primes; idx++) { + pinfo = sk_RSA_PRIME_INFO_value(key->prime_infos, idx); + if (BN_is_prime_ex(pinfo->r, BN_prime_checks, NULL, cb) != 1) { + ret = 0; + RSAerr(RSA_F_RSA_CHECK_KEY_EX, RSA_R_MP_R_NOT_PRIME); + } + } + + /* n = p*q * r_3...r_i? */ if (!BN_mul(i, key->p, key->q, ctx)) { ret = -1; goto err; } + for (idx = 0; idx < ex_primes; idx++) { + pinfo = sk_RSA_PRIME_INFO_value(key->prime_infos, idx); + if (!BN_mul(i, i, pinfo->r, ctx)) { + ret = -1; + goto err; + } + } if (BN_cmp(i, key->n) != 0) { ret = 0; - RSAerr(RSA_F_RSA_CHECK_KEY_EX, RSA_R_N_DOES_NOT_EQUAL_P_Q); + if (ex_primes) + RSAerr(RSA_F_RSA_CHECK_KEY_EX, + RSA_R_N_DOES_NOT_EQUAL_PRODUCT_OF_PRIMES); + else + RSAerr(RSA_F_RSA_CHECK_KEY_EX, RSA_R_N_DOES_NOT_EQUAL_P_Q); } - /* d*e = 1 mod lcm(p-1,q-1)? */ + /* d*e = 1 mod \lambda(n)? */ if (!BN_sub(i, key->p, BN_value_one())) { ret = -1; goto err; @@ -82,7 +110,7 @@ int RSA_check_key_ex(const RSA *key, BN_GENCB *cb) goto err; } - /* now compute k = lcm(i,j) */ + /* now compute k = \lambda(n) = LCM(i, j, r_3 - 1...) */ if (!BN_mul(l, i, j, ctx)) { ret = -1; goto err; @@ -91,6 +119,21 @@ int RSA_check_key_ex(const RSA *key, BN_GENCB *cb) ret = -1; goto err; } + for (idx = 0; idx < ex_primes; idx++) { + pinfo = sk_RSA_PRIME_INFO_value(key->prime_infos, idx); + if (!BN_sub(k, pinfo->r, BN_value_one())) { + ret = -1; + goto err; + } + if (!BN_mul(l, l, k, ctx)) { + ret = -1; + goto err; + } + if (!BN_gcd(m, m, k, ctx)) { + ret = -1; + goto err; + } + } if (!BN_div(k, NULL, l, m, ctx)) { /* remainder is 0 */ ret = -1; goto err; @@ -145,6 +188,32 @@ int RSA_check_key_ex(const RSA *key, BN_GENCB *cb) } } + for (idx = 0; idx < ex_primes; idx++) { + pinfo = sk_RSA_PRIME_INFO_value(key->prime_infos, idx); + /* d_i = d mod (r_i - 1)? */ + if (!BN_sub(i, pinfo->r, BN_value_one())) { + ret = -1; + goto err; + } + if (!BN_mod(j, key->d, i, ctx)) { + ret = -1; + goto err; + } + if (BN_cmp(j, pinfo->d) != 0) { + ret = 0; + RSAerr(RSA_F_RSA_CHECK_KEY_EX, RSA_R_MP_EXPONENT_NOT_CONGRUENT_TO_D); + } + /* t_i = R_i ^ -1 mod r_i ? */ + if (!BN_mod_inverse(i, pinfo->pp, pinfo->r, ctx)) { + ret = -1; + goto err; + } + if (BN_cmp(i, pinfo->t) != 0) { + ret = 0; + RSAerr(RSA_F_RSA_CHECK_KEY_EX, RSA_R_MP_COEFFICIENT_NOT_INVERSE_OF_R); + } + } + err: BN_free(i); BN_free(j); diff --git a/crypto/rsa/rsa_err.c b/crypto/rsa/rsa_err.c index 74b0feeae4..f7d29e1999 100644 --- a/crypto/rsa/rsa_err.c +++ b/crypto/rsa/rsa_err.c @@ -147,6 +147,8 @@ static const ERR_STRING_DATA RSA_str_reasons[] = { {ERR_PACK(ERR_LIB_RSA, 0, RSA_R_INVALID_MESSAGE_LENGTH), "invalid message length"}, {ERR_PACK(ERR_LIB_RSA, 0, RSA_R_INVALID_MGF1_MD), "invalid mgf1 md"}, + {ERR_PACK(ERR_LIB_RSA, 0, RSA_R_INVALID_MULTI_PRIME_KEY), + "invalid multi prime key"}, {ERR_PACK(ERR_LIB_RSA, 0, RSA_R_INVALID_OAEP_PARAMETERS), "invalid oaep parameters"}, {ERR_PACK(ERR_LIB_RSA, 0, RSA_R_INVALID_PADDING), "invalid padding"}, @@ -163,14 +165,23 @@ static const ERR_STRING_DATA RSA_str_reasons[] = { "invalid x931 digest"}, {ERR_PACK(ERR_LIB_RSA, 0, RSA_R_IQMP_NOT_INVERSE_OF_Q), "iqmp not inverse of q"}, + {ERR_PACK(ERR_LIB_RSA, 0, RSA_R_KEY_PRIME_NUM_INVALID), + "key prime num invalid"}, {ERR_PACK(ERR_LIB_RSA, 0, RSA_R_KEY_SIZE_TOO_SMALL), "key size too small"}, {ERR_PACK(ERR_LIB_RSA, 0, RSA_R_LAST_OCTET_INVALID), "last octet invalid"}, {ERR_PACK(ERR_LIB_RSA, 0, RSA_R_MGF1_DIGEST_NOT_ALLOWED), "mgf1 digest not allowed"}, {ERR_PACK(ERR_LIB_RSA, 0, RSA_R_MODULUS_TOO_LARGE), "modulus too large"}, + {ERR_PACK(ERR_LIB_RSA, 0, RSA_R_MP_COEFFICIENT_NOT_INVERSE_OF_R), + "mp coefficient not inverse of r"}, + {ERR_PACK(ERR_LIB_RSA, 0, RSA_R_MP_EXPONENT_NOT_CONGRUENT_TO_D), + "mp exponent not congruent to d"}, + {ERR_PACK(ERR_LIB_RSA, 0, RSA_R_MP_R_NOT_PRIME), "mp r not prime"}, {ERR_PACK(ERR_LIB_RSA, 0, RSA_R_NO_PUBLIC_EXPONENT), "no public exponent"}, {ERR_PACK(ERR_LIB_RSA, 0, RSA_R_NULL_BEFORE_BLOCK_MISSING), "null before block missing"}, + {ERR_PACK(ERR_LIB_RSA, 0, RSA_R_N_DOES_NOT_EQUAL_PRODUCT_OF_PRIMES), + "n does not equal product of primes"}, {ERR_PACK(ERR_LIB_RSA, 0, RSA_R_N_DOES_NOT_EQUAL_P_Q), "n does not equal p q"}, {ERR_PACK(ERR_LIB_RSA, 0, RSA_R_OAEP_DECODING_ERROR), diff --git a/crypto/rsa/rsa_gen.c b/crypto/rsa/rsa_gen.c index 4ced965519..f7f60754ad 100644 --- a/crypto/rsa/rsa_gen.c +++ b/crypto/rsa/rsa_gen.c @@ -1,5 +1,5 @@ /* - * Copyright 1995-2016 The OpenSSL Project Authors. All Rights Reserved. + * Copyright 1995-2017 The OpenSSL Project Authors. All Rights Reserved. * * Licensed under the OpenSSL license (the "License"). You may not use * this file except in compliance with the License. You can obtain a copy @@ -19,7 +19,7 @@ #include <openssl/bn.h> #include "rsa_locl.h" -static int rsa_builtin_keygen(RSA *rsa, int bits, BIGNUM *e_value, +static int rsa_builtin_keygen(RSA *rsa, int bits, int primes, BIGNUM *e_value, BN_GENCB *cb); /* @@ -31,17 +31,43 @@ static int rsa_builtin_keygen(RSA *rsa, int bits, BIGNUM *e_value, */ int RSA_generate_key_ex(RSA *rsa, int bits, BIGNUM *e_value, BN_GENCB *cb) { - if (rsa->meth->rsa_keygen) + if (rsa->meth->rsa_keygen != NULL) return rsa->meth->rsa_keygen(rsa, bits, e_value, cb); - return rsa_builtin_keygen(rsa, bits, e_value, cb); + + return RSA_generate_multi_prime_key(rsa, bits, RSA_DEFAULT_PRIME_NUM, + e_value, cb); } -static int rsa_builtin_keygen(RSA *rsa, int bits, BIGNUM *e_value, +int RSA_generate_multi_prime_key(RSA *rsa, int bits, int primes, + BIGNUM *e_value, BN_GENCB *cb) +{ + /* multi-prime is only supported with the builtin key generation */ + if (rsa->meth->rsa_multi_prime_keygen != NULL) + return rsa->meth->rsa_multi_prime_keygen(rsa, bits, primes, + e_value, cb); + return rsa_builtin_keygen(rsa, bits, primes, e_value, cb); +} + +static int rsa_builtin_keygen(RSA *rsa, int bits, int primes, BIGNUM *e_value, BN_GENCB *cb) { - BIGNUM *r0 = NULL, *r1 = NULL, *r2 = NULL, *r3 = NULL, *tmp; - int bitsp, bitsq, ok = -1, n = 0; + BIGNUM *r0 = NULL, *r1 = NULL, *r2 = NULL, *tmp, *prime; + int ok = -1, 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; BN_CTX *ctx = NULL; + BN_ULONG bitst = 0; + + /* + * From Github pull request #4241: + * + * We are in disagreement on how to handle security trade-off, in other + * words: + * + * mechanical-check-for-maximum-of-16-prime-factors vs. + * limiting-number-depending-on-length-less-factors-for-shorter-keys. + */ /* * When generating ridiculously small keys, we can get stuck @@ -53,6 +79,12 @@ static int rsa_builtin_keygen(RSA *rsa, int bits, BIGNUM *e_value, goto err; } + if (primes < RSA_DEFAULT_PRIME_NUM + || primes > RSA_MAX_PRIME_NUM || bits <= primes) { + RSAerr(RSA_F_RSA_BUILTIN_KEYGEN, RSA_R_KEY_PRIME_NUM_INVALID); + goto err; + } + ctx = BN_CTX_new(); if (ctx == NULL) goto err; @@ -60,12 +92,29 @@ static int rsa_builtin_keygen(RSA *rsa, int bits, BIGNUM *e_value, r0 = BN_CTX_get(ctx); r1 = BN_CTX_get(ctx); r2 = BN_CTX_get(ctx); - r3 = BN_CTX_get(ctx); - if (r3 == NULL) + if (r2 == NULL) + goto err; + + /* divide bits into 'primes' pieces evenly */ + quo = bits / primes; + rmd = bits % primes; + + if (primes > RSA_DEFAULT_PRIME_NUM && quo < RSA_MIN_PRIME_SIZE) { + /* + * this means primes are too many for the key bits. + * + * This only affects multi-prime keys. For normal RSA, + * it's limited above (bits >= 16, hence each prime >= 8). + * + * This is done in this way because the original normal + * RSA's behavior should not alter at least in OpenSSL 1.1.1. + */ + RSAerr(RSA_F_RSA_BUILTIN_KEYGEN, RSA_R_KEY_PRIME_NUM_INVALID); goto err; + } - bitsp = (bits + 1) / 2; - bitsq = bits - bitsp; + for (i = 0; i < primes; i++) + bitsr[i] = (i < rmd) ? quo + 1 : quo; /* We need the RSA components non-NULL */ if (!rsa->n && ((rsa->n = BN_new()) == NULL)) @@ -85,62 +134,191 @@ static int rsa_builtin_keygen(RSA *rsa, int bits, BIGNUM *e_value, if (!rsa->iqmp && ((rsa->iqmp = BN_secure_new()) == NULL)) goto err; + /* initialize multi-prime components */ + if (primes > RSA_DEFAULT_PRIME_NUM) { + rsa->version = RSA_ASN1_VERSION_MULTI; + prime_infos = sk_RSA_PRIME_INFO_new_reserve(NULL, primes - 2); + if (prime_infos == NULL) + goto err; + if (rsa->prime_infos != NULL) { + /* could this happen? */ + sk_RSA_PRIME_INFO_pop_free(rsa->prime_infos, 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(); + if (pinfo == NULL) + goto err; + (void)sk_RSA_PRIME_INFO_push(prime_infos, pinfo); + } + } + if (BN_copy(rsa->e, e_value) == NULL) goto err; - /* generate p and q */ - for (;;) { - if (!BN_generate_prime_ex(rsa->p, bitsp, 0, NULL, NULL, cb)) - goto err; - if (!BN_sub(r2, rsa->p, BN_value_one())) - goto err; - if (!BN_gcd(r1, r2, rsa->e, ctx)) - goto err; - if (BN_is_one(r1)) - break; - if (!BN_GENCB_call(cb, 2, n++)) + /* generate p, q and other primes (if any) */ + for (i = 0; i < primes; i++) { + adj = 0; + retries = 0; + + if (i == 0) { + prime = rsa->p; + } else if (i == 1) { + prime = rsa->q; + } else { + pinfo = sk_RSA_PRIME_INFO_value(prime_infos, i - 2); + prime = pinfo->r; + } + + for (;;) { + redo: + if (!BN_generate_prime_ex(prime, bitsr[i] + adj, 0, NULL, NULL, cb)) + goto err; + /* + * prime should not be equal to p, q, r_3... + * (those primes prior to this one) + */ + { + int j; + + for (j = 0; j < i; j++) { + BIGNUM *prev_prime; + + if (j == 0) + prev_prime = rsa->p; + else if (j == 1) + prev_prime = rsa->q; + else + prev_prime = sk_RSA_PRIME_INFO_value(prime_infos, + j - 2)->r; + + if (!BN_cmp(prime, prev_prime)) { + goto redo; + } + } + } + if (!BN_sub(r2, prime, BN_value_one())) + goto err; + if (!BN_gcd(r1, r2, rsa->e, ctx)) + goto err; + if (BN_is_one(r1)) + break; + if (!BN_GENCB_call(cb, 2, n++)) + goto err; + } + + bitse += bitsr[i]; + + /* calculate n immediately to see if it's sufficient */ + if (i == 1) { + /* we get at least 2 primes */ + if (!BN_mul(r1, rsa->p, rsa->q, ctx)) + goto err; + } else if (i != 0) { + /* modulus n = p * q * r_3 * r_4 ... */ + if (!BN_mul(r1, rsa->n, prime, ctx)) + goto err; + } else { + /* i == 0, do nothing */ + if (!BN_GENCB_call(cb, 3, i)) + 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 + * 0xF). If so, re-generate the last prime. + * + * NOTE: This actually can't happen in two-prime case, because of + * the way factors are generated. + * + * Besides, another consideration is, for multi-prime case, even the + * length modulus is as long as expected, the modulus could start at + * 0x8, which could be utilized to distinguish a multi-prime private + * key by using the modulus in a certificate. This is also covered + * by checking the length should not be less than 0x9. + */ + if (!BN_rshift(r2, r1, bitse - 4)) goto err; - } - if (!BN_GENCB_call(cb, 3, 0)) - goto err; - for (;;) { - do { - if (!BN_generate_prime_ex(rsa->q, bitsq, 0, NULL, NULL, cb)) + bitst = BN_get_word(r2); + + if (bitst < 0x9 || bitst > 0xF) { + /* + * For keys with more than 4 primes, we attempt longer factor to + * meet length requirement. + * + * Otherwise, we just re-generate the prime with the same length. + * + * This strategy has the following goals: + * + * 1. 1024-bit factors are effcient when using 3072 and 4096-bit key + * 2. stay the same logic with normal 2-prime key + */ + bitse -= bitsr[i]; + if (!BN_GENCB_call(cb, 2, n++)) goto err; - } while (BN_cmp(rsa->p, rsa->q) == 0); - if (!BN_sub(r2, rsa->q, BN_value_one())) + if (primes > 4) { + if (bitst < 0x9) + adj++; + else + adj--; + } else if (retries == 4) { + /* + * re-generate all primes from scratch, mainly used + * in 4 prime case to avoid long loop. Max retry times + * is set to 4. + */ + i = -1; + bitse = 0; + continue; + } + retries++; + goto redo; + } + /* save product of primes for further use, for multi-prime only */ + if (i > 1 && BN_copy(pinfo->pp, rsa->n) == NULL) goto err; - if (!BN_gcd(r1, r2, rsa->e, ctx)) + if (BN_copy(rsa->n, r1) == NULL) goto err; - if (BN_is_one(r1)) - break; - if (!BN_GENCB_call(cb, 2, n++)) + if (!BN_GENCB_call(cb, 3, i)) goto err; } - if (!BN_GENCB_call(cb, 3, 1)) - goto err; + if (BN_cmp(rsa->p, rsa->q) < 0) { tmp = rsa->p; rsa->p = rsa->q; rsa->q = tmp; } - /* calculate n */ - if (!BN_mul(rsa->n, rsa->p, rsa->q, ctx)) - goto err; - /* calculate d */ + + /* p - 1 */ if (!BN_sub(r1, rsa->p, BN_value_one())) - goto err; /* p-1 */ + goto err; + /* q - 1 */ if (!BN_sub(r2, rsa->q, BN_value_one())) - goto err; /* q-1 */ + goto err; + /* (p - 1)(q - 1) */ if (!BN_mul(r0, r1, r2, ctx)) - goto err; /* (p-1)(q-1) */ + goto err; + /* multi-prime */ + for (i = 2; i < primes; i++) { + pinfo = sk_RSA_PRIME_INFO_value(prime_infos, i - 2); + /* save r_i - 1 to pinfo->d temporarily */ + if (!BN_sub(pinfo->d, pinfo->r, BN_value_one())) + goto err; + if (!BN_mul(r0, r0, pinfo->d, ctx)) + 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); @@ -155,15 +333,26 @@ static int rsa_builtin_keygen(RSA *rsa, int bits, BIGNUM *e_value, if (d == NULL) goto err; + BN_with_flags(d, rsa->d, BN_FLG_CONSTTIME); - if ( /* calculate d mod (p-1) */ - !BN_mod(rsa->dmp1, d, r1, ctx) - /* calculate d mod (q-1) */ + /* 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); } @@ -180,6 +369,17 @@ static int rsa_builtin_keygen(RSA *rsa, int bits, BIGNUM *e_value, BN_free(p); 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); } @@ -193,6 +393,5 @@ static int rsa_builtin_keygen(RSA *rsa, int bits, BIGNUM *e_value, if (ctx != NULL) BN_CTX_end(ctx); BN_CTX_free(ctx); - return ok; } diff --git a/crypto/rsa/rsa_lib.c b/crypto/rsa/rsa_lib.c index e43d8238b5..198dbd3fc7 100644 --- a/crypto/rsa/rsa_lib.c +++ b/crypto/rsa/rsa_lib.c @@ -134,6 +134,7 @@ void RSA_free(RSA *r) BN_clear_free(r->dmq1); BN_clear_free(r->iqmp); RSA_PSS_PARAMS_free(r->pss); + sk_RSA_PRIME_INFO_pop_free(r->prime_infos, rsa_multip_info_free); BN_BLINDING_free(r->blinding); BN_BLINDING_free(r->mt_blinding); OPENSSL_free(r->bignum_data); @@ -240,6 +241,71 @@ int RSA_set0_crt_params(RSA *r, BIGNUM *dmp1, BIGNUM *dmq1, BIGNUM *iqmp) return 1; } +/* + * Is it better to export RSA_PRIME_INFO structure + * and related functions to let user pass a triplet? + */ +int RSA_set0_multi_prime_params(RSA *r, BIGNUM *primes[], BIGNUM *exps[], + BIGNUM *coeffs[], int pnum) +{ + STACK_OF(RSA_PRIME_INFO) *prime_infos, *old = NULL; + RSA_PRIME_INFO *pinfo; + int i; + + if (primes == NULL || exps == NULL || coeffs == NULL || pnum == 0) + return 0; + + prime_infos = sk_RSA_PRIME_INFO_new_reserve(NULL, pnum); + if (prime_infos == NULL) + return 0; + + if (r->prime_infos != NULL) + old = r->prime_infos; + + for (i = 0; i < pnum; i++) { + pinfo = rsa_multip_info_new(); + if (pinfo == NULL) + goto err; + if (primes[i] != NULL && exps[i] != NULL && coeffs[i] != NULL) { + BN_free(pinfo->r); + BN_free(pinfo->d); + BN_free(pinfo->t); + pinfo->r = primes[i]; + pinfo->d = exps[i]; + pinfo->t = coeffs[i]; + } else { + rsa_multip_info_free(pinfo); + goto err; + } + (void)sk_RSA_PRIME_INFO_push(prime_infos, pinfo); + } + + r->prime_infos = prime_infos; + + if (!rsa_multip_calc_product(r)) { + r->prime_infos = old; + goto err; + } + + if (old != NULL) { + /* + * This is hard to deal with, since the old infos could + * also be set by this function and r, d, t should not + * be freed in that case. So currently, stay consistent + * with other *set0* functions: just free it... + */ + sk_RSA_PRIME_INFO_pop_free(old, rsa_multip_info_free); + } + + r->version = RSA_ASN1_VERSION_MULTI; + + return 1; + err: + /* r, d, t should not be freed */ + sk_RSA_PRIME_INFO_pop_free(prime_infos, rsa_multip_info_free_ex); + return 0; +} + void RSA_get0_key(const RSA *r, const BIGNUM **n, const BIGNUM **e, const BIGNUM **d) { @@ -259,6 +325,36 @@ void RSA_get0_factors(const RSA *r, const BIGNUM **p, const BIGNUM **q) *q = r->q; } +int RSA_get_multi_prime_extra_count(const RSA *r) +{ + int pnum; + + pnum = sk_RSA_PRIME_INFO_num(r->prime_infos); + if (pnum <= 0) + pnum = 0; + return pnum; +} + +int RSA_get0_multi_prime_factors(const RSA *r, const BIGNUM *primes[]) +{ + int pnum, i; + RSA_PRIME_INFO *pinfo; + + if ((pnum = RSA_get_multi_prime_extra_count(r)) == 0) + return 0; + + /* + * return other primes + * it's caller's responsibility to allocate oth_primes[pnum] + */ + for (i = 0; i < pnum; i++) { + pinfo = sk_RSA_PRIME_INFO_value(r->prime_infos, i); + primes[i] = pinfo->r; + } + + return 1; +} + void RSA_get0_crt_params(const RSA *r, const BIGNUM **dmp1, const BIGNUM **dmq1, const BIGNUM **iqmp) @@ -271,6 +367,32 @@ void RSA_get0_crt_params(const RSA *r, *iqmp = r->iqmp; } +int RSA_get0_multi_prime_crt_params(const RSA *r, const BIGNUM *exps[], + const BIGNUM *coeffs[]) +{ + int pnum; + + if ((pnum = RSA_get_multi_prime_extra_count(r)) == 0) + return 0; + + /* return other primes */ + if (exps != NULL || coeffs != NULL) { + RSA_PRIME_INFO *pinfo; + int i; + + /* it's the user's job to guarantee the buffer length */ + for (i = 0; i < pnum; i++) { + pinfo = sk_RSA_PRIME_INFO_value(r->prime_infos, i); + if (exps != NULL) + exps[i] = pinfo->d; + if (coeffs != NULL) + coeffs[i] = pinfo->t; + } + } + + return 1; +} + void RSA_clear_flags(RSA *r, int flags) { r->flags &= ~flags; @@ -286,6 +408,12 @@ void RSA_set_flags(RSA *r, int flags) r->flags |= flags; } +int RSA_get_version(RSA *r) +{ + /* { two-prime(0), multi(1) } */ + return r->version; +} + ENGINE *RSA_get0_engine(const RSA *r) { return r->engine; diff --git a/crypto/rsa/rsa_locl.h b/crypto/rsa/rsa_locl.h index be3ef0cf64..6a53d89ede 100644 --- a/crypto/rsa/rsa_locl.h +++ b/crypto/rsa/rsa_locl.h @@ -1,5 +1,5 @@ /* - * Copyright 2006-2016 The OpenSSL Project Authors. All Rights Reserved. + * Copyright 2006-2017 The OpenSSL Project Authors. All Rights Reserved. * * Licensed under the OpenSSL license (the "License"). You may not use * this file except in compliance with the License. You can obtain a copy @@ -10,6 +10,21 @@ #include <openssl/rsa.h> #include "internal/refcount.h" +#define RSA_MAX_PRIME_NUM 16 +#define RSA_MIN_PRIME_SIZE 64 + +typedef struct rsa_prime_info_st { + BIGNUM *r; + BIGNUM *d; + BIGNUM *t; + /* save product of primes prior to this one */ + BIGNUM *pp; + BN_MONT_CTX *m; +} RSA_PRIME_INFO; + +DECLARE_ASN1_ITEM(RSA_PRIME_INFO) +DEFINE_STACK_OF(RSA_PRIME_INFO) + struct rsa_st { /* * The first parameter is used to pickup errors where this is passed @@ -28,6 +43,8 @@ struct rsa_st { BIGNUM *dmp1; BIGNUM *dmq1; BIGNUM *iqmp; + /* for multi-prime RSA, defined in RFC 8017 */ + STACK_OF(RSA_PRIME_INFO) *prime_infos; /* If a PSS only key this contains the parameter restrictions */ RSA_PSS_PARAMS *pss; /* be careful using this if the RSA structure is shared */ @@ -91,6 +108,8 @@ struct rsa_meth_st { * things as "builtin software" implementations. */ int (*rsa_keygen) (RSA *rsa, int bits, BIGNUM *e, BN_GENCB *cb); + int (*rsa_multi_prime_keygen) (RSA *rsa, int bits, int primes, + BIGNUM *e, BN_GENCB *cb); }; extern int int_rsa_verify(int dtype, const unsigned char *m, @@ -105,3 +124,8 @@ RSA_PSS_PARAMS *rsa_pss_params_create(const EVP_MD *sigmd, const EVP_MD *mgf1md, int saltlen); int rsa_pss_get_param(const RSA_PSS_PARAMS *pss, const EVP_MD **pmd, const EVP_MD **pmgf1md, int *psaltlen); +/* internal function to clear and free multi-prime parameters */ +void rsa_multip_info_free_ex(RSA_PRIME_INFO *pinfo); +void rsa_multip_info_free(RSA_PRIME_INFO *pinfo); +RSA_PRIME_INFO *rsa_multip_info_new(void); +int rsa_multip_calc_product(RSA *rsa); diff --git a/crypto/rsa/rsa_meth.c b/crypto/rsa/rsa_meth.c index 9480abd700..5dccc330dc 100644 --- a/crypto/rsa/rsa_meth.c +++ b/crypto/rsa/rsa_meth.c @@ -271,3 +271,17 @@ int RSA_meth_set_keygen(RSA_METHOD *meth, return 1; } +int (*RSA_meth_get_multi_prime_keygen(const RSA_METHOD *meth)) + (RSA *rsa, int bits, int primes, BIGNUM *e, BN_GENCB *cb) +{ + return meth->rsa_multi_prime_keygen; +} + +int RSA_meth_set_multi_prime_keygen(RSA_METHOD *meth, + int (*keygen) (RSA *rsa, int bits, + int primes, BIGNUM *e, + BN_GENCB *cb)) +{ + meth->rsa_multi_prime_keygen = keygen; + return 1; +} diff --git a/crypto/rsa/rsa_mp.c b/crypto/rsa/rsa_mp.c new file mode 100644 index 0000000000..d970564840 --- /dev/null +++ b/crypto/rsa/rsa_mp.c @@ -0,0 +1,95 @@ +/* + * Copyright 2017 The OpenSSL Project Authors. All Rights Reserved. + * Copyright 2017 BaishanCloud. All rights reserved. + * + * Licensed under the OpenSSL license (the "License"). You may not use + * this file except in compliance with the License. You can obtain a copy + * in the file LICENSE in the source distribution or at + * https://www.openssl.org/source/license.html + */ + +#include <openssl/bn.h> +#include "rsa_locl.h" + +void rsa_multip_info_free_ex(RSA_PRIME_INFO *pinfo) +{ + /* free pp and pinfo only */ + BN_clear_free(pinfo->pp); + OPENSSL_free(pinfo); +} + +void rsa_multip_info_free(RSA_PRIME_INFO *pinfo) +{ + /* free a RSA_PRIME_INFO structure */ + BN_clear_free(pinfo->r); + BN_clear_free(pinfo->d); + BN_clear_free(pinfo->t); + rsa_multip_info_free_ex(pinfo); +} + +RSA_PRIME_INFO *rsa_multip_info_new(void) +{ + RSA_PRIME_INFO *pinfo; + + /* create a RSA_PRIME_INFO structure */ + pinfo = OPENSSL_zalloc(sizeof(RSA_PRIME_INFO)); + if (pinfo == NULL) + return NULL; + if ((pinfo->r = BN_secure_new()) == NULL) + goto err; + if ((pinfo->d = BN_secure_new()) == NULL) + goto err; + if ((pinfo->t = BN_secure_new()) == NULL) + goto err; + if ((pinfo->pp = BN_secure_new()) == NULL) + goto err; + + return pinfo; + + err: + BN_free(pinfo->r); + BN_free(pinfo->d); + BN_free(pinfo->t); + BN_free(pinfo->pp); + return NULL; +} + +/* Refill products of primes */ +int rsa_multip_calc_product(RSA *rsa) +{ + RSA_PRIME_INFO *pinfo; + BIGNUM *p1 = NULL, *p2 = NULL; + BN_CTX *ctx = NULL; + int i, rv = 0, ex_primes; + + if ((ex_primes = sk_RSA_PRIME_INFO_num(rsa->prime_infos)) <= 0) { + /* invalid */ + goto err; + } + + if ((ctx = BN_CTX_new()) == NULL) + goto err; + + /* calculate pinfo->pp = p * q for first 'extra' prime */ + p1 = rsa->p; + p2 = rsa->q; + + for (i = 0; i < ex_primes; i++) { + pinfo = sk_RSA_PRIME_INFO_value(rsa->prime_infos, i); + if (pinfo->pp == NULL) { + pinfo->pp = BN_secure_new(); + if (pinfo->pp == NULL) + goto err; + } + if (!BN_mul(pinfo->pp, p1, p2, ctx)) + goto err; + /* save previous one */ + p1 = pinfo->pp; + p2 = pinfo->r; + } + + rv = 1; + err: + BN_CTX_free(ctx); + return rv; +} diff --git a/crypto/rsa/rsa_ossl.c b/crypto/rsa/rsa_ossl.c index 40c84dd3c2..ced11ad883 100644 --- a/crypto/rsa/rsa_ossl.c +++ b/crypto/rsa/rsa_ossl.c @@ -38,7 +38,8 @@ static RSA_METHOD rsa_pkcs1_ossl_meth = { 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 @@ static int rsa_ossl_private_encrypt(int flen, const unsigned char *from, } 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 @@ static int rsa_ossl_private_decrypt(int flen, const unsigned char *from, /* 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_public_decrypt(int flen, const unsigned char *from, 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 @@ static int rsa_ossl_mod_exp(BIGNUM *r0, const BIGNUM *I, RSA *rsa, BN_CTX *ctx) 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 @@ static int rsa_ossl_mod_exp(BIGNUM *r0, const BIGNUM *I, RSA *rsa, BN_CTX *ctx) 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 @@ static int rsa_ossl_mod_exp(BIGNUM *r0, const BIGNUM *I, RSA *rsa, BN_CTX *ctx) 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_init(RSA *rsa) 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; } diff --git a/crypto/rsa/rsa_pmeth.c b/crypto/rsa/rsa_pmeth.c index 5e2df3e8ff..8a114cff89 100644 --- a/crypto/rsa/rsa_pmeth.c +++ b/crypto/rsa/rsa_pmeth.c @@ -25,6 +25,7 @@ typedef struct { /* Key gen parameters */ int nbits; BIGNUM *pub_exp; + int primes; /* Keygen callback info */ int gentmp[2]; /* RSA padding mode */ @@ -54,6 +55,7 @@ static int pkey_rsa_init(EVP_PKEY_CTX *ctx) if (rctx == NULL) return 0; rctx->nbits = 1024; + rctx->primes = RSA_DEFAULT_PRIME_NUM; if (pkey_ctx_is_pss(ctx)) rctx->pad_mode = RSA_PKCS1_PSS_PADDING; else @@ -473,6 +475,14 @@ static int pkey_rsa_ctrl(EVP_PKEY_CTX *ctx, int type, int p1, void *p2) rctx->pub_exp = p2; return 1; + case EVP_PKEY_CTRL_RSA_KEYGEN_PRIMES: + if (p1 < RSA_DEFAULT_PRIME_NUM || p1 > RSA_MAX_PRIME_NUM) { + RSAerr(RSA_F_PKEY_RSA_CTRL, RSA_R_KEY_PRIME_NUM_INVALID); + return -2; + } + rctx->primes = p1; + return 1; + case EVP_PKEY_CTRL_RSA_OAEP_MD: case EVP_PKEY_CTRL_GET_RSA_OAEP_MD: if (rctx->pad_mode != RSA_PKCS1_OAEP_PADDING) { @@ -583,6 +593,7 @@ static int pkey_rsa_ctrl_str(EVP_PKEY_CTX *ctx, } if (strcmp(type, "rsa_padding_mode") == 0) { int pm; + if (strcmp(value, "pkcs1") == 0) { pm = RSA_PKCS1_PADDING; } else if (strcmp(value, "sslv23") == 0) { @@ -606,6 +617,7 @@ static int pkey_rsa_ctrl_str(EVP_PKEY_CTX *ctx, if (strcmp(type, "rsa_pss_saltlen") == 0) { int saltlen; + if (!strcmp(value, "digest")) saltlen = RSA_PSS_SALTLEN_DIGEST; else if (!strcmp(value, "max")) @@ -618,13 +630,14 @@ static int pkey_rsa_ctrl_str(EVP_PKEY_CTX *ctx, } if (strcmp(type, "rsa_keygen_bits") == 0) { - int nbits; - nbits = atoi(value); + int nbits = atoi(value); + return EVP_PKEY_CTX_set_rsa_keygen_bits(ctx, nbits); } if (strcmp(type, "rsa_keygen_pubexp") == 0) { int ret; + BIGNUM *pubexp = NULL; if (!BN_asc2bn(&pubexp, value)) return 0; @@ -634,6 +647,12 @@ static int pkey_rsa_ctrl_str(EVP_PKEY_CTX *ctx, return ret; } + if (strcmp(type, "rsa_keygen_primes") == 0) { + int nprimes = atoi(value); + + return EVP_PKEY_CTX_set_rsa_keygen_primes(ctx, nprimes); + } + if (strcmp(type, "rsa_mgf1_md") == 0) return EVP_PKEY_CTX_md(ctx, EVP_PKEY_OP_TYPE_SIG | EVP_PKEY_OP_TYPE_CRYPT, @@ -664,6 +683,7 @@ static int pkey_rsa_ctrl_str(EVP_PKEY_CTX *ctx, unsigned char *lab; long lablen; int ret; + lab = OPENSSL_hexstr2buf(value, &lablen); if (!lab) return 0; @@ -718,7 +738,8 @@ static int pkey_rsa_keygen(EVP_PKEY_CTX *ctx, EVP_PKEY *pkey) } else { pcb = NULL; } - ret = RSA_generate_key_ex(rsa, rctx->nbits, rctx->pub_exp, pcb); + ret = RSA_generate_multi_prime_key(rsa, rctx->nbits, rctx->primes, + rctx->pub_exp, pcb); BN_GENCB_free(pcb); if (ret > 0 && !rsa_set_pss_param(rsa, ctx)) { RSA_free(rsa); |