Add function to recover RSA CRT params.
Some RSA private keys are specified with only n, e and d. Although we
can use these keys directly, it's nice to have a uniform representation
that includes the precomputed CRT values. This change adds a function
that can recover the primes from a minimal private key of that form.
diff --git a/crypto/rsa/rsa.c b/crypto/rsa/rsa.c
index 061bc49..583e667 100644
--- a/crypto/rsa/rsa.c
+++ b/crypto/rsa/rsa.c
@@ -486,3 +486,141 @@
}
return ret;
}
+
+static void bn_free_and_null(BIGNUM **bn) {
+ if (*bn == NULL) {
+ return;
+ }
+
+ BN_free(*bn);
+ *bn = NULL;
+}
+
+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_recover_crt_params, RSA_R_EMPTY_PUBLIC_KEY);
+ return 0;
+ }
+
+ if (rsa->p || rsa->q || rsa->dmp1 || rsa->dmq1 || rsa->iqmp) {
+ OPENSSL_PUT_ERROR(RSA, RSA_recover_crt_params,
+ 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, RSA_recover_crt_params, 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, RSA_recover_crt_params, 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, RSA_recover_crt_params, ERR_R_BN_LIB);
+ goto err;
+ }
+
+ if (!BN_is_zero(rem)) {
+ OPENSSL_PUT_ERROR(RSA, RSA_recover_crt_params, 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, RSA_recover_crt_params, 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, RSA_recover_crt_params, ERR_R_BN_LIB);
+ goto err;
+ }
+
+ if (BN_cmp(multiple, rsa->n) != 0) {
+ OPENSSL_PUT_ERROR(RSA, RSA_recover_crt_params, 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, RSA_recover_crt_params, 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;
+}