From: Paul Yang Date: Tue, 1 Aug 2017 18:19:43 +0000 (+0800) Subject: Support multi-prime RSA (RFC 8017) X-Git-Tag: OpenSSL_1_1_1-pre1~425 X-Git-Url: https://git.openssl.org/?p=openssl.git;a=commitdiff_plain;h=665d899fa6d3571da016925067ebcf1789d7d19c 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 Reviewed-by: Bernd Edlinger (Merged from https://github.com/openssl/openssl/pull/4241) --- diff --git a/CHANGES b/CHANGES index 0b0c3cab2d..3ae8b4d0bd 100644 --- a/CHANGES +++ b/CHANGES @@ -9,6 +9,9 @@ Changes between 1.1.0f and 1.1.1 [xx XXX xxxx] + *) Add multi-prime RSA (RFC 8017) support. + [Paul Yang] + *) Add SM3 implemented according to GB/T 32905-2016 [ Jack Lloyd , Ronald Tse , diff --git a/apps/genrsa.c b/apps/genrsa.c index b4a986cb58..f147852902 100644 --- a/apps/genrsa.c +++ b/apps/genrsa.c @@ -27,13 +27,14 @@ NON_EMPTY_TRANSLATION_UNIT # include # define DEFBITS 2048 +# define DEFPRIMES 2 static int genrsa_cb(int p, int n, BN_GENCB *cb); typedef enum OPTION_choice { OPT_ERR = -1, OPT_EOF = 0, OPT_HELP, OPT_3, OPT_F4, OPT_ENGINE, - OPT_OUT, OPT_PASSOUT, OPT_CIPHER, + OPT_OUT, OPT_PASSOUT, OPT_CIPHER, OPT_PRIMES, OPT_R_ENUM } OPTION_CHOICE; @@ -49,6 +50,7 @@ const OPTIONS genrsa_options[] = { # ifndef OPENSSL_NO_ENGINE {"engine", OPT_ENGINE, 's', "Use engine, possibly a hardware device"}, # endif + {"primes", OPT_PRIMES, 'p', "Specify number of primes"}, {NULL} }; @@ -62,7 +64,7 @@ int genrsa_main(int argc, char **argv) const BIGNUM *e; RSA *rsa = NULL; const EVP_CIPHER *enc = NULL; - int ret = 1, num = DEFBITS, private = 0; + int ret = 1, num = DEFBITS, private = 0, primes = DEFPRIMES; unsigned long f4 = RSA_F4; char *outfile = NULL, *passoutarg = NULL, *passout = NULL; char *prog, *hexe, *dece; @@ -108,6 +110,10 @@ opthelp: if (!opt_cipher(opt_unknown(), &enc)) goto end; break; + case OPT_PRIMES: + if (!opt_int(opt_arg(), &primes)) + goto end; + break; } } argc = opt_num_rest(); @@ -131,13 +137,14 @@ opthelp: if (out == NULL) goto end; - BIO_printf(bio_err, "Generating RSA private key, %d bit long modulus\n", - num); + BIO_printf(bio_err, "Generating RSA private key, %d bit long modulus (%d primes)\n", + num, primes); rsa = eng ? RSA_new_method(eng) : RSA_new(); if (rsa == NULL) goto end; - if (!BN_set_word(bn, f4) || !RSA_generate_key_ex(rsa, num, bn, cb)) + if (!BN_set_word(bn, f4) + || !RSA_generate_multi_prime_key(rsa, num, primes, bn, cb)) goto end; RSA_get0_key(rsa, NULL, &e, NULL); diff --git a/apps/speed.c b/apps/speed.c index 063bc1c2dc..c52dac608a 100644 --- a/apps/speed.c +++ b/apps/speed.c @@ -339,7 +339,8 @@ static int found(const char *name, const OPT_PAIR *pairs, int *result) typedef enum OPTION_choice { OPT_ERR = -1, OPT_EOF = 0, OPT_HELP, OPT_ELAPSED, OPT_EVP, OPT_DECRYPT, OPT_ENGINE, OPT_MULTI, - OPT_MR, OPT_MB, OPT_MISALIGN, OPT_ASYNCJOBS, OPT_R_ENUM + OPT_MR, OPT_MB, OPT_MISALIGN, OPT_ASYNCJOBS, OPT_R_ENUM, + OPT_PRIMES } OPTION_CHOICE; const OPTIONS speed_options[] = { @@ -366,6 +367,7 @@ const OPTIONS speed_options[] = { #ifndef OPENSSL_NO_ENGINE {"engine", OPT_ENGINE, 's', "Use engine, possibly a hardware device"}, #endif + {"primes", OPT_PRIMES, 'p', "Specify number of primes (for RSA only)"}, {NULL}, }; @@ -1325,6 +1327,7 @@ int speed_main(int argc, char **argv) sizeof(test15360) }; int rsa_doit[RSA_NUM] = { 0 }; + int primes = RSA_DEFAULT_PRIME_NUM; #endif #ifndef OPENSSL_NO_DSA static const unsigned int dsa_bits[DSA_NUM] = { 512, 1024, 2048 }; @@ -1459,6 +1462,10 @@ int speed_main(int argc, char **argv) if (!opt_rand(o)) goto end; break; + case OPT_PRIMES: + if (!opt_int(opt_arg(), &primes)) + goto end; + break; } } argc = opt_num_rest(); @@ -1615,6 +1622,10 @@ int speed_main(int argc, char **argv) #ifndef OPENSSL_NO_RSA for (i = 0; i < loopargs_len; i++) { + if (primes > RSA_DEFAULT_PRIME_NUM) { + /* for multi-prime RSA, skip this */ + break; + } for (k = 0; k < RSA_NUM; k++) { const unsigned char *p; @@ -2395,6 +2406,34 @@ int speed_main(int argc, char **argv) if (!rsa_doit[testnum]) continue; for (i = 0; i < loopargs_len; i++) { + if (primes > 2) { + /* we haven't set keys yet, generate multi-prime RSA keys */ + BIGNUM *bn = BN_new(); + + if (bn == NULL) + goto end; + if (!BN_set_word(bn, RSA_F4)) { + BN_free(bn); + goto end; + } + + BIO_printf(bio_err, "Generate multi-prime RSA key for %s\n", + rsa_choices[testnum].name); + + loopargs[i].rsa_key[testnum] = RSA_new(); + if (loopargs[i].rsa_key[testnum] == NULL) { + BN_free(bn); + goto end; + } + + if (!RSA_generate_multi_prime_key(loopargs[i].rsa_key[testnum], + rsa_bits[testnum], + primes, bn, NULL)) { + BN_free(bn); + goto end; + } + BN_free(bn); + } st = RSA_sign(NID_md5_sha1, loopargs[i].buf, 36, loopargs[i].buf2, &loopargs[i].siglen, loopargs[i].rsa_key[testnum]); if (st == 0) diff --git a/crypto/err/openssl.txt b/crypto/err/openssl.txt index 8547d07882..e7353aa3e8 100644 --- a/crypto/err/openssl.txt +++ b/crypto/err/openssl.txt @@ -2224,6 +2224,7 @@ RSA_R_INVALID_HEADER:137:invalid header RSA_R_INVALID_LABEL:160:invalid label RSA_R_INVALID_MESSAGE_LENGTH:131:invalid message length RSA_R_INVALID_MGF1_MD:156:invalid mgf1 md +RSA_R_INVALID_MULTI_PRIME_KEY:167:invalid multi prime key RSA_R_INVALID_OAEP_PARAMETERS:161:invalid oaep parameters RSA_R_INVALID_PADDING:138:invalid padding RSA_R_INVALID_PADDING_MODE:141:invalid padding mode @@ -2233,12 +2234,17 @@ RSA_R_INVALID_SALT_LENGTH:150:invalid salt length RSA_R_INVALID_TRAILER:139:invalid trailer RSA_R_INVALID_X931_DIGEST:142:invalid x931 digest RSA_R_IQMP_NOT_INVERSE_OF_Q:126:iqmp not inverse of q +RSA_R_KEY_PRIME_NUM_INVALID:165:key prime num invalid RSA_R_KEY_SIZE_TOO_SMALL:120:key size too small RSA_R_LAST_OCTET_INVALID:134:last octet invalid RSA_R_MGF1_DIGEST_NOT_ALLOWED:152:mgf1 digest not allowed RSA_R_MODULUS_TOO_LARGE:105:modulus too large +RSA_R_MP_COEFFICIENT_NOT_INVERSE_OF_R:168:mp coefficient not inverse of r +RSA_R_MP_EXPONENT_NOT_CONGRUENT_TO_D:169:mp exponent not congruent to d +RSA_R_MP_R_NOT_PRIME:170:mp r not prime RSA_R_NO_PUBLIC_EXPONENT:140:no public exponent RSA_R_NULL_BEFORE_BLOCK_MISSING:113:null before block missing +RSA_R_N_DOES_NOT_EQUAL_PRODUCT_OF_PRIMES:172:n does not equal product of primes RSA_R_N_DOES_NOT_EQUAL_P_Q:127:n does not equal p q RSA_R_OAEP_DECODING_ERROR:121:oaep decoding error RSA_R_OPERATION_NOT_SUPPORTED_FOR_THIS_KEYTYPE:148:\ 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 #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 #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 #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 +#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); diff --git a/doc/man1/genpkey.pod b/doc/man1/genpkey.pod index ddfd04002c..d8f1c24f74 100644 --- a/doc/man1/genpkey.pod +++ b/doc/man1/genpkey.pod @@ -105,6 +105,29 @@ below. The number of bits in the generated key. If not specified 1024 is used. +=item B + +The number of primes in the generated key. If not specified 2 is used. + +=item B + +The RSA public exponent value. This can be a large decimal or +hexadecimal value if preceded by B<0x>. Default value is 65537. + +=back + +=head1 RSA-PSS KEY GENERATION OPTIONS + +Note: by default an B key has no parameter restrictions. + +=over 4 + +=item B, B + +These options have the same meaning as the B algorithm. + +=item B + =item B The RSA public exponent value. This can be a large decimal or diff --git a/doc/man1/genrsa.pod b/doc/man1/genrsa.pod index f6a2d8a7f3..3e42c98f5d 100644 --- a/doc/man1/genrsa.pod +++ b/doc/man1/genrsa.pod @@ -28,6 +28,7 @@ B B [B<-rand file...>] [B<-writerand file>] [B<-engine id>] +[B<-primes num>] [B] =head1 DESCRIPTION @@ -83,6 +84,13 @@ to attempt to obtain a functional reference to the specified engine, thus initialising it if needed. The engine will then be set as the default for all available algorithms. +=item B<-primes num> + +Specify the number of primes to use while generating the RSA key. The B +parameter must be a positive integer that is greater than 1 and less than 16. +If B is greater than 2, then the generated key is called a 'multi-prime' +RSA key, which is defined in RFC 8017. + =item B The size of the private key to generate in bits. This must be the last option @@ -92,15 +100,17 @@ specified. The default is 2048. =head1 NOTES -RSA private key generation essentially involves the generation of two prime -numbers. When generating a private key various symbols will be output to +RSA private key generation essentially involves the generation of two or more +prime numbers. When generating a private key various symbols will be output to indicate the progress of the generation. A B<.> represents each number which has passed an initial sieve test, B<+> means a number has passed a single -round of the Miller-Rabin primality test. A newline means that the number has -passed all the prime tests (the actual number depends on the key size). +round of the Miller-Rabin primality test, B<*> means the current prime starts +a regenerating progress due to some failed tests. A newline means that the number +has passed all the prime tests (the actual number depends on the key size). Because key generation is a random process the time taken to generate a key -may vary somewhat. +may vary somewhat. But in general, more primes lead to less generation time +of a key. =head1 BUGS diff --git a/doc/man1/speed.pod b/doc/man1/speed.pod index d8d5f6f22b..80602a4625 100644 --- a/doc/man1/speed.pod +++ b/doc/man1/speed.pod @@ -15,6 +15,7 @@ B [B<-decrypt>] [B<-rand file...>] [B<-writerand file>] +[B<-primes num>] [B] =head1 DESCRIPTION @@ -65,6 +66,11 @@ all others. Writes random data to the specified I upon exit. This can be used with a subsequent B<-rand> flag. +=item B<-primes num> + +Generate a B-prime RSA key and use it to run the benchmarks. This option +is only effective if RSA algorithm is specified to test. + =item B<[zero or more test algorithms]> If any options are given, B tests those algorithms, otherwise all of diff --git a/doc/man3/RSA_generate_key.pod b/doc/man3/RSA_generate_key.pod index be18ae24ff..6e8e50c0ca 100644 --- a/doc/man3/RSA_generate_key.pod +++ b/doc/man3/RSA_generate_key.pod @@ -2,13 +2,15 @@ =head1 NAME -RSA_generate_key_ex, RSA_generate_key - generate RSA key pair +RSA_generate_key_ex, RSA_generate_key, +RSA_generate_multi_prime_key - generate RSA key pair =head1 SYNOPSIS #include int RSA_generate_key_ex(RSA *rsa, int bits, BIGNUM *e, BN_GENCB *cb); + int RSA_generate_multi_prime_key(RSA *rsa, int bits, int primes, BIGNUM *e, BN_GENCB *cb); Deprecated: @@ -19,13 +21,19 @@ Deprecated: =head1 DESCRIPTION -RSA_generate_key_ex() generates a key pair and stores it in the B -structure provided in B. The pseudo-random number generator must +RSA_generate_key_ex() generates a 2-prime RSA key pair and stores it in the +B structure provided in B. The pseudo-random number generator must be seeded prior to calling RSA_generate_key_ex(). -The modulus size will be of length B, and the public exponent will be -B. Key sizes with B E 1024 should be considered insecure. -The exponent is an odd number, typically 3, 17 or 65537. +RSA_generate_multi_prime_key() generates a multi-prime RSA key pair and stores +it in the B structure provided in B. The number of primes is given by +the B parameter. The pseudo-random number generator must be seeded prior +to calling RSA_generate_multi_prime_key(). + +The modulus size will be of length B, the number of primes to form the +modulus will be B, and the public exponent will be B. Key sizes +with B E 1024 should be considered insecure. The exponent is an odd +number, typically 3, 17 or 65537. A callback function may be used to provide feedback about the progress of the key generation. If B is not B, it @@ -55,10 +63,12 @@ it is called as B. =back -The process is then repeated for prime q with B. +The process is then repeated for prime q and other primes (if any) +with B where B indicates the i-th prime. =head1 RETURN VALUE +RSA_generate_multi_prime_key() returns 1 on success or 0 on error. RSA_generate_key_ex() returns 1 on success or 0 on error. The error codes can be obtained by L. @@ -81,7 +91,7 @@ RSA_generate_key_ex() intsead. =head1 COPYRIGHT -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 diff --git a/doc/man3/RSA_get0_key.pod b/doc/man3/RSA_get0_key.pod index 55a39a3105..6e6576e7f3 100644 --- a/doc/man3/RSA_get0_key.pod +++ b/doc/man3/RSA_get0_key.pod @@ -4,8 +4,10 @@ RSA_set0_key, RSA_set0_factors, RSA_set0_crt_params, RSA_get0_key, RSA_get0_factors, RSA_get0_crt_params, RSA_clear_flags, -RSA_test_flags, RSA_set_flags, RSA_get0_engine - Routines for getting -and setting data in an RSA object +RSA_test_flags, RSA_set_flags, RSA_get0_engine, 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 +- Routines for getting and setting data in an RSA object =head1 SYNOPSIS @@ -24,6 +26,13 @@ and setting data in an RSA object int RSA_test_flags(const RSA *r, int flags); void RSA_set_flags(RSA *r, int flags); ENGINE *RSA_get0_engine(RSA *r); + int RSA_get_multi_prime_extra_count(const RSA *r); + int RSA_get0_multi_prime_factors(const RSA *r, const BIGNUM *primes[]); + int RSA_get0_multi_prime_crt_params(const RSA *r, const BIGNUM *exps[], + const BIGNUM *coeffs[]); + int RSA_set0_multi_prime_params(RSA *r, BIGNUM *primes[], BIGNUM *exps[], + BIGNUM *coeffs[], int pnum); + int RSA_get_version(RSA *r); =head1 DESCRIPTION @@ -36,6 +45,11 @@ private key (see PKCS#1 section 3 Key Types), where B

