5
$\begingroup$

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$?

$\endgroup$
  • 3
    $\begingroup$ Compute $\phi = (P-1)(Q-1)$ and then the modular multiplicative inverse of $e$ using extended euclidean. $\endgroup$ – CodesInChaos Oct 1 '14 at 10:56
8
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

Answer to the bonus question: Once $d$ has been computed, you can find the value of $e$ as $e = d^{-1} \bmod p'q'$ (again, you can add any multiple of $p'q'$ to get another valid value for public exponent $e$).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.