commit 839b881c612c698d7331191beac7d565649f5351
author Adam Langley <alangley@gmail.com> Tue May 26 11:36:46 2015 -0700
committer Adam Langley <agl@google.com> Fri Jun 05 18:39:44 2015 +0000
tree 0ab948fffb1c878944ef828f0cb567691b7ccebd
parent af0e32cb84f0c9cc65b9233a3414d2562642b342

Multi-prime RSA support.

RSA with more than two primes is specified in
https://tools.ietf.org/html/rfc3447, although the idea goes back far
earier than that.

This change ports some of the changes in
http://rt.openssl.org/Ticket/Display.html?id=3477&user=guest&pass=guest
to BoringSSL—specifically those bits that are under an OpenSSL license.

Change-Id: I51e8e345e2148702b8ce12e00518f6ef4683d3e1
Reviewed-on: https://boringssl-review.googlesource.com/4870
Reviewed-by: Adam Langley <agl@google.com>

crypto/rsa/rsa.c

diff --git a/crypto/rsa/rsa.c b/crypto/rsa/rsa.c
index 17059b0..51cc790 100644
--- a/crypto/rsa/rsa.c
+++ b/crypto/rsa/rsa.c
@@ -114,6 +114,18 @@
   return rsa;
 }
 
+void RSA_additional_prime_free(RSA_additional_prime *ap) {
+  if (ap == NULL) {
+    return;
+  }
+
+  BN_clear_free(ap->prime);
+  BN_clear_free(ap->exp);
+  BN_clear_free(ap->coeff);
+  BN_clear_free(ap->r);
+  OPENSSL_free(ap);
+}
+
 void RSA_free(RSA *rsa) {
   unsigned u;
 
@@ -145,6 +157,10 @@
   }
   OPENSSL_free(rsa->blindings);
   OPENSSL_free(rsa->blindings_inuse);
+  if (rsa->additional_primes != NULL) {
+    sk_RSA_additional_prime_pop_free(rsa->additional_primes,
+                                     RSA_additional_prime_free);
+  }
   CRYPTO_MUTEX_cleanup(&rsa->lock);
   OPENSSL_free(rsa);
 }
@@ -162,6 +178,16 @@
   return RSA_default_method.keygen(rsa, bits, e_value, cb);
 }
 
+int RSA_generate_multi_prime_key(RSA *rsa, int bits, int num_primes,
+                                 BIGNUM *e_value, BN_GENCB *cb) {
+  if (rsa->meth->multi_prime_keygen) {
+    return rsa->meth->multi_prime_keygen(rsa, bits, num_primes, e_value, cb);
+  }
+
+  return RSA_default_method.multi_prime_keygen(rsa, bits, num_primes, e_value,
+                                               cb);
+}
+
 int RSA_encrypt(RSA *rsa, size_t *out_len, uint8_t *out, size_t max_out,
                 const uint8_t *in, size_t in_len, int padding) {
   if (rsa->meth->encrypt) {
@@ -540,15 +566,37 @@
   BN_init(&dmq1);
   BN_init(&iqmp);
 
-  if (/* n = pq */
-      !BN_mul(&n, key->p, key->q, ctx) ||
-      /* lcm = lcm(p-1, q-1) */
+  if (!BN_mul(&n, key->p, key->q, ctx) ||
+      /* lcm = lcm(prime-1, for all primes) */
       !BN_sub(&pm1, key->p, BN_value_one()) ||
       !BN_sub(&qm1, key->q, BN_value_one()) ||
       !BN_mul(&lcm, &pm1, &qm1, ctx) ||
+      !BN_gcd(&gcd, &pm1, &qm1, ctx)) {
+    OPENSSL_PUT_ERROR(RSA, RSA_check_key, ERR_LIB_BN);
+    goto out;
+  }
+
+  size_t num_additional_primes = 0;
+  if (key->additional_primes != NULL) {
+    num_additional_primes = sk_RSA_additional_prime_num(key->additional_primes);
+  }
+
+  size_t i;
+  for (i = 0; i < num_additional_primes; i++) {
+    const RSA_additional_prime *ap =
+        sk_RSA_additional_prime_value(key->additional_primes, i);
+    if (!BN_mul(&n, &n, ap->prime, ctx) ||
+        !BN_sub(&pm1, ap->prime, BN_value_one()) ||
+        !BN_mul(&lcm, &lcm, &pm1, ctx) ||
+        !BN_gcd(&gcd, &gcd, &pm1, ctx)) {
+      OPENSSL_PUT_ERROR(RSA, RSA_check_key, ERR_LIB_BN);
+      goto out;
+    }
+  }
+
+  if (!BN_div(&lcm, NULL, &lcm, &gcd, ctx) ||
       !BN_gcd(&gcd, &pm1, &qm1, ctx) ||
-      !BN_div(&lcm, NULL, &lcm, &gcd, ctx) ||
-      /* de = d*e mod lcm(p-1, q-1) */
+      /* de = d*e mod lcm(prime-1, for all primes). */
       !BN_mod_mul(&de, key->d, key->e, &lcm, ctx)) {
     OPENSSL_PUT_ERROR(RSA, RSA_check_key, ERR_LIB_BN);
     goto out;
@@ -571,7 +619,7 @@
     goto out;
   }
 
-  if (has_crt_values) {
+  if (has_crt_values && num_additional_primes == 0) {
     if (/* dmp1 = d mod (p-1) */
         !BN_mod(&dmp1, key->d, &pm1, ctx) ||
         /* dmq1 = d mod (q-1) */
@@ -623,6 +671,12 @@
     return 0;
   }
 
+  if (rsa->additional_primes != NULL) {
+    OPENSSL_PUT_ERROR(RSA, RSA_recover_crt_params,
+                      RSA_R_CANNOT_RECOVER_MULTI_PRIME_KEY);
+    return 0;
+  }
+
   /* This uses the algorithm from section 9B of the RSA paper:
    * http://people.csail.mit.edu/rivest/Rsapaper.pdf */