No classical attack breaks properly implemented RSA with a sufficiently large modulus (2048 bits or more). Real-world RSA failures stem from too-small keys, weak random number generation, or missing/incorrect padding, not from a break of the algorithm itself. A large quantum computer would, however, break RSA via Shor's algorithm.

Why can't I just encrypt directly with the RSA function?

Raw 'textbook' RSA is deterministic and malleable, leaking information and allowing ciphertext manipulation. Secure use requires randomized padding such as OAEP for encryption and PSS for signatures, which is why standards mandate these schemes.

RSA and Integer Factorization

RSA is the most widely known public-key cryptosystem, providing encryption and digital signatures whose security rests on the difficulty of factoring the product of two large prime numbers.

Εύρεση θέματος με το PaperMindΣύντομαFind papers & topics

Tools & resources

Λήψη διαφανειών

Learn & explore

ΒίντεοΣύντομα

Definition

RSA is a public-key cryptosystem in which a public modulus n is the product of two secret primes; encryption raises the message to a public exponent modulo n, and decryption uses a private exponent derivable only from the factorization of n.

Scope

This topic covers the RSA algorithm — key generation, encryption, decryption, and signing via modular exponentiation — together with the integer-factorization problem on which it relies, the factoring algorithms that threaten it, and the padding schemes (OAEP, PSS) that make textbook RSA secure in practice. It addresses key-size recommendations and implementation attacks such as timing and fault attacks. It excludes discrete-log-based schemes and elliptic-curve cryptography, which are treated separately.

Core questions

How do the RSA public and private exponents arise from the structure of modular arithmetic?
Why does RSA's security depend on the hardness of factoring the modulus?
How fast can large integers be factored, and what does that imply for key sizes?
Why is textbook RSA insecure, and how do padding schemes like OAEP and PSS fix it?
What implementation-level attacks (timing, fault, weak randomness) threaten RSA in practice?

Key concepts

modular exponentiation
public and private exponents
Euler's totient and Carmichael function
factoring problem
general number field sieve
OAEP padding
PSS signature padding
key size and security level

Key theories

RSA trapdoor permutation: RSA defines a trapdoor one-way permutation: raising to the public exponent modulo n is easy, but inverting it requires the private exponent, which can be computed only from the prime factorization of n — the trapdoor.
Factoring assumption and key size: RSA's practical security tracks the best factoring algorithms (currently the general number field sieve, subexponential in the modulus length); resisting them is why modern RSA uses 2048-bit or larger moduli.

Mechanisms

Key generation chooses two large random primes p and q, sets n = p*q, picks a public exponent e coprime to (p-1)(q-1), and computes the private exponent d as the modular inverse of e. Encryption computes c = m^e mod n; decryption recovers m = c^d mod n. Correctness follows from Euler's theorem. Secure deployment wraps the plaintext in OAEP padding for encryption and uses PSS for signatures, since raw 'textbook' RSA is malleable and deterministic.

Clinical relevance

RSA secures decades of deployed infrastructure: TLS server certificates, code signing, SSH keys, PGP/S-MIME email, smart cards, and document signing. Although elliptic-curve schemes are increasingly preferred for new systems because of smaller keys, RSA remains pervasive in certificates and legacy protocols, and understanding it is essential for assessing real-world cryptographic risk.

Evidence & guidelines

RSA is standardized in PKCS #1 (RFC 8017), which specifies OAEP and PSS. NIST (SP 800-57) recommends a minimum 2048-bit modulus, with 3072-bit for higher security levels. Notable failures (the Debian weak-key bug, the ROCA flaw in Infineon key generation, and the FREAK downgrade to 512-bit export RSA) underscore the importance of correct key generation and parameter sizes.

History

RSA was published in 1977-1978 by Rivest, Shamir, and Adleman at MIT, the first practical realization of the public-key concept proposed by Diffie and Hellman. (Clifford Cocks had discovered an equivalent scheme secretly at GCHQ in 1973.) Advances in factoring — the quadratic sieve and then the number field sieve in the 1980s-1990s — progressively raised the secure key size, and the RSA Factoring Challenges tracked practical progress.

Key figures

Ronald Rivest
Adi Shamir
Leonard Adleman
Carl Pomerance
Arjen Lenstra

Seminal works

rivest1978
katz2020
menezes1996

Frequently asked questions

Is RSA broken?: No classical attack breaks properly implemented RSA with a sufficiently large modulus (2048 bits or more). Real-world RSA failures stem from too-small keys, weak random number generation, or missing/incorrect padding, not from a break of the algorithm itself. A large quantum computer would, however, break RSA via Shor's algorithm.
Why can't I just encrypt directly with the RSA function?: Raw 'textbook' RSA is deterministic and malleable, leaking information and allowing ciphertext manipulation. Secure use requires randomized padding such as OAEP for encryption and PSS for signatures, which is why standards mandate these schemes.