3
$\begingroup$

I am currently looking into RSA and have some questions. I am interested in theoretical answers, assuming there is infinite time for decryption.

  1. Is it necessary to work out the private-key exponent for decryption? Are there no alternative options?
  2. Can a message encrypted using RSA be decrypted using only the public key? If so, how? If not, why?
$\endgroup$
2
  • $\begingroup$ About 2) if it was possible, the private key would be unnecessary and therefore, if no private information was used to decrypt a ciphertext, the encryption won't stand. The scheme would be completely broken. $\endgroup$
    – ddddavidee
    Dec 21, 2015 at 9:58
  • $\begingroup$ Are we talking about the (deterministic) "textbook RSA"? $\endgroup$
    – fkraiem
    Dec 21, 2015 at 11:02

1 Answer 1

4
$\begingroup$

I am interested in theoretical answers, assuming there is infinite time for decryption.

We call such an attacker a 'computationally unbounded adversary'

  1. Is it necessary to work out the private-key exponent for decryption? Are there no alternative options?

One approach that a computationally unbounded adversary could is as go through all possible values $M$, and find one which has $M^e = C \bmod n$; such a message $M$ is the decryption of the ciphertext $C$.

This approach actually takes longer than the more traditional approaches that involve factoring $n$ (and from that, rederiving the decryption exponent); however a computationally unbounded attacker might not care.

  1. Can a message encrypted using RSA be decrypted using only the public key? If so, how? If not, why?

Actually, there are a number of different ways that RSA could be decrypted by a computationally unbounded attacker

  • They can brute force the message (as listed above)

  • They could factor the modulus, and rederive the decrypion exponent

  • As pointed out here, they could generate every possible public/private keypair, and pick out the public key that they actually see. Any public key cryptosystem can be broken by this method.

So, if RSA can so easily be broken by a computationally unbounded adversary, why do we still use it? Well, we don't believe that computationally unbounded adversaries exist, and so that's not considered a real world requirement on crypto systems. Actually, if they do exist, we don't have that much in the crypto toolbox that they can't trivially break anyways.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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