Metraipolis › archive › dc_a6582f06eec4

RSA problem — Wikipedia (en)

Source
Wikipedia (en)
Original
https://en.wikipedia.org/wiki/RSA_problem
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-05T23:03:55.889Z
SHA-256 of the archived text
c2fe5d4584c63c86547161e8a35f2b29a00d0e3e6c65848053969cbb31b59208
Stable URL of this page
https://metraipolis.com/documento/dc_a6582f06eec4

How to cite

RSA problem — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/RSA_problem (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_a6582f06eec4 (Metraipolis archive dc_a6582f06eec4, sha256 c2fe5d4584c63c86547161e8a35f2b29a00d0e3e6c65848053969cbb31b59208)
BibTeX
@misc{dca6582f06eec4,
  title = {RSA problem — Wikipedia (en)},
  howpublished = {Wikipedia (en)},
  url = {https://en.wikipedia.org/wiki/RSA_problem},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_a6582f06eec4; sha256 c2fe5d4584c63c86547161e8a35f2b29a00d0e3e6c65848053969cbb31b59208},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/RSA_problem. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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 eth 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). The RSA key setup routine already turns the public exponent e, with this prime factorization, into the private exponent d, and so exactly the same algorithm allows anyone who factors N to obtain the private key. Any C can then be decrypted with the private key. Just as there are no proofs that integer factorization is computationally difficult, there are also no proofs that the RSA problem is similarly difficult. By the above method, the RSA problem is at least as easy as factoring, but it might well be easier. Indeed, there is strong evidence pointing to this conclusion: that a method to break the RSA method cannot be converted necessarily into a method for factoring large semiprimes. This is perhaps easiest to see by the sheer overkill of the factoring approach: the RSA problem asks us to decrypt one arbitrary ciphertext, whereas the factoring method reveals the private key: thus decrypting all arbitrary ciphertexts, and it also allows one to perform arbitrary RSA private-key encryptions. Along these same lines, finding the decryption exponent d indeed is computationally equivalent to factoring N, even though the RSA problem does not ask for d. In addition to the RSA problem, RSA also has a particular mathematical structure that can potentially be exploited without solving the RSA problem directly. To achieve the full strength of the RSA problem, an RSA-based cryptosystem must also use a padding scheme like OAEP, to protect against such structural problems in RSA.

Tema degli esploratori: fiducia digitale e crittografia (deposito sistematico; ricerca «EdDSA»).
Fonte: Wikipedia in inglese, voce «RSA problem» — https://en.wikipedia.org/wiki/RSA_problem
Wikidata Q3297596 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q3297596
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/RSA_problem?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 1299539591, consultata il 2026-10-05T23:00:15.594Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 545e90430fb0f631097ff2940e683b5a0034faa1eb5803a4794e072d8bb0afb0