Use a minimal totient when generating RSA keys.
FIPS 186-4 wants d = e^-1 (mod lcm(p-1, q-1)), not (p-1)*(q-1).
Note this means the size of d might reveal information about p-1 and
q-1. However, we do operations with Chinese Remainder Theorem, so we
only use d (mod p-1) and d (mod q-1) as exponents. Using a minimal
totient does not affect those two values.
This removes RSA_recover_crt_params. Using a minimal d breaks (or rather
reveals an existing bug in) the function.
While I'm here, rename those ridiculous variable names.
Change-Id: Iaf623271d49cd664ba0eca24aa25a393f5666fac
Reviewed-on: https://boringssl-review.googlesource.com/15944
Commit-Queue: David Benjamin <davidben@google.com>
Commit-Queue: Adam Langley <agl@google.com>
Reviewed-by: Adam Langley <agl@google.com>
CQ-Verified: CQ bot account: commit-bot@chromium.org <commit-bot@chromium.org>
diff --git a/crypto/rsa/rsa.c b/crypto/rsa/rsa.c
index afc1432..7ad78a1 100644
--- a/crypto/rsa/rsa.c
+++ b/crypto/rsa/rsa.c
@@ -564,11 +564,6 @@
return ret;
}
-static void bn_free_and_null(BIGNUM **bn) {
- BN_free(*bn);
- *bn = NULL;
-}
-
int RSA_check_key(const RSA *key) {
BIGNUM n, pm1, qm1, lcm, gcd, de, dmp1, dmq1, iqmp_times_q;
BN_CTX *ctx;
@@ -612,7 +607,7 @@
BN_init(&iqmp_times_q);
if (!BN_mul(&n, key->p, key->q, ctx) ||
- /* lcm = lcm(prime-1, for all primes) */
+ /* lcm = lcm(p, q) */
!BN_sub(&pm1, key->p, BN_value_one()) ||
!BN_sub(&qm1, key->q, BN_value_one()) ||
!BN_mul(&lcm, &pm1, &qm1, ctx) ||
@@ -623,7 +618,7 @@
if (!BN_div(&lcm, NULL, &lcm, &gcd, ctx) ||
!BN_gcd(&gcd, &pm1, &qm1, ctx) ||
- /* de = d*e mod lcm(prime-1, for all primes). */
+ /* de = d*e mod lcm(p, q). */
!BN_mod_mul(&de, key->d, key->e, &lcm, ctx)) {
OPENSSL_PUT_ERROR(RSA, ERR_LIB_BN);
goto out;
@@ -767,134 +762,6 @@
return ret;
}
-int RSA_recover_crt_params(RSA *rsa) {
- BN_CTX *ctx;
- BIGNUM *totient, *rem, *multiple, *p_plus_q, *p_minus_q;
- int ok = 0;
-
- if (rsa->n == NULL || rsa->e == NULL || rsa->d == NULL) {
- OPENSSL_PUT_ERROR(RSA, RSA_R_EMPTY_PUBLIC_KEY);
- return 0;
- }
-
- if (rsa->p || rsa->q || rsa->dmp1 || rsa->dmq1 || rsa->iqmp) {
- OPENSSL_PUT_ERROR(RSA, RSA_R_CRT_PARAMS_ALREADY_GIVEN);
- return 0;
- }
-
- /* This uses the algorithm from section 9B of the RSA paper:
- * http://people.csail.mit.edu/rivest/Rsapaper.pdf */
-
- ctx = BN_CTX_new();
- if (ctx == NULL) {
- OPENSSL_PUT_ERROR(RSA, ERR_R_MALLOC_FAILURE);
- return 0;
- }
-
- BN_CTX_start(ctx);
- totient = BN_CTX_get(ctx);
- rem = BN_CTX_get(ctx);
- multiple = BN_CTX_get(ctx);
- p_plus_q = BN_CTX_get(ctx);
- p_minus_q = BN_CTX_get(ctx);
-
- if (totient == NULL || rem == NULL || multiple == NULL || p_plus_q == NULL ||
- p_minus_q == NULL) {
- OPENSSL_PUT_ERROR(RSA, ERR_R_MALLOC_FAILURE);
- goto err;
- }
-
- /* ed-1 is a small multiple of φ(n). */
- if (!BN_mul(totient, rsa->e, rsa->d, ctx) ||
- !BN_sub_word(totient, 1) ||
- /* φ(n) =
- * pq - p - q + 1 =
- * n - (p + q) + 1
- *
- * Thus n is a reasonable estimate for φ(n). So, (ed-1)/n will be very
- * close. But, when we calculate the quotient, we'll be truncating it
- * because we discard the remainder. Thus (ed-1)/multiple will be >= n,
- * which the totient cannot be. So we add one to the estimate.
- *
- * Consider ed-1 as:
- *
- * multiple * (n - (p+q) + 1) =
- * multiple*n - multiple*(p+q) + multiple
- *
- * When we divide by n, the first term becomes multiple and, since
- * multiple and p+q is tiny compared to n, the second and third terms can
- * be ignored. Thus I claim that subtracting one from the estimate is
- * sufficient. */
- !BN_div(multiple, NULL, totient, rsa->n, ctx) ||
- !BN_add_word(multiple, 1) ||
- !BN_div(totient, rem, totient, multiple, ctx)) {
- OPENSSL_PUT_ERROR(RSA, ERR_R_BN_LIB);
- goto err;
- }
-
- if (!BN_is_zero(rem)) {
- OPENSSL_PUT_ERROR(RSA, RSA_R_BAD_RSA_PARAMETERS);
- goto err;
- }
-
- rsa->p = BN_new();
- rsa->q = BN_new();
- rsa->dmp1 = BN_new();
- rsa->dmq1 = BN_new();
- rsa->iqmp = BN_new();
- if (rsa->p == NULL || rsa->q == NULL || rsa->dmp1 == NULL || rsa->dmq1 ==
- NULL || rsa->iqmp == NULL) {
- OPENSSL_PUT_ERROR(RSA, ERR_R_MALLOC_FAILURE);
- goto err;
- }
-
- /* φ(n) = n - (p + q) + 1 =>
- * n - totient + 1 = p + q */
- if (!BN_sub(p_plus_q, rsa->n, totient) ||
- !BN_add_word(p_plus_q, 1) ||
- /* p - q = sqrt((p+q)^2 - 4n) */
- !BN_sqr(rem, p_plus_q, ctx) ||
- !BN_lshift(multiple, rsa->n, 2) ||
- !BN_sub(rem, rem, multiple) ||
- !BN_sqrt(p_minus_q, rem, ctx) ||
- /* q is 1/2 (p+q)-(p-q) */
- !BN_sub(rsa->q, p_plus_q, p_minus_q) ||
- !BN_rshift1(rsa->q, rsa->q) ||
- !BN_div(rsa->p, NULL, rsa->n, rsa->q, ctx) ||
- !BN_mul(multiple, rsa->p, rsa->q, ctx)) {
- OPENSSL_PUT_ERROR(RSA, ERR_R_BN_LIB);
- goto err;
- }
-
- if (BN_cmp(multiple, rsa->n) != 0) {
- OPENSSL_PUT_ERROR(RSA, RSA_R_INTERNAL_ERROR);
- goto err;
- }
-
- if (!BN_sub(rem, rsa->p, BN_value_one()) ||
- !BN_mod(rsa->dmp1, rsa->d, rem, ctx) ||
- !BN_sub(rem, rsa->q, BN_value_one()) ||
- !BN_mod(rsa->dmq1, rsa->d, rem, ctx) ||
- !BN_mod_inverse(rsa->iqmp, rsa->q, rsa->p, ctx)) {
- OPENSSL_PUT_ERROR(RSA, ERR_R_BN_LIB);
- goto err;
- }
-
- ok = 1;
-
-err:
- BN_CTX_end(ctx);
- BN_CTX_free(ctx);
- if (!ok) {
- bn_free_and_null(&rsa->p);
- bn_free_and_null(&rsa->q);
- bn_free_and_null(&rsa->dmp1);
- bn_free_and_null(&rsa->dmq1);
- bn_free_and_null(&rsa->iqmp);
- }
- return ok;
-}
-
int RSA_private_transform(RSA *rsa, uint8_t *out, const uint8_t *in,
size_t len) {
if (rsa->meth->private_transform) {
diff --git a/crypto/rsa/rsa_impl.c b/crypto/rsa/rsa_impl.c
index 012a984..5f5eb5e 100644
--- a/crypto/rsa/rsa_impl.c
+++ b/crypto/rsa/rsa_impl.c
@@ -928,11 +928,11 @@
goto bn_err;
}
BN_CTX_start(ctx);
- BIGNUM *r0 = BN_CTX_get(ctx);
- BIGNUM *r1 = BN_CTX_get(ctx);
- BIGNUM *r2 = BN_CTX_get(ctx);
- BIGNUM *r3 = BN_CTX_get(ctx);
- if (r0 == NULL || r1 == NULL || r2 == NULL || r3 == NULL) {
+ BIGNUM *totient = BN_CTX_get(ctx);
+ BIGNUM *pm1 = BN_CTX_get(ctx);
+ BIGNUM *qm1 = BN_CTX_get(ctx);
+ BIGNUM *gcd = BN_CTX_get(ctx);
+ if (totient == NULL || pm1 == NULL || qm1 == NULL || gcd == NULL) {
goto bn_err;
}
@@ -969,11 +969,19 @@
rsa->q = tmp;
}
- /* Calculate d. */
- if (!BN_sub(r1 /* p-1 */, rsa->p, BN_value_one()) ||
- !BN_sub(r2 /* q-1 */, rsa->q, BN_value_one()) ||
- !BN_mul(r0 /* (p-1)(q-1) */, r1, r2, ctx) ||
- !BN_mod_inverse(rsa->d, rsa->e, r0, ctx)) {
+ /* Calculate d = e^(-1) (mod lcm(p-1, q-1)), per FIPS 186-4. This differs
+ * from typical RSA implementations which use (p-1)*(q-1).
+ *
+ * Note this means the size of d might reveal information about p-1 and
+ * q-1. However, we do operations with Chinese Remainder Theorem, so we only
+ * use d (mod p-1) and d (mod q-1) as exponents. Using a minimal totient
+ * does not affect those two values. */
+ if (!BN_sub(pm1, rsa->p, BN_value_one()) ||
+ !BN_sub(qm1, rsa->q, BN_value_one()) ||
+ !BN_mul(totient, pm1, qm1, ctx) ||
+ !BN_gcd(gcd, pm1, qm1, ctx) ||
+ !BN_div(totient, NULL, totient, gcd, ctx) ||
+ !BN_mod_inverse(rsa->d, rsa->e, totient, ctx)) {
goto bn_err;
}
@@ -984,9 +992,9 @@
if (/* Calculate n. */
!BN_mul(rsa->n, rsa->p, rsa->q, ctx) ||
/* Calculate d mod (p-1). */
- !BN_mod(rsa->dmp1, rsa->d, r1, ctx) ||
+ !BN_mod(rsa->dmp1, rsa->d, pm1, ctx) ||
/* Calculate d mod (q-1) */
- !BN_mod(rsa->dmq1, rsa->d, r2, ctx)) {
+ !BN_mod(rsa->dmq1, rsa->d, qm1, ctx)) {
goto bn_err;
}
diff --git a/crypto/rsa/rsa_test.cc b/crypto/rsa/rsa_test.cc
index 415f6b8..be69abe 100644
--- a/crypto/rsa/rsa_test.cc
+++ b/crypto/rsa/rsa_test.cc
@@ -555,43 +555,6 @@
buf_len, key.get()));
}
-TEST(RSATest, RecoverCRTParams) {
- bssl::UniquePtr<BIGNUM> e(BN_new());
- ASSERT_TRUE(e);
- ASSERT_TRUE(BN_set_word(e.get(), RSA_F4));
-
- bssl::UniquePtr<RSA> key1(RSA_new());
- ASSERT_TRUE(key1);
- ASSERT_TRUE(RSA_generate_key_ex(key1.get(), 512, e.get(), nullptr));
-
- EXPECT_TRUE(RSA_check_key(key1.get()));
-
- // Create a copy of the key without CRT parameters.
- bssl::UniquePtr<RSA> key2(RSA_new());
- ASSERT_TRUE(key2);
- key2->n = BN_dup(key1->n);
- key2->e = BN_dup(key1->e);
- key2->d = BN_dup(key1->d);
- ASSERT_TRUE(key2->n);
- ASSERT_TRUE(key2->e);
- ASSERT_TRUE(key2->d);
-
- ASSERT_TRUE(RSA_recover_crt_params(key2.get()));
-
- // The recovered RSA parameters should work.
- EXPECT_TRUE(RSA_check_key(key2.get()));
-
- uint8_t buf[128];
- unsigned buf_len = sizeof(buf);
- ASSERT_LE(RSA_size(key2.get()), buf_len);
-
- const uint8_t kDummyHash[32] = {0};
- EXPECT_TRUE(RSA_sign(NID_sha256, kDummyHash, sizeof(kDummyHash), buf,
- &buf_len, key2.get()));
- EXPECT_TRUE(RSA_verify(NID_sha256, kDummyHash, sizeof(kDummyHash), buf,
- buf_len, key2.get()));
-}
-
TEST(RSATest, ASN1) {
// Test that private keys may be decoded.
bssl::UniquePtr<RSA> rsa(
diff --git a/include/openssl/rsa.h b/include/openssl/rsa.h
index b697a7d..6ce75f6 100644
--- a/include/openssl/rsa.h
+++ b/include/openssl/rsa.h
@@ -336,13 +336,6 @@
* if they pass and zero otherwise. Opaque keys always fail. */
OPENSSL_EXPORT int RSA_check_fips(RSA *key);
-/* RSA_recover_crt_params uses |rsa->n|, |rsa->d| and |rsa->e| in order to
- * calculate the two primes used and thus the precomputed, CRT values. These
- * values are set in the |p|, |q|, |dmp1|, |dmq1| and |iqmp| members of |rsa|,
- * which must be |NULL| on entry. It returns one on success and zero
- * otherwise. */
-OPENSSL_EXPORT int RSA_recover_crt_params(RSA *rsa);
-
/* RSA_verify_PKCS1_PSS_mgf1 verifies that |EM| is a correct PSS padding of
* |mHash|, where |mHash| is a digest produced by |Hash|. |EM| must point to
* exactly |RSA_size(rsa)| bytes of data. The |mgf1Hash| argument specifies the
