Nitpick: RSA isn't known to be backed by factoring. More precisely, there is no proof that if textbook-RSA encrypted messages could be decrypted quickly that in

Nitpick: RSA isn't known to be backed by factoring. More precisely, there is no proof that if textbook-RSA encrypted messages could be decrypted quickly that integer factorization could also be done quickly. (Of course if you can factor integers you can decrypt RSA messages quickly). http://en.wikipedia.org/wiki/RSA_problem http://en.wikipedia.org/wiki/RSA_problem There are encryption schemes where decyption of an encrypted message is provably equivalent to factoring. http://en.wikipedia.org/wiki/Rabin_encryption http://en.wikipedia.org/wiki/Rabin_encryption