am b8494591: Revert "Revert "external/boringssl: sync with upstream.""

* commit 'b8494591d1b1a143f3b192d845c238bbf3bc629d':
  Revert "Revert "external/boringssl: sync with upstream.""

1 files changed, 255 insertions, 56 deletions

diff --git a/src/crypto/rsa/rsa_impl.c b/src/crypto/rsa/rsa_impl.c
index e14f0f5..eb4a36f 100644
--- a/src/crypto/rsa/rsa_impl.c
+++ b/src/crypto/rsa/rsa_impl.c
@@ -78,6 +78,15 @@ static int finish(RSA *rsa) {
   BN_MONT_CTX_free(rsa->_method_mod_p);
   BN_MONT_CTX_free(rsa->_method_mod_q);
 
+  if (rsa->additional_primes != NULL) {
+    size_t i;
+    for (i = 0; i < sk_RSA_additional_prime_num(rsa->additional_primes); i++) {
+      RSA_additional_prime *ap =
+          sk_RSA_additional_prime_value(rsa->additional_primes, i);
+      BN_MONT_CTX_free(ap->method_mod);
+    }
+  }
+
   return 1;
 }
 
@@ -94,24 +103,24 @@ static int encrypt(RSA *rsa, size_t *out_len, uint8_t *out, size_t max_out,
   int i, ret = 0;
 
   if (rsa_size > OPENSSL_RSA_MAX_MODULUS_BITS) {
-    OPENSSL_PUT_ERROR(RSA, encrypt, RSA_R_MODULUS_TOO_LARGE);
+    OPENSSL_PUT_ERROR(RSA, RSA_R_MODULUS_TOO_LARGE);
     return 0;
   }
 
   if (max_out < rsa_size) {
-    OPENSSL_PUT_ERROR(RSA, encrypt, RSA_R_OUTPUT_BUFFER_TOO_SMALL);
+    OPENSSL_PUT_ERROR(RSA, RSA_R_OUTPUT_BUFFER_TOO_SMALL);
     return 0;
   }
 
   if (BN_ucmp(rsa->n, rsa->e) <= 0) {
-    OPENSSL_PUT_ERROR(RSA, encrypt, RSA_R_BAD_E_VALUE);
+    OPENSSL_PUT_ERROR(RSA, RSA_R_BAD_E_VALUE);
     return 0;
   }
 
   /* for large moduli, enforce exponent limit */
   if (BN_num_bits(rsa->n) > OPENSSL_RSA_SMALL_MODULUS_BITS &&
       BN_num_bits(rsa->e) > OPENSSL_RSA_MAX_PUBEXP_BITS) {
-    OPENSSL_PUT_ERROR(RSA, encrypt, RSA_R_BAD_E_VALUE);
+    OPENSSL_PUT_ERROR(RSA, RSA_R_BAD_E_VALUE);
     return 0;
   }
 
@@ -125,7 +134,7 @@ static int encrypt(RSA *rsa, size_t *out_len, uint8_t *out, size_t max_out,
   result = BN_CTX_get(ctx);
   buf = OPENSSL_malloc(rsa_size);
   if (!f || !result || !buf) {
-    OPENSSL_PUT_ERROR(RSA, encrypt, ERR_R_MALLOC_FAILURE);
+    OPENSSL_PUT_ERROR(RSA, ERR_R_MALLOC_FAILURE);
     goto err;
   }
 
@@ -142,7 +151,7 @@ static int encrypt(RSA *rsa, size_t *out_len, uint8_t *out, size_t max_out,
       i = RSA_padding_add_none(buf, rsa_size, in, in_len);
       break;
     default:
-      OPENSSL_PUT_ERROR(RSA, encrypt, RSA_R_UNKNOWN_PADDING_TYPE);
+      OPENSSL_PUT_ERROR(RSA, RSA_R_UNKNOWN_PADDING_TYPE);
       goto err;
   }
 
@@ -156,7 +165,7 @@ static int encrypt(RSA *rsa, size_t *out_len, uint8_t *out, size_t max_out,
 
   if (BN_ucmp(f, rsa->n) >= 0) {
     /* usually the padding functions would catch this */
-    OPENSSL_PUT_ERROR(RSA, encrypt, RSA_R_DATA_TOO_LARGE_FOR_MODULUS);
+    OPENSSL_PUT_ERROR(RSA, RSA_R_DATA_TOO_LARGE_FOR_MODULUS);
     goto err;
   }
 
@@ -175,7 +184,7 @@ static int encrypt(RSA *rsa, size_t *out_len, uint8_t *out, size_t max_out,
   /* put in leading 0 bytes if the number is less than the length of the
    * modulus */
   if (!BN_bn2bin_padded(out, rsa_size, result)) {
-    OPENSSL_PUT_ERROR(RSA, encrypt, ERR_R_INTERNAL_ERROR);
+    OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR);
     goto err;
   }
 
@@ -309,13 +318,13 @@ static int sign_raw(RSA *rsa, size_t *out_len, uint8_t *out, size_t max_out,
   int i, ret = 0;
 
   if (max_out < rsa_size) {
-    OPENSSL_PUT_ERROR(RSA, sign_raw, RSA_R_OUTPUT_BUFFER_TOO_SMALL);
+    OPENSSL_PUT_ERROR(RSA, RSA_R_OUTPUT_BUFFER_TOO_SMALL);
     return 0;
   }
 
   buf = OPENSSL_malloc(rsa_size);
   if (buf == NULL) {
-    OPENSSL_PUT_ERROR(RSA, sign_raw, ERR_R_MALLOC_FAILURE);
+    OPENSSL_PUT_ERROR(RSA, ERR_R_MALLOC_FAILURE);
     goto err;
   }
 
@@ -327,7 +336,7 @@ static int sign_raw(RSA *rsa, size_t *out_len, uint8_t *out, size_t max_out,
       i = RSA_padding_add_none(buf, rsa_size, in, in_len);
       break;
     default:
-      OPENSSL_PUT_ERROR(RSA, sign_raw, RSA_R_UNKNOWN_PADDING_TYPE);
+      OPENSSL_PUT_ERROR(RSA, RSA_R_UNKNOWN_PADDING_TYPE);
       goto err;
   }
 
@@ -359,18 +368,23 @@ static int decrypt(RSA *rsa, size_t *out_len, uint8_t *out, size_t max_out,
   int ret = 0;
 
   if (max_out < rsa_size) {
-    OPENSSL_PUT_ERROR(RSA, decrypt, RSA_R_OUTPUT_BUFFER_TOO_SMALL);
+    OPENSSL_PUT_ERROR(RSA, RSA_R_OUTPUT_BUFFER_TOO_SMALL);
     return 0;
   }
 
-  buf = OPENSSL_malloc(rsa_size);
-  if (buf == NULL) {
-    OPENSSL_PUT_ERROR(RSA, decrypt, ERR_R_MALLOC_FAILURE);
-    goto err;
+  if (padding == RSA_NO_PADDING) {
+    buf = out;
+  } else {
+    /* Allocate a temporary buffer to hold the padded plaintext. */
+    buf = OPENSSL_malloc(rsa_size);
+    if (buf == NULL) {
+      OPENSSL_PUT_ERROR(RSA, ERR_R_MALLOC_FAILURE);
+      goto err;
+    }
   }
 
   if (in_len != rsa_size) {
-    OPENSSL_PUT_ERROR(RSA, decrypt, RSA_R_DATA_LEN_NOT_EQUAL_TO_MOD_LEN);
+    OPENSSL_PUT_ERROR(RSA, RSA_R_DATA_LEN_NOT_EQUAL_TO_MOD_LEN);
     goto err;
   }
 
@@ -388,22 +402,22 @@ static int decrypt(RSA *rsa, size_t *out_len, uint8_t *out, size_t max_out,
                                             NULL, 0, NULL, NULL);
       break;
     case RSA_NO_PADDING:
-      r = RSA_padding_check_none(out, rsa_size, buf, rsa_size);
+      r = rsa_size;
       break;
     default:
-      OPENSSL_PUT_ERROR(RSA, decrypt, RSA_R_UNKNOWN_PADDING_TYPE);
+      OPENSSL_PUT_ERROR(RSA, RSA_R_UNKNOWN_PADDING_TYPE);
       goto err;
   }
 
   if (r < 0) {
-    OPENSSL_PUT_ERROR(RSA, decrypt, RSA_R_PADDING_CHECK_FAILED);
+    OPENSSL_PUT_ERROR(RSA, RSA_R_PADDING_CHECK_FAILED);
   } else {
     *out_len = r;
     ret = 1;
   }
 
 err:
-  if (buf != NULL) {
+  if (padding != RSA_NO_PADDING && buf != NULL) {
     OPENSSL_cleanse(buf, rsa_size);
     OPENSSL_free(buf);
   }
@@ -421,24 +435,24 @@ static int verify_raw(RSA *rsa, size_t *out_len, uint8_t *out, size_t max_out,
   BN_CTX *ctx = NULL;
 
   if (BN_num_bits(rsa->n) > OPENSSL_RSA_MAX_MODULUS_BITS) {
-    OPENSSL_PUT_ERROR(RSA, verify_raw, RSA_R_MODULUS_TOO_LARGE);
+    OPENSSL_PUT_ERROR(RSA, RSA_R_MODULUS_TOO_LARGE);
     return 0;
   }
 
   if (BN_ucmp(rsa->n, rsa->e) <= 0) {
-    OPENSSL_PUT_ERROR(RSA, verify_raw, RSA_R_BAD_E_VALUE);
+    OPENSSL_PUT_ERROR(RSA, RSA_R_BAD_E_VALUE);
     return 0;
   }
 
   if (max_out < rsa_size) {
-    OPENSSL_PUT_ERROR(RSA, verify_raw, RSA_R_OUTPUT_BUFFER_TOO_SMALL);
+    OPENSSL_PUT_ERROR(RSA, RSA_R_OUTPUT_BUFFER_TOO_SMALL);
     return 0;
   }
 
   /* for large moduli, enforce exponent limit */
   if (BN_num_bits(rsa->n) > OPENSSL_RSA_SMALL_MODULUS_BITS &&
       BN_num_bits(rsa->e) > OPENSSL_RSA_MAX_PUBEXP_BITS) {
-    OPENSSL_PUT_ERROR(RSA, verify_raw, RSA_R_BAD_E_VALUE);
+    OPENSSL_PUT_ERROR(RSA, RSA_R_BAD_E_VALUE);
     return 0;
   }
 
@@ -450,14 +464,23 @@ static int verify_raw(RSA *rsa, size_t *out_len, uint8_t *out, size_t max_out,
   BN_CTX_start(ctx);
   f = BN_CTX_get(ctx);
   result = BN_CTX_get(ctx);
-  buf = OPENSSL_malloc(rsa_size);
-  if (!f || !result || !buf) {
-    OPENSSL_PUT_ERROR(RSA, verify_raw, ERR_R_MALLOC_FAILURE);
+  if (padding == RSA_NO_PADDING) {
+    buf = out;
+  } else {
+    /* Allocate a temporary buffer to hold the padded plaintext. */
+    buf = OPENSSL_malloc(rsa_size);
+    if (buf == NULL) {
+      OPENSSL_PUT_ERROR(RSA, ERR_R_MALLOC_FAILURE);
+      goto err;
+    }
+  }
+  if (!f || !result) {
+    OPENSSL_PUT_ERROR(RSA, ERR_R_MALLOC_FAILURE);
     goto err;
   }
 
   if (in_len != rsa_size) {
-    OPENSSL_PUT_ERROR(RSA, verify_raw, RSA_R_DATA_LEN_NOT_EQUAL_TO_MOD_LEN);
+    OPENSSL_PUT_ERROR(RSA, RSA_R_DATA_LEN_NOT_EQUAL_TO_MOD_LEN);
     goto err;
   }
 
@@ -466,7 +489,7 @@ static int verify_raw(RSA *rsa, size_t *out_len, uint8_t *out, size_t max_out,
   }
 
   if (BN_ucmp(f, rsa->n) >= 0) {
-    OPENSSL_PUT_ERROR(RSA, verify_raw, RSA_R_DATA_TOO_LARGE_FOR_MODULUS);
+    OPENSSL_PUT_ERROR(RSA, RSA_R_DATA_TOO_LARGE_FOR_MODULUS);
     goto err;
   }
 
@@ -483,7 +506,7 @@ static int verify_raw(RSA *rsa, size_t *out_len, uint8_t *out, size_t max_out,
   }
 
   if (!BN_bn2bin_padded(buf, rsa_size, result)) {
-    OPENSSL_PUT_ERROR(RSA, verify_raw, ERR_R_INTERNAL_ERROR);
+    OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR);
     goto err;
   }
 
@@ -492,15 +515,15 @@ static int verify_raw(RSA *rsa, size_t *out_len, uint8_t *out, size_t max_out,
       r = RSA_padding_check_PKCS1_type_1(out, rsa_size, buf, rsa_size);
       break;
     case RSA_NO_PADDING:
-      r = RSA_padding_check_none(out, rsa_size, buf, rsa_size);
+      r = rsa_size;
       break;
     default:
-      OPENSSL_PUT_ERROR(RSA, verify_raw, RSA_R_UNKNOWN_PADDING_TYPE);
+      OPENSSL_PUT_ERROR(RSA, RSA_R_UNKNOWN_PADDING_TYPE);
       goto err;
   }
 
   if (r < 0) {
-    OPENSSL_PUT_ERROR(RSA, verify_raw, RSA_R_PADDING_CHECK_FAILED);
+    OPENSSL_PUT_ERROR(RSA, RSA_R_PADDING_CHECK_FAILED);
   } else {
     *out_len = r;
     ret = 1;
@@ -511,7 +534,7 @@ err:
     BN_CTX_end(ctx);
     BN_CTX_free(ctx);
   }
-  if (buf != NULL) {
+  if (padding != RSA_NO_PADDING && buf != NULL) {
     OPENSSL_cleanse(buf, rsa_size);
     OPENSSL_free(buf);
   }
@@ -535,7 +558,7 @@ static int private_transform(RSA *rsa, uint8_t *out, const uint8_t *in,
   result = BN_CTX_get(ctx);
 
   if (f == NULL || result == NULL) {
-    OPENSSL_PUT_ERROR(RSA, private_transform, ERR_R_MALLOC_FAILURE);
+    OPENSSL_PUT_ERROR(RSA, ERR_R_MALLOC_FAILURE);
     goto err;
   }
 
@@ -545,14 +568,14 @@ static int private_transform(RSA *rsa, uint8_t *out, const uint8_t *in,
 
   if (BN_ucmp(f, rsa->n) >= 0) {
     /* Usually the padding functions would catch this. */
-    OPENSSL_PUT_ERROR(RSA, private_transform, RSA_R_DATA_TOO_LARGE_FOR_MODULUS);
+    OPENSSL_PUT_ERROR(RSA, RSA_R_DATA_TOO_LARGE_FOR_MODULUS);
     goto err;
   }
 
   if (!(rsa->flags & RSA_FLAG_NO_BLINDING)) {
     blinding = rsa_blinding_get(rsa, &blinding_index, ctx);
     if (blinding == NULL) {
-      OPENSSL_PUT_ERROR(RSA, private_transform, ERR_R_INTERNAL_ERROR);
+      OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR);
       goto err;
     }
     if (!BN_BLINDING_convert_ex(f, NULL, blinding, ctx)) {
@@ -593,7 +616,7 @@ static int private_transform(RSA *rsa, uint8_t *out, const uint8_t *in,
   }
 
   if (!BN_bn2bin_padded(out, len, result)) {
-    OPENSSL_PUT_ERROR(RSA, private_transform, ERR_R_INTERNAL_ERROR);
+    OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR);
     goto err;
   }
 
@@ -616,6 +639,11 @@ static int mod_exp(BIGNUM *r0, const BIGNUM *I, RSA *rsa, BN_CTX *ctx) {
   BIGNUM local_dmp1, local_dmq1, local_c, local_r1;
   BIGNUM *dmp1, *dmq1, *c, *pr1;
   int ret = 0;
+  size_t i, num_additional_primes = 0;
+
+  if (rsa->additional_primes != NULL) {
+    num_additional_primes = sk_RSA_additional_prime_num(rsa->additional_primes);
+  }
 
   BN_CTX_start(ctx);
   r1 = BN_CTX_get(ctx);
@@ -724,6 +752,42 @@ static int mod_exp(BIGNUM *r0, const BIGNUM *I, RSA *rsa, BN_CTX *ctx) {
     goto err;
   }
 
+  for (i = 0; i < num_additional_primes; i++) {
+    /* multi-prime RSA. */
+    BIGNUM local_exp, local_prime;
+    BIGNUM *exp = &local_exp, *prime = &local_prime;
+    RSA_additional_prime *ap =
+        sk_RSA_additional_prime_value(rsa->additional_primes, i);
+
+    BN_with_flags(exp, ap->exp, BN_FLG_CONSTTIME);
+    BN_with_flags(prime, ap->prime, BN_FLG_CONSTTIME);
+
+    /* c will already point to a BIGNUM with the correct flags. */
+    if (!BN_mod(r1, c, prime, ctx)) {
+      goto err;
+    }
+
+    if ((rsa->flags & RSA_FLAG_CACHE_PRIVATE) &&
+        !BN_MONT_CTX_set_locked(&ap->method_mod, &rsa->lock, prime, ctx)) {
+      goto err;
+    }
+
+    if (!rsa->meth->bn_mod_exp(m1, r1, exp, prime, ctx, ap->method_mod)) {
+      goto err;
+    }
+
+    BN_set_flags(m1, BN_FLG_CONSTTIME);
+
+    if (!BN_sub(m1, m1, r0) ||
+        !BN_mul(m1, m1, ap->coeff, ctx) ||
+        !BN_mod(m1, m1, prime, ctx) ||
+        (BN_is_negative(m1) && !BN_add(m1, m1, prime)) ||
+        !BN_mul(m1, m1, ap->r, ctx) ||
+        !BN_add(r0, r0, m1)) {
+      goto err;
+    }
+  }
+
   if (rsa->e && rsa->n) {
     if (!rsa->meth->bn_mod_exp(vrfy, r0, rsa->e, rsa->n, ctx,
                                rsa->_method_mod_n)) {
@@ -766,12 +830,20 @@ err:
   return ret;
 }
 
-static int keygen(RSA *rsa, int bits, BIGNUM *e_value, BN_GENCB *cb) {
+static int keygen_multiprime(RSA *rsa, int bits, int num_primes,
+                             BIGNUM *e_value, BN_GENCB *cb) {
   BIGNUM *r0 = NULL, *r1 = NULL, *r2 = NULL, *r3 = NULL, *tmp;
   BIGNUM local_r0, local_d, local_p;
   BIGNUM *pr0, *d, *p;
-  int bitsp, bitsq, ok = -1, n = 0;
+  int prime_bits, ok = -1, n = 0, i, j;
   BN_CTX *ctx = NULL;
+  STACK_OF(RSA_additional_prime) *additional_primes = NULL;
+
+  if (num_primes < 2) {
+    ok = 0; /* we set our own err */
+    OPENSSL_PUT_ERROR(RSA, RSA_R_MUST_HAVE_AT_LEAST_TWO_PRIMES);
+    goto err;
+  }
 
   ctx = BN_CTX_new();
   if (ctx == NULL) {
@@ -782,12 +854,36 @@ static int keygen(RSA *rsa, int bits, BIGNUM *e_value, BN_GENCB *cb) {
   r1 = BN_CTX_get(ctx);
   r2 = BN_CTX_get(ctx);
   r3 = BN_CTX_get(ctx);
-  if (r3 == NULL) {
+  if (r0 == NULL || r1 == NULL || r2 == NULL || r3 == NULL) {
     goto err;
   }
 
-  bitsp = (bits + 1) / 2;
-  bitsq = bits - bitsp;
+  if (num_primes > 2) {
+    additional_primes = sk_RSA_additional_prime_new_null();
+    if (additional_primes == NULL) {
+      goto err;
+    }
+  }
+
+  for (i = 2; i < num_primes; i++) {
+    RSA_additional_prime *ap = OPENSSL_malloc(sizeof(RSA_additional_prime));
+    if (ap == NULL) {
+      goto err;
+    }
+    memset(ap, 0, sizeof(RSA_additional_prime));
+    ap->prime = BN_new();
+    ap->exp = BN_new();
+    ap->coeff = BN_new();
+    ap->r = BN_new();
+    if (ap->prime == NULL ||
+        ap->exp == NULL ||
+        ap->coeff == NULL ||
+        ap->r == NULL ||
+        !sk_RSA_additional_prime_push(additional_primes, ap)) {
+      RSA_additional_prime_free(ap);
+      goto err;
+    }
+  }
 
   /* We need the RSA components non-NULL */
   if (!rsa->n && ((rsa->n = BN_new()) == NULL)) {
@@ -815,11 +911,14 @@ static int keygen(RSA *rsa, int bits, BIGNUM *e_value, BN_GENCB *cb) {
     goto err;
   }
 
-  BN_copy(rsa->e, e_value);
+  if (!BN_copy(rsa->e, e_value)) {
+    goto err;
+  }
 
   /* generate p and q */
+  prime_bits = (bits + (num_primes - 1)) / num_primes;
   for (;;) {
-    if (!BN_generate_prime_ex(rsa->p, bitsp, 0, NULL, NULL, cb) ||
+    if (!BN_generate_prime_ex(rsa->p, prime_bits, 0, NULL, NULL, cb) ||
         !BN_sub(r2, rsa->p, BN_value_one()) ||
         !BN_gcd(r1, r2, rsa->e, ctx)) {
       goto err;
@@ -834,19 +933,20 @@ static int keygen(RSA *rsa, int bits, BIGNUM *e_value, BN_GENCB *cb) {
   if (!BN_GENCB_call(cb, 3, 0)) {
     goto err;
   }
+  prime_bits = ((bits - prime_bits) + (num_primes - 2)) / (num_primes - 1);
   for (;;) {
     /* When generating ridiculously small keys, we can get stuck
      * continually regenerating the same prime values. Check for
      * this and bail if it happens 3 times. */
     unsigned int degenerate = 0;
     do {
-      if (!BN_generate_prime_ex(rsa->q, bitsq, 0, NULL, NULL, cb)) {
+      if (!BN_generate_prime_ex(rsa->q, prime_bits, 0, NULL, NULL, cb)) {
         goto err;
       }
     } while ((BN_cmp(rsa->p, rsa->q) == 0) && (++degenerate < 3));
     if (degenerate == 3) {
       ok = 0; /* we set our own err */
-      OPENSSL_PUT_ERROR(RSA, keygen, RSA_R_KEY_SIZE_TOO_SMALL);
+      OPENSSL_PUT_ERROR(RSA, RSA_R_KEY_SIZE_TOO_SMALL);
       goto err;
     }
     if (!BN_sub(r2, rsa->q, BN_value_one()) ||
@@ -860,20 +960,91 @@ static int keygen(RSA *rsa, int bits, BIGNUM *e_value, BN_GENCB *cb) {
       goto err;
     }
   }
-  if (!BN_GENCB_call(cb, 3, 1)) {
+
+  if (!BN_GENCB_call(cb, 3, 1) ||
+      !BN_mul(rsa->n, rsa->p, rsa->q, ctx)) {
     goto err;
   }
+
+  for (i = 2; i < num_primes; i++) {
+    RSA_additional_prime *ap =
+        sk_RSA_additional_prime_value(additional_primes, i - 2);
+    prime_bits = ((bits - BN_num_bits(rsa->n)) + (num_primes - (i + 1))) /
+                 (num_primes - i);
+
+    for (;;) {
+      if (!BN_generate_prime_ex(ap->prime, prime_bits, 0, NULL, NULL, cb)) {
+        goto err;
+      }
+      if (BN_cmp(rsa->p, ap->prime) == 0 ||
+          BN_cmp(rsa->q, ap->prime) == 0) {
+        continue;
+      }
+
+      for (j = 0; j < i - 2; j++) {
+        if (BN_cmp(sk_RSA_additional_prime_value(additional_primes, j)->prime,
+                   ap->prime) == 0) {
+          break;
+        }
+      }
+      if (j != i - 2) {
+        continue;
+      }
+
+      if (!BN_sub(r2, ap->prime, BN_value_one()) ||
+          !BN_gcd(r1, r2, rsa->e, ctx)) {
+        goto err;
+      }
+
+      if (!BN_is_one(r1)) {
+        continue;
+      }
+      if (i != num_primes - 1) {
+        break;
+      }
+
+      /* For the last prime we'll check that it makes n large enough. In the
+       * two prime case this isn't a problem because we generate primes with
+       * the top two bits set and so the product is always of the expected
+       * size. In the multi prime case, this doesn't follow. */
+      if (!BN_mul(r1, rsa->n, ap->prime, ctx)) {
+        goto err;
+      }
+      if (BN_num_bits(r1) == bits) {
+        break;
+      }
+
+      if (!BN_GENCB_call(cb, 2, n++)) {
+        goto err;
+      }
+    }
+
+    /* ap->r is is the product of all the primes prior to the current one
+     * (including p and q). */
+    if (!BN_copy(ap->r, rsa->n)) {
+      goto err;
+    }
+    if (i == num_primes - 1) {
+      /* In the case of the last prime, we calculated n as |r1| in the loop
+       * above. */
+      if (!BN_copy(rsa->n, r1)) {
+        goto err;
+      }
+    } else if (!BN_mul(rsa->n, rsa->n, ap->prime, ctx)) {
+      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 */
   if (!BN_sub(r1, rsa->p, BN_value_one())) {
     goto err; /* p-1 */
@@ -884,6 +1055,14 @@ static int keygen(RSA *rsa, int bits, BIGNUM *e_value, BN_GENCB *cb) {
   if (!BN_mul(r0, r1, r2, ctx)) {
     goto err; /* (p-1)(q-1) */
   }
+  for (i = 2; i < num_primes; i++) {
+    RSA_additional_prime *ap =
+        sk_RSA_additional_prime_value(additional_primes, i - 2);
+    if (!BN_sub(r3, ap->prime, BN_value_one()) ||
+        !BN_mul(r0, r0, r3, ctx)) {
+      goto err;
+    }
+  }
   pr0 = &local_r0;
   BN_with_flags(pr0, r0, BN_FLG_CONSTTIME);
   if (!BN_mod_inverse(rsa->d, rsa->e, pr0, ctx)) {
@@ -912,21 +1091,38 @@ static int keygen(RSA *rsa, int bits, BIGNUM *e_value, BN_GENCB *cb) {
     goto err;
   }
 
+  for (i = 2; i < num_primes; i++) {
+    RSA_additional_prime *ap =
+        sk_RSA_additional_prime_value(additional_primes, i - 2);
+    if (!BN_sub(ap->exp, ap->prime, BN_value_one()) ||
+        !BN_mod(ap->exp, rsa->d, ap->exp, ctx) ||
+        !BN_mod_inverse(ap->coeff, ap->r, ap->prime, ctx)) {
+      goto err;
+    }
+  }
+
   ok = 1;
+  rsa->additional_primes = additional_primes;
+  additional_primes = NULL;
 
 err:
   if (ok == -1) {
-    OPENSSL_PUT_ERROR(RSA, keygen, ERR_LIB_BN);
+    OPENSSL_PUT_ERROR(RSA, ERR_LIB_BN);
     ok = 0;
   }
   if (ctx != NULL) {
     BN_CTX_end(ctx);
     BN_CTX_free(ctx);
   }
-
+  sk_RSA_additional_prime_pop_free(additional_primes,
+                                   RSA_additional_prime_free);
   return ok;
 }
 
+static int keygen(RSA *rsa, int bits, BIGNUM *e_value, BN_GENCB *cb) {
+  return keygen_multiprime(rsa, bits, 2 /* num primes */, e_value, cb);
+}
+
 const struct rsa_meth_st RSA_default_method = {
   {
     0 /* references */,
@@ -955,4 +1151,7 @@ const struct rsa_meth_st RSA_default_method = {
   RSA_FLAG_CACHE_PUBLIC | RSA_FLAG_CACHE_PRIVATE,
 
   keygen,
+  keygen_multiprime,
+
+  NULL /* supports_digest */,
 };