If the public key $(e,n)$ and the private key $(d,n)$ are known, what is the easiest way to find the primes $p$ and $q$?
When $n$ and $\phi(n)$ are given this is easy to solve. But I can't manage it given just $(e,d,n)$.
Thanks for any help.
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.Sign up to join this community
It's quite easy to find out the two primes $p$ and $q$ given the secret integer $d$ and the public modulus $n$ and the public exponent $e$.
An algorithm is found on the Appendix C of document SP800-56B.
I copy it here:
Appendix C: Prime Factor Recovery (Normative)
The following algorithm recovers the prime factors of a modulus, given the public and private exponents. The algorithm is based on Fact 1 in [Twenty Years of Attacks on the RSA Cryptosystem, D. Boneh, Notices of the American Mathematical Society (AMS), 46(2), 203 – 213. 1999. ].
Function call: RecoverPrimeFactors(n,e,d)
2.e: public exponent
3.d: private exponent
Output:1.(p,q): prime factors of modulus
Errors: “prime factors not found”
Assumptions: The modulus $n$ is the product of two prime factors $p$ and $q$; the public and private exponents satisfy $de ≡ 1 \, (\mod \lambda(n))$ where $λ(n) = LCM(p– 1,q– 1)$
For $i=1 \dots 100$ do:
a. Generate a random integer $g \in [0, n−1]$.
b. Let $y = g^r \mod n$.
c. If $y= 1$ or $y = n– 1$, then go to Step g.
d. For $j \in [1, t– 1]$ do:
I. Let $x = y^2 \mod n$. II. If $x = 1$, go to Step 5. III. If $x =n– 1$, go to Step g. IV. Let $y=x$.
e. Let $x=y^2 \mod n$.
f. If $x = 1$, go to Step 5.
Output “prime factors not found” and stop.
Let $p = \gcd(y– 1, n)$ and let $q = n / p$.
Output $(p,q)$ as the prime factors.