RSA problem

From Wikipedia, the free encyclopedia

In cryptography, the RSA problem is the task of finding e^th 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 P^e ≡ 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 believed to be impractical 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 ^[1] that no such proof will ever be forthcoming. It has long been known that finding the private RSA exponent d is equivalent^[2] 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. OAEP reaches this purpose under the random oracle model.

[edit] See also

• Strong RSA assumption
• RSA Factoring Challenge
• Computational hardness assumptions

[edit] References

1. ^ Breaking RSA may not be equivalent to factoring, D. Boneh and R. Venkatesan, 1998.
2. ^ RSA Problem, R. L. Rivest and B. Kaliski, 2003.

[edit] Further reading

• 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.

v • d • e   Public-key cryptography Algorithms: CEILIDH | Cramer-Shoup | DH | DSA | ECDH | ECDSA | EKE | ElGamal encryption | ElGamal signature scheme | GMR | IES | Lamport | MQV | NTRUEncrypt | NTRUSign | Paillier | Rabin | RSA | Schnorr | SPEKE | SRP | XTR Theory: Discrete logarithm | Elliptic curve cryptography | RSA problem Standardization: ANS X9F1 | CRYPTREC | IEEE P1363 | NESSIE | NSA Suite B Misc: Digital signature | Fingerprint | PKI | Web of trust | Key size v • d • e   Cryptography History of cryptography | Cryptanalysis | Cryptography portal | Topics in cryptography Symmetric-key algorithm | Block cipher | Stream cipher | Public-key cryptography | Cryptographic hash function | Message authentication code | Random numbers | Steganography