RSA problem

Article summary

In cryptography, the RSA problem summarizes the task of performing an RSA private-key operation given only the public key. The RSA algorithm raises a message to an exponent, modulo a composite number N whose factors are not known. Thus, the task can be neatly described as finding the e th roots of an arbitrary number, modulo N. For large RSA key sizes (in excess of 1024 bits), no efficient method for solving this problem is known; if an efficient method is ever developed, it would threaten the current or eventual security of RSA-based cryptosystems—both for public-key encryption and digital signatures. More specifically, the RSA problem is to efficiently compute P given an RSA public key (N, e) and a ciphertext C ≡ P e (mod N). The structure of the RSA public key requires that N be a large semiprime (i.e., a product of two large prime numbers), that 2 < e < N, that e be coprime to φ(N), and that 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. The most efficient method known to solve the RSA problem is by first factoring the modulus N, a task believed to be impractical if N is sufficiently large (see integer factorization).…

Key claims

No claims recorded.

Discussion questions

1. Summarise the article in your own words. Which single claim would you verify first, and why?
2. Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
3. If two sources disagreed about one of these facts, what would you need in order to trust one over the other?

Bibliography

No sources recorded.