In cryptography, the RSA problem is the task of finding eth roots modulo a composite number N whose factors are not known. In other words, the problem is to perform the RSA private-key operation given only the public key. A fast means of solving the RSA problem would yield a method for breaking all RSA-based public-key encryption and signing systems.
More specifically, the RSA problem is to find integer P such that Pe ≡ C (mod N), given integers N, e and C such that N is the product of two large primes, 2 < e < N is coprime 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 hard if N is sufficiently large (see integer 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 that no such proof will ever be forthcoming. It is known that finding the private RSA exponent d is equivalent to factoring N, and that finding square roots modulo N (the equivalent problem for Rabin cryptosystems) 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.
See also
References