Talk:RSA problem

From Wikipedia, the free encyclopedia

This article is part of WikiProject Cryptography, an attempt to build a comprehensive and detailed guide to cryptography in the Wikipedia. If you would like to participate, you can choose to edit the article attached to this page, or visit the project page, where you can join the project and see a list of open tasks.

[edit] Definition of the problem?

decrypting a message without knowing the recipient's private key, or of finding someone's private key.

Thanks for starting this article! Quick question: are both of the above the RSA problem? I thought the RSA problem was finding a plaintext corresponding to a ciphertext, given the public parameters; and that finding the private key from the public key is not (yet known to be...) an equivalent problem? I was under the impression that the second problem was known to be equivalent in difficulty to integer factorisation, but the first is still an open question? I'm not very au fait with RSA, though, so please put me right if necessary ;-) — Matt Crypto 19:26, 25 Feb 2005 (UTC)

OK, it turns out you're right. The Handbook of Applied Cryptography states the problem thus: "Given a positive integer n that is a product of two distinct odd primes p and q, a positive integer e such that gcd(e, (p − 1)(q − 1)) = 1, and an integer c, find an integer m such that m^e ≡ c (mod n)." So it's just decrypting a ciphertext. However, I wonder if we shouldn't keep in the information about finding private keys. It's relevant to breaking RSA. Also, I'm not sure if finding someone's private key is known to be equivalent in difficulty to integer factorization. The first question (decryption w/o the private key) is definitely an open question. It's not known if there isn't a way of doing it without factoring the modulus. That I'm sure of. Also, it might be worth mentioning that there are some variants of RSA that have been proven to be equivalent to factoring (it's in Schneier). Anyway, sorry about the mistake. Decrypt3 22:19, Feb 25, 2005 (UTC)

There are no such variants on RSA. Perhaps you're thinking of the Rabin cryptosystem. -- ciphergoth 19:07, 2005 Apr 12 (UTC)

[edit] uhh

What does RSA stand for?

Its the initials of the protocols authors, see http://en.wikipedia.org/wiki/RSA--Bah23 10:59, 26 January 2007 (UTC)

[edit] Total rewrite

Hope I'm not treading on anyone's toes, but what was there before was pretty much utterly wrong. I've rewritten it to give a more accurate description of what cryptographers mean when they say "RSA problem". -- ciphergoth 19:07, 2005 Apr 12 (UTC)