and B are the first and second factor of B and B, B and B are the exponents and coefficient for CRT calculations. +For multi-prime RSA (defined in RFC 8017), there are also one or more +'triplet' in an RSA object. A triplet contains three members, B, B +and B. B is the additional prime besides B

and B. B and +B are the exponent and coefficient for CRT calculations. + The B, B and B parameters can be obtained by calling RSA_get0_key(). If they have not been set yet, then B<*n>, B<*e> and B<*d> will be set to NULL. Otherwise, they are set to pointers to @@ -59,9 +73,15 @@ B and B parameters can be obtained and set with RSA_get0_crt_params() and RSA_set0_crt_params(). For RSA_get0_key(), RSA_get0_factors(), and RSA_get0_crt_params(), -NULL value BIGNUM ** output parameters are permitted. The functions +NULL value BIGNUM ** output parameters are permitted. The functions ignore NULL parameters but return values for other, non-NULL, parameters. +For multi-prime RSA, RSA_get0_multi_prime_factors() and RSA_get0_multi_prime_params() +can be used to obtain other primes and related CRT parameters. The +return values are stored in an array of B. RSA_set0_multi_prime_params() +sets a collect of multi-prime 'triplet' members (prime, exponent and coefficient) +into an RSA object. + RSA_set_flags() sets the flags in the B parameter on the RSA object. Multiple flags can be passed in one go (bitwise ORed together). Any flags that are already set are left set. RSA_test_flags() tests to @@ -74,6 +94,8 @@ RSA object. RSA_get0_engine() returns a handle to the ENGINE that has been set for this RSA object, or NULL if no such ENGINE has been set. +RSA_get_version() returns the version of an RSA object B. + =head1 NOTES Values retrieved with RSA_get0_key() are owned by the RSA object used @@ -82,10 +104,27 @@ needed, duplicate the received value using BN_dup() and pass the duplicate. The same applies to RSA_get0_factors() and RSA_set0_factors() as well as RSA_get0_crt_params() and RSA_set0_crt_params(). +The caller should obtain the size by calling RSA_get_multi_prime_extra_count() +in advance and allocate sufficient buffer to store the return values before +calling RSA_get0_multi_prime_factors() and RSA_get0_multi_prime_params(). + +RSA_set0_multi_prime_params() always clears the original multi-prime +triplets in RSA object B and assign the new set of triplets into it. + =head1 RETURN VALUES -RSA_set0_key(), RSA_set0_factors and RSA_set0_crt_params() return 1 on -success or 0 on failure. +RSA_set0_key(), RSA_set0_factors(), RSA_set0_crt_params() and +RSA_set0_multi_prime_params() return 1 on success or 0 on failure. + +RSA_get0_multi_prime_factors() and RSA_get0_multi_prime_crt_params() return +1 on success or 0 on failure. + +RSA_get_multi_prime_extra_count() returns two less than the number of primes +in use, which is 0 for traditional RSA and the number of extra primes for +multi-prime RSA. + +RSA_get_version() returns B for multi-prime RSA and +B for normal two-prime RSA, as defined in RFC 8017. RSA_test_flags() returns the current state of the flags in the RSA object. @@ -98,11 +137,15 @@ L, L =head1 HISTORY -The functions described here were added in OpenSSL 1.1.0. +RSA_get_multi_prime_extra_count(), RSA_get0_multi_prime_factors(), +RSA_get0_multi_prime_crt_params(), RSA_set0_multi_prime_params(), +and RSA_get_version() functions were added in OpenSSL 1.1.1. + +Other functions described here were added in OpenSSL 1.1.0. =head1 COPYRIGHT -Copyright 2016 The OpenSSL Project Authors. All Rights Reserved. +Copyright 2016-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 diff --git a/doc/man3/RSA_meth_new.pod b/doc/man3/RSA_meth_new.pod index a578389ba8..fde1a41e64 100644 --- a/doc/man3/RSA_meth_new.pod +++ b/doc/man3/RSA_meth_new.pod @@ -12,7 +12,8 @@ RSA_meth_set_priv_dec, RSA_meth_get_mod_exp, RSA_meth_set_mod_exp, RSA_meth_get_bn_mod_exp, RSA_meth_set_bn_mod_exp, RSA_meth_get_init, RSA_meth_set_init, RSA_meth_get_finish, RSA_meth_set_finish, RSA_meth_get_sign, RSA_meth_set_sign, RSA_meth_get_verify, -RSA_meth_set_verify, RSA_meth_get_keygen, RSA_meth_set_keygen +RSA_meth_set_verify, RSA_meth_get_keygen, RSA_meth_set_keygen, +RSA_meth_get_multi_prime_keygen, RSA_meth_set_multi_prime_keygen - Routines to build up RSA methods =head1 SYNOPSIS @@ -111,6 +112,15 @@ RSA_meth_set_verify, RSA_meth_get_keygen, RSA_meth_set_keygen int (*keygen)(RSA *rsa, int bits, BIGNUM *e, BN_GENCB *cb)); + int (*RSA_meth_get_multi_prime_keygen(const RSA_METHOD *meth))(RSA *rsa, int bits, + int primes, BIGNUM *e, + BN_GENCB *cb); + + int RSA_meth_set_multi_prime_keygen(RSA_METHOD *meth, + int (*keygen) (RSA *rsa, int bits, + int primes, BIGNUM *e, + BN_GENCB *cb)); + =head1 DESCRIPTION The B type is a structure used for the provision of custom @@ -193,8 +203,14 @@ by this function. This function may be NULL. RSA_meth_get_keygen() and RSA_meth_set_keygen() get and set the function used for generating a new RSA key pair respectively. This function will be called in response to the application calling -RSA_generate_key(). The parameter for the function has the same -meaning as for RSA_generate_key(). +RSA_generate_key_ex(). The parameter for the function has the same +meaning as for RSA_generate_key_ex(). + +RSA_meth_get_multi_prime_keygen() and RSA_meth_set_multi_prime_keygen() get +and set the function used for generating a new multi-prime RSA key pair +respectively. This function will be called in response to the application calling +RSA_generate_multi_prime_key(). The parameter for the function has the same +meaning as for RSA_generate_multi_prime_key(). RSA_meth_get_pub_enc(), RSA_meth_set_pub_enc(), RSA_meth_get_pub_dec(), RSA_meth_set_pub_dec(), @@ -223,12 +239,16 @@ success or 0 on failure. =head1 SEE ALSO -L, L, L, -L, L, L +L, L, L, +L, L, L, +L =head1 HISTORY -The functions described here were added in OpenSSL 1.1.0. +RSA_meth_get_multi_prime_keygen() and RSA_meth_set_multi_prime_keygen() were +added in OpenSSL 1.1.1. + +Other functions described here were added in OpenSSL 1.1.0. =head1 COPYRIGHT diff --git a/include/openssl/rsa.h b/include/openssl/rsa.h index f45ea2e90c..8985219aee 100644 --- a/include/openssl/rsa.h +++ b/include/openssl/rsa.h @@ -45,6 +45,12 @@ extern "C" { # define RSA_3 0x3L # define RSA_F4 0x10001L +/* based on RFC 8017 appendix A.1.2 */ +# define RSA_ASN1_VERSION_DEFAULT 0 +# define RSA_ASN1_VERSION_MULTI 1 + +# define RSA_DEFAULT_PRIME_NUM 2 + # define RSA_METHOD_FLAG_NO_CHECK 0x0001/* don't check pub/private * match */ @@ -120,6 +126,10 @@ extern "C" { RSA_pkey_ctx_ctrl(ctx, EVP_PKEY_OP_KEYGEN, \ EVP_PKEY_CTRL_RSA_KEYGEN_PUBEXP, 0, pubexp) +# define EVP_PKEY_CTX_set_rsa_keygen_primes(ctx, primes) \ + RSA_pkey_ctx_ctrl(ctx, EVP_PKEY_OP_KEYGEN, \ + EVP_PKEY_CTRL_RSA_KEYGEN_PRIMES, primes, NULL) + # define EVP_PKEY_CTX_set_rsa_mgf1_md(ctx, md) \ RSA_pkey_ctx_ctrl(ctx, EVP_PKEY_OP_TYPE_SIG | EVP_PKEY_OP_TYPE_CRYPT, \ EVP_PKEY_CTRL_RSA_MGF1_MD, 0, (void *)(md)) @@ -170,6 +180,8 @@ extern "C" { # define EVP_PKEY_CTRL_GET_RSA_OAEP_MD (EVP_PKEY_ALG_CTRL + 11) # define EVP_PKEY_CTRL_GET_RSA_OAEP_LABEL (EVP_PKEY_ALG_CTRL + 12) +# define EVP_PKEY_CTRL_RSA_KEYGEN_PRIMES (EVP_PKEY_ALG_CTRL + 13) + # define RSA_PKCS1_PADDING 1 # define RSA_SSLV23_PADDING 2 # define RSA_NO_PADDING 3 @@ -192,15 +204,22 @@ int RSA_security_bits(const RSA *rsa); int RSA_set0_key(RSA *r, BIGNUM *n, BIGNUM *e, BIGNUM *d); int RSA_set0_factors(RSA *r, BIGNUM *p, BIGNUM *q); int RSA_set0_crt_params(RSA *r,BIGNUM *dmp1, BIGNUM *dmq1, BIGNUM *iqmp); +int RSA_set0_multi_prime_params(RSA *r, BIGNUM *primes[], BIGNUM *exps[], + BIGNUM *coeffs[], int pnum); void RSA_get0_key(const RSA *r, const BIGNUM **n, const BIGNUM **e, const BIGNUM **d); void RSA_get0_factors(const RSA *r, const BIGNUM **p, const BIGNUM **q); +int RSA_get_multi_prime_extra_count(const RSA *r); +int RSA_get0_multi_prime_factors(const RSA *r, const BIGNUM *primes[]); void RSA_get0_crt_params(const RSA *r, const BIGNUM **dmp1, const BIGNUM **dmq1, const BIGNUM **iqmp); +int RSA_get0_multi_prime_crt_params(const RSA *r, const BIGNUM *exps[], + const BIGNUM *coeffs[]); void RSA_clear_flags(RSA *r, int flags); int RSA_test_flags(const RSA *r, int flags); void RSA_set_flags(RSA *r, int flags); +int RSA_get_version(RSA *r); ENGINE *RSA_get0_engine(const RSA *r); /* Deprecated version */ @@ -210,6 +229,9 @@ DEPRECATEDIN_0_9_8(RSA *RSA_generate_key(int bits, unsigned long e, void /* New version */ int RSA_generate_key_ex(RSA *rsa, int bits, BIGNUM *e, BN_GENCB *cb); +/* Multi-prime version */ +int RSA_generate_multi_prime_key(RSA *rsa, int bits, int primes, + BIGNUM *e, BN_GENCB *cb); int RSA_X931_derive_ex(RSA *rsa, BIGNUM *p1, BIGNUM *p2, BIGNUM *q1, BIGNUM *q2, const BIGNUM *Xp1, const BIGNUM *Xp2, @@ -468,6 +490,12 @@ int (*RSA_meth_get_keygen(const RSA_METHOD *meth)) int RSA_meth_set_keygen(RSA_METHOD *rsa, int (*keygen) (RSA *rsa, int bits, BIGNUM *e, BN_GENCB *cb)); +int (*RSA_meth_get_multi_prime_keygen(const RSA_METHOD *meth)) + (RSA *rsa, int bits, int primes, BIGNUM *e, BN_GENCB *cb); +int RSA_meth_set_multi_prime_keygen(RSA_METHOD *meth, + int (*keygen) (RSA *rsa, int bits, + int primes, BIGNUM *e, + BN_GENCB *cb)); int ERR_load_RSA_strings(void); # ifdef __cplusplus diff --git a/include/openssl/rsaerr.h b/include/openssl/rsaerr.h index 6e6aac28b0..94bfd93fc7 100644 --- a/include/openssl/rsaerr.h +++ b/include/openssl/rsaerr.h @@ -114,6 +114,7 @@ int ERR_load_RSA_strings(void); # define RSA_R_INVALID_LABEL 160 # define RSA_R_INVALID_MESSAGE_LENGTH 131 # define RSA_R_INVALID_MGF1_MD 156 +# define RSA_R_INVALID_MULTI_PRIME_KEY 167 # define RSA_R_INVALID_OAEP_PARAMETERS 161 # define RSA_R_INVALID_PADDING 138 # define RSA_R_INVALID_PADDING_MODE 141 @@ -123,12 +124,17 @@ int ERR_load_RSA_strings(void); # define RSA_R_INVALID_TRAILER 139 # define RSA_R_INVALID_X931_DIGEST 142 # define RSA_R_IQMP_NOT_INVERSE_OF_Q 126 +# define RSA_R_KEY_PRIME_NUM_INVALID 165 # define RSA_R_KEY_SIZE_TOO_SMALL 120 # define RSA_R_LAST_OCTET_INVALID 134 # define RSA_R_MGF1_DIGEST_NOT_ALLOWED 152 # define RSA_R_MODULUS_TOO_LARGE 105 +# define RSA_R_MP_COEFFICIENT_NOT_INVERSE_OF_R 168 +# define RSA_R_MP_EXPONENT_NOT_CONGRUENT_TO_D 169 +# define RSA_R_MP_R_NOT_PRIME 170 # define RSA_R_NO_PUBLIC_EXPONENT 140 # define RSA_R_NULL_BEFORE_BLOCK_MISSING 113 +# define RSA_R_N_DOES_NOT_EQUAL_PRODUCT_OF_PRIMES 172 # define RSA_R_N_DOES_NOT_EQUAL_P_Q 127 # define RSA_R_OAEP_DECODING_ERROR 121 # define RSA_R_OPERATION_NOT_SUPPORTED_FOR_THIS_KEYTYPE 148 diff --git a/test/build.info b/test/build.info index d7cfd7e6c4..3d7af31ab6 100644 --- a/test/build.info +++ b/test/build.info @@ -46,7 +46,7 @@ INCLUDE_MAIN___test_libtestutil_OLB = /INCLUDE=MAIN x509_time_test x509_dup_cert_test x509_check_cert_pkey_test \ recordlentest drbgtest sslbuffertest \ time_offset_test pemtest ssl_cert_table_internal_test ciphername_test \ - servername_test ocspapitest + servername_test ocspapitest rsa_mp_test SOURCE[aborttest]=aborttest.c INCLUDE[aborttest]=../include @@ -152,6 +152,10 @@ INCLUDE_MAIN___test_libtestutil_OLB = /INCLUDE=MAIN INCLUDE[rsa_test]=.. ../include DEPEND[rsa_test]=../libcrypto libtestutil.a + SOURCE[rsa_mp_test]=rsa_mp_test.c + INCLUDE[rsa_mp_test]=.. ../include + DEPEND[rsa_mp_test]=../libcrypto libtestutil.a + SOURCE[evp_test]=evp_test.c INCLUDE[evp_test]=../include DEPEND[evp_test]=../libcrypto libtestutil.a diff --git a/test/recipes/15-test_mp_rsa.t b/test/recipes/15-test_mp_rsa.t new file mode 100644 index 0000000000..f601c4c11d --- /dev/null +++ b/test/recipes/15-test_mp_rsa.t @@ -0,0 +1,126 @@ +#! /usr/bin/env perl +# 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 + + +use strict; +use warnings; + +use File::Spec; +use OpenSSL::Test qw/:DEFAULT data_file/; +use OpenSSL::Test::Utils; + +setup("test_mp_rsa"); + +plan tests => 61; + +ok(run(test(["rsa_mp_test"])), "running rsa multi prime test"); + +my $cleartext = data_file("plain_text"); + +my @test_param = ( + # 3 primes, 2048-bit + { + primes => '3', + bits => '2048', + }, + # 4 primes, 2048-bit + { + primes => '4', + bits => '2048', + }, + # 8 primes, 2048-bit + { + primes => '8', + bits => '2048', + }, + # 15 primes, 2048-bit + { + primes => '15', + bits => '2048', + }, + # 8 primes, 15360-bit (3 & 4 primes for 15360 bit is too long to gen a key) + { + primes => '8', + bits => '15360', + }, + # 15 primes, 15360-bit + { + primes => '15', + bits => '15360', + }, +); + +# genrsa +run_mp_tests(0); +# evp +run_mp_tests(1); + +sub run_mp_tests { + my $evp = shift; + + foreach my $param (@test_param) { + my $primes = $param->{primes}; + my $bits = $param->{bits}; + my $name = ($evp ? "evp" : "") . "${bits}p${primes}"; + + if ($evp) { + ok(run(app([ 'openssl', 'genpkey', '-out', 'rsamptest.pem', + '-algorithm', 'RSA', '-pkeyopt', "rsa_keygen_primes:$primes", + '-pkeyopt', "rsa_keygen_bits:$bits"])), "genrsa $name"); + } else { + ok(run(app([ 'openssl', 'genrsa', '-out', 'rsamptest.pem', + '-primes', $primes, $bits])), "genrsa $name"); + } + + ok(run(app([ 'openssl', 'rsa', '-check', '-in', 'rsamptest.pem', + '-noout'])), "rsa -check $name"); + if ($evp) { + ok(run(app([ 'openssl', 'pkeyutl', '-inkey', 'rsamptest.pem', + '-encrypt', '-in', $cleartext, + '-out', 'rsamptest.enc' ])), "rsa $name encrypt"); + ok(run(app([ 'openssl', 'pkeyutl', '-inkey', 'rsamptest.pem', + '-decrypt', '-in', 'rsamptest.enc', + '-out', 'rsamptest.dec' ])), "rsa $name decrypt"); + } else { + ok(run(app([ 'openssl', 'rsautl', '-inkey', 'rsamptest.pem', + '-encrypt', '-in', $cleartext, + '-out', 'rsamptest.enc' ])), "rsa $name encrypt"); + ok(run(app([ 'openssl', 'rsautl', '-inkey', 'rsamptest.pem', + '-decrypt', '-in', 'rsamptest.enc', + '-out', 'rsamptest.dec' ])), "rsa $name decrypt"); + } + + ok(check_msg(), "rsa $name check result"); + + # clean up temp files + unlink 'rsamptest.pem'; + unlink 'rsamptest.enc'; + unlink 'rsamptest.dec'; + } +} + +sub check_msg { + my $msg; + my $dec; + + open(my $fh, "<", $cleartext) or return 0; + binmode $fh; + read($fh, $msg, 10240); + close $fh; + open($fh, "<", "rsamptest.dec") or return 0; + binmode $fh; + read($fh, $dec, 10240); + close $fh; + + if ($msg ne $dec) { + print STDERR "cleartext and decrypted are not the same"; + return 0; + } + return 1; +} diff --git a/test/recipes/15-test_mp_rsa_data/plain_text b/test/recipes/15-test_mp_rsa_data/plain_text new file mode 100644 index 0000000000..60d11c0f69 --- /dev/null +++ b/test/recipes/15-test_mp_rsa_data/plain_text @@ -0,0 +1,4 @@ +It was the best of times, it was the worst of times, +it was the age of wisdom, it was the age of foolishness, +it was the epoch of belief, it was the epoch of incredulity, +it was the season of Light, it was the season of Darkness. diff --git a/test/rsa_mp_test.c b/test/rsa_mp_test.c new file mode 100644 index 0000000000..ea4701e762 --- /dev/null +++ b/test/rsa_mp_test.c @@ -0,0 +1,370 @@ +/* + * 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 + */ + +/* This aims to test the setting functions */ + +#include +#include + +#include +#include +#include +#include + +#include "testutil.h" + +#ifndef OPENSSL_NO_RSA +# include + +#define NUM_EXTRA_PRIMES 5 + +static int key4096p7(RSA *key) +{ + /* C90 requires string should <= 509 bytes */ + static unsigned char n1[] = + "\x00\xeb\xa2\x2b\x74\x76\x32\x33\xbf\xb9\x9a\xe4\xb0\x84\xac" + "\x9a\x20\x1b\xe6\x1a\x22\x3f\xcd\x13\xe1\x42\xee\xd8\x1a\x6e" + "\xe3\xd5\x91\x1e\xee\x32\x5c\x78\x76\x8b\x5d\x82\x6f\xd0\xaf" + "\xa3\x56\xd6\x15\x5f\x64\xb3\x5a\xcf\xc8\x7d\xa3\xb1\x3d\x10" + "\xbf\x47\x00\xa9\xc9\x96\x9d\xfd\x7c\x82\x4f\xb5\x70\x39\xd4" + "\xd9\x0f\xd7\xd9\x86\xd4\xd4\x35\x06\x35\x07\xa3\x1b\x8c\xf4" + "\x35\xb8\xb2\xd4\xa3\xbe\x6c\x64\x7d\x74\x17\x88\x36\x07\x32" + "\x6f\x84\x48\xd4\xb8\x4a\x12\xba\xe8\x40\x5b\xc6\xa5\xa4\x11" + "\x0d\x8a\xa6\x60\x3d\x98\x8b\xf8\x11\x8f\x43\xab\x2f\x95\x0f" + "\x3b\x20\x3f\x48\x88\xaa\x3d\x20\xa6\xaf\x6a\xdf\xc0\x95\x38" + "\xff\x47\x7c\x8a\x8b\xec\x76\x45\x43\xd0\x06\x7c\x71\x76\x5f" + "\x0d\x11\x58\x0a\xa9\x0e\x7e\x07\xe9\x89\xc1\x9e\x56\x6d\x08" + "\xe4\xe3\x16\xb4\xa0\x03\x7a\x49\x96\xa8\x88\xcf\x89\xe3\xdb" + "\x47\x0c\xd2\x1b\x6f\x67\x4d\xc8\xee\x53\xe9\x0b\x3d\xe5\x11" + "\x9d\x85\x75\xfe\x26\x4a\x99\x58\x79\x28\x91\x03\x8b\xe4\xbf" + "\x49\xd3\xfa\x8e\x25\xe3\xb1\xb2\xc2\x33\xd9\x8b\xe0\x9d\x1b" + "\xa4\xa0\xcf\x05\x5f\xb9\x19\x65\x74\x24\xae\x2e\x33\xc8\xd9"; + + static unsigned char n2[] = + "\x55\xae\xcb\x37\xa1\x3b\x95\xf7\x5f\xff\x1f\x06\x4a\xab\x85" + "\x94\x37\x15\x6f\xf2\xc8\x9b\x73\xb9\x1d\x8e\x30\x63\x5a\xa1" + "\x84\x31\xa8\xbe\x7e\x4f\xeb\xa0\xe6\x73\xc7\xbe\xd4\x5e\xe7" + "\x5e\xae\x5d\xfd\xf7\xf5\xa4\xb6\xb8\x3c\x15\xac\x1b\xcd\x3a" + "\xb6\xbd\xa9\x11\xd0\x44\xa5\x08\x7e\x60\x1d\x1d\x4d\xa6\xd7" + "\x06\xe5\x4f\x37\x0d\x5c\xbd\xad\x8d\x40\x18\xbd\xc7\x58\x20" + "\xed\xa8\x4d\xd8\x29\xdc\x42\x4f\x50\xa6\x03\xf0\xa5\xa2\x18" + "\x2b\xdd\x1c\x0e\x89\x3f\xbc\x5d\x35\xac\xa8\x55\x6d\x17\x28" + "\xae\xee\x78\xeb\x6d\x7a\x21\xd6\x6c\xdd\x21\x1d\xcc\xe5\xb0" + "\xf2\xef\x7f\x1d\x8a\xb7\x95\xaf\x40\xb5\x5c\x8b\x0d\x59\x45" + "\x21\x86\x34\x6d\x13\xd7\x14\xa5\x0e\xca\x88\x32\x57\xfe\x2d" + "\xd1\xcb\xad\x14\xbe\x30\xb1\x69\x9b\x72\x82\xad\x47\xb5\x45" + "\xc8\x65\x83\xce\x07\x21\x15\x6b\x65\x9d\xf3\x4d\x92\x19\xbe" + "\x67\x73\xd0\x60\x9f\xc7\xef\xee\xfa\xb0\xd3\xa4\x95\x81\xb0" + "\xbd\x4b\xd5\xf8\xbd\xbd\x9f\x41\x41\xc0\xfd\xe9\x17\xe3\x16" + "\xd3\xdc\xc8\xe2\xa5\xca\xff\xea\x91\xf4\x33\xc0\xfb\xdc\x02" + "\x62\x0a\x4e\x26\x92\xb5\x13\xec\x43\xd2\x25\x19\xe2\x6d\xef" + "\xea\x38\x75"; + + static unsigned char e[] = "\x01\x00\x01"; + + static unsigned char d1[] = + "\x60\x43\x92\x69\x33\xd8\x72\x97\xc3\x25\xea\x83\xca\xd0\x10" + "\xef\x49\x36\x8a\x3a\xaf\xc2\x02\x7b\x26\xb3\x19\x0a\x43\x7f" + "\x44\xc2\xd2\xd6\x11\x31\x01\xed\xbc\x25\xe9\xa1\xf0\xa9\xb0" + "\x9b\x4b\x3e\xd4\x07\xf9\xd6\x01\xc9\x30\xba\xed\x2f\xbb\x65" + "\xc9\x86\x15\xd7\x4b\x77\x24\x15\xf7\xce\xc4\x9b\x21\x62\x4d" + "\xde\x77\xf0\x1e\x62\x49\x54\xda\xda\xcd\xdd\x0f\x53\xe2\xd2" + "\x39\x4f\x60\x8e\xec\xe3\x49\x1b\xe7\x9a\x3e\x17\x8e\x5a\x77" + "\x4a\x15\xf6\x57\xc5\xfe\x2b\xa5\x94\x04\x94\x9c\xe7\xa8\xcc" + "\x07\x4b\xd8\xb8\x55\xaa\xdf\x33\xca\x2c\x8c\xee\x61\x1a\x89" + "\x0d\x3b\xcd\x16\x28\xb5\x50\x62\x2f\xb1\x9e\x61\x27\xd7\xf1" + "\xe1\x22\x58\x84\xcd\x18\xc3\xbf\xde\x52\x25\xdd\xc1\xcd\x2a" + "\x20\x78\x5e\xde\x65\x6a\x25\x12\x2d\x78\x28\xdb\x2c\x6f\x1b" + "\x65\x71\x1b\x2e\x1c\x18\x62\xf6\x71\x82\xdc\xa8\x80\x0e\xb5" + "\x8b\x09\x97\xc3\x81\xe1\x23\x2e\x40\x75\xbf\xd3\x78\xdc\xd5" + "\xc3\xe6\x75\x8b\xb0\x48\x7a\x78\x7d\xfe\xcc\x4c\xa1\x40\x11" + "\x20\xbe\x2a\xc1\xaf\x18\x53\x45\x6a\xb4\x2a\x0a\xc9\x01\x36" + "\x60\xf1\x61\x97\x73\xde\xac\x3e\x24\xff\x5b\x25\xdb\x93\x97"; + + static unsigned char d2[] = + "\x03\xf4\xef\x4a\x73\x47\xa8\x31\xd1\x63\x5b\xba\xa6\xe2\x7a" + "\xd8\xef\xea\x2f\x04\x76\x3c\x7a\x8d\x4e\xc1\x81\xc5\x39\x4f" + "\x09\xc4\xb1\xfb\x75\xd0\xae\x32\x2e\x44\xa3\xb6\xdc\x60\xc6" + "\x60\x1e\x40\x6f\x04\xc2\x7a\xd3\x0f\x8a\xa4\x23\x8f\x0e\x2e" + "\x2a\xcd\x65\x2a\x6e\x97\xa8\xe5\x01\x96\xd1\x41\x27\xa5\x16" + "\x2f\xb0\x15\x0a\x33\x06\x72\x40\xa5\xe4\x74\xbe\x4a\x87\x28" + "\x8a\x68\xea\x39\x42\x08\x47\xff\x9d\x9e\x06\x03\xfa\x4a\x6a" + "\xbb\xe5\x6f\x97\x05\x5f\xae\x47\xe6\xc4\xe0\x48\x62\x65\x9b" + "\x91\x50\xda\x84\xcf\xa3\xb2\x9d\x51\x84\x02\x4b\xe6\x12\xa2" + "\x87\x6e\x1f\x43\x2f\x90\x36\xb1\x15\xc6\xf6\xe0\xde\x52\x39" + "\x8e\x22\x39\x8c\x4f\x1c\x08\xac\x55\x5c\xa9\x69\x4e\x77\x8d" + "\x74\x6e\x0b\x06\xda\x61\xcd\xe2\xc8\xc6\x02\x54\x70\x05\xc1" + "\x50\x6d\x5e\x3e\x66\x7d\x41\x3c\x57\x68\x8a\x16\xb9\xd8\x29" + "\xfb\xeb\x05\x57\x87\xdc\x88\xc6\x91\x67\x3c\xcc\x19\x28\xa1" + "\x23\x54\xc3\x88\xc4\x28\x63\xca\xf7\xb2\xea\x34\xa1\x9e\xc1" + "\xca\x9b\x96\xe7\x4d\x82\x22\xf9\xcb\xc3\x2a\x3f\x19\xe3\x7c" + "\xce\x8c\x66\x45\xfe\xe6\x31\x31\x66\xd4\x1a\xb5\x47\x98\xea" + "\x80\x01"; + + static unsigned char p[] = + "\x03\xf5\x90\x21\xf3\xa6\x13\xdd\x33\x2a\x4c\x1f\x53\xd6\x9e" + "\x64\x1d\xfc\xed\xfb\xa1\xe6\xd0\x80\xd1\x6a\xcd\x20\x68\xea" + "\x75\x72\x59\x24\x8b\x1b\x28\x37\xbd\x8f\xc4\xc9\xb6\xda\xef" + "\x55\xb9\x0e\x26\x93\x8a\x8a\xec\x2f\x47\xe6\x4e\xa9\x42\xfb" + "\x02\x28\x5e\x37\xb7\x5a\x61\xfa\x39\xab\x63\x61\x1b\xbb"; + + static unsigned char q[] = + "\x01\xea\x64\x6e\x7d\xaa\xd7\x6a\xfa\x0c\x52\xfa\x2b\x00\x51" + "\x7d\x4d\xc3\x9f\x1d\x21\xb2\x62\x11\xd4\x7d\x0e\xc2\xe7\xdf" + "\xd0\x04\xd6\x30\x02\x54\xb2\xa5\xb7\x85\xd5\x96\xc7\x24\x83" + "\x8e\x3d\x60\xc3\x42\xa5\xa3\x76\xdd\x6e\x60\xa0\xbf\x85\x05" + "\xb6\x52\x32\xeb\x41\x6f\x08\xc8\x56\x43\xd8\x80\x06\xf7"; + + static unsigned char dmp1[] = + "\x03\xcc\x5c\xe7\x45\x91\x49\xb3\x47\x77\xc7\xa9\xb2\x4b\xce" + "\x8e\xab\xfa\x4f\xf1\xbd\x63\xeb\x19\xfa\x4e\x64\xd6\x37\xf0" + "\xde\x95\xc2\x11\x7d\xe6\xa2\xd1\xbe\xe9\x23\x58\x85\x35\x4a" + "\xb0\xc9\xa5\x5a\xba\xe7\x09\xda\x06\x8e\x0a\xd3\xe2\x2c\x61" + "\x14\xb3\xd7\x97\xca\x2e\x4a\x9a\xbd\x22\xc0\x67\x94\x2b"; + + static unsigned char dmq1[] = + "\x01\x66\x28\x8d\xce\x38\x8d\x76\xb3\x43\x77\x03\x01\x8f\x0c" + "\xf5\x40\x6b\x84\x75\x69\x5b\xf8\x66\x5f\x54\x2b\x08\xcd\x03" + "\x58\xd1\x7f\x81\xb6\xe2\x17\x4c\x13\x3a\xab\x21\xa1\x36\x98" + "\xe2\xb5\x0f\x4b\xed\x0c\x3e\xd4\x1c\xab\x75\xe5\x51\x9b\x9c" + "\xed\x69\x21\x89\x52\xd3\xfe\x8d\x1a\xfc\x18\x4e\x81\x47"; + + static unsigned char iqmp[] = + "\x02\x31\xad\xe8\xa5\xa9\x5d\x52\x70\x68\xc1\x6e\x6b\x4e\xb5" + "\x0b\xc2\xd9\x89\xe5\xbc\x46\xca\xac\xac\x04\xe2\x39\x7f\xc4" + "\xa0\xe4\x9e\x8a\xb8\x1e\x67\x66\x85\xb8\x3e\x42\x7c\xc7\x2c" + "\x02\x64\x7c\xd3\x40\xda\x5d\x9f\x38\xa7\x7c\x30\xcd\x6b\x7d" + "\x4d\xd0\x77\x2d\x9b\xd1\xc3\x55\x03\x69\x3d\xda\x48\xe2"; + + static char *primes[] = { + "\x01\xb2\xe2\xf7\x3b\x29\xdc\x90\xf9\xc4\x5a\x75\x09\x00\xbe" + "\xec\xa6\x97\xbc\x47\x89\x24\x71\x48\xa7\xc9\xc8\xed\x9c\x88" + "\xb9\x9f\xcd\x79\xc9\x2d\xb1\x78\xf7\x54\x2c\x28\x01\x37\x01" + "\xa0\xff\xf2\x69\x52\x93\xf0\x16\x08\xaa\x2f\xff\x35\x14\x2d" + "\x65\x8d\x21\x05\x30\x84\x9b\xcb\x58\x42\xc6\x9b\xa7\xb5", + + "\x01\xb7\x66\xfe\xb5\x94\xf8\x46\xcb\x06\x2a\x7a\xd4\x35\xe4" + "\x68\x6d\xcf\x58\x0b\xb3\x12\xe6\x7b\x66\xee\x36\xf5\x1f\x79" + "\x8f\x82\x1e\xd9\x97\x33\x45\x37\xa3\x84\x54\xab\x4b\x12\x96" + "\x76\x9f\xf9\x98\x02\xf1\x5e\xcb\x97\xe8\x13\xde\x91\x0b\xd5" + "\xec\x7f\x2b\x27\x55\xc1\x69\x58\xad\x8b\xaa\xce\x68\xc5", + + "\x01\xbe\xdf\xa5\x33\xfb\xa1\xfa\xf6\xd2\x43\xcd\x76\x3e\x23" + "\xa2\xf7\x29\xeb\x65\xe5\xae\xe8\xfc\xfd\xca\x55\x16\x01\x57" + "\xcd\xca\x9e\x83\xf9\x61\x6a\x17\xac\x61\xec\x04\x32\x9f\x69" + "\xb8\x6d\x66\x33\x9b\xef\xf4\x91\xf1\x99\x02\xc2\xea\x58\x6e" + "\xad\x3d\x0e\xa9\x87\x17\x7c\x9b\x72\xcc\xab\x1c\x93\x2b", + + "\x03\x2f\x4a\x9c\x49\x66\x9d\xbc\xae\xec\x54\x7d\xe6\x07\x52" + "\xc2\x9a\x09\xf5\xa7\x56\xa6\x68\x45\x38\x75\x7d\xb0\x0e\xee" + "\xf3\x23\xec\x74\x1e\x3b\xc0\x58\x1d\x43\xd9\x35\x15\x7e\x2f" + "\x28\xff\x08\x7a\x79\x44\xfc\x24\x06\xc5\x3f\xaa\xe0\xfa\xb2" + "\x1f\xd9\x4e\xd8\xc8\xda\xed\x1f\xaa\x77\x64\xae\xb3\xe3", + + "\x01\xea\xaa\x9d\x90\x67\x3b\x2f\x9a\xe3\x7b\x56\x5c\x35\x9f" + "\x65\x0b\x0c\x3b\xa6\x60\x5f\x98\x36\x2c\xb6\xaa\xdb\xb2\x86" + "\x8b\x20\xba\xa4\x85\x7b\xa8\x80\x41\xee\x22\x1c\x7a\x92\xf5" + "\x39\x4e\x4a\x0b\x29\x0b\xe7\xdd\x3c\xb6\x51\xec\xc3\x26\xbc" + "\x33\x11\xbc\x29\x7a\x10\x68\x32\x55\xb4\x15\xd9\x8e\xc1" + }; + + static int primes_len[] = { 74, 74, 74, 74, 74 }; + + static char *exponents[] = { + "\x01\xa4\x49\xb7\x57\xc5\x50\x36\x08\x3c\xdc\x93\x29\x1d\x40" + "\x67\x63\x65\x57\x7f\xe7\x29\x82\x16\x0e\x9a\x74\x06\x37\x76" + "\xe7\xb6\x6a\x15\x5d\xf9\x3c\x00\x45\x3f\x62\xe1\x52\xb3\x3f" + "\x6e\xc2\x8d\x1b\x7e\xc4\x1c\x8e\x9e\xd7\x23\x45\xc8\x9d\x74" + "\x76\x25\x5b\x99\x31\x57\xa7\x5d\x71\x32\x2f\xd1\x74\xd5", + + "\x01\x3a\xa4\x6d\x05\xf7\xeb\xa5\x3d\xe2\x67\x6e\xd7\x20\xd4" + "\x33\x17\x56\xdf\x34\x59\x81\xd2\x3b\x51\x64\x89\x44\x13\xca" + "\xc7\x41\xa4\xf7\xa8\xf6\xd4\xbc\xd7\xc1\x7d\xa3\xbf\x39\x4b" + "\x37\x1c\xac\xec\xf6\x46\x82\xdc\x05\x25\xf1\x7c\x71\x9e\xe9" + "\x0b\xd5\xb0\x40\x15\x7f\x4f\x01\x6a\x1c\x56\x2e\x42\x05", + + "\x00\x9b\xd7\x14\x9e\xcf\x47\x4a\xe5\x1e\xa8\xc4\x93\x52\xd2" + "\x4c\xb7\xd3\x67\xa3\x4e\x79\x34\x09\x5e\x5c\x5c\x55\xe3\x3c" + "\x02\xa9\x81\xa4\x56\xa8\xb1\x3d\xf6\x40\xe3\xf5\x06\xce\x6f" + "\x29\x01\x05\xde\x43\xa8\x67\xeb\x29\x8d\x09\xd8\x7d\xaf\x3f" + "\x51\xac\xf4\x5b\x0c\xa0\x95\x35\x04\xd0\xf9\x6f\x6a\xa7", + + "\x02\xfd\x38\x42\x48\x82\x90\x3a\xb0\xd4\x10\xd9\xba\x35\xd5" + "\x6f\xe1\xb4\xc7\x65\x30\xe7\x2f\xa7\x08\xbe\xfe\x21\x69\x62" + "\xcd\xc3\x42\x04\x1a\xfc\x6a\x24\x4a\x13\x8c\xa3\x4e\x71\x09" + "\x42\xa9\x5d\x03\xd7\x1e\xf0\xa9\xbf\xd1\x13\x59\x07\xa1\x45" + "\xde\xae\xd0\x5a\x98\xeb\x22\xf5\x3d\xc2\xa2\x35\x77\x91", + + "\x13\x1d\x2c\x60\x28\xb5\x54\x88\x6b\x1e\x2d\xe2\x0f\xb0\xb2" + "\xe5\xf8\x47\x06\x97\x30\x82\x24\x72\x1f\x77\x8e\x71\x68\xee" + "\x58\x8b\x0c\xc7\xaa\x66\x89\x00\x88\x7f\x49\xae\xb8\xb4\xd6" + "\xd3\xa6\xec\xc2\x5f\x95\x5b\xb7\xf6\xbe\x40\x43\xe5\xe9\x64" + "\xef\xe6\xed\x92\xb4\xba\xea\x63\x0e\x4d\xdf\x98\xc1" + }; + + static int exps_len[] = { 74, 74, 74, 74, 73 }; + + static char *coefficients[] = { + "\x18\x19\x50\xc2\x69\x6a\x63\x66\x40\x6a\x43\xa6\x7d\x0d\x12" + "\x0f\x04\x3a\xe7\xb2\x1c\xe3\xfc\x6f\xa7\x8b\x5e\x99\xe3\x43" + "\x97\x68\x10\xee\x68\x73\x01\xc6\xaf\x5e\x26\xaf\xcc\x1f\x39" + "\x9c\x8d\xa9\x06\x80\x21\x7a\xaa\x29\x8a\x4b\x71\x03\xb0\x9a" + "\x2f\xd6\x6b\xb0\x0b\x93\xc9\x4d\x0b\x9d\x3f\xe6\x21", + + "\x00\xa4\x80\x6e\xef\x34\xba\x3f\xe7\x96\xec\x25\x16\x25\xe9" + "\x77\x5f\x61\xb1\x48\xdb\x03\xfa\x80\xf3\xbd\x20\xd1\x60\x9a" + "\x10\x9d\xf0\x1b\xff\xb8\x50\x14\x54\x75\x53\x2b\x89\x9f\x39" + "\x96\x63\x05\x89\xfb\xfb\x7f\x59\x93\xdc\x61\xe2\x8c\xfc\x5a" + "\x6f\x2c\x6a\xcf\xd4\xac\xa5\x81\xf2\xdd\x68\x75\xd4\x48", + + "\x00\xf6\xec\xd6\x98\x10\x42\x38\x94\x30\x2c\xd4\xe7\xb1\x5f" + "\xa2\xfd\xc9\xc4\x92\x78\xf6\x31\x34\xb7\x26\xa1\x7f\x0b\xa3" + "\xc3\xf6\x4f\xd0\x05\x4e\x98\x1b\xa5\x98\xde\x26\xb8\xc2\x14" + "\x12\xa4\xae\x2f\xd8\x48\x39\x1b\x33\x1d\x0f\x72\xaf\xd3\x8d" + "\xd8\xb0\x9f\x52\x42\x5d\xae\xf6\x3c\xe1\xd2\x09\xd8\x53", + + "\x00\xb3\xce\x4b\x87\x41\x21\x34\x7b\xe3\x64\x74\xef\x9f\x71" + "\xcc\x01\x19\x50\x69\xbb\x5f\x69\xc8\xbc\x62\x8b\x4d\xa9\x73" + "\x23\x7f\xc6\xce\xfa\xe7\x96\xa7\x22\x44\x33\x32\x47\x60\x23" + "\xb4\xd2\x5e\xa4\xa1\xbd\x31\x1f\x04\x1a\xdf\xdb\x05\xe9\x4c" + "\x44\xfb\x9b\x73\xfe\x25\x3d\x7a\x61\xc2\x22\x9a\xd6\x18", + + "\x01\x8d\x43\x63\x89\x6d\x97\xf3\x4a\x3e\x10\xa0\x94\x46\x1a" + "\x1c\x34\x22\xb3\xe3\x21\xff\xad\xf2\x1b\x56\x74\x32\xdc\xd2" + "\x0e\xd7\x3a\x9c\xe9\x87\xcc\xf1\x9c\x56\xfe\xff\x2f\x3d\xec" + "\x70\xba\xfb\x5d\x37\xa8\x57\xd1\xc4\xa9\x1b\xc9\xdc\x76\x68" + "\xca\x7d\x39\x59\x97\x2d\x07\x03\x52\xf6\x8d\xb6\x0e\x24" + }; + + static int coeffs_len[] = { 73, 74, 74, 74, 74 }; + + BIGNUM **pris = NULL, **exps = NULL, **coeffs = NULL; + int i, rv = 512; + unsigned char *n, *d; + size_t len_n, len_d; + + len_n = sizeof(n1) + sizeof(n2) - 2; + n = OPENSSL_zalloc(len_n); + if (n == NULL) + return 0; + + memcpy(n, n1, sizeof(n1) - 1); + memcpy(n + sizeof(n1) - 1, n2, sizeof(n2) - 1); + + len_d = sizeof(d1) + sizeof(d2) - 2; + d = OPENSSL_zalloc(len_d); + if (d == NULL) + goto err; + + memcpy(d, d1, sizeof(d1) - 1); + memcpy(d + sizeof(d1) - 1, d2, sizeof(d2) - 1); + + if (!TEST_int_eq(RSA_set0_key(key, + BN_bin2bn(n, len_n, NULL), + BN_bin2bn(e, sizeof(e) - 1, NULL), + BN_bin2bn(d, len_d, NULL)), 1)) + goto err; + + if (!TEST_int_eq(RSA_set0_factors(key, + BN_bin2bn(p, sizeof(p) - 1, NULL), + BN_bin2bn(q, sizeof(q) - 1, NULL)), 1)) + goto err; + + if (!TEST_int_eq(RSA_set0_crt_params(key, + BN_bin2bn(dmp1, sizeof(dmp1) - 1, NULL), + BN_bin2bn(dmq1, sizeof(dmq1) - 1, NULL), + BN_bin2bn(iqmp, sizeof(iqmp) - 1, + NULL)), 1)) + return 0; + + pris = OPENSSL_zalloc(sizeof(BIGNUM *) * NUM_EXTRA_PRIMES); + exps = OPENSSL_zalloc(sizeof(BIGNUM *) * NUM_EXTRA_PRIMES); + coeffs = OPENSSL_zalloc(sizeof(BIGNUM *) * NUM_EXTRA_PRIMES); + if (!TEST_ptr(pris) || !TEST_ptr(exps) || !TEST_ptr(coeffs)) + goto err; + + for (i = 0; i < NUM_EXTRA_PRIMES; i++) { + pris[i] = BN_bin2bn((unsigned char *)primes[i], primes_len[i], NULL); + exps[i] = BN_bin2bn((unsigned char *)exponents[i], exps_len[i], NULL); + coeffs[i] = BN_bin2bn((unsigned char *)coefficients[i], + coeffs_len[i], NULL); + if (!TEST_ptr(pris[i]) || !TEST_ptr(exps[i]) || !TEST_ptr(coeffs[i])) + goto err; + } + + if (!TEST_true(RSA_set0_multi_prime_params(key, pris, exps, + coeffs, NUM_EXTRA_PRIMES))) + goto err; + + ret: + OPENSSL_free(pris); + OPENSSL_free(exps); + OPENSSL_free(coeffs); + OPENSSL_free(n); + OPENSSL_free(d); + return rv; + err: + for (i = 0; i < 5; i++) { + if (pris != NULL) + BN_free(pris[i]); + if (exps != NULL) + BN_free(exps[i]); + if (coeffs != NULL) + BN_free(coeffs[i]); + } + rv = 0; + goto ret; +} + +static int test_rsa_mp(void) +{ + int ret = 0; + RSA *key; + unsigned char ptext[512]; + unsigned char ctext[512]; + static unsigned char ptext_ex[] = "\x54\x85\x9b\x34\x2c\x49\xea\x2a"; + int plen; + int clen = 0; + int num; + + plen = sizeof(ptext_ex) - 1; + key = RSA_new(); + if (!TEST_ptr(key)) + goto err; + clen = key4096p7(key); + if (!TEST_int_eq(clen, 512)) + goto err; + + if (!TEST_true(RSA_check_key_ex(key, NULL))) + goto err; + + num = RSA_public_encrypt(plen, ptext_ex, ctext, key, + RSA_PKCS1_PADDING); + if (!TEST_int_eq(num, clen)) + goto err; + + num = RSA_private_decrypt(num, ctext, ptext, key, RSA_PKCS1_PADDING); + if (!TEST_mem_eq(ptext, num, ptext_ex, plen)) + goto err; + + ret = 1; +err: + RSA_free(key); + return ret; +} +#endif + +int setup_tests(void) +{ +#ifndef OPENSSL_NO_RSA + ADD_TEST(test_rsa_mp); +#endif + return 1; +} diff --git a/util/libcrypto.num b/util/libcrypto.num index 8d9db312a6..10ffa2c3d5 100644 --- a/util/libcrypto.num +++ b/util/libcrypto.num @@ -4438,3 +4438,11 @@ EVP_PKEY_asn1_set_param_check 4382 1_1_1 EXIST::FUNCTION: DH_check_ex 4383 1_1_1 EXIST::FUNCTION:DH DH_check_pub_key_ex 4384 1_1_1 EXIST::FUNCTION:DH DH_check_params_ex 4385 1_1_1 EXIST::FUNCTION:DH +RSA_generate_multi_prime_key 4386 1_1_1 EXIST::FUNCTION:RSA +RSA_get_multi_prime_extra_count 4387 1_1_1 EXIST::FUNCTION:RSA +RSA_get0_multi_prime_factors 4388 1_1_1 EXIST::FUNCTION:RSA +RSA_get0_multi_prime_crt_params 4389 1_1_1 EXIST::FUNCTION:RSA +RSA_set0_multi_prime_params 4390 1_1_1 EXIST::FUNCTION:RSA +RSA_get_version 4391 1_1_1 EXIST::FUNCTION:RSA +RSA_meth_get_multi_prime_keygen 4392 1_1_1 EXIST::FUNCTION:RSA +RSA_meth_set_multi_prime_keygen 4393 1_1_1 EXIST::FUNCTION:RSA