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.

Given the RSA modulus $N$ the fastest method to factor it is of sub-exponent order. But, now if I know the private key $d$ of RSA, does that mean I can factor $N$ efficiently?. It intuitively seems true as I know the public/private key pair. Can someone help me to prove this?

Please provide references so that I can read further into this subject.

share|improve this question
1  
If you know $e$, $d$ and $n$, you can efficiently factor $n$. Just knowing $d$ is not enough if $e$ is big. –  CodesInChaos May 6 at 6:44
    
@CodesInChaos Do you mean that knowing $(N,e,d)$ if $e$ is big, then we cannot still factor $N$? –  Alex May 6 at 8:17
2  
Knowing $(N,e,d)$, including with big $e$, allows finding the factorization of $N$, by heuristic or deterministic methods pointed in Samuel Neves's nice answer. If $e$ is unknown but small, we can enumerate small values to find $e$, using $(x^d)^e\equiv x\pmod N$ for arbitrary $x$ such as 2 as a test of having reached the right $e$; and then are back to the same problem [reposted with fix]. –  fgrieu May 6 at 10:12
add comment

1 Answer 1

up vote 6 down vote accepted

Yes, they are (deterministically) equivalent. The original RSA paper (Section IX.C), working off Miller's results (Theorem 3), showed how knowing the secret exponent $d$ was probabilistically equivalent to factoring $n$.

Later, using more advanced techniques, Coron and May showed how to deterministically reduce finding $d$ to factoring $n$.

share|improve this answer
    
when we select $e,d$, generally speaking, if they should $e,d <\phi(N)$ ? –  Alex May 18 at 2:33
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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