- RSA problem
In
cryptography , the RSA problem is the task of finding "e"th roots modulo acomposite number "N" whose factors are not known. In other words, the problem is to perform theRSA private-key operation given only the public key. A fast means of solving the RSA problem would yield a method for breaking all RSA-basedpublic-key encryption and signing systems.More specifically, the RSA problem is to find
integer "P" such that "P""e" ≡ "C" (mod "N"), given integers "N", "e" and "C" such that "N" is the product of two large primes, 2 < "e" < "N" iscoprime to φ("N"), and 0 <= "C" < "N". "C" is chosen randomly within that range; to specify the problem with complete precision, one must also specify how "N" and "e" are generated, which will depend on the precise means of RSA random keypair generation in use.As of 2005 , the most efficient means known to solve the RSA problem is to factor the modulus "N" and thus discover the private key, which is believed to be impractical if "N" is sufficiently large (seeinteger factorization ). However, there is no proof that there might not be a way of solving this problem more efficient than factoring "N", and indeed there is strong evidence [ [http://theory.stanford.edu/~dabo/abstracts/no_rsa_red.html "Breaking RSA may not be equivalent to factoring"] , D. Boneh and R. Venkatesan, 1998.] that no such proof will ever be forthcoming. It has long been known that finding the private RSA exponent "d" is equivalent [ [http://theory.lcs.mit.edu/~rivest/RivestKaliski-RSAProblem.pdf "RSA Problem"] , R. L. Rivest and B. Kaliski, 2003.] to factoring "N", and that finding square roots modulo "N" (the equivalent problem forRabin cryptosystem s) is as hard as factoring "N".The goal of a secure RSA padding scheme is to make breaking the resulting cryptosystem provably as hard as solving the RSA problem. OAEP reaches this purpose under the
random oracle model .ee also
*
Strong RSA assumption
*RSA Factoring Challenge
*Computational hardness assumptions References
Further reading
* [http://eprint.iacr.org/2005/380 "Breaking RSA may be as difficult as factoring"] , D. Brown, 2005. Purports that solving the RSA problem using a
Straight line program is as difficult as factoring provided "e" has a small factor.
Wikimedia Foundation. 2010.
