The RSA cryptosystem is a public-key cryptographic system in which a publicly distributed key and a mathematically related private key support encryption or digital signatures. Its name comes from the surnames of Ronald Rivest, Adi Shamir, and Leonard Adleman, who developed it in 1977. RSA became one of the foundational techniques of modern cryptography, making it possible to protect information or verify its origin without first sharing a secret key over a secure channel.
RSA operates on integers using exponentiation modulo a large composite number, normally the product of two secret prime numbers. Its security relies on the difficulty of reversing this operation without the private key; factoring the modulus provides a way to do so, although the general RSA inversion problem has not been proved equivalent to factoring. Secure applications combine this arithmetic with carefully specified encoding schemes, cryptographic hash functions, reliable randomness, and protections against implementation attacks.
RSA has been widely used in digital certificates, secure communications, software signing, and hardware security devices. Its encryption and signature schemes serve different purposes and require different encodings. Although RSA remains important in deployed infrastructure, its relatively large keys, lack of inherent forward secrecy in historical key-transport protocols, and vulnerability to sufficiently capable quantum computers have shaped its changing role.
Origins and historical development
RSA emerged from efforts to solve the key-distribution problem of conventional encryption. In a symmetric system, communicating parties need access to the same secret key. Establishing that secret across an insecure network becomes difficult when the parties have no prior relationship. Whitfield Diffie and Martin Hellman’s 1976 paper on new directions in cryptography publicly articulated the concept of public-key systems and introduced a practical key-agreement method. It did not provide the RSA construction, but it helped establish the research setting in which RSA appeared.
Rivest, Shamir, and Adleman developed their system at the Massachusetts Institute of Technology in 1977. Their paper, “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems,” appeared in Communications of the ACM in February 1978. The construction offered both public-key encryption and a basis for signatures using closely related arithmetic. A public exponent could transform a message into a ciphertext, while knowledge of a corresponding private exponent enabled recovery. In a signature setting, the private operation produced a value that anyone possessing the public key could check.
A mathematically equivalent idea had been discovered independently by Clifford Cocks at the British Government Communications Headquarters in 1973. That work remained classified until 1997 and therefore did not contribute to the public development or early commercial deployment of RSA. The distinction between classified discovery and public invention matters historically: RSA’s published construction, analysis, software implementations, and commercial ecosystem developed without access to Cocks’s work.
A 1977 article by Martin Gardner in Scientific American helped introduce RSA to a wider audience. It presented a challenge involving a 129-decimal-digit modulus, subsequently known as RSA-129. An international distributed effort factored that number in 1994. The result illustrated both the feasibility of coordinated computational attacks and the need to increase cryptographic parameters as algorithms and computing resources improved; it did not invalidate RSA with appropriately larger keys.
Commercialization and standardization followed. The United States patent covering RSA was issued in 1983 and expired in 2000. RSA became central to certificate systems, commercial security software, and early secure web protocols. The PKCS #1 specification developed into a major reference for RSA primitives, key representations, and encoding methods. Its version 2.2 was published as RFC 8017 in 2016. Rivest, Shamir, and Adleman received the 2002 Turing Award for their contribution to making public-key cryptography useful in practice.
Mathematical construction and correctness
RSA uses modular arithmetic, in which integers are treated as equivalent when they have the same remainder after division by a modulus. In the usual two-prime construction, two distinct large primes, and , are selected and multiplied:
The integer is the modulus. It can be published, while its factors remain secret. For distinct primes, Euler’s totient is . A closely related quantity, Carmichael’s function, is
A public exponent is chosen so that . The private exponent satisfies
The public key is the pair . The private key contains and usually the factors and additional values that accelerate private operations. For a message representative with , the basic public operation computes . The corresponding private operation computes . These are arithmetic primitives, not complete secure encryption schemes.
Correctness follows by considering the calculation separately modulo and modulo . If is not divisible by , Fermat’s little theorem and the condition on imply . If is divisible by , the same equality holds because both sides are zero modulo . The argument is identical for . The Chinese remainder theorem then implies . Thus correctness holds for every representative in the permitted range, not just integers relatively prime to .
A small example uses , , and . Taking and gives a valid exponent pair. The representative becomes
and . Such small numbers are useful only for illustration: their factors can be found almost immediately.
Computations do not require constructing the enormous integer directly. Repeated squaring reduces intermediate results modulo , keeping their size manageable. This makes RSA a practical algorithm even with moduli thousands of bits long. Nevertheless, the arithmetic relationship alone provides neither confidentiality against realistic attackers nor meaningful message authentication; those properties depend on the schemes built around it.
Key generation, parameters, and key representation
RSA key generation begins with unpredictable candidate integers of appropriate size. Candidates are filtered and subjected to primality tests, commonly including the Miller–Rabin probabilistic test. The resulting primes must be distinct and must satisfy the constraints imposed by the chosen public exponent. For a conventional modulus, the two primes have approximately equal bit lengths, so that neither becomes an unnecessarily easy target for factoring.
The public exponent is widely used. Its binary representation has only two nonzero digits, allowing efficient public-key operations while avoiding some difficulties associated with very small exponents. Choosing this exponent does not remove the need for secure message encoding. During prime generation, candidates for which or are rejected. Once the factors are accepted, the private exponent is computed using an extended Euclidean algorithm.
Key size refers to the length of the modulus, measured in bits, rather than the length of either prime or the amount of equivalent symmetric-key security. A 2048-bit RSA modulus normally uses two primes of about 1024 bits each. Common security-strength estimates associate 2048-bit RSA with roughly 112 bits of classical security and 3072-bit RSA with roughly 128 bits. These estimates concern the work required by the best relevant classical attacks and are not exact guarantees. A 256-bit symmetric key and a 256-bit RSA modulus therefore have radically different security properties.
Randomness is a fundamental security dependency. If two independently generated moduli accidentally share a prime, their greatest common divisor reveals that prime efficiently. For example, if and , then , assuming no further shared factors. Large-scale studies published in 2012 found shared-prime vulnerabilities among real-world keys, particularly in some embedded and network devices. These failures arose from inadequate entropy during generation, rather than from a general factoring breakthrough.
Practical private-key formats commonly store , , , , , and the Chinese-remainder parameters , , and . Exposing any sufficient combination of these values can compromise the key. In particular, knowledge of , , and enables probabilistic recovery of the factors.
Keys are serialized through structures such as PKCS #1 and PKCS #8, often using ASN.1 encoding. A private key may be encrypted at rest or retained inside a hardware security module. Public-key authenticity is a separate issue: a correctly generated public key offers no protection if an attacker can substitute a different key during distribution.
Encryption schemes and message encoding
The direct transformation , often called textbook RSA, is deterministic. Encrypting the same representative under the same key always produces the same ciphertext. An observer can therefore test guesses for messages drawn from a small set simply by encrypting each possibility. This violates the confidentiality expected of a modern encryption scheme, even when the modulus is too large to factor.
Textbook RSA also has a multiplicative structure. If and , then
An attacker can thus transform ciphertexts in ways that predictably affect the underlying plaintext. Secure encryption schemes must prevent this algebraic property from becoming a useful attack. They do so by encoding the message into a structured, randomized representative before applying the RSA primitive.
RSAES-OAEP uses Optimal Asymmetric Encryption Padding, combining a message, a random seed, a label hash, and a mask-generation function. Its two interdependent masking stages make simple relationships between messages and RSA representatives difficult to exploit. The construction uses a cryptographic hash function and is analyzed under specific assumptions in the random-oracle model. Its security is not an unconditional consequence of the modular arithmetic.
OAEP has a strict payload limit. If the modulus occupies bytes and the hash output occupies bytes, then the maximum message length is
For a 2048-bit modulus, . With SHA-256, whose output is 32 bytes, the maximum payload is 190 bytes. RSA is consequently not normally used to encrypt large files or continuous data streams. A hybrid encryption design uses RSA to protect a short random secret, while a symmetric scheme based on an algorithm such as the Advanced Encryption Standard protects the actual data.
An older scheme, RSAES-PKCS1-v1_5, encodes messages with a block beginning with the bytes 00 02, followed by nonzero random padding, a separator, and the message. Daniel Bleichenbacher’s 1998 attack showed how a server that reveals whether this padding is valid can become a decryption oracle. Repeated, adaptively selected queries can recover plaintext without factoring the modulus.
OAEP also requires careful error handling. Timing differences, distinct error messages, or other observable behavior during decoding can undermine intended protections. Encryption security therefore depends on the full decryption interface, including its treatment of malformed inputs, not merely on selecting a named padding scheme.
Digital signatures and verification
RSA signatures provide evidence that a holder of a private key approved a particular encoded message. They do not conceal the message. Signing begins by processing the message with a signature encoding scheme; the private RSA operation is applied to the resulting representative. Verification applies the public operation to the signature and checks whether the recovered representation matches the message under the specified encoding rules.
A digital signature should not be described simply as “encrypting with the private key.” That phrase obscures the security requirements and can suggest that encryption and signing are interchangeable. They are distinct constructions, with different threat models and encodings. Applying the private exponent directly to an arbitrary integer is insecure as a general signature system: an attacker can choose a value , compute , and thereby obtain an algebraically valid pair without ever asking the legitimate signer to sign that representative.
RSASSA-PKCS1-v1_5, a widely deployed deterministic signature scheme, hashes the message and places the digest in a prescribed encoded structure. Its representative includes a leading block type, a sequence of padding bytes, a separator, and an encoding identifying the hash algorithm and digest. Verification must check the entire required structure. Historically, permissive verification routines that accepted malformed blocks, missing fields, or extraneous data enabled signature forgeries in some implementations, particularly with small public exponents.
RSASSA-PSS uses the Probabilistic Signature Scheme. It combines a message hash, a salt, a mask-generation function, and a structured encoding before the RSA private operation. Its security has a well-developed analysis under RSA-related assumptions in the random-oracle model. With a fresh random salt, repeated signatures on the same message will generally differ. The hash, mask-generation hash, and salt length are parameters that must be interpreted consistently by signer and verifier.
Hash security is essential because a signature usually authenticates a digest rather than processing the complete message directly through RSA. If an attacker can construct two relevant messages with the same digest, a signature on one may validate the other. Collision weaknesses in older hash algorithms therefore affect RSA signature systems even when their moduli remain secure. Increasing the RSA key size does not repair a weak hash function.
A valid signature establishes a relationship among a message, a public key, and a signing operation. Identifying the signer requires additional evidence, such as a trusted certificate or an independently authenticated key. Claims about legal attribution or nonrepudiation also depend on key custody, authorization, revocation, and applicable procedures; the RSA calculation alone cannot establish them.
Security assumptions and mathematical attacks
Factoring an RSA modulus reveals its prime factors, from which an attacker can compute and derive a private exponent. Integer factorization is therefore a sufficient route to breaking RSA. The reverse relationship is less settled: no general proof shows that efficiently inverting RSA for arbitrary properly generated keys necessarily yields an equally efficient factoring algorithm. Security discussions distinguish the factoring problem, the RSA inversion assumption, and the properties of complete encryption or signature schemes.
For large, general RSA moduli, the best known classical factoring method is the general number field sieve. Its asymptotic running time is subexponential, often expressed as
where
This growth is slower than exponential in the modulus bit length but remains prohibitive at appropriately chosen sizes. The assessment belongs to computational complexity and empirical cryptanalysis rather than to a proof that all faster methods are impossible.
Public factoring records demonstrate the importance of parameter size. RSA-768, a 768-bit challenge number, was factored in 2009, and RSA-250, a 250-decimal-digit number with an 829-bit modulus, was factored in 2020. Such achievements involve substantial computation and algorithmic engineering. They establish that those sizes cannot serve as dependable security margins, but they do not imply that 2048-bit RSA can be factored with comparable resources.
Poor exponent or message choices can permit attacks much cheaper than general factoring. Wiener’s attack, published in 1990, uses continued fractions to recover sufficiently small private exponents under appropriate conditions. Further attacks extended the analysis of small- choices. These results constrain parameter selection; they do not apply indiscriminately to ordinary keys with suitably generated exponents.
A small public exponent can also expose unencoded messages. If and the integer is smaller than , the ciphertext is simply the ordinary integer cube, so taking an integer cube root recovers the message. In Håstad’s broadcast attack, encrypting the same unpadded message under several independent moduli with the same small exponent can allow recovery using the Chinese remainder theorem. Randomized encoding removes the simple common-message structure on which this attack relies.
Other weaknesses arise from unusually close primes, shared factors, partial leakage of private parameters, or specially structured prime-generation methods. These cases explain why “RSA security” is not a single assumption. It depends jointly on modulus construction, exponent selection, encoding, implementation, and the information available to the attacker.
Efficient implementation and side-channel resistance
RSA’s public and private operations have different performance profiles. With the common exponent , public exponentiation requires relatively few modular multiplications. The private exponent is usually much longer, making decryption and signing more expensive. Implementations use repeated-squaring variants, window methods, and Montgomery multiplication to perform large-integer modular arithmetic efficiently. Actual performance depends on modulus size, processor architecture, software, and whether hardware acceleration is available.
The Chinese remainder theorem accelerates private operations by replacing one exponentiation modulo with two smaller exponentiations. Given an input representative , the implementation computes
Using , it forms
Because arithmetic on half-length numbers is substantially cheaper, this method provides a major speed improvement. The exact gain depends on the multiplication algorithms and implementation.
Efficiency can create observable dependencies on secrets. A side-channel attack extracts information from execution time, power consumption, electromagnetic emissions, cache behavior, or similar effects rather than solving the intended mathematical problem. Paul Kocher’s 1996 work established timing attacks as a practical concern for cryptographic implementations, including RSA. Secret-dependent branches and table accesses can reveal information about exponent bits.
Constant-time implementations aim to avoid execution behavior that depends on secret values. RSA blinding adds another defense: before a private operation, an input is multiplied by , where is a fresh random invertible value. After private exponentiation, multiplication by removes the mask. This randomizes the internal input without changing the final mathematical result. Exponent blinding can also vary the exponent representation used in individual operations.
CRT acceleration introduces a distinctive fault risk. If an erroneous signature is correct modulo one prime but incorrect modulo the other, an attacker with a suitable faulty output and the corresponding encoded representative may recover a factor using a greatest-common-divisor calculation. This class of attack was publicized in the 1990s through work commonly associated with the Bellcore attack. It can apply when faults are induced physically or arise from other computational failures.
Implementations counter these risks through measures such as verifying private-operation outputs with the public exponent, checking intermediate consistency, protecting key storage, and controlling error responses. Libraries such as OpenSSL integrate many such defenses, but applications can still defeat them through unsafe interfaces or protocol behavior. Mathematical correctness and resistance to leakage are separate engineering requirements.
Certificates, protocols, and operational roles
RSA’s deployment has been closely tied to public-key infrastructure. An X.509 certificate binds a public key to an identity or other attributes through a certification authority’s signature. The certificate’s subject key algorithm and the algorithm used to sign the certificate are separate fields: a certificate containing an RSA public key may be signed using a different family of signature algorithms, and an RSA authority may sign a certificate containing a non-RSA key.
In earlier versions of Transport Layer Security, RSA could provide both server authentication and key transport. In the RSA key-transport mode, the client generated a premaster secret and encrypted it under the server’s RSA public key. The parties then derived symmetric session keys. If an attacker recorded such a session and later obtained the server’s private key, the attacker could potentially recover the premaster secret and decrypt the recorded traffic.
This limitation concerns forward secrecy, the property that later compromise of long-term credentials does not by itself reveal past session keys. TLS 1.3, standardized in 2018, removed RSA key transport. RSA remains available for authentication through RSA-PSS signatures, while key establishment uses other mechanisms. Thus the statement that a connection “uses RSA” is insufficient to determine whether RSA protects a secret, authenticates a handshake, or appears only elsewhere in the certificate chain.
RSA also supports software and firmware signing, document signatures, secure email formats, and authentication protocols. In code signing, a signature allows a verifier to detect changes to a signed object and associate it with a trusted signing credential. It does not prove that the code is free of vulnerabilities or harmful behavior. Likewise, an authenticated network service can still be compromised or misconfigured; cryptographic identity is only one part of cybersecurity.
Operational design affects the consequences of compromise. A broadly distributed signing key can authorize many artifacts, while a server decryption key may expose archived ciphertexts as well as current traffic. Separating roles, enforcing key-use restrictions, and controlling access to private operations are therefore significant features of deployed systems. Certificate expiration and revocation affect trust decisions, but neither changes the underlying mathematics nor makes a disclosed private key secret again.
Large-scale installations also face processing and availability constraints. RSA private operations can become bottlenecks under heavy connection or signing loads, motivating hardware accelerators and distributed signing services. These arrangements introduce authorization and availability questions beyond the RSA primitive itself: a protected key can still be misused if an attacker gains permission to request signatures or decryptions.
Quantum computing and the transition beyond RSA
RSA’s central long-term limitation is its vulnerability to Shor’s algorithm, introduced by Peter Shor in 1994. On a sufficiently capable fault-tolerant quantum computer, the algorithm can factor integers in time polynomial in their bit length. Once the modulus is factored, deriving the RSA private key is straightforward. This attack targets the mathematical foundation and is not prevented by OAEP, PSS, blinding, or more careful implementation.
The relevant machine is not simply a quantum processor with a large advertised number of physical qubits. A practical attack requires reliable logical operations, substantial circuit depth, and quantum error correction. Resource estimates depend on hardware error rates, architecture, error-correcting codes, arithmetic circuits, and available runtime. Consequently, a fixed date for breaking deployed RSA keys cannot be inferred from the algorithm alone.
Increasing the modulus size raises the cost of both classical and quantum attacks, but it does not make RSA a post-quantum construction. Shor’s algorithm retains polynomial scaling as key sizes increase, whereas RSA’s classical security rationale depends on the absence of efficient classical factoring methods. The transition is therefore toward different mathematical assumptions, rather than merely toward ever-larger RSA moduli.
Post-quantum cryptography develops encryption, key-establishment, and signature mechanisms intended to resist known attacks by both classical and quantum computers. In 2024, the United States National Institute of Standards and Technology finalized FIPS 203 for the lattice-based ML-KEM key-encapsulation mechanism, FIPS 204 for the lattice-based ML-DSA signature algorithm, and FIPS 205 for the hash-based SLH-DSA signature algorithm. These mechanisms address roles that RSA has historically occupied, but they have different key formats, ciphertext or signature sizes, performance characteristics, and security assumptions.
Confidentiality and signature verification create different migration pressures. An adversary can store RSA-protected ciphertext now and attempt decryption after obtaining sufficient future capabilities, a scenario often called “harvest now, decrypt later.” Long-lived secrets are particularly exposed to that timing mismatch. For signatures, a future ability to recover an RSA private key could enable forgery, while archival validation additionally depends on timestamps, preserved trust records, and the rules used to establish when a signature existed.
Migration therefore involves protocols, certificates, hardware, software interfaces, and long-lived data formats, not just replacing one arithmetic routine. Some transitional designs combine classical and post-quantum mechanisms, with security determined by the precise method of combination. RSA compatibility can remain necessary in legacy systems even as newer systems adopt different primitives, making cryptographic agility—the ability to change algorithms and parameters without rebuilding an entire infrastructure—a significant architectural concern.