This question already has an answer here:

I have a private key components p, q, Dp, Dq, and QInv. I need to calculate the public key modulus and exponent. Modulus was super simple p*q, but exponent I can't figure out. Have searched all the articles and often found how to go opposite way - generating public private key once you pick the exponenet.

I have been trying ModInverse from p-1 and q-1, and solve x with GCD on all the componenets, but nothing gave me the right value (I know the value I should get is x010001). Seems to be a little bit more complex that this...

Im really in to the code and less in math, so if I could get the answer which use simple math operations as 'Add', 'Sub', 'Multiply', 'Mod', 'ModInverse', 'GCD' etc. would be great!


marked as duplicate by Gilles, kelalaka, Maarten Bodewes Jan 21 at 12:48

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

migrated from security.stackexchange.com Jan 19 at 11:26

This question came from our site for information security professionals.

  • $\begingroup$ @Gilles: the present question is not a duplicate of that, even if we consider that $d$ and $e$ are symmetric. In the other question we have $e$, $p$, $q$ (and so other unneeded stuff), and we want $d$. Here, we want $e$ and we do not have $d$, so we'll have to use $p$, $q$, $d_P$ and $d_Q$. $\endgroup$ – fgrieu Jan 19 at 15:56
  • $\begingroup$ @fgrieu The other question as asked doesn't cover that case, but it has an answer that does, so there's no point in repeating that answer here. $\endgroup$ – Gilles Jan 19 at 15:58
  • $\begingroup$ @Gilles: Ah yes, that answer indeed explains how to compute the lowest positive $d$ from $p$, $q$, $d_P$ and $d_Q$, and that can be put to good use here. Or we can use the same method to compute the lowest possible $e$ from $e_P={d_P}^{-1}\bmod(p-1)$ and $e_Q={d_Q}^{-1}\bmod(p-1)$. $\endgroup$ – fgrieu Jan 19 at 16:07

Your public key contains two numbers. First it is a number n, which is called the Modulus and are computed through $p \cdot q = n$. The second number is e, which is the public exponent and are used to encrypt your message m. The number e is choosen that it have the following properties:

\begin{equation} 1 < e < \phi(n) = (p-1)(q-1) \end{equation} \begin{equation} gcd(e, (p-1)(q-1)) = 1 \end{equation}

$\phi$ is the euler's totient function.

The private key contains the numbers p,q and d. The number d is your private exponent and p,q are your prime numbers, which helps you do calculate n and the private and public exponent.

The private exponent have the following properties:

\begin{equation} 1 < d < (p-1)(q-1) \end{equation} \begin{equation} d = e^{-1} mod~(p-1)(q-1) \end{equation}

I am not sure, what are Dp, Dq and QInv in your configuration is, but if you have d you are able to compute e with:

\begin{equation} e = d^{-1} mod~(p-1)(q-1) \end{equation}

I hope it will help you. If that doesn't help may specifiy what are Dp, Dq and QInv are.

EDIT: I think you are using the PKCS#1, which are mentioned in the comments below of this answer.

In the PKCS#1 you are also able to have a quintuple as a private key, which are p, q, Dp, Dq and QInv.

Dp and Dq satisfy the following equations:

\begin{equation} e \cdot Dp \equiv 1~mod~(p-1) \Leftrightarrow e = Dp^{-1} ~mod ~(p-1) \\ e \cdot Dq \equiv 1~mod~(q-1) \Leftrightarrow e = Dq^{-1} ~mod ~(q-1) \end{equation}

and the number e have a little bit different property. The property of e is:

\begin{equation} gcd(e, \lambda(n)) = 1~and~\lambda(n) = LCM(p,q) \end{equation}

Additionally your d is satisfying this equation instead of that from above:

\begin{equation} ed \equiv 1 ~mod ~\lambda(n) \Leftrightarrow e = d^{-1} ~mod ~\lambda(n) \end{equation}

This equation should give you the right e from your giving d and $e = d^{-1}~mod~\lambda(n)$ means compute the modular inverse from d with the modulus $LCM(p,q)$.

I hope this will help you.

  • $\begingroup$ $e$ is arbitrarily chosen, which nowadays are almost always 65537 (0x010001) $\endgroup$ – DannyNiu Jan 19 at 12:49
  • $\begingroup$ Dp and Dq are the special exponents used in a fast decryption/signing algorithm, see PKCS#1 $\endgroup$ – DannyNiu Jan 19 at 12:51
  • 1
    $\begingroup$ The stated $e={d_P}^{-1}\bmod(p-1)$ is wrong. What holds is $e\equiv{d_P}^{-1}\pmod{(p-1)}$, which contrary to the former does not define a single $e$. This answer does not fully explain how to compute (a working) $e$. To apply $e=d^{-1}\bmod((p-1)(q-1))$ or $e = d^{-1}\bmod(\text{lcm}(p-1,q-1))$ one needs to compute $d$, and that's not a given. And to compute an $e$ knowing that $e\equiv{d_P}^{-1}\pmod{(p-1)}$ and $e\equiv{d_Q}^{-1}\pmod{(q-1)}$, we need some extra math. Hint: if $p-1$ and $q-1$ where coprime (which does not hold), it would just be applying the Chinese Remainder Theorem. $\endgroup$ – fgrieu Jan 19 at 15:40
  • 1
    $\begingroup$ @fgrieu: while it is true that $e \equiv dp^{-1} \pmod {p-1}$ does not define a single $e$, however unless $e$ is huge (larger than $p-1$), then $e = dp^{-1} \mod (p-1)$ will be the correct value $\endgroup$ – poncho Jan 19 at 17:06
  • $\begingroup$ @fgrieu yes you are right, I thought that he has the private exponent $d$. Thank you for the comment. I considered that $e \equiv d_P^{-1}~(mod (p-1)) \Leftrightarrow e = d_P^{-1}~mod~(p-1)$ is the same, because the congruence are in the sense of the modulus (p-1). $\endgroup$ – pascalao Jan 19 at 17:13