# How to calculate Public Key exponent if I have p, q, Dp, Dq, QInv? [duplicate]

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!

## migrated from security.stackexchange.comJan 19 at 11:26

This question came from our site for information security professionals.

• @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$. – fgrieu Jan 19 at 15:56
• @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. – Gilles Jan 19 at 15:58
• @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)$. – 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:

$$$$1 < e < \phi(n) = (p-1)(q-1)$$$$ $$$$gcd(e, (p-1)(q-1)) = 1$$$$

$$\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:

$$$$1 < d < (p-1)(q-1)$$$$ $$$$d = e^{-1} mod~(p-1)(q-1)$$$$

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:

$$$$e = d^{-1} mod~(p-1)(q-1)$$$$

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:

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

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

$$$$gcd(e, \lambda(n)) = 1~and~\lambda(n) = LCM(p,q)$$$$

$$$$ed \equiv 1 ~mod ~\lambda(n) \Leftrightarrow e = d^{-1} ~mod ~\lambda(n)$$$$
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)$$.
• $e$ is arbitrarily chosen, which nowadays are almost always 65537 (0x010001) – DannyNiu Jan 19 at 12:49
• 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. – fgrieu Jan 19 at 15:40
• @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 – poncho Jan 19 at 17:06
• @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). – pascalao Jan 19 at 17:13