Calculate the RSA private exponent from the CRT parameters

Question

I am trying to make the RSA structure of Openssl manually, knowing the public key ($n$, $e$) and the CRT parameters $p$, $q$, $d_P$, $d_Q$, and $u = q^{-1} \mod p$.

That is, I want to get the $d$ value (private exponent) of the RSA structure by using Openssl API. If there are already any implemented functions, it would be great to me.

Bonus question: is it possible if I have $p$, $q$, $d_P$, $d_Q$ and $u$ but not the public key? I know that $n = p q$, but what about $e$?

Answer 1

Calculate $\phi(n) = (p-1) (q-1) = n - p - q + 1$. Then $d = e^{-1} \mod \phi(n)$.

With OpenSSL, the code should look something like this (error checking omitted):

BN_CTX *ctx = BN_ctx_new();
BIGNUM *d = BN_dup(n);
BN_sub(d, d, p);
BN_sub(d, d, q);
BN_add_word(d, 1);
BN_mod_inverse(d, e, d);
BN_ctx_free(ctx);
return d;

If the public exponent is not known, it's usually possible to guess it, since it's usually chosen from a very small pool. But failing that it's possible to find working values of both the public and private exponents from $d_p$, $d_q$, $p$ and $q$. See user94293's answer.

The inverse calculation is less straightforward. There's a good description in Twenty Years of Attacks on the RSA Cryptosystem by Dan Boneh (Fact 1) or in How to calculate RSA CRT parameters from public key and private exponent

Answer 2

user94293's answer is true but missing an important part which is, second and third steps should be iterative. By meaning that after second step, gcd is needed to be checked until it gets 1. Think of it like that: $p - 1 = a.c^1 $ and $q - 1 = b.c^x$, in that case we need to divide $q^′$ x times.

1. $p' = p - 1$ and $q' = q - 1$
2. $δ=gcd(p',q');$
3. $q'=q'/δ;$
4. $while(δ$ != $1)$ goto step 2;
5. $i_{q^{'}} = (q^{'})^{-1} \mod p^{'}$ and $d_{q^{'}} = d_q \mod q^{'};$
6. $d = d_{q^{'}} + q^{'}[i_{q^{'}}(d_p - d_{q^{'}}) \mod p^{'}];$

In that way you can obtain correct result. Because gcd result must be always 1 for a meaningful modular inversion return.