3

Given that an attacker only knows the public key and cipher text, why is it difficult to decrpyt the message ? If the knows the N value will he be able to decrypt it ?

8

The short answer is that nobody knows how to compute the inverse RSA (the "decryption") without knowing the prime factors of the modulus N; and nobody knows how to efficiently recover these prime factors from N alone. The private key, then, is knowledge of the prime factors: whoever generated the key pair produced the factors first, then multiplied them together to get N.

Knowing N (the public key) does not allow decryption; that's the whole point of the public key being, yeah, public: revealing it does not give away decryption power.


The long answer, when we get down to it, is: we don't know. There is no positive reason which explains why RSA decryption is hard without knowing the private key. We have no mathematical proof that factoring N is a real prerequisite for RSA decryption; it is just that we don't know how to decrypt RSA without knowing the prime factors (either a priori, or easily obtained from the private key). We have no proof either that factoring is hard; but 2500 years of research have not come up with a really efficient factoring algorithm.

3
  • But isnt private key calculated by: e * d mod N ? So if I know e and N the I can calculate d right ?
    – Cemre
    Jun 2 '14 at 11:23
  • 1
    @Cemre, no, private key is d where ed=1 mod phi(N). Computing phi(N) given only N is equivalent to factoring.
    – mikeazo
    Jun 2 '14 at 12:47
  • I thought shors algorithm did efficiently allow factorisation, of course it can't be run on classical computers and quantum machines running it have managed to factorise the number 21 before decoherence set in. So i think 2048 numbers are safe for a while.
    – ewanm89
    Jun 3 '14 at 0:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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