Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

This question already has an answer here:

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.

share|improve this question

marked as duplicate by e-sushi, AFS, Stephen Touset, DrLecter, xagawa May 12 at 8:15

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.

    
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 at 19:26
    
Maybe that p-1 and q-1 are divisors of ed-1? @Thomas –  Eryndis May 11 at 19:39
1  
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 at 20:42
1  
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 at 21:37
2  
show 2 more comments

1 Answer 1

It's quite easy to find out the two primes $p$ and $q$ given the secret integers $e, d$ and the public modulus $n$.

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

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

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.

  4. Output “prime factors not found” and stop.

  5. Let $p = \gcd(y– 1, n)$ and let $q = n / p$.

  6. Output $(p,q)$ as the prime factors.

share|improve this answer
    
Before seeing your question, I was looking for the same algorithm and when I found the specification and wrote some python code to implement it and test. You'll find an improvable but working code here: gist.github.com/ddddavidee/b34c2b67757a54ce75cb –  ddddavidee May 12 at 7:23
add comment

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