Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I stumbled across this paragraph in a paper:

Hence, user b cannot decrypt C directly. But using e and d , user b can quickly factor N.

How is it possible to speedup the prime factorization when knowing e (public key) and d (private key)?

For clarification:

RSA provides us with these equations:

$n = pq$

$\phi = (p-1)(q-1)$

$gcd(e, \phi) = 1$

$de = 1\pmod{\phi}$

In order to determine $p$ and $q$ an attacker has to factor n which is not feasible. However the paper stated that it is easy to reconstruct $p$ and $q$ when a person knows both (his) private and public keys.

share|improve this question
1  
It might help if you told us what $d$ and $e$ are. –  Robin Chapman Nov 29 '10 at 11:03
    
d is the private key and e is the public key –  Chris Nov 29 '10 at 11:13
    
Chris means: N = pq, with p and q odd primes; and ed = 1 mod (p-1)(q-1). –  TonyK Nov 29 '10 at 12:17
4  
For "small" public exponents $e$ (i.e., $<\sqrt{n}$) you can rewrite your last equation as $de = 1 + k\varphi$ and divide this equation by $n$. As $\phi \approx n$ and as $k$ is an integer, you get $k$ by rounding $de/n$ and hence $\varphi$. For the general case see 8.2.2(i) in cacr.math.uwaterloo.ca/hac/about/chap8.pdf –  j.p. Nov 29 '10 at 12:49
add comment

1 Answer 1

up vote 6 down vote accepted

It is not difficult to prove that one can factor $\rm N$ in polynomial time given any multiple of $\rm \phi(N)$ (here $\rm \:de-1\:$).$\ $ See, for example, Gary Miller: Riemann's hypothesis and tests for primality. 1976

NOTE $\ $ This fact was well-known to the discoverers of RSA. Indeed they mention it explicitly in section IX of the original 1978 paper on RSA, which is quite readable.

share|improve this answer
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.