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)

6 files changed, 138 insertions, 26 deletions

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<rsa_keygen_primes:numprimes>
+
+The number of primes in the generated key. If not specified 2 is used.
+
+=item B<rsa_keygen_pubexp:value>
+
+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<RSA-PSS> key has no parameter restrictions.
+
+=over 4
+
+=item B<rsa_keygen_bits:numbits>, B<rsa_keygen_pubexp:value>
+
+These options have the same meaning as the B<RSA> algorithm.
+
+=item B<rsa_pss_keygen_md:digest>
+
 =item B<rsa_keygen_pubexp:value>
 
 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<openssl> B<genrsa>
 [B<-rand file...>]
 [B<-writerand file>]
 [B<-engine id>]
+[B<-primes num>]
 [B<numbits>]
 
 =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<num>
+parameter must be a positive integer that is greater than 1 and less than 16.
+If B<num> is greater than 2, then the generated key is called a 'multi-prime'
+RSA key, which is defined in RFC 8017.
+
 =item B<numbits>
 
 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<openssl speed>
 [B<-decrypt>]
 [B<-rand file...>]
 [B<-writerand file>]
+[B<-primes num>]
 [B<algorithm...>]
 
 =head1 DESCRIPTION
@@ -65,6 +66,11 @@ all others.
 Writes random data to the specified I<file> upon exit.
 This can be used with a subsequent B<-rand> flag.
 
+=item B<-primes num>
+
+Generate a B<num>-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<speed> 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 <openssl/rsa.h>
 
  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<RSA>
-structure provided in B<rsa>. The pseudo-random number generator must
+RSA_generate_key_ex() generates a 2-prime RSA key pair and stores it in the
+B<RSA> structure provided in B<rsa>. The pseudo-random number generator must
 be seeded prior to calling RSA_generate_key_ex().
 
-The modulus size will be of length B<bits>, and the public exponent will be
-B<e>. Key sizes with B<num> E<lt> 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<RSA> structure provided in B<rsa>. The number of primes is given by
+the B<primes> 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<bits>, the number of primes to form the
+modulus will be B<primes>, and the public exponent will be B<e>. Key sizes
+with B<num> E<lt> 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<cb> is not B<NULL>, it
@@ -55,10 +63,12 @@ it is called as B<BN_GENCB_call(cb, 3, 0)>.
 
 =back
 
-The process is then repeated for prime q with B<BN_GENCB_call(cb, 3, 1)>.
+The process is then repeated for prime q and other primes (if any)
+with B<BN_GENCB_call(cb, 3, i)> where B<i> 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<ERR_get_error(3)>.
 
@@ -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<p> and B<q> are
 the first and second factor of B<n> and B<dmp1>, B<dmq1> and B<iqmp>
 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<r>, B<d>
+and B<t>. B<r> is the additional prime besides B<p> and B<q>. B<d> and
+B<t> are the exponent and coefficient for CRT calculations.
+
 The B<n>, B<e> and B<d> 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<dmq1> and B<iqmp> 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<BIGNUM *>. 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<flags> 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<r>.
+
 =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<r> 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<RSA_ASN1_VERSION_MULTI> for multi-prime RSA and
+B<RSA_ASN1_VERSION_DEFAULT> 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<RSA_new(3)>, L<RSA_size(3)>
 
 =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<RSA_METHOD> 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<RSA_new(3)>, L<RSA_generate_key(3)>, L<RSA_sign(3)>,
-L<RSA_set_method(3)>, L<RSA_size(3)>, L<RSA_get0_key(3)>
+L<RSA_new(3)>, L<RSA_generate_key_ex(3)>, L<RSA_sign(3)>,
+L<RSA_set_method(3)>, L<RSA_size(3)>, L<RSA_get0_key(3)>,
+L<RSA_generate_multi_prime_key(3)>
 
 =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