7
$\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$
1
  • 3
    $\begingroup$ Compute $\phi = (P-1)(Q-1)$ and then the modular multiplicative inverse of $e$ using extended euclidean. $\endgroup$ Oct 1, 2014 at 10:56

2 Answers 2

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$
0
1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ It still does not work.Try it with $p=11$, $q=17$, $e=3$, thus $d_p=7$, $d_q=11$. We get $p'=10$, first $q'=16$, final $q'=1$, $i_{q'}=1$, $d_{q'}=0$, $d=6$. But that's even, thus not a valid $d$. $\endgroup$
    – fgrieu
    Jun 2, 2023 at 9:36
  • $\begingroup$ The conceptually simplest is $δ←\gcd(p-1,q-1)$, $d_δ←d_p\bmodδ$, check $d_q\bmodδ=d_δ$, $p'←(p-1)/δ$, $d_{p'}←d_p\bmod p'$, $q'←(q-1)/δ$, $d_{q'}←d_q\bmod q'$, and we are back to a CRT with three coprime moduli $δ,p',q'$ and remainders $d_δ,d_{p'},d_{q'}$. Another option is to keep two coprime moduli $p'$ and $q'$ (as in the answer), but have two branches, one with $p'←p-1$ and $q'←(q-1)/δ$ (as in the now deleted user94293's answer), the other with $p'←(p-1)/δ$ and $q'←q-1$. $\endgroup$
    – fgrieu
    Jun 2, 2023 at 10:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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