# Calculate the RSA private exponent from the CRT parameters

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.

-
1) Do you know e? Different es result in different ds. 2) How did you end up with knowing all those values but not knowing d? – CodesInChaos Oct 1 '14 at 9:30
if you use a standard $e$ it is quite easy to recover the $d$ exponent. (but at the moment I dont remember if there is a direct function in OpenSSL API) – ddddavidee Oct 1 '14 at 9:59
I am supposed to receive N,E,P,Q,DP1,. and etc, except for the D value. With the values (N,E,D), I should test encryption/decripton. – GT Kim Oct 1 '14 at 10:15
Compute $\phi = (P-1)(Q-1)$ and then the modular multiplicative inverse of $e$ using extended euclidean. – CodesInChaos Oct 1 '14 at 10:56
Thanks, I will try it. – GT Kim Oct 1 '14 at 11:56

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_mod_inverse(d, e, d);
BN_ctx_free(ctx);
return d;


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).

-
Thank you, Gilles. Your codes helped me greatly. :) – GT Kim Oct 2 '14 at 2:09
BN_mod_inverse(d,e,n) should be BN_mod_inverse(d,e,d) because the value in d is the euler totient phi(n). – Frank Zonneveld May 19 at 12:06

For completeness, here is how to compute $d$ without resorting to the value of public exponent $e$.

1. Compute $\delta = \gcd(p-1,q-1)$;
2. Define $p' = p-1$ and $q' = (q-1)/\delta$;
3. Compute $i_{q'} = (q')^{-1} \bmod p'$ and $d_{q'} = d_q \bmod q'$;
4. Return $d = d_{q'} + q'[i_{q'} (d_{p}-d_{q'}) \bmod p']$.

Note that the so-obtained value for $d$ is defined modulo $\lambda(N)=p'q'$ (i.e., the Carmichael function of $N$). If the implementation requires a private exponent $d$ of a larger size, adding any multiple of $p'q'$ gives another valid private exponent.

-