# RSA, finding p,q [duplicate]

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.

• If you have $e$ and $d$, and you know that $ed \equiv 1 \pmod{\varphi(n)}$ - or $\mathrm{lcm}{(p - 1, q - 1)}$ - what can you deduce? – Thomas May 11 '14 at 19:26
• Maybe that p-1 and q-1 are divisors of ed-1? @Thomas – Eryndis May 11 '14 at 19:39
• I'm not sure I follow what you mean by "2 divides p - 1 ϕ(p-1) times", but the basic idea is this: if 2 divides $p - 1$, $x$ times, and 2 divides $q - 1$, $y$ times, then 2 divides $ed - 1$ at least $\max(x, y)$ times. So if you keep dividing $ed - 1$ by 2, at some point you will end up with a number that is a multiple of $p - 1$ but not of $q - 1$ (or vice versa). Then using Fermat's little theorem can produce a factor of $n$ (there are some details but that is essentially the idea). – Thomas May 11 '14 at 20:42
• If you prefer, you can use the following idea: since $ed - 1$ is a multiple of both $p - 1$ and $q - 1$, if follows that $a^{\frac{ed - 1}{2^k}} \equiv \pm 1 \pmod{p, q}$ for some small $k$. Thus trying a bunch of random $a$'s, you will quickly find an $a$ which is a quadratic residue modulo $p$ but a quadratic nonresidue modulo $q$, such that $a^{\frac{ed - 1}{2^k}} - 1$ is a multiple of $p$ but not of $q$, and you are done. – Thomas May 11 '14 at 21:37
• – T.B May 12 '14 at 0:19

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)

Input:

1. n: modulus

2.e: public exponent

3.d: private exponent

Output:1.(p,q): prime factors of modulus

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

Process:

1. Let $k = de – 1$. If $k$ is odd, then go to Step 4.
2. Write $k$ as $k= 2^tr$, where $r$ is the largest odd integer dividing $k$, and $t ≥ 1$.
3. 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.

g. Continue.

5. Let $p = \gcd(y– 1, n)$ and let $q = n / p$.
6. Output $(p,q)$ as the prime factors.
• $e$ is not supposed to be secret. $\;$ – user991 Aug 8 '14 at 8:03
• You can skip step 1. $\lambda(n)$ is even, $ed$ has to be odd, and $ed-1$ has to be even again. – tylo Aug 8 '14 at 13:05