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.

Is it possible to perform RSA decryption if one only knows $N$ and $e$?

Failing that, what is the maximum key length where brute-force is still practically feasible?

share|improve this question
    
The $N$ you provide is 512-bit long, not 128 (unless I messed up a calculation). If it were 128 bits long, and you had a couple of hours (possibly days depending on your gear) to spare, brute-forcing it would be feasible. For 512 I'm not so sure. –  rath Nov 21 '13 at 0:46
    
I've edited your question. If my edit gets accepted you'll notice it's been trimmed down quite a bit. I did this because requests to decrypt a block of data are off-topic on this site, and your question would get closed as a result. If you feel I've been too liberal with my edit, feel free to rollback, but keep in mind the above. Cheers –  rath Nov 21 '13 at 0:52
add comment

1 Answer

The current best way of decryption an RSA ciphertext (assuming good padding was used) is to factor $N$ into its prime factors $p$ and $q$, and from that, reconstruct the decryption exponent $d = e^{-1} \bmod lcm( p-1, q-1 )$

The current record for factoring an RSA-type modulus (with large prime factors, and not of a special form) is 768 bits.

It is likely that, in the next couple years, slightly larger modulii will be factored; the record for "largest general number factored" has been slowly increasing; someone might manage to factor a 1024 bit number within the next decade. There is little reason to expect that RSA modulii significantly larger will be vulnerable to factoring in the near future.

share|improve this answer
    
what does lcm stands for ? –  user10500 Nov 21 '13 at 10:04
    
@user10500: lcm == "Least Common Multiple"; lcm(a,b) is the smallest integer that is a multiple of both a and b. We also have $lcm(a,b) = ab / gcd(a,b)$ (where gcd is the more commonly known greatest common divisor function) –  poncho Nov 21 '13 at 13:03
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.